Placement por simulated annealing em um cluster de estações de trabalho - Knopman, Jonas; Aude, Júlio Salek (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD); 1995: Anais do VII Simpósio Brasileiro de Arquitetura de Computadores e Processamento de Alto DesempenhoDO - 10.5753/sbac-pad.1995.19864, 1995)
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.