Parallel application characterization for multiprocessor scheduling policy design

Thu D. Nguyen, Raj Vaswani, John Zahorjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations


Much of the recent work on multiprocessor scheduling disciplines has used abstract workload models to explore the fundamental, high-level properties of the various alternatives. As continuing work on these policies increases their level of sophistication, however, it is clear that the choice of appropriate policies must be guided at least in part by the typical behavior of actual parallel applications. Our goal in this paper is to examine a variety of such applications, providing measurements of properties relevant to scheduling policy design. We give measurements for both hand-coded parallel programs (from the SPLASH benchmark suites) and compiler-parallelized programs (from the PERFECT Club suite) running on a KSR-2 shared-memory multiprocessor. The measurements we present are intended primarily to address two aspects of multiprocessor scheduling policy design: - In the spectrum between aggressively dynamic and static allocation policies, what is an appropriate choice for the rate at which reallocations should take place? - Is it possible to take measurements of application speedup and efficiency at runtime that are sufficiently accurate to guide allocation decisions? We address these questions through three sets of measurements: - First, we examine application speedup, and the sources of speedup loss. Our results confirm that there is considerable variation in job speedup, and that the bulk of the speedup loss is due to communication and idleness. - Next, we examine runtime measurement of speedup information. We begin by looking at how such information might be acquired accurately and at acceptable cost. We then investigate the extent to which recent measurements of speedup accurately predict the future, and so the extent to which such measurements might reasonably be expected to guide allocation decisions. - Finally, we examine the durations of individual processor idle periods, and relate these to the cost of reallocating a processor at those times. These results shed light on the potential for aggressively dynamic policies to improve performance.

Original languageEnglish (US)
Title of host publicationJob Scheduling Strategies for Parallel Processing - IPPS 1996 Workshop, Proceedings
EditorsDror G. Feitelson, Larry Rudolph
PublisherSpringer Verlag
Number of pages25
ISBN (Print)3540618643, 9783540618645
StatePublished - 1996
Externally publishedYes
Event2nd Workshop on Job Scheduling Strategies for Parallel Processing, IPPS 1996 - Honolulu, United States
Duration: Apr 16 1996Apr 16 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other2nd Workshop on Job Scheduling Strategies for Parallel Processing, IPPS 1996
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Parallel application characterization for multiprocessor scheduling policy design'. Together they form a unique fingerprint.

Cite this