单层树型网格下独立任务的周期性调度
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

“核高基”国家科技重大专项(2012ZX01039-004-03-2);广东省教育部产学研合作专项(2012B091100420)


Scheduling Periodic Independent Tasks on Single-Level Tree Grid
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    提出单层树型网格下单位独立任务的周期性调度方法,单位独立任务是大小相等的独立任务.首先,为单层树型网格下的单位独立任务调度建立线性规划模型,通过分析整数线性规划求解过程,发现一个单层树型网格平台在节点构成不同时,分别具有非饱和态、临界态或冗余态特征;并且,随着网格节点上任务数的增多,线性规划最优解呈线性增长,任务调度具有周期性特性.据此给出非饱和态、临界态或冗余态网格的定义、性质和判定方法,推导出单位独立任务调度的周期长度.最后,分析了周期性调度的时间复杂性,提出一种周期性调度算法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.

    参考文献
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2011-10-18
  • 最后修改日期:2012-04-01
  • 录用日期:
  • 在线发布日期: 2013-02-02
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号