Earticle

초록

영어

One of the most important challenges to achieve high-performance in multiprocessor environments such as parallel and distributed systems is task scheduling. In such architectures, each program is decomposed into the smaller and dependent segments so-called tasks. To formulate the problem, execution times of the tasks, precedence constrains and communication costs among them are modeled using a directed acyclic graph (DAG) named task graph. The goal is to minimize the program completion-time (makespan) by means of mapping the tasks to a predefined number of identical processors in such a way that precedence constrains are preserved. This problem is shown to be NP-hard in general form, and hence, a number of heuristic approaches to solve it have been introduced. A large number of proposed approaches in the literature use list-scheduling technique in which a list of tasks is created based on some priority measurements, and then in each step, the most priority task in the list is selected to schedule on the processor that allows the earliest start time (EST) until all tasks are scheduled. Assigning tasks to the processors using the EST is based on the two different techniques: insertion-based assigning (IBA) and non-insertion based (non-IBA). In this paper, we survey these two different approaches in details, and analyze the strategies and philosophies behind them. In addition, a comprehensive set of experiments and evaluations from different points of view has been done, and various results and conclusions have been presented.

목차

Abstract
 1. Introduction
 2. Multiprocessor Task Scheduling
 3. List-Scheduling Technique
  3.1. The HLFET Algorithm
  3.2. The ISH Algorithm
  3.3. The MCP Algorithm
  3.4. The ETF Algorithm
  3.5. The DLS Algorithm
 4. Task-Assigning Methods
 5. Implementation and Experimental Details
 6. Results and Comparisons
 7. Conclusion
 References

키워드

저자

• Hamid Reza Boveiri [ Sama Technical and Vocational Training College, Islamic Azad University, Shoushtar Branch, Shoushtar, Iran ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Software Engineering and Its Applications

• 간기

  월간

• pISSN

  1738-9984

• 수록기간

  2008~2016

• 등재여부

  SCOPUS

• 십진분류

  KDC 505 DDC 605