Algoritmos para escalonamento de tarefas em plataformas heterogêneas usando o paradigma mestre-escravo

  • Fabio Henrique Nishihara USP
  • Alfredo Goldman USP

Resumo


Neste trabalho abordamos o problema de escalonar tarefas independentes e de mesmo tamanho em uma plataforma heterogênea, onde os tempos de comunicação e de processamento são diferentes. Propomos algoritmos para escalonar tarefas usando o paradigma mestre-escravo em diversos tipos de rede que são casos especiais de uma grade heterogênea. Desta forma estendemos os trabalhos anteriores para plataformas heterogêneas. Através de simulações analisamos o desempenho dos algoritmos propostos em diferentes situações.

Referências

Entropia. URL: http://www.entropia.com.

Mersenne prime search. URL: http://www.mersenne.org.

Seti at home. URL: http://setiathome.ssl.berkeley.edu.

S. Bataineh, T. Hsiung, and T. Robertazzi. Closed form solutions for bus and tree networks of processors load sharing a divisible job. IEEE Transactions on Computers, 43(10):1184-1196, 1994.

O. Beaumont, L. Carter, A. Legrand, and Y. Robert. Bandwidth-centric allocation of indepedent tasks on heterogeneous plataform. lnternacional Parallel and Distributed Processing Symposium, 2002.

S. Charcranoon, T. Robertazzi, and S. Luryi. Optimizing computing costs using divisible load analysis. IEEE Transactions on Computers, 49(9):987-991, 2000.

Y. Cheng and T. Robertazzi. Distributed computation for a tree network with communication delays. IEEE Transactions on Aerospace and Eletronic Systems, 24(6):700-712, 1988.

J. Cowie, B. Dodson, R. M. Elkenbracht-Huizing, A. K. Lenstra, P. L. Montgomery, and J. Zayer. A world wide number field sieve factoring record: On to 512 bits. Advances in Cryptology-ASIACRYPT'96, 11 63:382-394, 1996.

P.-F. Dutot. Master-slave tasking on heterogeneous processors. lntemational Parallel and Distributed Processing Symposium, 2003.

J. Y.-T. Leung. Handbook of Scheduling: Algorithms, Modeis, and Performance Analysis. CRC Press, 2004.

K. Li. Scheduling divisible task on heterogeneous linear arrays with applications to layered networks. Workshop on Parallel and Distributed Scientific and Engineering Computing with Applicalion, 2002.

F. H. Nishihara. Algoritmos para escalonamento de tarefas em plataformas heterogêneas usando o paradigma mestre-escravo. Master's thesis, Universidade de São Paulo, 2008.

J. Sohn, T. Robertazzi, and S. Luryi. Optimizing computing costs using divisible load analysis. IEEE Transactions.
Publicado
29/10/2008
NISHIHARA, Fabio Henrique; GOLDMAN, Alfredo. Algoritmos para escalonamento de tarefas em plataformas heterogêneas usando o paradigma mestre-escravo. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 9. , 2008, Campo Grande. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2008 . p. 125-132. DOI: https://doi.org/10.5753/wscad.2008.17676.