Yao-Jen Chang and Jean-Lien C. Wu+
Department of Electrical Engineering
National Taiwan University
Taipei, Taiwan 10764, R.O.C.
+Department of Electrical Engineering
National Taiwan Institute of Technology
Taipei, Taiwan, R.O.C.
This paper concerns scheduling parallel programs in multiprocessing systems. The goal is to improve 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. From another perspective, the study is intended to be a queueing counterpart of Amdahl's Law. In this paper, various two-stage cases are investigated with preemptive or FCFS scheduling policies, and the optimal strategy is determined. Methods of solving the queueing models encompass the z-transform approach and the state-of-the-art matrix-geometric method, whichever is appropriate. In addition, probability projection is devised to enhance the z-transform methods and handle Markov chains which have more than one boundary probability. Results indicate that, with nonhomogeneous parallelism profiles, it would be a better processor allocation policy to give preferential treatment to serial stages. This study might hopefully improve the design of parallel operating systems as well as parallel algorithms, databases, and parallelizing compilers.
Keywords: processor scheduling, parallel systems, performance modeling,workload characterization, queueing models
Received May 8, 1991; revised November 1, 1991.
Communicated by Ferng-Ching Lin.
*A previous version of this paper appeared in Supercomputing '91, November 18-22, 1991. This conference, sponsored by the ACM and the IEEE, was held in Albuquerque, New Mexico, USA. This paper also received the Supercomputing '91 best student paper award.