New UpDown Project Uses “Intelligent Data Movement” to Accelerate Graph Analytics

Graph analytics is at the heart of some of today’s most exciting computational applications in science and technology. The organization of data into graphs – large networks of people, molecules, or locations connected by their interactions and relationships – can unleash powerful insights for ecommerce, scientific discovery, social networks, recommendation and search engines, and fraud or anomaly detection. However, today’s computing architectures were not designed for graphs, and struggle with efficiency and scalability.

With a $9.2 million grant from IARPA, Andrew A. Chien will lead a team of UChicago Computer Science researchers including Henry Hoffmann, Yanjing Li, and Michael Maire researching the UpDown System, a new approach that could speed up graph analytics a hundredfold. The effort will reinvent computer architecture, dramatically increasing efficiency and scalability for graph computing. The team also includes graph computing experts from Purdue University and Tactical Computing Laboratories, who will design and test the UpDown hardware.

“Efficient and scalable computation over massive graph structures is the signature computing challenge for the next several decades,” said Chien, William Eckhardt Distinguished Service Professor in the Department of Computer Science and Senior Computer Scientist at Argonne National Laboratory. “The UpDown architecture that we’ve invented has novel capabilities to both encode information efficiently and move it intelligently around the machine, both of which are critical for faster graph computing.”

For decades, high-performance computer architectures were optimized to perform linear algebra and other dense operations, with improvements concentrated on the single value transformations (floating point) instead of the complex, intelligent data movement required by sophisticated data structures. In working with large and sparse graphs, the priorities are flipped: computers conduct fewer operations, but must intelligently interpret and move much larger amounts of data.

The UpDown architecture thus enables flexible graph representation and programmable intelligence to move it within the system. The UpDown accelerator resides between the CPU and memory, empowering an application to create “software-defined hardware” that customizes how data is encoded, interpreted, and moves through a node. Programmers can write software to increase performance for specific applications, or draw upon machine learning to optimize the flow of data through the system.

“The UpDown architecture supports programming paradigms not previously viable,” Hoffmann said. “For example, UpDown can transform data representations on-the-fly where prior work would have forced programmers into a single compromise representation. We will apply automated techniques based on our prior work on self-aware to exploit this opportunity, selecting the best representation at each point. The goal is to intelligently extract the maximum value from this new architectural capability.”

In preliminary evaluations with Argonne scientists and applications, the UpDown team demonstrated 100x performance increases on several graph computing benchmarks. In addition to speeding up graph analytics tasks, these improvements would also make them more energy-efficient.

For the next phase of the project, the team will build on the radical design of the UpDown system, exploring new applications as well as expanding the architecture up to tens of thousands of nodes. Such a scope will be necessary to efficiently analyze the world’s largest graphs from social media, financial transactions, or Internet of Things device networks that contain billions or trillions of vertices and edges, Chien said.

“The selection of UChicago reflects the institution’s leadership in large-scale systems, computer architecture, and machine learning, as well as the collaborative synergy across these areas at UChicago and Argonne,” Chien said.

The UpDown project was funded as part of the IARPA AGILE (Advanced Graphic Intelligence Logical Computing Environment) program. Additional members of the UpDown team include David F. Gleich of Purdue University, and Dave Donofrio and John Leidel of Tactical Computing Laboratories.