| Full text | |
| Author(s): |
Total Authors: 2
|
| Affiliation: | [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
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | International Transactions in Operational Research; v. 25, n. 5, p. 1417-1441, SEP 2018. |
| Web of Science Citations: | 0 |
| Abstract | |
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) | |
| FAPESP's process: | 16/23552-7 - Cutting and Packing Problems: Practical and Theoretical Approaches |
| Grantee: | Rafael Crivellari Saliba Schouery |
| Support Opportunities: | Regular Research Grants |
| 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 |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |