Task scheduling with data locality in grids

Sistemas computacionais conhecidos como Data Grids fornecem uma infraestrutura computacional distribuída para processamento e armazenamento de dados, com várias aplicações envolvendo computação em larga escala. Devido ao uso de um grande volume de dados, é necessário não apenas um escalonamento eficiente de tarefas, mas também uma distribuição inteligente de réplicas dos dados para se atingir o melhor desempenho. Esses dois problemas já foram extensivamente estudados de forma independente na literatura, mas estamos concentrados em um formulação integrada em um problema estático, de forma a otimizar uma única função objetivo. Primeiramente, mostramos que este problema não pode admitir um algoritmo aproximado. Porém, considerando uma versão restrita do problema, apresentamos um algoritmo aproximado original com fator de aproximação constante. Também fazemos um estudo de algoritmos aproximados para problemas relacionados disponíveis na literatura. Sob um aspecto mais prático, introduzimos duas heurísticas originais para o problema. A primeira é baseada no agrupamento de máquinas próximas em clusters, enquanto a segunda procura identificar grupos de dados frequentemente acessados em conjunto. Comparamos esses algoritmos com duas abordagens adaptadas da literatura, através de simulações computacionais em um grande conjunto de instâncias baseadas em grids reais. Mostramos que nossa primeira heurística costuma obter melhores soluções que as outras com boa eficiência de tempo, enquanto a segunda heurística é ainda mais rápida e ainda obtém soluções competitivas.Computational systems known as Data Grids provide a flexible, distributed computing infrastructure for processing and storage and has many applications in large-scale computing. Due to the use of great amounts of data, not only efficient task scheduling but also thorough file replication are crucial for achieving the best performance. Both these problems have already been studied independently in the literature, but we are interested in a combined formulation as a static problem, in order to minimize a single objective function. First, we show that this problem does not admit an approximation algorithm. However, considering a restricted version of the problem, we provide a constant ratio approximation algorithm. We also conduct a study of approximation algorithms for related problems avaliable in the literature. On a more practical side, we introduce two novel heuristics for the problem. The first is based on grouping neighbor nodes into clusters, while the second tries to identify groups of files frequently accessed together. We compare these algorithms with two adapted approaches from other works in the literature by doing computational simulations using an extensive set of instances based on real grids. We show that our first heuristic often obtains the best solutions with good time efficiency, while the second is even faster and still provides competitive solutions