Graphs are everywhere. They allow trends and patterns to be more easily seen.
Achieving high performance is critical because many modern applications often need to process very large graphs and/or have strict latency requirements.
To achieve high performance, Ajay Brahmakshatriya, a Ph.D. student in MIT‘s Department of Electrical Engineering and Computer Science and the Computer Science and Artificial Intelligence Laboratory, has developed software to more efficiently run graph applications on a wider range of computer hardware. The software broadens Graphlt, a best-in-class graph programming language, to run on graphics processing units (GPUs).
GPUs are the hardware that processes many data streams in parallel. The advance could accelerate graph analysis, especially for applications that benefit from a GPU’s parallelism, such as recommendation algorithms.
The Graphlt was originally developed in 2018 that allows the user to input an algorithm and schedule how that algorithm runs on the hardware.
Brahmakshatriya said, “The user can provide different scheduling options until they figure out what works best for them. GraphIt generates very specialized code tailored for each application to run as efficiently as possible.”
“The first iteration of GraphIt had a shortcoming: It only runs on central processing units or CPUs, the type of processor in a typical laptop.”
“Some algorithms are massively parallel, meaning they can better utilize hardware like a GPU that has 10,000 cores for execution. Some types of graph analysis, including recommendation algorithms, require a high degree of parallelism. So Brahmakshatriya extended GraphIt to enable graph analysis to flourish on GPUs.”
“Our major design decision in extending GraphIt to GPUs was to keep the algorithm representation the same. Instead, we added a new scheduling language. So, the user can keep the same algorithms that they had written before [for CPUs], and change the scheduling input to get the GPU code.”
This new, optimized scheduling for GPUs boosts graph algorithms that require high parallelism — including recommendation algorithms or internet search functions that sift through millions of websites simultaneously. To confirm the efficacy of Graphlt’s new extension, the team ran 90 experiments pitting Graphlt’s runtime against other state-of-the-art graph compilers on GPUs. The experiments included a range of algorithms and graph types, from road networks to social networks. Graphlt ran fastest in 65 of the 90 cases and was close behind the leading algorithm in the rest of the trials, demonstrating its speed and versatility.
Adrian Sampson, a computer scientist at Cornell University who was not involved with the research, said, “Graphlt “advances the field by attaining performance and productivity simultaneously. “Traditional ways of doing graph analysis have one or the other: Either you can write a simple algorithm with mediocre performance, or you can hire an expert to write a speedy implementation — but that kind of performance is rarely accessible to mere mortals. The Graphlt extension is the key to letting ordinary people write high-level, abstract algorithms and nonetheless getting expert-level performance out of GPUs.”
“The advance could be particularly useful in rapidly changing fields: “An exciting domain like that is genomics, where algorithms are evolving so quickly that high-performance expert implementations can’t keep up with the rate of change. I’m excited for bioinformatics practitioners to get their hands on Graphlt to expand the kinds of genomic analyses they’re capable of.”
Brahmakshatriya says, “the new Graphlt extension provides a meaningful advance in graph analysis, enabling users to go between CPUs and GPUs with state-of-the-art performance with ease. The field these days is tooth-and-nail competition. New frameworks are coming out every day.”
“The payoff for even slight optimization is worth it. Companies are spending millions of dollars each day to run graph algorithms. Even if you make it run just 5 percent faster, you’re saving many thousands of dollars.”
Journal Reference:
- Ajay Brahmakshatriya et al. Compiling Graph Applications for GPUs with GraphIt.Â