earticle

영어

Optimized task scheduling is one the most important factors to achieve high-performance in multiprocessor environments such as parallel and distributed systems. In such architectures, each program is decomposed into the smaller dependent segments so-called tasks. To formulate the problem, execution times of 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 the 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. In this paper, we survey five different list-scheduling approaches namely HLFET, ISH, MCP, ETF and DLS from the different points of view, and describe the strategies and philosophies behind them. In addition, a comprehensive set of experiments and evaluations has been done, and different results and conclusions have been presented.