Optimal Scheme for Search State Space and Scheduling on Multiprocessor Systems

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• （社）電子情報通信学会の論文

著者

• YOUNESS Hassan

  Graduate School of Information Science and Technology, Osaka University

• SAKANUSHI Keishi

  Graduate School of Information Science and Technology, Osaka University

• TAKEUCHI Yoshinori

  Graduate School of Information Science and Technology, Osaka University

• SALEM Ashraf

  Faculty of Engineering, Ain Shams University

• WAHDAN Abdel-Moneim

  Faculty of Engineering, Ain Shams University

• IMAI Masaharu

  Graduate School of Information Science and Technology, Osaka University

関連論文

• Optimal Scheme for Search State Space and Scheduling on Multiprocessor Systems
• An Improved Method of Convex Rectilinear Block Packing Based on Sequence-Pair(Place and Routing)(VLSI Design and CAD Algorithms)
• COMBINING GLOBAL AND SIMPLIFIED PARTS-BASED APPROACH TO ESTIMATE HUMAN BODY CONFIGURATION(International Workshop on Advanced Image Technology 2005)
• Code Efficiency Evaluation for Embedded Processors(Special Section of Selected Papers from the 14th Workshop on Circuits and Systems in Karuizawa)
• Optimal Scheme for Search State Space and Scheduling on Multiprocessor Systems
• Reconfigurable AGU : An Address Generation Unit Based on Address Calculation Pattern for Low Energy and High Performance Embedded Processors
• Efficient Method to Generate an Energy Efficient Schedule Using Operation Shuffling
• Heart Instantaneous Frequency Based Estimation of HRV from Blood Pressure Waveforms
• DETERMINATION OF CORRESPONDENCE BETWEEN AUDIO AND VISUAL EVENTS THROUGH ACTIVE MOTION(International Workshop on Advanced Image Technology 2007)
• DETERMINATION OF CORRESPONDENCE BETWEEN AUDIO AND VISUAL EVENTS THROUGH ACTIVE MOTION
• AN ATTENTIONAL CORRESPONDENCE OF AUDIO-VISUAL EVENTS(International Workshop on Advanced Image Technology 2005)
• Generation of Pack Instruction Sequence for Media Processors Using Multi-Valued Decision Diagram(System Level Design,VLSI Design and CAD Algorithms)
• JPEG Encoder Design Space Exploration Using the ASIP Development System: PEAS-3 (特集:システムLSIの設計技術と設計自動化)
• Advantage and Possibility of Application-domain Specific Instruction-set Processor (ASIP)
• Advantage and Possibility of Application-domain Specific Instruction-set Processor (ASIP)

もっと見る 閉じる

スポンサーリンク