Lonestar: A Suite of Parallel Irregular Programs

Milind Kulkarni, Martin Burtscher, Calin Cascaval, and Keshav Pingali

ISPASS 2009 · International Symposium on Performance Analysis of Systems and Software · April 2009 · pp. 65-76

Acceptance rate 29%

Abstract

Until recently, parallel programming has mainly focused on the exploitation of data-parallelism in dense matrix programs. However, many important application domains, including meshing, clustering, simulation, and machine learning, have very different algorithmic foundations: they require building, computing with, and modifying large sparse graphs. In the parallel programming literature, these types of applications are usually classified as irregular applications, and relatively little attention has been paid to them. To better study and understand the patterns of parallelism and locality in sparse graph computations, we implemented five programs that target domains such as data mining, survey propagation, and design automation. applications often expose large amounts of parallelism in the form of amorphous data-parallelism. Our speedup numbers demonstrate that this new type of parallelism can successfully be exploited on modern multi-core machines.

BibTeX

@inproceedings{kulkarni09ispass,
  author    = {Milind Kulkarni and Martin Burtscher and Calin Cascaval and Keshav Pingali},
  title     = {Lonestar: A Suite of Parallel Irregular Programs},
  booktitle = {Proceedings of the International Symposium on Performance Analysis of Systems and Software (ISPASS)},
  pages     = {65--76},
  year      = {2009},
  month     = apr,
  doi       = {10.1109/ISPASS.2009.4919639}
}