Scheduling tasks of a parallel program in two-processor systems with use of cellular automata |
| |
Authors: | F Seredy
ski |
| |
Affiliation: | Institute of Computer Science, Polish Academy of Sciences, Ordona 21, 01-237, Warsaw, Poland |
| |
Abstract: | In this paper, a cellular automaton (CA) is proposed as a tool for designing distributed scheduling algorithms for allocating parallel program tasks in multiprocessor systems. For this purpose, a program graph is considered as a CA containing elementary automata interacting locally according to some rules. In the first phase of the algorithm, effective rules for the CA are discovered by a genetic algorithm. In the second phase, the CA works as a distributed scheduler. In this phase, for any initial allocation of tasks in a multiprocessor system, the CA-based scheduler finds an allocation minimizing the total execution time of the program in a given system topology. The effectiveness of the proposed scheduling algorithm is shown for a number of program graphs scheduled in a two-processor system. |
| |
Keywords: | Cellular automata Scheduling tasks Parallel program |
本文献已被 ScienceDirect 等数据库收录! |
|