Most success in parallel computing is achieved with regular data parallel algorithms, where the same task is independently performed on all elements of a data structure--typically, a dense vector or matrix. However, it is not a priori clear how much parallelism is inherent in irregular applications with amorphous data parallelism; such applications operate on pointer-based graphs, where, due to algorithmic constraints at any time, only a subset of graph nodes can be simultaneously processed.

For analyzing such algorithms, Kulkarni et al. developed the ParaMeter tool, a simulator for programs written in a sequential style, extended by an iteration construct for the parallel processing of all elements of a set. The simulation proceeds in a number of rounds where essentially, in every round, a maximal set of independent nodes is selected, and then the effect of processing these nodes in parallel is determined. The number of independent nodes per round thus serves as a measure for the amount of parallelism inherent in the algorithm.

As the authors point out, the resulting parallelism profile is influenced by the tool’s greedy scheduling strategy and by the particular (random) choice of a maximal independent set of nodes per round (there may exist better choices that amount to more parallelism). However, the paper contains sample analyses of six algorithms, five of which seem insensitive to the choices; only the last one significantly underestimates the available parallelism. Therefore, the tool is certainly valuable as an initial guide for the development of irregular parallel applications.