Task scheduling with data locality in grids

Author(s)

Marcelo Galvão Póvoa

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2015-04-02

Examining board members

Eduardo Candido Xavier; Daniel Morgato Martin; Flávio Keidi Miyazawa

• Advisor: Eduardo Candido Xavier

Abstract

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 (AU)

• FAPESP's process: 14/02104-0 - Task scheduling with data locality in grids
• Grantee: Marcelo Galvão Póvoa
• Support Opportunities: Scholarships in Brazil - Master