Algoritmos para escalonamento de tarefas dependentes representadas por grafos acíclicos direcionados em grades computacionais / Scheduling algorithms for dependent tasks represented by directed acyclic graphs on computational grids
AUTOR(ES)
Luiz Fernando Bittencourt
DATA DE PUBLICAÇÃO
2010
RESUMO
Computational grids are potentially large distributed systems composed of heterogeneous resources connected by a network with heterogeneous links. These systems became largely used in the execution of tasks which require large processing capacities. Because they are shared systems, task submission in grids independently originate from a number of users, leading to a concurrent demand over the computational resources, which must be managed by the grid middleware. The scheduler is the component responsible for deciding how the distribution of such tasks will occur, and it must deal with peculiarities of this environment, such as the heterogeneity and dynamic behavior of the resources, with variations in both quality and quantity. The objective function usually adopted in task scheduling is makespan minimization, which means that the scheduler tries to minimize the finish time of the tasks being scheduled. Among the tasks executed in grids we can find independent tasks, which execute without communication among them, and dependent tasks, which have data dependencies that yield in precedence constraints and are frequently modeled as directed acyclic graphs (DAGs). Among the applications composed of dependent tasks, e-Science DAGs are distinguished because of their complexity and increasing demand for computational resources. Additionally, the task scheduling problem, in its general form, is NP-Complete. Therefore, the study of scheduling of dependent tasks represented by directed acyclic graphs in computational grids is important to improve the execution of scientific applications in many areas of knowledge. In this thesis we present algorithms for four types of problems related to the DAG scheduling in grids: static scheduling of DAGs, dynamic scheduling of DAGs, bi-criteria scheduling, and scheduling of multiple DAGs. We present evaluations of the makespan generated by the algorithms after the initial scheduling and after the execution of the tasks with simulated external load in the resources
ASSUNTO(S)
workflow sistemas distribuidos computação em grade (sistemas de computador) escalonamento de produção fluxo de trabalho distributed systems computational grids (computer systems) scheduling
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=000771315Documentos Relacionados
- Comparative Study of Task Dependent Scheduling Algorithms to Grid Computing
- Algoritmos para problemas de escalonamento em grades
- Escalonamento em grids computacionais: estudo de caso
- Modelos computacionais para o escalonamento de tarefas em redes de dutos
- Algoritmos para problemas de grafos com incertezas