A Multi-Round Scheduling Algorithm of Data-Collection for Divisible Workload

您当前的位置：

首页 >

文章列表页 >

A Multi-Round Scheduling Algorithm of Data-Collection for Divisible Workload

更新时间：2025-07-09

- A Multi-Round Scheduling Algorithm of Data-Collection for Divisible Workload
- Vol. 43, Issue 8, Pages: 125-129(2009)
- 作者机构：
  
  西安交通大学生物医学信息工程教育部重点实验室,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  CLC： TH772.2;R319
- Online First：10 August 2009，
  
  Published：2009
- 稿件说明：
移动端阅览
A Multi-Round Scheduling Algorithm of Data-Collection for Divisible Workload[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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Turbulent Kinetic Energy Dissipation Mechanism of Supercritical Carbon Dioxide Leakage Flow in a Scallop Bionic Seal Cavity

A Fast Calculation Method for Thermal Flow Fields in Transformer Windings Based on PI-DeepONet

Review of the Application of EBSILON Software in Combined Heat and Power System Optimization

Diffusion Characteristics and Influencing Factors in Case of Hydrogen Leakage from Fuel Cell Vehicles Running in Tunnels

Numerical Simulation of Heat-Moisture Barrier Performance of a Horizontal Air Curtain in Cold Storage

Related Author

No data

Related Institution

No data

⁰