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

Abstract

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.