Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Approximation algorithms and heuristics for task scheduling in data-intensive distributed systems

Texto completo
Autor(es):
Povoa, Marcelo G. [1, 2] ; Xavier, Eduardo C. [1]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Ave Albert Einstein 1251, BR-13083852 Campinas, SP - Brazil
[2] Google, Ave Andradas 3000, BR-30260070 Belo Hozitonte - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: International Transactions in Operational Research; v. 25, n. 5, p. 1417-1441, SEP 2018.
Citações Web of Science: 0
Resumo

In this work, we are interested in the problem of task scheduling on large-scale data-intensive computing systems. In order to achieve good performance, one must construct not only good task schedules but also good data allocation across nodes on the system, since before a task can be executed, it must have access to data distributed on the system. In this article, we present a general formulation of a static problem that combines both scheduling and replication problems in data-intensive distributed systems. We show that this problem does not admit an approximation algorithm. However, considering a restricted version of the problem that considers some practical constraints, an approximation algorithm can be designed. From a practical perspective, we introduce a novel heuristic for the problem that is based on nodes clustering. We compare the heuristic with two adapted approaches from other works in the literature by computational simulations using an extensive set of instances based on real computer grids. We show that our heuristic often obtains the best solutions and also runs faster than other approaches. (AU)

Processo FAPESP: 16/23552-7 - Problemas de corte e empacotamento: abordagens práticas e teóricas
Beneficiário:Rafael Crivellari Saliba Schouery
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 14/02104-0 - Escalonamento de tarefas com localidade de dados em grids
Beneficiário:Marcelo Galvão Póvoa
Linha de fomento: Bolsas no Brasil - Mestrado
Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Temático