.png){kind=icon}
.png){kind=icon}
Return
GraphOpt: Constrained-Optimization-Based Parallelization of Irregular Graphs
.png){kind=icon}
OA
AI
DOI：10.1109/TPDS.2022.3151194.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Sparse, irregular graphs show up in various applications like linear algebra, machine learning, engineering simulations, robotic control, etc. These graphs have a high degree of parallelism, but their execution on parallel threads of modern platforms remains challenging due to the irregular data dependencies. The execution performance can be improved by efficiently partitioning the graphs such that the communication and thread synchronization overheads are minimized without hurting the utilization of the threads. To achieve this, this article proposes GraphOpt, a tool that models the graph parallelization as a constrained optimization problem and uses the open Google OR-Tools solver to find good partitions. Several scalability techniques are developed to handle large real-world graphs with millions of nodes and edges. Extensive experiments are performed on the graphs of sparse matrix triangular solves (linear algebra) and sum-product networks (machine learning), respectively, showing a mean speedup of 2.0x and 1.8x over previous state-of-the-art libraries, demonstrating the effectiveness of the constrained-optimization-based graph parallelization.
Keywords:
Parallel processing
Task analysis
Instruction sets
Synchronization
Hardware
Optimization
Scalability
Graph parallelization
partitioning
constrained optimization
sparse matrix triangular solves
CPU multithreading
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W