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.)

Generic algorithms for scheduling applications on heterogeneous platforms

Texto completo
Autor(es):
Amaris, Marcos [1, 2] ; Lucarelli, Giorgio [2] ; Mommessin, Clement [2] ; Trystram, Denis [2]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Inst Math & Stat, Sao Paulo - Brazil
[2] Univ Grenoble Alpes, CNRS, INRIA, Grenoble INP, LIG, Grenoble - France
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE; v. 31, n. 15 AUG 10 2019.
Citações Web of Science: 0
Resumo

We study the problem of executing an application represented by a precedence task graph on a parallel machine composed of standard computing cores and accelerators. Both off-line and on-line settings are addressed by proposing generic scheduling approaches. In the first case, we establish strong lower bounds on the worst-case performance of a known approach based on Linear Programming and replace the greedy List Scheduling policy used in this approach by a better task ordering. Although this modification leads to the same approximability guarantees, it performs much better in practice. We also extend this algorithm to more types of computing units, achieving an approximation ratio which depends on the number of different types. In the on-line case, tasks arrive in any order which respects the precedence relations and the scheduler has to take irrevocable decisions about their allocation and execution. We propose the first on-line scheduling algorithm taking into account precedences, which is based on adequate rules for selecting the type of processor where to allocate the tasks. Finally, all the previous algorithms have been experimented on a large number of simulations built on actual libraries, assessing their good practical behavior with respect to the state-of-the-art solutions and baseline algorithms. (AU)

Processo FAPESP: 12/23300-7 - Modelo BSP em Placas Gráficas
Beneficiário:Marcos Tulio Amaris González
Modalidade de apoio: Bolsas no Brasil - Doutorado