
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

ParallelismIndependent Scheduling Method
Kirilka NIKOLOVA Atusi MAEDA Masahiro SOWA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83A
No.6
pp.11381150 Publication Date: 2000/06/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section of Papers Selected from 1999 International Technical Conference on Circuits/Systems, Computers and Communications (ITCCSCC'99)) Category: Keyword: instruction scheduling, static scheduling algorithms, multiprocessor scheduling, degree of parallelism (DOP), directed acyclic graphs (DAGs),
Full Text: PDF>>
Summary:
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 ParallelismIndependent Scheduling Method, which enables the execution of the scheduled program on parallel computers with any degree of parallelism in nearoptimal time. We propose three ParallelismIndependent 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.

