Conducting operations and defending the nations critical networks in cyberspace requires processing and analyzing massive quantities of graph data in near-real time. New approaches for high performance graph analytics and query are needed for cyber defense and operations at massive data scales. Scaling graphs is a hard problem. Due to non-locality, CPU-based solutions are limited by main memory bandwidth. GPUs have superior memory bandwidth and offer the potential of a significant increase over multi-core, CPU in-memory (100-1000X) and disk-based (10,000X) approaches. However building analytics for GPUs is challenging due to the complexities of parallel programming and the specialized languages. Phase II will develop a comprehensive software implementation for GPUs that provides 100-10,000X acceleration of common graph programming frameworks for graph-oriented queries (SPARQL). The research will develop ways to model graphs on the GPU and use Sparse Matrix Vector multiplication (SPMV) and Linear Algebra libraries for accelerating graph query. The resulting technology will process billions graph edges in seconds using common graph query languages and frameworks. It will enable existing DARPA programs using graph query to achieve massive data scale. There are significant commercial applications in the areas of network security, drug discovery, regulatory compliance, and social networking/e-commerce.
