Acceleration of Graph Analytics Codes
Abstract
The purpose of this proposal I to develop accelerated versions of centrality algorithms, supporting code, and execution management software targeting problem sizes of navy interest, and adapted to modern accelerators, especially the NVIDIA GPUs. The effort will concentrate on technical issues encountered with road-network graphs, which have low degree and high diameter, and are not efficiently handled by the current generation of accelerated codes. The Awardee will develop accelerator-appropriate versions of centrality algorithms and their components, such as shortest-path algorithms. Contractor hierarchies or similar techniques will be investigated to overcome problems with road network graphs. The end product will be documented code computing the centrality measures of sponsor interest on accelerated systems. Analyses of the performance of these codes suitable for estimating hardware needs will also be delivered. An execution management system will be developed that will submit the code for execution in a way appropriate for the problem size and available computing resources. The first year will focus on delivering a GPGPU-tuned package for a centrality measure of prime interest, which will be tuned for graphs of moderate size. Subsequent years will be focused on achieving cost goals for graphs of larger size, and for targeting computation at different device mixes. The execution management system should be delivered by the end of the second year, and updated in subsequent years.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 18, 2016
- Source ID
- N00173162C901
Entities
People
- David Koppelman
Organizations
- Louisiana State University System
- United States Naval Research Laboratory
- United States Navy