The Impact of Program Structure on the Performance of Scheduling Policies in Multiprocessor Systems

A simple fork and join type of job structure has been extensively used for performance evaluation of processor scheduling policies in multiprocessor systems. However, parallel programs often exhibit a more complicated structure. It is not clear how the program structure affects the performance of processor scheduling policies. This paper studies the impact of the program structure on the performance of processor scheduling policies that are appropriate for uniform memory access (UMA) shared-memory systems. We consider four types of parallel program structures that are frequently employed in parallel applications. These are the fork-and-join, divide-and-conquer, Gaussian elimination, and state space search programs. The impact of these four job structures on the performance of four processor scheduling policies is considered. These are the job-based round robin (RRJob), coscheduling, dynamic (Dynamic), and the preemptive smallest cumulative demand first (PSCDF) policies. These policies ..