Researchers develop speedier network analysis for a range of computer hardware

February 22, 2021

Graphs -- data structures that show the relationship among objects -- are highly versatile. It's easy to imagine a graph depicting a social media network's web of connections. But graphs are also used in programs as diverse as content recommendation (what to watch next on Netflix?) and navigation (what's the quickest route to the beach?). As Ajay Brahmakshatriya summarizes: "graphs are basically everywhere."

Brahmakshatriya has developed software to more efficiently run graph applications 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 data streams in parallel. The advance could accelerate graph analysis, especially for applications that benefit from a GPU's 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 Career Development Assistant Professor of Software Technology Julian Shun, postdoc Changwan Hong, recent MIT PhD student Yunming Zhang PhD '20 (now with Google), and Adobe Research's Shoaib Kamil.

When programmers write code, they don't talk directly to the computer hardware. The hardware itself operates in binary -- 1s and 0s -- while the coder writes in a structured, "high-level" language made up of words and symbols. Translating that high-level language into hardware-readable binary requires programs called compilers. "A compiler converts the code to a format that can run on the hardware," says Brahmakshatriya. One such compiler, specially designed 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 input an algorithm, but also to schedule how that algorithm runs on the hardware. "The user can provide different options for the scheduling, until they figure out what works best for them," says Brahmakshatriya. "GraphIt generates very specialized code tailored for each application to run as efficiently as possible."

A number of startups and established tech firms alike have adopted GraphIt to aid their development of graph applications. But Brahmakshatriya says 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," says Brahmakshatriya, "meaning they can better utilize hardware like a GPU that has 10,000 cores for execution." He notes that 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.

Brahmakshatriya's team preserved the way GraphIt users input algorithms, but adapted the scheduling component for a wider array of hardware. "Our main design decision in extending GraphIt to GPUs was to keep the algorithm representation exactly the same," says Brahmakshatriya. "Instead, we added a new scheduling language. So, the user can keep the same algorithms that they had before written before [for CPUs], and just change the scheduling input to get the GPU code."

This new, optimized scheduling for GPUs gives a boost to 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 GraphIt's new extension, the team ran 90 experiments pitting GraphIt'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. GraphIt ran fastest in 65 of the 90 cases and was close behind the leading algorithm in the rest of the trials, demonstrating both its speed and versatility.

Brahmakshatriya says the new GraphIt 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. There are new frameworks coming out every day," He says. But he emphasizes that 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."
This research was funded, in part, by the National Science Foundation, U.S. Department of Energy, the Applications Driving Architectures Center, and the Defense Advanced Research Projects Agency.

Written by Daniel Ackerman, MIT News Office

Additional background

Paper: "Compiling Graph Applications for GPUs with GraphIt"

Massachusetts Institute of Technology

Related Social Networks Articles from Brightsurf:

AI methods of analyzing social networks find new cell types in tissue
In situ sequencing enables gene activity inside body tissues to be depicted in microscope images.

Teen social networks linked to adult depression
Teens who have a larger number of friends may be less likely to suffer from depression later in life, especially women, a new MSU research study has found.

Drexel study: Measuring social networks of young adults with autism
While social isolation is a core challenge associated with autism, researchers from Drexel University's A.J.

Study suggests optimal social networks of no more than 150 people
New rules of engagement on the battlefield will require a deep understanding of networks and how they operate according to new Army research.

Social networks can support academic success
Social networks have been found to influence academic performance: students tend to perform better with high-performers among their friends, as some people are capable of inspiring others to try harder, according to Sofia Dokuka, Dilara Valeyeva and Maria Yudkevich of the HSE University.

Brain builds and uses maps of social networks, physical space, in the same way
Even in these social-distanced days, we keep in our heads a map of our relationships with other people: family, friends, coworkers and how they relate to each other.

Twitter fight: Birds use social networks to pick opponents wisely
In a new article published in the journal Current Opinion in Psychology, UC biologist Elizabeth Hobson says animals such as monk parakeets seem to understand where they fit in a dominance hierarchy and pick their fights accordingly.

Study questions benefits of social networks to disaster response
Faced with a common peril, people delay making decisions that might save lives, fail to alert each other to danger and spread misinformation.

'McDonaldization' based analysis of Russian social networks
The author describes his concept this way: 'the principles of the fast-food restaurant are coming to dominate more and more sectors of recent'.

Hunter-gatherers facilitated a cultural revolution through small social networks
Hunter-gatherer ancestors, from around 300,000 years ago, facilitated a cultural revolution by developing ideas in small social networks, and regularly drawing on knowledge from neighbouring camps, suggests a new study by UCL and University of Zurich.

Read More: Social Networks News and Social Networks Current Events is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to