Iterative Scheduling Algorithms Based on the Subdivision of the Solution Space into Domains
Источник: Moscow University Computational Mathematics and Cybernetics, 2008, Vol. 32, No. 3, pp. 177–181. © Allerton Press, Inc., 2008
Аннотация: Iterative multiprocessor scheduling algorithms are considered. The iterative algorithms make it possible to solve scheduling problems for a wide class of computer architectures but are very intricate from the computational point of view. To simplify the iterative algorithms, we propose an approach to their construction based on the subdivision of the space of correct schedules into disjoint domains, namely, an algorithm for constructing domains is proposed, the operations of the schedule transformations closed within the domains are introduced, and a technique for cutting off domains is developed. The approach developed also makes it possible to construct parallel algorithms with a low traffic of the exchange between parallel processes.
Скачать pdf-файл материала