How much parallelism is there in irregular applications?
Milind V. Kulkarni, Martin Burtscher, Rajeshkar Inkulu, Keshav K. Pingali, Călin Caşcaval · 2009
Irregular programs are programs organized around pointer-based data structures such as trees and graphs. Recent investigations by the Galois project have shown that many irregular programs have a generalized form of data-parallelism called amorphous data-parallelism. However, in many programs, amorphous data-parallelism cannot be uncovered using static techniques, and its exploitation requires runtime strategies such as optimistic parallel execution. This raises a natural question: how much amorphous data-parallelism actually exists in irregular programs?