ICES researcher [and UTCS professor] Keshav Pingali envisions a world in which the power of parallel computing is available to all programmers—even those who don’t write parallel computer programs. That’s the central theme behind developing his Galois software system that turns sequential computer code into parallel code. It’s a highly technical research program. But it’s a philosophy too, complete with sacred texts, disciples, and plans for evangelizing its methods throughout the programming community.
Welcome to what Pingali jokingly calls the church of Galois.
Parallel worlds
The Galois system was developed to automatically take serial code—code meant to be executed in sequential order by a single processor¬—and enable it to run in parallel on multi-processor computers. But why would someone want to run a computer program in parallel in the first place?
In short, it’s often the only way to efficiently analyze information in the world of “big data.” The multiple processors of parallel systems enable faster run times and permit more data to be analyzed. It’s no surprise that climate researchers, geophysicists, and finance companies are among the top users of parallel systems.
Galois’ foundational research paper, “The Tao of Parallelism in Algorithms,” outlines a way for serial programs to be executed in parallel: apply the Galois software to release the parallel “essence” hidden within serially defined code, using a method Pingali calls “Tao-analysis.” The paper was published in 2011 in the Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation.
All the programmer must do is indicate which parts of the program should be run in parallel, and organize his or her code to use data structures that are recognizable to the Galois system.
And if “parallel essence” sounds a little obtuse when talking about something as scripted as computer code, know that it’s supposed to be. There is technical and computational logic that supports the transformation from serial to parallel, but it is, at its root, amorphous and hard to define in simple rules. In fact, Pingali ends the Tao with a quote from the Ashtavarka Gita, a classical Hindu scripture written around 500 BCE, emphasizing its undefined nature:
“That which has form is not real; only the amorphous endures. When you understand this, you will not return to illusion."
Still, for those interested in the technical side of the Tao, its computational structure is outlined in the text and Galois is free for anyone to download.
Reading the Graph
Tao-analysis seeks to expose the structure of algorithms to determine how they can be executed in parallel. Traditional high-performance computing (HPC) algorithms are known as “regular” algorithms because the parallelism in these algorithms in independent of run time, and can be found before the program is executed. Then, there are “irregular” algorithms. The parallel nature in these algorithms is much more slippery, shifting depending on the data inputs, and making it so that the parallelism must be uncovered during program execution. Galois can handle both because it defines regular algorithms as a special case of irregulars.
And that’s an important feature of the system because irregular algorithms are the driving force behind the growing field of graph applications. These programs analyze data by evaluating connections between entities to identify relationships. These connections then inform the system how to act. Graph applications are behind Facebook’s friend recommendation system, and what song Pandora will choose to include in a playlist. IBM’s artificial intelligent system Watson used graphical reasoning to win Jeopardy! in 2011.
The immense amount of data available nowadays (think of the 1.11 billion of users on Facebook, or websites pulled up by a search engine) makes parallel computing systems the logical choice for processing graph applications. But that doesn’t mean the future will belong to parallel programmers.
“One school of thought says that since computers are parallel, all programmers have to be parallel programmers. But I don’t think that’s a reasonable idea,” said Pingali, explaining that the split-processing nature of parallel computers is far from intuitive. Most programmers will not be able to write effective parallel programs, said Pingali.
“Human beings find it very hard to think in terms of doing things in parallel. We multitask, but we really only do one thing at a time.”
Instead, he says Galois is a better method to make parallel systems—and all their speed and computing power— accessible to all programmers.
“A small number of expert parallel programmers should support a very large number of [general] programmers who don’t have to write in parallel,” said Pingali. “The Galois system is making this model work in the relatively complex domain of these graph programs.”
Galois on tour
This summer Pingali will be receiving the Distinguished Alumnus Award from his undergraduate alma mater The Indian Institute of Technology Kampur. It’s the university’s highest award for alumni. The award acknowledges achievements such as Pingali’s past work being incorporated into products by Intel, IBM, Hewlett-Packard, Silicon Graphics, and Digital Equipment Corporation.
Pingali says he is pushing for Galois to be next on the list for adoption and adaptation by researchers and industry.
To help make that happen, Pingali and his students are spending the summer spreading the word of Galois near and far, and in different ways. Pingali, by hosting a group of Polish researchers at ICES who will apply Galois to their own computational codes, and his students by taking Galois and its Tao to technology firms through internships.
Hosting interns is chance for companies to get to know the Galois approach up close, and optimize it for their systems. And that’s the first step toward taking the approach from research to market, said Pingali.
“The point of doing research in academia is doing something that’s kind of far out or risky. And once you’ve established that this thing is actually a feasible idea, others like to look at that software, take it apart and write their own version of it,” said Pingali.
“It takes awhile for any idea, especially if it’s an idea that’s different from what most people are pursuing, to get to the point where it’s accepted.”
Pingali speaks from experience. He says it took about five or six years for his earlier software that optimized computer processor cache usage to be incorporated by companies. Now it’s standard practice.
With the need for parallel programs expanding across industry and research, it’s prime time for people to start converting, their code that is, and joining Pingali’s “church of Galois.”
Article and photos by Monica Kortsha