Parallelism-Independent Scheduling Method

Kirilka NIKOLOVA  Atusi MAEDA  Masahiro SOWA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.6   pp.1138-1150
Publication Date: 2000/06/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Papers Selected from 1999 International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC'99))
instruction scheduling,  static scheduling algorithms,  multiprocessor scheduling,  degree of parallelism (DOP),  directed acyclic graphs (DAGs),  

Full Text: PDF>>
Buy this Article

All the existing scheduling algorithms order the instructions of the program in such a way that it can 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 Parallelism-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 schedule, 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.