Graphs – data structures that show the relationship among objects – are very flexible. It is easy to imagine a graph showing a network of social media network of connections. But graphs are also used in programs as diverse as content recommendation (what do you watch next on Netflix?) And navigation (which is the fastest way to the beach?). As Ajay Brahmakshatriya sums up: “graphs are basically everywhere.”
Brahmakshatriya has developed software to run graph applications more efficiently on a wider range of computer hardware. The software extends GraphIt, a state-of-the-art graph programming language, to run on graphics processing units (GPUs), hardware that processes many parallel data streams. Progress could accelerate graph analysis, especially for applications that benefit from GPU parallelism, such as recommendation algorithms.
Brahmakshatriya, a PhD student in MIT’s Department of Electrical Engineering and Computer Science and the Computer Science and Artificial Intelligence laboratory, will present the work at this month’s International Symposium on Code Generation and Optimization. Co-authors include Brahmakshatriya’s advisor, Professor Saman Amarasinghe, as well as Douglas T. Ross Software Development Technology Career Associate Julian Shun, postdoc Changwan Hong, a recent MIT PhD student short Yunming Zhang PhD ’20 (now with Google), and Adobe Research Shoaib Kamil.
When programmers write code, they do not speak directly to the computer hardware. The hardware itself works in binary – 1s and 0s – while the coder writes in a structured, “advanced” language made up of words and symbols. Translating that advanced language into a hardware reader requires programs called compilers. “A compiler converts the code to a format that can run on the hardware,” Brahmakshatriya says. One such collector, designed specifically for graph analysis, is GraphIt.
The researchers developed GraphIt in 2018 to optimize the performance of graph-based algorithms regardless of the size and shape of the graph. GraphIt allows the user not only to install an algorithm, but also to record how that algorithm runs on the hardware. “The user can be given different options for their registration, so that they can find out what works best for them,” Brahmakshatriya says. “GraphIt generates highly specialized code that is designed for each application to run as efficiently as possible.”
GraphIt has been adopted by a number of start-ups and established technical companies to help develop graph applications. But Brahmakshatriya says there was a flaw in the first flight of GraphIt: It only runs on central processing units or CPUs, the type of processor in a typical laptop.
“Some algorithms are parallel to each other,” Brahmakshatriya says, “meaning they can use hardware like a GPU that has 10,000 cores to execute.” It notes that a high degree of coherence is required in some types of graph analysis, including recommendation algorithms. So Brahmakshatriya expanded GraphIt to allow graph analysis to succeed on GPUs.
The Brahmakshatriya team retained the way GraphIt users entered algorithms, but changed the registration part for a wider range of hardware. “Our main design decision in extending GraphIt to GPUs was to keep the representation of the algorithm exactly the same,” Brahmakshatriya said. “Instead, we added a new registration language. So the user can follow the same algorithm as what they wrote before. [for CPUs], and simply modify the registry input to get the GPU code. “
This new, fully developed programming for GPUs will boost graphics algorithms that require high parallelism – including recommendation algorithms or web analytics tasks that move through millions of websites at at the same time. To test the effectiveness of GraphIt’s new extension, the team ran 90 tests setting GraphIt’s runtime against other modern graph comparators on GPUs. The experiments covered a range of algorithms and graph types, from road networks to social networks. GraphIt ran fastest in 65 of the 90 cases and was close behind the advanced algorithm in the rest of the tests, showing both speed and flexibility.
Brahmakshatriya says the new GraphIt extension provides significant advancement in graph analysis, allowing users to easily switch between CPUs and GPUs with state-of-the-art performance. “Today’s field is a competition of teeth and nails. New frames are coming out every day,” he says. But he emphasizes that there is value in paying for even a little optimization. “Companies spend millions of dollars every day to run graph algorithms. Even if you make it run just 5 percent faster, you’ll save thousands of dollars.”
###
This research was funded, in part, by the National Science Foundation, the U.S. Department of Energy, the Application Driving Architecture Center, and the Defense Advanced Research Projects Agency.
Written by Daniel Ackerman, MIT Press Office
Additional background information
Paper: “Compiling Graph Applications for GPUs with GraphIt”
https: /
Disclaimer: AAAS and EurekAlert! they are not responsible for the accuracy of press releases posted to EurekAlert! by sending institutions or for using any information through the EurekAlert system.