A Periodical Multi-Installment Scheduling Model and Algorithm for Divisible Loads in Distributed Computing Systems

doi:10.7652/xjtuxb201808013

您当前的位置：

首页 >

文章列表页 >

A Periodical Multi-Installment Scheduling Model and Algorithm for Divisible Loads in Distributed Computing Systems

更新时间：2025-07-09

- A Periodical Multi-Installment Scheduling Model and Algorithm for Divisible Loads in Distributed Computing Systems
- Vol. 52, Issue 8, Pages: 80-86(2018)
- 作者机构：
  
  1. 周口师范学院网络工程学院,河南,周口,466001
  2. 西安电子科技大学计算机学院,西安,710071
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201808013
  CLC： TP338.8
- Online First：10 August 2018，
  
  Published：2018
- 稿件说明：
移动端阅览
A Periodical Multi-Installment Scheduling Model and Algorithm for Divisible Loads in Distributed Computing Systems[J]. 2018, 52(8): 80-86.
DOI：

A Periodical Multi-Installment Scheduling Model and Algorithm for Divisible Loads in Distributed Computing Systems[J]. 2018, 52(8): 80-86. DOI： 10.7652/xjtuxb201808013.

摘要

针对已有单趟任务调度模型因无法充分利用分布式平台的并行特性导致系统利用率和任务完成效率较低的问题

提出了一种新的周期性多趟任务调度优化模型。在给定处理机调度顺序的情况下

推导得到了分布式系统最优任务分配方案的解析解; 通过分析任务完成时间关于调度趟数和服务器数的变化曲线

设计了一种启发式算法寻求最优的调度趟数和参与计算的服务器数; 为了获得最优的服务器调度顺序

提出了一种高效的全局优化进化算法。实验结果表明:与已有调度算法相比

所提算法能够在分布式平台下最小化任务的完成时间

对于小规模和大规模任务

任务完成时间分别降低了至少25%和43%。

Abstract

A new periodical multi-installment task-scheduling model is proposed to solve the problem that the existing single-installment task-scheduling models could not take full advantage of the parallel characteristics of distributed platforms

which results in low system utilization and inefficiency of task computation. A closed-form of the solution for an optimal load distribution strategy is firstly derived for a given scheduling sequence of servers. Then

a heuristic algorithm to find optimal numbers of installments and servers involved in workload computation is designed by analyzing the function of finish time with respect to the numbers of installments and servers. An efficient global optimization evolutionary algorithm is proposed to obtain an optimal scheduling sequence of servers. Experiment results and comparisons with existing scheduling algorithms show that the proposed algorithms obtain a minimum finish time of tasks under distributed computing systems. As for relatively small workloads

the proposed algorithm can reduce the finish time of workloads by at least 25% and 43% for relatively small workloads and large-scale workloads

respectively.

关键词

Keywords

references

孙健, 张兴军, 董小社. 异构系统中带可用性约束的性能优化调度算法 [J]. 西安交通大学学报, 2018, 52(2): 18-23.

SUN Jian, ZHANG Xingjun, DONG Xiaoshe, A performance optimization scheduling strategy with availability constraints for heterogeneous systems [J]. Journal of Xi'an Jiaotong University, 2018, 52(2): 18-23.

IYER G N, VEERAVALLI B, KRISHNAMOORTHY S G. On handling large-scale polynomial multiplications in compute cloud environments using divisible load paradigm [J]. IEEE Transactions on Aerospace Electronic Systems, 2012, 48(1): 820-831.

MILLOT D, PARROT C. Optimization of the processing of data streams on roughly characterized distributed resources [J]. IEEE Transactions on Parallel Distributed Systems, 2016, 27(5): 1415-1429.

赖俊凡, 王宇平, 王晓丽. 考虑处理机时间窗口的可分任务调度优化模型 [J]. 西安交通大学学报, 2017, 51(9): 118-124.

LAI Junfan, WANG Yuping, WANG Xiaoli, An optimization model for divisible-load scheduling considering processor time-window [J]. Journal of Xi'an Jiaotong University, 2017, 51(9): 118-124.

GHANBARI S, OTHMAN M, BAKAR M R A, et al. Multi-objective method for divisible load scheduling in multi-level tree network [J]. Future Generation Computer Systems, 2016, 54(C): 132-143.

ZHANG Z, ROBERTAZZI T G. Scheduling divisible loads in Gaussian, mesh and torus network of processors [J]. IEEE Transactions on Computers, 2015, 64(11): 3249-3264.

SINGH S, CHANA I. Cloud resource provisioning: survey, status and future research directions [J]. Knowledge Information Systems, 2016, 49(3): 1-65.

CHEN C Y, CHU C P. A novel computational model for non-linear divisible loads on a linear network [J]. IEEE Transactions on Computers, 2016, 65(1): 53-65.

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

BRAND(～overA)O J S, NORONHA T F, RESENDE M G C, et al. A biased random-key genetic algorithm for scheduling heterogeneous multi-round systems [J]. International Transactions in Operational Research, 2017, 24(5): 1061-1077.

CHANG Y K, WU J H, CHEN C Y, et al. Improved methods for divisible load distribution on k-dimensional meshes using multi-installment [J]. IEEE Transactions on Parallel Distributed Systems, 2007, 18(11): 1618-1629.

CHEN C Y, CHU C P. Novel methods for divisible load distribution with start-up costs on a complete b-ary tree [J]. IEEE Transactions on Parallel Distributed Systems, 2015, 26(10): 2836-2848.

ZHAO T, JING M. Bandwidth-aware multi round task scheduling algorithm for cloud computing [J]. Journal of Intelligent Fuzzy Systems, 2016, 31(2): 1053-1063.

SURESH S, HUANG H, KIM H J. Hybrid real-coded genetic algorithm for data partitioning in multi-round load distribution and scheduling in heterogeneous systems [J]. Applied Soft Computing, 2014, 24(C): 500-510.

YANG Y, RAADT K V D, CASANOVA H. Multi round algorithms for scheduling divisible loads [J]. IEEE Transactions on Parallel Distributed Systems, 2005, 16(11): 1092-1102.

SHOKRIPOUR A, OTHMAN M, IBRAHIM H, et al. A method for scheduling heterogeneous multi-installment systems [J]. Future Generation Computer Systems, 2012, 28(8): 1205-1216.

HSU C H, CHEN T L, PARK J H. On improving resource utilization and system throughput of master slave job scheduling in heterogeneous systems [J]. Journal of Supercomputing, 2008, 45(1): 129-150.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Pareto Optimality Based Genetic Algorithm in Web Services Composition

Global Optimization Method of the Design for Multi-Layer Planar Inductors

Global Optimization Algorithm Based on Lagrangian Dual

Integrated Intelligent Algorithms for Global Optimization

Profiling Based Optimization Method for CPU-GPU Heterogeneous Parallel Processing System

Related Author

赵晓昳 1

张星 1

符锐 1

董渭清 1

胡焕耀 1

耿莉

邵志标

Related Institution

西安交通大学电子与信息工程学院

中兴通讯股份有限公司上海研发中心

School of Electronics and Information Engineering, Xi'an Jiaotong University

School of Sciences, Xi'an Jiaotong University

School of Mechanical Engineering, Xi'an Jiaotong University

⁰