IEICE TRANSACTIONS on Fundamentals
Optimal Scheme for Search State Space and Scheduling on Multiprocessor Systems
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.4 pp.1088-1095
- Publication Date
- 2009/04/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E92.A.1088
- Type of Manuscript
- Special Section PAPER (Special Section on Advanced Technologies Emerging Mainly from the 21st Workshop on Circuits and Systems in Karuizawa)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hassan A. YOUNESS, Keishi SAKANUSHI, Yoshinori TAKEUCHI, Ashraf SALEM, Abdel-Moneim WAHDAN, Masaharu IMAI, "Optimal Scheme for Search State Space and Scheduling on Multiprocessor Systems" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 4, pp. 1088-1095, April 2009, doi: 10.1587/transfun.E92.A.1088.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1088/_p
Copy
@ARTICLE{e92-a_4_1088,
author={Hassan A. YOUNESS, Keishi SAKANUSHI, Yoshinori TAKEUCHI, Ashraf SALEM, Abdel-Moneim WAHDAN, Masaharu IMAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Optimal Scheme for Search State Space and Scheduling on Multiprocessor Systems},
year={2009},
volume={E92-A},
number={4},
pages={1088-1095},
abstract={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.},
keywords={},
doi={10.1587/transfun.E92.A.1088},
ISSN={1745-1337},
month={April},}
Copy
TY - JOUR
TI - Optimal Scheme for Search State Space and Scheduling on Multiprocessor Systems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1088
EP - 1095
AU - Hassan A. YOUNESS
AU - Keishi SAKANUSHI
AU - Yoshinori TAKEUCHI
AU - Ashraf SALEM
AU - Abdel-Moneim WAHDAN
AU - Masaharu IMAI
PY - 2009
DO - 10.1587/transfun.E92.A.1088
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2009
AB - 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.
ER -
English
