On multiprocessor system scheduling
Xiaotie Deng, Patrick W. Dymond · 1996
We show that there is a good algorithm for scheduling the average completion time of a set of unknown DAGs (i.e., data dependency relation graphs of programs) on a multiprocessor in the PRAM model [12] (or other similar shared memory models.) Then, we show that a large class of parallel jobs can be scheduled with near-optimal average completion time in the BSP model [31] though this is not possible for the class of all unknown DAGs [6] (the same holds for other similar distributed memory models.) 1 Introduction The execution of programs on a uniprocessor system is straightforward: any non-idle scheduling strategy achieves optimal schedule length. If average completion time is taken as the system performance metric, the Round-Robin policy achieves a mean response time within twice the optimum [20]. Notice that the Round-Robin policy does not need to know the control/data dependency graph (DAG) of the program's execution at compile time. On the other hand, scheduling of multiprocessor s...