Scheduling parallel programs with non-uniform parallelism profiles
Yao‐Jen Chang, Jean‐Lien C. Wu, Jingshown Wu · 1991
This paper concerns scheduling parallel programs in multiprocessing systems. The goal is to improve the job turnaround time and speedup. As most programs are not fully parallelizable, parallel programs consisting of serial, partially parallel, and (perfectly) parallel stages, are modeled by task graphs which depict the parallelism profiles. In another perspective, the study is intended to be a queueing counterpart of Amdahl's Law. Various two-stage cases are investigated with FCFS or priority scheduling policies and the optimal strategy is determined. Results indicate that, with nonhomogeneous parallelism profiles, it would be a better processor allocation policy to give a preferential treatment to serial stages. The study might hopefully improve the design of parallel operating systems as well as parallel algorithms, databases, and parallelizing compilers.