Brief Announcement: Locality-aware Load Balancing for Speculatively-parallelized Irregular Applications

Youngjoon Jo and Milind Kulkarni

SPAA 2010 · Symposium on Parallelism in Algorithms and Architectures · June 2010 · pp. 183-185

Abstract

Load balancing is an important consideration when running data-parallel programs. While traditional techniques trade off the cost of load imbalance with the overhead of mitigating that imbalance, when speculatively parallelizing amorphous data-parallel applications, we must also consider the effects of load balancing decisions on locality and speculation accuracy. We present two data centric load balancing strategies which account for the intricacies of amorphous data-parallel execution. We implement these strategies as schedulers in the Galois system and demonstrate that they outperform traditional load balancing schedulers, as well as a data-centric, non-load-balancing scheduler.

BibTeX

@inproceedings{jo10spaa,
  author    = {Youngjoon Jo and Milind Kulkarni},
  title     = {Brief Announcement: Locality-aware Load Balancing for Speculatively-parallelized Irregular Applications},
  booktitle = {Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA)},
  pages     = {183--185},
  publisher = {ACM},
  address   = {Thira, Santorini, Greece},
  year      = {2010},
  month     = jun,
  doi       = {10.1145/1810479.1810516}
}

Group members