Delay point schedules for irregular parallel computations

David M. Nicol, Joel H. Saltz, James C. Townsend

Research output: Contribution to journalArticlepeer-review


In irregular scientific computational problems one is periodically forced to choose a delay point where some overhead cost is suffered to ensure correctness, or to improve subsequent performance. Examples of delay points are problem remappings, and global synchronizations. One sometimes has considerable latitude in choosing the placement and frequency of delay points; we consider the problem of scheduling delay points so as to minimize the overal execution time. We illustrate the problem with two examples, a regridding method which changes the problem discretization during the course of the computation, and a method for solving sparse triangular systems of linear equations. We show that one can optimally choose delay points in polynomial time using dynamic programming. However, the cost models underlying this approach are often unknown. We consequently examine a scheduling heuristic based on maximizing performance locally, and empirically show it to be nearly optimal on both problems. We explain this phenomenon analytically by identifying underlying assumptions which imply that overall performance is maximized asymptotically if local performance is maximized.

Original languageEnglish (US)
Pages (from-to)69-90
Number of pages22
JournalInternational Journal of Parallel Programming
Issue number1
StatePublished - Feb 1989
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems


Dive into the research topics of 'Delay point schedules for irregular parallel computations'. Together they form a unique fingerprint.

Cite this