Efficient Genetic Algorithm Encoding for Large-Scale Multi-Objective Resource Allocation

摘要

Efficiently managing large-scale computing systems presents many challenging problems for system administrators. Such environments often consist of hundreds of thousands of processors, execute workloads with millions of tasks, and consume enormous amounts of energy. These sizes are going to further increase as the first exascale machines come online within the next decade. To effectively utilize such resources (in terms of both performance and energy consumption), it is imperative to design techniques to quickly and intelligently schedule tasks to machines. Further complicating matters is the heterogeneous nature most large-scale systems exhibit. Certain tasks may be more suited to run on certain architectures than others. Future schedulers need to be able to exploit this heterogeneity to produce task/machine mappings that are both energy efficient and achieve high performance. Genetic algorithms have successfully been applied to the task scheduling problem, but most implementations rely on a "task-based" structure that is linearly dependent on the number of tasks in the problem, making them infeasible for large-scale systems. In this paper, a new structure is presented that is highly scalable in terms of problem size, solution quality, and execution time. This new structure is compared to the existing task-based structure using a multi-objective genetic algorithm via a simulation study for a few example systems.