Automating Runtime Optimizations for Load Balancing in Irregular Problems

In order to reduce the effort required for attaining good performance for parallel programs, it is necessary to use automated performance optimizing techniques. In this paper we describe run-time optimizations for load balancing, and techniques to automate them without programmer intervention using post-mortem analysis of parallel program execution. These techniques are very useful for applications having irregular, non-uniform or dynamic load patterns. We classify the characteristics of parallel programs with respect to object placement (which determines load balance), then describe techniques to discover these characteristics by post-mortem analysis, and present heuristics to choose appropriate load balancing schemes based on these characteristics. Our ideas have been developed in the framework of the Paradise post-mortem analysis tool for the parallel object-oriented language Charm++. We also present results for optimizing simple parallel programs running on the Thinking Machines CM-5.

Sanjeev Krishnan and L. V. Kale, "Automating Runtime Optimizations for Load 
Balancing in Irregular Problems", Proc. Conf. on Parallel and Distributed 
Processing Technology and Applications, San Jose, California, August 1996.

@inproceedings{RuntimeOptsPDPTA96,
  author = "Sanjeev Krishnan and L. V. Kale",
  title = "{Automating Runtime Optimizations for Load Balancing
           in Irregular Problems}",
  booktitle = "Proc. Conf. on Parallel and Distributed Processing
               Technology and Applications",
  year = "1996",
  address = "San Jose, California",
  month = "August",
}