Their ‘very simple scheme’ earns award in annual competition
PNNL computer scientists Sayan Ghosh, left, and Mahantesh Halappanavar were one of the winning teams in the recent MIT GraphChallenge 2020.
(Photos by Andrea Starr | Pacific Northwest National Laboratory)
Pacific Northwest National Laboratory (PNNL) computer scientists Sayan Ghosh and Mahantesh Halappanavar were one of the winning teams in the recent MIT GraphChallenge 2020.
The competition conducted by the Massachusetts Institute of Technology Lincoln Laboratory encourages community approaches to developing new solutions for analyzing graphs and sparse data. The annual event, which attracts entrants from national laboratories, research universities, and industry, stimulates research and highlights innovations in software, hardware, algorithms, and systems. Participants respond to problems crafted by GraphChallenge organizers and use supercomputers to solve a challenge and submit their findings to judges who choose winners based on criteria, such as which solution is fastest and most novel.
Ghosh and Halappanavar were among four winners in the Champions category for their entry, “TriC: Distributed-memory Triangle Counting by Exploiting the Graph Structure.”
“We came up with a code that is able to run on supercomputers,” said Ghosh, who holds a computer science doctoral degree from Washington State University. “We showed scalability. Others did the same, but ultimately ours was chosen.”
Graph analytics has emerged as an important tool in the analysis of large-scale data from diverse application domains, such as social networks, cyber security, and bioinformatics. Counting the number of triangles in a graph is a fundamental kernel with several applications, such as detecting the community structure of a graph or in identifying important vertices in a graph.
In their graph-data formula, Ghosh and Halappanavar used parallel computing concepts, where many calculations or the execution of processes are carried out simultaneously. Large problems are divided into smaller pieces.
“We have come up with a very simple scheme to solve this problem,” said Ghosh. The solution pays attention to the need for the supercomputer to work swiftly and economically on the analysis. “There have been other ways to solve this problem, but I think our implementation is one of the simplest. And that’s what I think is kind of the novelty of our solution, and what ultimately captured the attention of the judges.”
The GraphChallenge also made awards to three teams for Innovation and two teams for Honorable Mention. Winners were announced in late August. In addition to MIT, GraphChallenge presenters included the Institute of Electrical and Electronics Engineers and Amazon Web Services.
The awards started in 2017. PNNL has had at least one winning team each year.
“The challenge keeps us on our toes,” said Halappanavar, a team leader and acting group manager of PNNL’s Data Sciences group. “It not only promotes our work in the community, but also helps us improve our codes.”
Ghosh and Halappanavar used resources of the National Energy Research Scientific Computing Center facility, supported by the U.S. Department of Energy Office of Science. The research is in part supported by the ExaGraph project at PNNL.
Published: November 6, 2020