Optimal Divisible Load Scheduling for Resource-Sharing Network

Fei Wu, Yang Cao, Thomas G. RobertazziarXiv 2019 · DOI · arXiv

Abstract: Scheduling is an important task allowing parallel systems to perform efficiently and reliably. For modern computation systems, divisible load is a special type of data which can be divided into arbitrary sizes and independently processed in parallel. Such loads are commonly encountered in applications which are processing a great amount of similar data units. For a multi-task processor, the processor's speed may be time-varying due to the arrival and departure of other background jobs. This paper studies an optimal divisible loads scheduling problem on a single level tree network, whose processing speeds and channel speeds are time-varying. Two recursive algorithms are provided to solve this problem when the arrival and departure times of the background jobs are known a priori and an iterative algorithm is provided to solve the case where such times are not known. Numerical tests and evaluations are performed for these three algorithms under different numbers of background jobs and processors.

Introduction

Modern parallel computing systems, such as virtualized cloud clusters, 5G network slices, and Wireless Sensor Networks, operate in dynamic environments where resources are shared among multiple users and background tasks. In these "resource-sharing" networks, the available processing power and communication bandwidth for a specific task fluctuate over time as background jobs arrive and depart. Traditional Divisible Load Theory (DLT) often assumes constant speeds, which fails to capture the realities of these systems. This paper addresses the challenge of optimally partitioning a large divisible load—data that can be split into arbitrary sizes—across a single-level tree network to minimize the total processing time (makespan) despite these fluctuations.

System Model and Problem Formulation

The study focuses on a single-level tree network consisting of one controller ($P_0$) and $N$ worker processors ($P_1, \dots, P_N$).

Single-level tree network topology.

The core objective is to determine the optimal load distribution such that all processors finish their assigned tasks simultaneously at time $T_f$. This condition is a fundamental property of an optimal DLT schedule. The authors explicitly model the impact of background jobs using a hypervisor logic, where a physical processor's total capacity is shared among multiple virtual machines.

Methodology

The authors propose solutions for both deterministic and stochastic environments.

Deterministic Analysis

When the arrival and departure times of background jobs are known in advance, the time-varying speeds can be mathematically transformed into equivalent constant values. This is achieved by integrating the inverse of the speed over the processing interval. Two recursive algorithms are developed:

  • Algorithm 1: Handles systems where only worker speeds vary.
  • Algorithm 2: Addresses scenarios where the controller, workers, and communication links all exhibit time-varying speeds.
Timing diagram for divisible load scheduling with time-varying speeds and equivalent constant values.

Stochastic Analysis

In unpredictable environments, background jobs are modeled as an M/M/1 queueing system (Poisson arrivals and exponential stay times). To solve this, the authors introduce:

  • Algorithm 3 (Simulation-based): Uses Monte Carlo simulations to estimate the statistical median finishing time.
  • Algorithm 4 (Iterative): A more efficient approach that iteratively refines equivalent speed estimates to converge on an optimal schedule without exhaustive simulation.

Results and Discussion

Numerical simulations were conducted to evaluate the proposed algorithms across various cluster sizes (3 to 14 workers) and background noise levels. Key findings include:

  • Computational Efficiency: The Iterative Algorithm (Alg 4) demonstrated significant speedups over the simulation-based approach. For a 15-processor system, it required only 182–267 seconds, compared to over 2,200 seconds for simulation, while maintaining high accuracy.
  • Impact of Parallelism: Parallelism provides a more pronounced "speedup" benefit in congested systems compared to idle ones.
  • Model Accuracy: The new stochastic approach outperformed previous models by accounting for the initial state of processors (the number of existing background jobs), leading to more precise scheduling.

Conclusion

This research provides a robust framework for divisible load scheduling in dynamic, resource-sharing networks. By introducing the "equivalent invariant" principle, the authors simplify complex time-varying problems into manageable constant-speed equivalents. Future work will explore extending these algorithms to multi-level tree and mesh topologies, as well as handling non-Poisson background job distributions.

Summary updated

Abstract

Scheduling is an important task allowing parallel systems to perform efficiently and reliably. For modern computation systems, divisible load is a special type of data which can be divided into arbitrary sizes and independently processed in parallel. Such loads are commonly encountered in applications which are processing a great amount of similar data units. For a multi-task processor, the processor's speed may be time-varying due to the arrival and departure of other background jobs. This paper studies an optimal divisible loads scheduling problem on a single level tree network, whose processing speeds and channel speeds are time-varying. Two recursive algorithms are provided to solve this problem when the arrival and departure times of the background jobs are known a priori and an iterative algorithm is provided to solve the case where such times are not known. Numerical tests and evaluations are performed for these three algorithms under different numbers of background jobs and processors.
BibTeX
@misc{wu2019optimal,
  author = {Fei Wu and Yang Cao and Thomas G. Robertazzi},
  title = {{Optimal Divisible Load Scheduling for Resource-Sharing Network}},
  year = {2019},
  eprint = {1902.01898},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.01898},
}
Figure