Reinforcement Learning for Optimal Load Distribution Sequencing in Resource-Sharing System

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

Abstract

Divisible Load Theory (DLT) is a powerful tool for modeling divisible load problems in data-intensive systems. This paper studied an optimal divisible load distribution sequencing problem using a machine learning framework. The problem is to decide the optimal sequence to distribute divisible load to processors in order to achieve minimum finishing time. The scheduling is performed in a resource-sharing system where each physical processor is virtualized to multiple virtual processors. A reinforcement learning method called Multi-armed bandit (MAB) is used for our problem. We first provide a naive solution using the MAB algorithm and then several optimizations are performed. Various numerical tests are conducted. Our algorithm shows an increasing performance during the training progress and the global optimum will be achieved when the sample size is large enough.

Introduction

In high-performance computing, the efficient distribution of massive datasets—such as medical imaging sets or signal processing data—is critical. Divisible Load Theory (DLT) provides the mathematical foundation for splitting these loads into chunks for parallel processing. However, traditional DLT models often assume dedicated hardware with static, known speeds. Modern cloud and data center environments rely heavily on virtualization, where a hypervisor manages resources across multiple virtual machines on a single physical processor. This introduces "noise" into the system: background tasks and varying workloads make processor availability unpredictable and time-varying.

The Virtualization Challenge

In a virtualized resource-sharing system, finding the best sequence to send data to processors is no longer a simple deterministic calculation. If data is sent to a slow or heavily loaded processor too early, the entire job is delayed; conversely, sending data to a fast processor too late results in idle resources.

Architecture of a virtualized resource-sharing system where a hypervisor manages multiple virtual processors.

Because the available computation and communication speeds are dynamic, there is no static analytical solution. The system must instead "learn" the environment's characteristics through observation and iterative refinement.

Methodology: Multi-Armed Bandit Framework

The researchers frame this sequencing challenge as a Multi-Armed Bandit (MAB) problem. In this context, each possible sequence of processors is treated as an "arm" of a slot machine, and the "reward" is a minimized finishing time (makespan).

To navigate this, the authors utilized Thompson Sampling (TS), a Bayesian reinforcement learning algorithm that effectively balances exploration (testing new sequences) with exploitation (using known high-performing sequences).

Optimization for Scalability

A significant hurdle in this approach is the search space. For $N$ processors, there are $N!$ (factorial) possible sequences. To make the problem tractable for large clusters, the authors reformulated the parameter space into an $N^2$ weight matrix. This matrix tracks the "fitness" of a specific processor at a specific position in the sequence, reducing computational complexity from factorial to polynomial time. Further optimizations, such as Hill Climbing for local searches and Batch Optimization to prioritize the most sensitive early positions in a sequence, were implemented to accelerate convergence.

Experimental Results and Convergence

The algorithm was tested using numerical simulations of a single-level tree network with added random variables to simulate background noise. The results demonstrate that the system successfully learns to navigate the complex search space.

The algorithm demonstrates a clear downward trend in finishing time as it gathers more samples.

As shown in the performance trials, the finishing time decreases consistently as the MAB algorithm gathers more samples. In time-invariant environments, the algorithm identifies the global optimum within approximately 100 trials. Even in noisy, high-dimensional environments (such as a 20-processor system with $2.4 \times 10^{18}$ possible sequences), the optimized MAB approach significantly outperforms random selection within just a few dozen iterations.

Conclusion

By shifting from deterministic calculations to an iterative learning process, this research provides a robust framework for load balancing in dynamic, virtualized environments. The reformulation of the sequence search space into a positional fitness matrix allows Reinforcement Learning to scale to modern cluster sizes. Future work may explore hybrid approaches combining MAB with Genetic Algorithms to further avoid local optima and adapt the framework to more complex network topologies beyond single-level trees.

Summary updated

Abstract

Divisible Load Theory (DLT) is a powerful tool for modeling divisible load problems in data-intensive systems. This paper studied an optimal divisible load distribution sequencing problem using a machine learning framework. The problem is to decide the optimal sequence to distribute divisible load to processors in order to achieve minimum finishing time. The scheduling is performed in a resource-sharing system where each physical processor is virtualized to multiple virtual processors. A reinforcement learning method called Multi-armed bandit (MAB) is used for our problem. We first provide a naive solution using the MAB algorithm and then several optimizations are performed. Various numerical tests are conducted. Our algorithm shows an increasing performance during the training progress and the global optimum will be acheived when the sample size is large enough.
BibTeX
@misc{wu2019reinforcement,
  author = {Fei Wu and Yang Cao and Thomas G. Robertazzi},
  title = {{Reinforcement Learning for Optimal Load Distribution Sequencing in Resource-Sharing System}},
  year = {2019},
  eprint = {1902.01899},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.01899},
}
Figure