Metaheuristic Based Scheduling Meta-Tasks in Distributed Heterogeneous Computing Systems

Hesam Izakian, Ajith Abraham, Václav SnáselSensors 2009 · DOI

TL;DR

This paper tackles the NP-complete problem of scheduling independent tasks onto distributed heterogeneous computing systems to minimize the overall completion time (makespan). The authors propose a novel metaheuristic approach by combining Particle Swarm Optimization (PSO) with a problem-specific heuristic, demonstrating improved efficiency and reduced makespan compared to existing Genetic Algorithm (GA) and standard PSO methods.

What Problem Does This Paper Address?

Distributed heterogeneous computing (HC) systems, composed of diverse high-performance machines connected by networks, offer immense computational power. However, effectively utilizing this power for computationally intensive applications is a significant challenge, primarily due to the complexity of the scheduling problem. Scheduling involves assigning tasks to resources to optimize performance. For independent tasks in HC systems, this problem is NP-complete, meaning that finding the absolute optimal solution becomes computationally infeasible as the problem size grows. This necessitates the use of heuristic and metaheuristic approaches that can find near-optimal solutions efficiently. The specific challenge addressed here is the "meta-task scheduling" problem, which deals with allocating a set of independent tasks from various users to a pool of computing resources, aiming to minimize the makespan – the time when the last task finishes.

Methods

The core of this paper is the development of a modified Particle Swarm Optimization (PSO) algorithm for meta-task scheduling. Standard PSO is a population-based search algorithm inspired by social behavior like bird flocking. Particles (potential solutions) move through a search space, updating their positions based on their own best-found position and the best-found position of their neighbors.

The authors introduce two key modifications to the standard PSO for this specific problem:

  • Particle Encoding: Each particle's position is represented by an n-dimensional vector, where 'n' is the number of tasks. Each dimension corresponds to a task, and its value indicates the machine to which that task is assigned. This is a natural number within the range of available machines.
  • Velocity Update and Heuristic Integration: The velocity update mechanism is adapted, and crucially, a heuristic function, denoted by 'η', is incorporated. This heuristic biases the search towards more attractive solutions and is problem-dependent. Specifically, 'η' is inversely proportional to the estimated completion time of a task on a machine, encouraging assignments to faster machines. The probability of assigning a task to a machine is calculated using this heuristic and the particle's velocity, followed by a selection mechanism (roulette wheel or direct selection based on a probability threshold).

The fitness of a solution (particle) is defined as the inverse of the makespan, meaning a lower makespan results in a higher fitness.

Datasets

The paper uses a benchmark dataset for simulating HC environments, originally proposed in [14]. This benchmark consists of 512 tasks and 16 machines, with the expected time to compute (ETC) matrix classified into 12 types based on task heterogeneity, machine heterogeneity, and consistency. These classifications are denoted by labels like "u-c-hi-hi" (uniform distribution, consistent, high task heterogeneity, high machine heterogeneity). No new datasets were introduced.

Key Insights and Ideas

  • Heuristic Integration is Key: The most significant insight is that incorporating a problem-specific heuristic (η) into the PSO velocity update and position selection process dramatically improves performance. This heuristic effectively guides the search towards better solutions by prioritizing faster machine assignments.
  • PSO's Adaptability: PSO proves to be a flexible metaheuristic that can be adapted to complex scheduling problems by carefully designing particle encoding and velocity update mechanisms.
  • Makespan Minimization is Achievable: The proposed method demonstrates that even for NP-complete scheduling problems, metaheuristics can achieve substantial reductions in makespan, making large-scale distributed systems more practical.
  • Trade-off in Convergence: While the proposed method shows excellent results, the paper hints at a potential trade-off between convergence speed and the number of tasks. For very large task sets, GA might become more efficient in terms of convergence time.

Key Results

The proposed PSO-based scheduler was compared against a Genetic Algorithm (GA) [14] and a continuous PSO [25].

  • Scenario (a) - Random Initialization: In all tested instances, the proposed PSO approach achieved the best results, yielding the lowest makespans. The paper highlights a "large amount of reduction in makespan" due to the heuristic.
  • Scenario (b) - Min-min Initialization: The proposed method also surpassed other methods in most instances, except for those with low heterogeneity in tasks and machines, where the min-min heuristic itself performed well.
  • Standard Deviation: The proposed method consistently showed the lowest standard deviation across scenarios (a) and (b), indicating more stable and reliable performance across multiple runs.
  • Convergence Time: For most cases, the proposed method achieved convergence in the lowest CPU time. However, for a large number of tasks (1024), the GA scheduler required less time for convergence.

Limitations and Future Work

  • Limitations:
    • The paper notes that for a very large number of tasks (1024), the GA scheduler exhibited faster convergence time than the proposed method. This suggests a potential scalability issue in terms of convergence speed for extremely large problem instances.
  • While the min-min heuristic initialization improved performance in scenario (b), the proposed method still struggled in instances with low heterogeneity.
  • Future Work:
    • The authors plan to extend the proposed method to address multi-objective optimization, specifically minimizing both makespan and flowtime simultaneously. This would involve formulating the problem as a multi-objective optimization task.

Summary updated

BibTeX
@article{izakian2009metaheuristic,
  author = {Hesam Izakian and Ajith Abraham and Václav Snásel},
  title = {{Metaheuristic Based Scheduling Meta-Tasks in Distributed Heterogeneous Computing Systems}},
  journal = {Sensors},
  year = {2009},
  doi = {10.3390/s90705339},
}
Figure