Técnicas para Alocação Estática de Tarefas em Sistemas Distribuídos
Resumo
Neste trabalho enfocamos o problema de alocação estática de tarefas em sistemas distribuídos nos quais processadores podem ter diferentes velocidades de processamento e canais de comunicação podem ter diferentes capacidades. A partir da definição de uma função para medir o custo de uma alocação, duas abordagens são propostas. A primeira usa o algoritmo A* e é semelhante a algumas técnicas já propostas anteriormente. Foram criadas uma nova heurística a partir da função de custo e formas de melhorar o desempenho do método. O segundo método proposto, utiliza a idéia de uma rede neuronal, segundo o trabalho de Hopfield e Tank. Os testes realizados permitem concluir que os dois métodos são comparáveis. A rede neuronal, porém, tem a grande vantagem de poder facilmente ser implementada em paralelo.
Referências
KRUMME, D. W., VENKATARAMAN, K.N., e CYBENKO, G., "Hypercube Embedding is NP-Complete," Hypercube Multiprocessor 1986, pp. 148-157 em M. T. Heath (Ed.), SIAM, Philadelphia, PA, 1986.
HOPFIELD, J.J., e TANK, D.W., "Computing with Neural Circuits: a Model", Science, vol 233, pp 625-633, ago, 1986.
FOX, G.C., e OTTO, S. W., "Concurrent Computation and the Theory of Complex Systems", Hypercube Multiprocessors 1986, SIAM, Philadelphia, PA, 1986.
SINCLAIR, J.B., "Efficient Computational of Optimal Assignments for Distributed Tasks", Journal of Parallel and Distributed Computing 4, pp 342-3621, 1987.
SHEN, C.C., e TSAI, W.H., "A Graph Matching Approach to Optimal Task Assignment in Distributed Computation System Using a Minimax Criterion", IEEE Transactions on Computers, vol c-34, n 3, pp 197-203, mar, 1985.
FOX, G.C., KOLAWA, A., e WILLIAMS, R., "The Implementation of a Dynamic Load Balancer", pp. 114-121 em M. T. Heath (Ed.), Hypercube Multiprocessor 1987, SIAM, Philadelphia, PA, 1987.
NILSSON, N.J., "Principies of Artificial lntelligence", Tioga Publishing Co, Palo Alto, 1980.
PEARL, J., "Heuristics-Intelligent Search Strategies for Computer Problem Solving", Addison-Wesley Publishing Company, 1984.
McCULLOCH, W.S., e PITTS, W., Bull Math. Biophys. 5, 115, 1943.
HUANG, H.K., "Técnicas para Alocação Estática de Tarefas em Sistemas Distribuídos", Tese de Mestrado em Engenharia de Sistemas, COPPE-Sistemas, UFRJ, jun, 1988.
