Architecture Neutral Parallel Graph Algorithms with LPG

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


Phase 1 SBIR

Recipient Firm

Galois, Inc.
421 SW Sixth Ave Suite 300
Portland, OR 97204
Principal Investigator


We propose to build a high-level Domain Specific Language (DSL) for graph processing. This DSL, Language For Processing Graphs (LPG), will be embedded in Python and can be compiled to multiple parallel architectures. By using a high-level architecturally-neutral DSL, we gain two things: (1) we can develop programs more quickly, and (2) our programs will not be tied to any specific parallel architecture. When it comes to code generation, the high-level nature of LPG is a two-edged sword: on the one hand, there is a greater semantic gap to bridge; but on the other hand, there will be more possibilities to perform powerful transformations and optimizations. To support better code generation, LPG allows the programmer to add annotations that describe the characteristics of graph data (e.g., sparsity, weight-distribution, problem-size, etc.). Python is already used extensively in the data-analytics community. Embedding LPG in Python means that it is instantly accessible to a large community of users and developers can exploit the extensive Python ecosystem including libraries and tools for plotting and data visualization.