An Empirical Study of the Workload Distribution under Static Scheduling
- 1 August 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In the decision regarding static scheduling vs. dynamic scheduling, the only argument against the former is the potential imbalance of the workload. However, it has never been clear how the workload distributes in the iterations of Fortran parallel loops. This work examines a set of Perfect benchmarking programs [2] and report two striking results. First, when using operation counts as the measure, almost all the parallel loops identified by the Parafrase 2 compiler [11] in those programs have an equal workload among different iterations. Second, simulation shows that, although run time events on the memory system can lead to considerable variation in the execution time of different iterations which are scheduled statically, the finish time of the slowest processor normally does not exceed the average processor by the mean execution time of one loop iteration. Such workload distribution is as good as any known dynamic scheduling policy can guarantee.Keywords
This publication has 12 references indexed in Scilit:
- An Empirical Study of the Workload Distribution under Static SchedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1994
- Locality and Loop Scheduling on NUMA MultiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1993
- Factoring: a method for scheduling parallel loopsCommunications of the ACM, 1992
- The Stanford Dash multiprocessorComputer, 1992
- Comparative performance evaluation of cache-coherent NUMA and COMA architecturesPublished by Association for Computing Machinery (ACM) ,1992
- DDM-a cache-only memory architectureComputer, 1992
- The Monarch parallel processor hardware designComputer, 1990
- PARAFRASE-2: AN ENVIRONMENT FOR PARALLELIZING, PARTITIONING, SYNCHRONIZING, AND SCHEDULING PROGRAMS ON MULTIPROCESSORSInternational Journal of High Speed Computing, 1989
- Guided Self-Scheduling: A Practical Scheduling Scheme for Parallel SupercomputersIEEE Transactions on Computers, 1987
- Multis: A New Class of Multiprocessor ComputersScience, 1985