任意可分负载的多轮调度算法

康雨; 闫相国; 郑崇勋; 申广杰

您当前的位置：

首页 >

文章列表页 >

任意可分负载的多轮调度算法

更新时间：2025-07-09

- 任意可分负载的多轮调度算法
- A Multi-Round Scheduling Algorithm of Data-Collection for Divisible Workload
- 西安交通大学学报 2009年43卷第8期页码：125-129
- 作者机构：
  
  西安交通大学生物医学信息工程教育部重点实验室,西安,710049
- 作者简介：
- 基金信息：
  
  : 2008-12-15. 作者简介: 康雨(1979-),男,博士生;闫相国(联系人),男,教授. 基金项目: 陕西省科技发展计划资助项目(2007K04-16)
- DOI：
  中图分类号： TH772.2;R319
- 网络首发：2009-08-10，
  
  纸质出版：2009
- 稿件说明：
移动端阅览
康雨, 闫相国, 郑崇勋, 等. 任意可分负载的多轮调度算法[J]. 西安交通大学学报, 2009,43(8):125-129.

A Multi-Round Scheduling Algorithm of Data-Collection for Divisible Workload[J]. 2009, 43(8): 125-129.
康雨, 闫相国, 郑崇勋, 等. 任意可分负载的多轮调度算法[J]. 西安交通大学学报, 2009,43(8):125-129. DOI：

A Multi-Round Scheduling Algorithm of Data-Collection for Divisible Workload[J]. 2009, 43(8): 125-129. DOI：

摘要

为了提高并行计算中具有负载任意可分特性的大规模应用的任务响应速度

提出了一种针对带传输和计算延迟的三阶段多轮调度模型求解近似最优调度轮数的算法(DCMR).通过对特定的调度时序分析

得出闭合式方程组

然后利用二分法快速搜索并结合回溯调整法求解近似最优调度轮数

使计算时间尽可能多地与传输时间重叠

从而缩短了整个应用的执行时间.算法经仿真表明:在多种参数变化的情况下

可以求解出近似最优的调度方案; 与经典的FIFO和LIFO算法相比具有更强的自适应能力; 在计算时间明显大于传输时间的情况下

能够稳定地保持任务响应时间为理想时间的1.1倍左右.

Abstract

A multi-round scheduling algorithm

data-collection multi-round(DCMR)

is presented to minimize the makespan of divisible workloads in parallel computing. A three-stage model is proposed and takes communication latency and computation start-up time into consideration. The algorithm provides a method to generate a near-optimal number of scheduling rounds. Close-form equations are given through analyzing a specific time sequence of load distribution

and then the bisection method

combined with back-forward adjustment

is used to get an asymptotically optimal number of scheduling rounds

which make the computation time overlap the communication time as much as possible and reduce the makespan. Simulation results show that the algorithm can find a near-optimal number of scheduling rounds under different network parameters. Compared with the classical algorithms such as FIFO and LIFO

the DCMR has higher adaptability. When the computation time dominates the communication time

the algorithm can keep the makespan at a rather low level which is about 1.1 times of the ideal time.

关键词

Keywords

references

康雨, 闫相国, 郑崇勋, 等. 医学可视化网格平台的设计与实现 [J]. 西安交通大学学报, 2007, 41(8): 1000-1002.

KANG Yu, YAN Xiangguo, ZHENG Chongxun, et al. Design and realization for a medical image visualization grid platform [J]. Journal of Xi'an Jiaotong University, 2007, 41(8): 1000-1002

KWANGIL K, ROBERTAZZI T G. Signature search time evaluation in flat file databases [J]. IEEE Trans on Aerospace and Electronic Systems,2008, 44(2): 493-502.

HUNG T G, ROBERTAZZI T G. Scheduling nonlinear computational loads [J]. IEEE Trans on Aerospace and Electronic Systems, 2008, 44(3): 1169-1182.

BHARADWAJ V, GHOSE D, MAN V. Multi-installment load distribution in tree networks with delays[J]. IEEE Trans on Aerospace and Electronic Systems, 1995, 31(2): 555-567.

BHARADWAJ V, GHOSE D, MAN V, et al. Scheduling divisible loads in parallel and distributed systems [M]. Los Alemitos, USA: IEEE Computer Society, 1996.

HAGERUP T. Allocating independent tasks to parallel processors: an experimental study [J]. Journal of Parallel and Distributed Computing, 1996,11(17):1-33.

BEAUMONT O, LEGRAND A, ROBERT Y. Scheduling divisible workloads on heterogeneous platforms[J]. Parallel Computing, 2003, 29(9):1121-1152.

YANG Y, RAADT K, CASANOVA H. Multiround algorithms for scheduling divisible loads[J]. IEEE Trans on Parallel and Distributed Systems, 2005, 16(11): 1092-1102.

赵明宇,张田文. 三段可任意划分负载应用的多次数据分配 [J]. 哈尔滨工业大学学报, 2008, 40(5):745-749.

ZHAO Mingyu, ZHANG Tianwen. A collection-aware multi-round scheduling algorithm [J]. Journal of Harbin Institute of Technology, 2008, 40(5):745-749.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

混合电解槽阵列协同的风光耦合制氢系统双层多目标优化

超临界水异常区域热力学特性研究

冷库水平空气幕热湿阻隔性能数值模拟研究

张角凹坑气膜孔对双层壁气膜冷却特性的影响

扇贝仿生密封腔室内超临界二氧化碳泄漏流湍动能耗散机理研究