Estratégias de Otimização e Paralelização do Algoritmo de Lee para o Problema de Roteamento

William Felipe da Cunha Tavares, Nahri Balesdent Moreano

Resumo


O algoritmo de Lee é uma técnica popular para realizar o roteamento de trilhas em uma placa de circuito. No âmbito de VLSI, essa tarefa se torna computacionalmente intensa e exige grande quantidade de memória. Este artigo avalia otimizações descritas na literatura que reduzem o consumo de tempo e memória do algoritmo. O artigo também propõe técnicas para a paralelização do algoritmo de Lee, avaliando diferentes estratégias para a sincronização entre as threads, a persistência das mesmas e compartilhamento de dados entre elas. Através de uma avaliação experimental detalhada, obteve-se como resultado final speedups de 2,25 com 2 threads e 3,70 com 4 threads.

Palavras-chave


programação paralela;VLSI

Texto completo:

PDF


A REIC mudou de endereço! Para acessar as edições publicadas e/ou submeter seu artigo, acesse https://sol.sbc.org.br/journals/index.php/reic.