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.