Performance Portable Framework for Developing Graph Applications

Period of Performance: 01/01/2015 - 12/31/2015

$150K

Phase 1 SBIR

Recipient Firm

RNET Technologies, Inc.
240 West Elmwood Dr Suite 2010
Dayton, OH 45459
Principal Investigator

Abstract

The importance of graph applications is growing as society becomes more interconnected. Many real world datasets are best modeled as graphs, e.g., road networks, the Internet, social networks, protein-protein interactions, utility grids, and communication. Graph analytics are used to answer many different categories of questions, including traversal, querying, and data mining. It is often desirable to execute graph analytics applications on a wide range of hardware platforms (from supercomputers to mobile devices). The fundamental question we will explore include: Can a small set of high-level graph/matrix operations be identified and implemented, to enable high performance, high user productivity, and performance portability for a wide range of graph analytics applications of interest to the DoD, with effectiveness on a diverse collection of data sets? The equivalence between a graph and the associated sparse matrix encoding a graph's adjacency list has prompted considerable interest in casting various graph algorithms in terms of sparse matrix operations. We propose to identify a set of high-level matrix and graph operations, create efficient implementations for multiple platforms (using multiple algorithms/representations to optimize for data-set dependence), and demonstrate their effectiveness on a range of graph analytics applications.