Scheduling Parallel Tasks: Approximation Algorithms
Scheduling Parallel Tasks: Approximation Algorithms
复制标题
调度并行任务：近似算法
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
D. Trystram
中科院分区：
文献类型：
--
作者：
P. Dutot;G. Mounié;D. Trystram
在并行和分布式处理中，调度是一个至关重要的问题。它包括确定将执行并行程序的何时执行。平行算法的设计必须由新的执行支持的影响（即工作站，网格计算和全球计算）的影响重新考虑，这些算法的特征在于较大的异质处理器，通常由层次子系统组织组织。大约15年前，已引入了并行任务模型（需要多个处理器才能执行其执行者的任务），作为安排并行应用程序的有希望的替代方案，尤其是在慢速通信媒体的情况下。基本思想是在粗略的粒度上考虑应用程序（较大的任务以减少通信的相对权重）。由于在实际系统中调度的主要困难来自有效地处理通信，因此对问题的新看法使我们能够隐含地考虑它们，从而导致了更加可行的问题。我们请邀请读者查看Maciej Drozdowski（在本书中）的章节，以详细介绍一般环境中各种并行任务的详细介绍，以及Feitelson等人的调查文件。 \ cite {feitelsonSurvey}在并行处理领域进行讨论。即使调度并行任务的基本问题仍然是NP-HARD，也可以设计一些近似算法。最近，用于安排不同类型的平行任务（即刚性，可塑造或可延展性）的不同类型的结果。我们将在多用户上下文中区分同一应用程序内的并行任务。将讨论各种优化标准。本章旨在提出几种近似算法，以计划可塑性和可延展的任务，并特别强调新的执行支持。
Scheduling is a crucial problem in parallel and distributed processing. It consists of determining where and when the tasks of parallel programs will be executed. The design of parallel algorithms has to be reconsidered by the influence of new execution supports (namely, clusters of workstations, grid computing and global computing) which are characterized by a larger number of heterogeneous processors, often organized by hierarchical sub-systems. Parallel Tasks model (tasks that require more than one processor for their execution) has been introduced about 15 years ago as a promising alternative for scheduling parallel applications, especially in the case of slow communication media. The basic idea is to consider the application at a rough level of granularity (larger tasks in order to decrease the relative weight of communications). As the main difficulty for scheduling in actual systems comes from handling efficiently the communications, this new view of the problem allows us to consider them implicitly, thus leading to more tractable problems. We kindly invite the reader to look at the chapter of Maciej Drozdowski (in this book) for a detailed presentation of various kinds of Parallel Tasks in a general context and the survey paper from Feitelson et al. \cite{Feitelsonsurvey} for a discussion in the field of parallel processing. Even if the basic problem of scheduling Parallel Tasks remains NP-hard, some approximation algorithms can be designed. A lot of results have been derived recently for scheduling the different types of Parallel Tasks, namely, Rigid, Moldable or Malleable ones. We will distinguish Parallel Tasks inside the same application or between applications in a multi-user context. Various optimization criteria will be discussed. This chapter aims to present several approximation algorithms for scheduling moldable and malleable tasks with a special emphasis on new execution supports.