SHF: Medium: A Tensor Formulation for Graph Analytics

University Of California-Davis, Davis CA

Investigators

Abstract

Many real-world applications can be described by a list of entities and the relationships between them. For instance, a social network is a list of people and their friendships; a streaming media site might have a list of users and movies with a link between a user and a movie if the user has liked that movie; a genetic researcher might link specific genes with diseases if such a correlation has been established. Computer scientists express these relationships in a "graph", which represents entities as "vertices" and relationships as "edges" in the graph. Given such a graph, scientists can design methods -- "algorithms" -- to extract useful information from the graph, such as groupings of friends, suggestions for unseen movies, or potentially interesting gene-disease linkages. Insights from graph analysis are powerful and widely used today across science, engineering, and commerce, but designing and optimizing the algorithms that deliver these insights is a significant research and practical challenge that is rarely pursued in a systematic, automated, principled way. The researchers propose a new abstraction to characterize graph computation and, with that abstraction, a way to systematically explore the design space of a particular graph computation to identify efficient and novel implementations that can deliver best-in-class performance across different computer systems. The project will enable the combination of high-level programmability, automated exploration of design alternatives, and high and portable performance for graph analytics in a single open-source framework. It will also educate students on performance engineering topics critical to the efficiency of artificial intelligence (AI) applications. The investigators propose a framework to express, explore, and compile graph algorithms in a rigorous, succinct, expressive mathematical tensor framework suitable for both human and machine manipulation. The input to the new framework is an algorithmic description in Einstein summation notation, an "einsum", traditionally used in tensor-algebra and machine-learning applications, extended for graph computation. The new framework allows automated design explorations of graph and implementation choices that incorporate common algorithmic and implementation design patterns and transformations. The proposed design is separated into platform-independent and platform-dependent phases, enabling target-specific backends. The preliminary design exploration indicates that combining simple algebraic transformations within the proposed framework can produce meaningful results. The researchers will release the framework as open-source software, primarily focusing on an NVIDIA Computer Unified Device Architecture (CUDA) backend but also targeting AMD (Graphics Processing Unit, i.e., GPU) and C++ (Central Processing Unit, i.e., CPU) environments. Finally, the researchers will also work with the OpenCilk academic board and NVIDIA's education team to advance the field of GPU performance engineering and continue their strong record of mentoring and advising students. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.