Observations on using genetic algorithms for dynamic load-balancing

TLDR

Load‑balancing partitions programs into concurrent tasks and maps them to processors, and while most research focuses on static heuristic approaches, genetic algorithms have recently emerged as a powerful adaptive search technique for this domain. This study examines the use of a genetic algorithm to address the dynamic load‑balancing problem in parallel computing systems. The authors design a dynamic load‑balancing algorithm that evolves task allocations during runtime, incorporating threshold policies, information‑exchange criteria, and inter‑processor communication. The paper reports how these factors influence the performance of the genetic‑based load‑balancing scheme relative to a first‑fit heuristic.

Abstract

Load-balancing problems arise in many applications, but, most importantly, they play a special role in the operation of parallel and distributed computing systems. Load-balancing deals with partitioning a program into smaller tasks that can be executed concurrently and mapping each of these tasks to a computational resource such as a processor (e.g., in a multiprocessor system) or a computer (e.g., in a computer network). By developing strategies that can map these tasks to processors in a way that balances out the load, the total processing time will be reduced with improved processor utilization. Most of the research on load-balancing focused on static scenarios that, in most of the cases, employ heuristic methods. However, genetic algorithms have gained immense popularity over the last few years as a robust and easily adaptable search technique. The work proposed here investigates how a genetic algorithm can be employed to solve the dynamic load-balancing problem. A dynamic load-balancing algorithm is developed whereby optimal or near-optimal task allocations can "evolve" during the operation of the parallel computing system. The algorithm considers other load-balancing issues such as threshold policies, information exchange criteria, and interprocessor communication. The effects of these and other issues on the success of the genetic-based load-balancing algorithm as compared with the first-fit heuristic are outlined.