Every time you Google sometime, you’re benefiting from something called graph data. Google represents everything on the web as a giant graph of different webpages and their relationships to each other. (This is in contrast to representing data as essentially a series of rows and columns.)
So-called “graph processing” is used for all sorts of things in our lives, from Uber driving directions to Facebook “People You May Know” friend recommendations. However, there have been many limits in terms of being able to use graph processing on a larger scale. As a result, programmers often have to use different combinations of techniques that make trade-offs in terms of efficiency and flexibility.
However, a team from MIT CSAIL has developed a new programming language for graph processing that could help. Dubbed “GraphIt,” the new domain-specific language has been shown to outperform existing frameworks by a factor of nearly 5x while also reducing the lines of code by almost an entire order of magnitude.
GraphIt generates fast implementations for algorithms with different performance characteristics running on graphs with different sizes and structures. According to MIT CSAIL PhD student Yunming Zhang, it separates what is computed from how it is computed. Programmers specify the algorithm using an algorithm language, and performance optimizations are specified using a separate scheduling language. The algorithm language simplifies expressing the algorithms, while exposing opportunities for optimizations.
“GraphIt enables programmers to easily search through this complicated tradeoff space by composing together a large set of edge traversal, vertex data layout, and program structure optimizations,” says Zhang, first author on a paper about GraphIt that was presented this past month at OOPSLA. “The separation of algorithm and schedule also enables us to build an autotuner on top of GraphIt to automatically find high-performance schedules.”
Zhang co-wrote the paper with MIT professors Saman Amarasinghe and Julian Shun, alongside MIT undergraduate Mengjiao Yang, MIT CSAIL postdoc Riyadh Baghdadi and Shoaib Kamil of Adobe Research.