Optimal Scheme for Search State Space and Scheduling on Multiprocessor Systems

Hassan A. YOUNESS  Keishi SAKANUSHI  Yoshinori TAKEUCHI  Ashraf SALEM  Abdel-Moneim WAHDAN  Masaharu IMAI 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E92-A  No.4  pp.1088-1095
Publication Date: 2009/04/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Advanced Technologies Emerging Mainly from the 21st Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
optimal scheduling,  task graphs,  state-space search,  A*,  geometric analysis, 

Full Text: PDF(1.4MB)

Summary: 
A scheduling algorithm aims to minimize the overall execution time of the program by properly allocating and arranging the execution order of the tasks on the core processors such that the precedence constraints among the tasks are preserved. In this paper, we present a new scheduling algorithm by using geometry analysis of the Task Precedence Graph (TPG) based on A* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity and pruning techniques to produce an optimal solution for the allocation/scheduling problem of a parallel application to parallel and multiprocessor architecture. The main goal of this work is to significantly reduce the search space and achieve the optimality or near optimal solution. We implemented the algorithm on general task graph problems that are processed on most of related search work and obtain the optimal scheduling with a small number of states. The proposed algorithm reduced the exhaustive search by at least 50% of search space. The viability and potential of the proposed algorithm is demonstrated by an illustrative example.