Fine-grained Parallel Traversals of Irregular Data Structures

Fine-grain data parallelism is increasingly common in mainstream processors in the form of long vectors and on-chip GPUs. This paper develops compiler and runtime support to exploit such data parallelism for non-numeric, non-graphic, irregular parallel tasks that perform simple computations while traversing many independent, irregular data structures, like trees and graphs. We vectorize the traversal of trees and graphs by treating a set of irregular data structures as a parallel control-flow graph and compiling the traversal into a domain-specific bytecodes. We produce a SIMD interpreter for these bytecodes, so each lane of a SIMD unit traverses one irregular data structure. Despite the overhead of interpretation, we demonstrate significant increases in single-core performance over optimized baselines.


Published in:
21st International Conference on Parallel Architectures and Compilation Techniques, 461-462
Year:
2012
Publisher:
ACM
Note:
2370896
Laboratories:




 Record created 2013-12-23, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)