The aim of SHARP is to enable platform independent implementation of fast, scalable and approximate, static and streaming graph algorithms. SHARP will develop a software tool-kit for seamless acceleration of graph analytics (GA) applications, for a first of its kind collection of graph processors. We develop novel hierarchical abstractions to represent graph algorithms, optimal memory data layouts for static and dynamic graphs and efficient linear programming based scheduling algorithms for graph processors that synergistically enable easy and efficient mapping of algorithms and data structures on a variety of heterogeneous hardware architectures.
SHARP is a collaborative effort led by Viktor Prasanna at the USC Viterbi School of Engineering and David Bader at the Georgia Institute of Technology. It is focused on the software infrastructure technology area of the Hierarchical Identify Verify Exploit (HIVE) program sponsored by the Defense Advanced Research Projects Agency (DARPA). The goal of the HIVE program is to create an end to end graph processing system that achieves 1000x improvement in processing efficiency and enables relationship in events to be discovered in real-time as they unfold in the field. The goal is to develop specialized Graph Processors, software tools for easy programming on the hardware and system architecture to enable efficient scaling a variety of graph analytics to trillion edge graphs with special emphasis on Department of Defense (DoD) applications like anomaly detection, N-x contingency analysis, causal event modelling etc.
CHALLENGES
The challenges that SHARP project must address are:
- Platform independent support to accelerate DoD applications on various HIVE architectures consisting of various state of the art technologies like near memory computing, 3D memory, vector processing etc.
- Scalability to extremely large static and dynamic graphs with billions of nodes and trillions of edges
- Powerful Uniform Abstraction for ease of programming a multitude of applications using a single framework
OBJECTIVE
The objective of SHARP is to accelerate graph analytics through:
- Optimal Primitive Selection to decompose high level graph applications into a hierarchy of backbone programs that can run very efficiently on HIVE architectures
- Scheduling and Load Balancing to ensure uniform equivalent work distribution across multiple accelerators and processors in HIVE architecture
- Data Layouts for static and dynamic graphs that dramatically reduce memory access times and improve bandwidth utilization