Uma Comparação da Eficiência de Duas Heurísticas para Alocação Estática de Processos
Resumo
Neste trabalho apresentamos os resultados da implementação de dois algoritmos heurísticos para alocação estática de processos em arquiteturas paralelas. Comparamos a eficiência das alocações geradas pelos algoritmo segundo o tempo gasto com execução por cada processador e o volume de comunicação realizada entre diferentes processadores. Analisamos, também, o efeito do balanceamento de carga nas referidas alocações. Nos experimentos realizados apontamos falhas nas duas heurísticas e sugerimos possíveis melhoras.
Referências
Bokhari, S.H., "On the Mapping Problem", IEEE Transactions On Computers, Vol C-30, March 1981, pp 207-214.
Bokhari, S.H., "Partioning Problems in Parallel, Pipelined and Distributed Computing", IEEE Transactions on Computers, Vol 37, January 1988, pp 48-57.
Bowen, N.S., Nikolau, C.N., Ghafoor, A., "On The Assignment Problem of Arbitrary Process Systems to Heterogeneous Distributed Computer Systems", IEEE Transactions on Computers, Vol 41, March 1992, pp 257-273.
Canaley, L.M.M.B, Alocação de Tarefas em Sistemas Distribuídos, Tese de Mestrado COPPE-UFRJ, Abril 1993.
Chu, W.W., Holloway, L.J., Lan, M.T., Efe, K., "Task Allocation in Distributed Data Processing", IEEE Transactions on Computers, Vol C-30, November 1988, pp57-70.
Gupta, A., Tucker, A. and Urushibara, S., "The Impact of Operating System Scheduling Policies and Synchronization Methods on the Performance of Parallel Applications", Proceedings of the 1991 ACM SIGMETRICS Conference On Measurements and Modeling of Computer Systems, May 1991, San Diego, CA, pp143-155.
Kim S.J., A General Approach to Multiprocessor Scheduling, PhD. Thesis, The University of Texas at Austin, December 1988.
Lee,S-Y and Aggarwal, J.K., "A Mapping Strategy for Parallel Processing", IEEE Transactions on Computers, Vol C-36, April 1987, pp 433-442.
Lo, V.M., "Heuristic Algorithms for Task Assignment in Distributed Systems", IEEE Transactions on Computers, Vol 37, November 1988, pp 1384-1397.
Markatos, E.P. and LeBlanc, T.J., "Load balancing vs. Locality Management in Shared Memory Multiprocessors", Technical Report 399, University of Rochester, October 1991.
Shirazi, B. and Wang,M.,"Analysis and Evaluation of Heuristic Methods for Static Scheduling", Journal of Parallel and Distributed Computing, Vol 10, 1990, pp 222-232.
Squillance,M.S. and Nelson, R.D., "Analysis of Task Migration in Shared Memory Multiprocessor Scheduling", Proceedings of the 1991 ACM SIGMETRICS Conference On Measurements and Modeling of Computer Systems, May 1991, San Diego, CA, pp 143-155.
Stone H.S.,"Multiprocessor Scheduling with the Aid of Network Flow Algorithms", IEEE-SE, Vol SE-3, No 1, January 1977, pp 85-93.
Bokhari, S.H., "Partioning Problems in Parallel, Pipelined and Distributed Computing", IEEE Transactions on Computers, Vol 37, January 1988, pp 48-57.
Bowen, N.S., Nikolau, C.N., Ghafoor, A., "On The Assignment Problem of Arbitrary Process Systems to Heterogeneous Distributed Computer Systems", IEEE Transactions on Computers, Vol 41, March 1992, pp 257-273.
Canaley, L.M.M.B, Alocação de Tarefas em Sistemas Distribuídos, Tese de Mestrado COPPE-UFRJ, Abril 1993.
Chu, W.W., Holloway, L.J., Lan, M.T., Efe, K., "Task Allocation in Distributed Data Processing", IEEE Transactions on Computers, Vol C-30, November 1988, pp57-70.
Gupta, A., Tucker, A. and Urushibara, S., "The Impact of Operating System Scheduling Policies and Synchronization Methods on the Performance of Parallel Applications", Proceedings of the 1991 ACM SIGMETRICS Conference On Measurements and Modeling of Computer Systems, May 1991, San Diego, CA, pp143-155.
Kim S.J., A General Approach to Multiprocessor Scheduling, PhD. Thesis, The University of Texas at Austin, December 1988.
Lee,S-Y and Aggarwal, J.K., "A Mapping Strategy for Parallel Processing", IEEE Transactions on Computers, Vol C-36, April 1987, pp 433-442.
Lo, V.M., "Heuristic Algorithms for Task Assignment in Distributed Systems", IEEE Transactions on Computers, Vol 37, November 1988, pp 1384-1397.
Markatos, E.P. and LeBlanc, T.J., "Load balancing vs. Locality Management in Shared Memory Multiprocessors", Technical Report 399, University of Rochester, October 1991.
Shirazi, B. and Wang,M.,"Analysis and Evaluation of Heuristic Methods for Static Scheduling", Journal of Parallel and Distributed Computing, Vol 10, 1990, pp 222-232.
Squillance,M.S. and Nelson, R.D., "Analysis of Task Migration in Shared Memory Multiprocessor Scheduling", Proceedings of the 1991 ACM SIGMETRICS Conference On Measurements and Modeling of Computer Systems, May 1991, San Diego, CA, pp 143-155.
Stone H.S.,"Multiprocessor Scheduling with the Aid of Network Flow Algorithms", IEEE-SE, Vol SE-3, No 1, January 1977, pp 85-93.
Publicado
07/09/1993
Como Citar
SEIDEL, Cristiana Bentes; CANALEY, Lysia Maria M. B.; ARNORIM, Cláudio Luis.
Uma Comparação da Eficiência de Duas Heurísticas para Alocação Estática de Processos. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 5. , 1993, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1993
.
p. 487-501.
DOI: https://doi.org/10.5753/sbac-pad.1993.23054.
