Placement por simulated annealing em um cluster de estações de trabalho
Resumo
A resolução de problemas de otimização combinatória com base no método de Simulated Annealing mostrou produzir resultados de extrema qualidade mas, tipicamente, a um custo de processamento muito alto. Visando reduzir este custo diversas soluções têm sido propostas com o uso de hardware dedicado, processadores velozes ou explorando possibilidades de paralelizar o algoritmo. Neste artigo é apresentada uma implementação paralela do algoritmo de simulated annealing visando resolver o problema do placement de células no projeto de circuitos impressos ou de circuitos VLSI. É mostrado que a escolha do mecanismo de paralelização é influenciada pela temperatura. Em particular introduz-se a idéia do uso de estratégias adaptativas que, dinamicamente, mudam o esquema de partição do problema visando obter o máximo de desempenho. O algoritmo foi implementado em um cluster de workstations usando PVM (Parallel Virtual Machine) formando assim uma máquina paralela virtual com comunicação através de troca de mensagens. O algoritmo seqüencial é apresentado juntamente com algumas técnicas de paralelização. São apresentadas medidas extensivas da qualidade dos algoritmos propostos bem como são levantados uma série de problemas, alguns dos quais levaram a modificações dos algoritmos inicialmente testados enquanto outros mantêm-se ainda não resolvidos.
Referências
Diekmann R., Lüling R., Simon J., "Problem Independent Distributed Simulated Annealing and its Applications ", Proc. of the 4th IEEE Symposium on Parallel and Distributed Processing (SPDP '92).
Geist A. et al., "PVM3 Users 's Guide and Reference Manual", Oak Ridge National Laboratory, 1994.
Huang M.D., Romeo F., Vincentelli A. S., "An Efficienl General Cooling Schedule for Simulated Annealing", IEEE International Conference on Computer Aided Design, 1986.
Kirkpatrick S., Gelatt C.D., Vecchi M.P., "Optimizalion by Simulated Annealing", SCIENCE, Volume 220, Number 4598, May 1983.
Kravitz S.A., Rutenbar R.A., "Placement by Simulated Annealing on a Multiprocessor", IEEE Transactions on Computer-Aided Design, Vol. CAD-6, No. 4, July 1987.
Laarhoven P.J.M., Aarts E., "Simulated Annealing. Theory and Applications", D.Reidel Publishing Company, 1987.
Sechen C., Vincentelli A. S., "The Timberwolf Placement and Routing Package ", IEEE Journal of Solid-State Circuits, Vol SC-20, No. 2, April 1985.
