XPS: FULL: Collaborative Research: PARAGRAPH: Parallel, Scalable Graph Analytics

University Of California-Davis, Davis CA

Investigators

Abstract

Many real world problems can be effectively modeled as complex relationship networks or graphs where nodes represent entities of interest and edges mimic the interactions or relationships among them. The number of such problems and the diversity of domains from which they arise is growing. However developing high-performance applications to extract useful information from such datasets is very challenging. Graphical processing units are very attractive for such applications because they offer higher computational performance and energy efficiency than standard multi-core processors. However, the development of high-performance applications for them is currently much more challenging than parallel program development for standard multi-core processors. Effective application development to use graphical processing units generally requires that developers possess considerable expertise on their architectural characteristics and use specialized programming models and performance optimization techniques. Thus, simultaneously achieving high performance and high user productivity for data analytics applications for such devices is a daunting challenge. This project proposes a scalable high-level software framework to enable the productive development of high-performance applications for graphical processing units. It features two distinct abstractions to address the performance and productivity challenges in developing graph/data analytics applications: 1) a frontier-centric abstraction that is based on a common iterative characteristic of many of these applications, with a dynamically moving active frontier of vertices (or edges) where computation is centered, and 2) an abstraction based on sparse linear algebra primitives, exploiting the dual relationship between sparse matrices and graphs. A benchmark suite of graph analytics applications will be developed and evaluated using both abstractions, enabling insights into the effectiveness of these alternate high-level abstractions for a range of analytics applications. The benchmark suite and the software framework will be publicly released.