An Empirical Study of the Workload Distribution under Static Scheduling

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.