Parallelism-independent scheduling method
All the existing scheduling algorithms order the instructions of the program in such a wag that it call be executed in minimal time only for one fixed number of processors. In this paper we propose a new scheduling method. called Parallelism-Independent Scheduling Method. which enables the execution of the scheduled program on parallel computers with any degree of parallelism in near-optimal time. We propose three Paralielism-Independent algorithms, which have the following phases: obtaining a parallel schedule by using a list scheduling heuristics. optimization of the parallel schedule by rearranging the tasks in each level, so that they can be executed efficiently with different degrees: of parallelism, serialization of the parallel scheduler and insertion of markers for the parallel execution limits. The three algorithms differ in their optimization phase. To prove the efficiency of our algorithms, we have made simulations with random directed acyclic graphs with different size and degree of parallelism. We compared the results in terms of schedule length to those obtained using the Critical Path Algorithm separately for each degree of parallelism.
instruction scheduling static scheduling algorithms multiprocessor scheduling degree of parallelism (dop) directed acyclic graphs (dags)