Avaliação de algoritmos de escalonamento de tarefas em ambientes heterogêneos e distribuídos baseado em workflows científicos

Abstract

Task scheduling in heterogeneous and distributed environments is a classic (NP-complete) challenge and is fundamental to the optimization of certain systems. In the literature, most analyses of scheduling algorithms are based on synthetic graphs, which can mask bottlenecks, communication patterns, and dependency patterns that are present in real production environments. Based on this, this thesis aims to evaluate the performance of five heuristics (HEFT, IHEFT, PEFT, IPEFT, and DLS) using instances of real scientific workflows (1000genome, BWA, Epigenomics, and Montage). The methodology was based on the development of a simulator that analyzed the heuristics using graphs of different scales and environments with varying numbers of processors (4, 8, 16, and 32). Following the simulation, the results were evaluated using the following metrics: makespan, scheduling length ratio, load balancing, waiting time, and communication cost. The results demonstrate that scheduling efficiency is heavily influenced by the graph topology, the scale of the infrastructure, and the heuristics used by the algorithms. IPEFT stood out for minimizing makespan by protecting the critical path, while PEFT, using its look-ahead strategy, proved highly efficient in managing waiting time and communication cost. On the other hand, algorithms based on non-insertion policies, such as DLS, or on threshold-based processor-switching mechanisms, such as IHEFT, yielded the worst results depending on the graph density. It can be concluded that, although there is no universal solution for all scenarios, approaches that anticipate bottlenecks (look-ahead) or protect critical tasks demonstrate greater adaptability, reinforcing the fact that the development of distributed systems requires a deep understanding of the nature of each problem and application.