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.

• （社）電子情報通信学会の論文
• 2009-04-01

著者

• 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

• Takeuchi Yoshinori

  Osaka University

• Imai Masaharu

  Graduate School Of Information Science And Technology Osaka University

• Salem Ashraf

  Faculty Of Engineering Ain Shams University

• Youness Hassan

  Graduate School Of Information Science And Technology Osaka University

• Sakanushi K

  Graduate School Of Information Science And Technology Osaka University

• Takeuchi Yoshinori

  Graduate School Of Information Science And Technology Osaka University

• Wahdan Abdel-moneim

  Faculty Of Engineering Ain Shams University

• Takeuchi Yoshinori

  Graduate School Of Engineering Science Osaka University

• Imai Masaharu

  Graduate School of Electrical and Electronic Engineering Kogakuin University

• Masaharu Imai

  Osaka University

関連論文

• Software Development Tool Generation Method Suitable for Instruction Set Extension of Embedded Processors
• 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)
• VLSI Architecture for Real-Time Fractal Image Coding Processors (Special Section of Selected Papers from the 12th Workshop on Circuit and Systems in Karuizawa)
• Heuristic Instruction Scheduling Algorithm Using Available Distance for Partial Forwarding Processor
• AS-1-2 ASIP Meister : An ASIP Design Environment
• Informative Patches Sampling for Image Classification by Utilizing Bottom-up and Top-down Information (パターン認識・メディア理解)
• Informative Patches Sampling for Image Classification by Utilizing Bottom-up and Top-down Information
• Two-Stage Configurable Decoder Model for Domain Specific FEC Decoder Design
• A Small-Area and Low-Power SoC for Less-Invasive Pressure Sensing Capsules in Ambulatory Urodynamic Monitoring
• Informative Patches Sampling for Image Classification by Utilizing Bottom-up and Top-down Information
• BS-5-43 Proposed End-to-End Available Bandwidth Estimation Method Using RTT Taking into Account Traffic Load in Return Path(BS-5. Network and Service Design, Control and Management)
• Software Development Tool Generation Method Suitable for Instruction Set Extension of Embedded Processors
• A Low-power ASIP Generation Method by Extracting Minimum Execution Conditions
• Advantage and Possibility of Application-domain Specific Instruction-set Processor (ASIP)
• Informative Patches Sampling for Image Classification by Utilizing Bottom-up and Top-down Information
• A Low-power ASIP Generation Method by Extracting Minimum Execution Conditions

もっと見る 閉じる

スポンサーリンク