###
Journal of Software:2013.24(2):378-390

单层树型网格下独立任务的周期性调度
王振宇,李照瑜
(华南理工大学 软件学院,广东 广州 510006;华南理工大学 计算机科学与工程学院,广东 广州 510006)
Scheduling Periodic Independent Tasks on Single-Level Tree Grid
WANG Zhen-Yu,LI Zhao-Yu
(School of Software Engineering, South China University of Technology, Guangzhou 510006, China;School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2334   Download 2648
Received:October 18, 2011    Revised:April 01, 2012
> 中文摘要: 提出单层树型网格下单位独立任务的周期性调度方法,单位独立任务是大小相等的独立任务.首先,为单层树型网格下的单位独立任务调度建立线性规划模型,通过分析整数线性规划求解过程,发现一个单层树型网格平台在节点构成不同时,分别具有非饱和态、临界态或冗余态特征;并且,随着网格节点上任务数的增多,线性规划最优解呈线性增长,任务调度具有周期性特性.据此给出非饱和态、临界态或冗余态网格的定义、性质和判定方法,推导出单位独立任务调度的周期长度.最后,分析了周期性调度的时间复杂性,提出一种周期性调度算法Periodic-Sched.实验结果表明,周期性调度是有效的.单位独立任务的周期性调度将大规模的任务调度问题简化为一个周期内的任务调度,降低了调度问题的复杂度.该调度方法适用于对Hadoop平台的Map任务进行调度.
Abstract:This paper suggests that the periodic scheduling of identical independent tasks on a single-level tree grid and identical independent tasks are independent tasks in the same size in computation. First, an integer linear programming model for scheduling identical independent tasks is presented. By analyzing the procedure of solving the linear programming model, and obtaining the optimal number of tasks assigned to each computing node, the study finds that a single-level tree grid composed of different nodes will be in one of three states, respectively: unsaturated, critical, and redundant states. Furthermore, the optimal number of tasks assigned to each node increases linearly as the number of tasks arriving to the master grows, and the periodic feature appears in the task scheduling. Next, some features and theories that determine the states of grid systems among unsaturated, critical, and redundant states are obtained, periodic scheduling of identical independent tasks on single-level grid is proposed, the length of period is derived. Their computational complexity is also analyzed, and a periodic scheduling algorithm, Periodic-Sched, is given. Both the theory and experiments have proved that the periodic scheduling is feasible. In this way, the problem of large-scale independent task scheduling is simplified and resolved in one period, which reduces the computational complexity dramatically. The periodic scheduling of independent tasks is suitable for Map tasks scheduling on Hadoop platform.
文章编号:     中图分类号:    文献标志码:
基金项目:“核高基”国家科技重大专项(2012ZX01039-004-03-2);广东省教育部产学研合作专项(2012B091100420) “核高基”国家科技重大专项(2012ZX01039-004-03-2);广东省教育部产学研合作专项(2012B091100420)
Foundation items:
Reference text:

王振宇,李照瑜.单层树型网格下独立任务的周期性调度.软件学报,2013,24(2):378-390

WANG Zhen-Yu,LI Zhao-Yu.Scheduling Periodic Independent Tasks on Single-Level Tree Grid.Journal of Software,2013,24(2):378-390