Soluções Paralelas para o Problema de Roteamento Usando o Algoritmo de Lee
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, e propõe, de maneira construtiva, técnicas para a paralelização do mesmo. O resultado final apresentou speedup de 2, 25 com 2 threads e 3, 70 com 4 threads.
Referências
Akers, S. B. (1967). A modification of Lee’s path connection algorithm. IEEE Transactions on Electronic Computers, EC-16(1):97–98.
Chen, H.-Y. and Chang, Y.-W. (2009). Global and detailed routing. In Electronic Design Automation, pages 687–749. Elsevier.
Lee, C. Y. (1961). An algorithm for path connections and its applications. IRE Transactions on Electronic Computers, EC-10(3):346–365.
Olukotun, O. A. and Mudge, T. N. (1987). A preliminary investigation into parallel routing on a hypercube computer. In 24th ACM/IEEE Design Automation. OpenMP Architecture Review Board (2018). OpenMP API version 5.0.
Sait, S. and Youssef, H. (1999). VLSI Physical Design Automation: Theory and Practice. Lecture Notes Series. World Scientific.
Seaton, C., Goodman, D., and Luján, M. (2012). Applying dataflow and transactions to lee routing. In Workshop on Programmability Issues for Heterogeneous Multicores.
Yen, I., Dubash, R., and Bastani, F. (1993). Strategies for mapping Lee’s maze routing algorithm into parallel architectures. In International Parallel Processing Symposium.
Chen, H.-Y. and Chang, Y.-W. (2009). Global and detailed routing. In Electronic Design Automation, pages 687–749. Elsevier.
Lee, C. Y. (1961). An algorithm for path connections and its applications. IRE Transactions on Electronic Computers, EC-10(3):346–365.
Olukotun, O. A. and Mudge, T. N. (1987). A preliminary investigation into parallel routing on a hypercube computer. In 24th ACM/IEEE Design Automation. OpenMP Architecture Review Board (2018). OpenMP API version 5.0.
Sait, S. and Youssef, H. (1999). VLSI Physical Design Automation: Theory and Practice. Lecture Notes Series. World Scientific.
Seaton, C., Goodman, D., and Luján, M. (2012). Applying dataflow and transactions to lee routing. In Workshop on Programmability Issues for Heterogeneous Multicores.
Yen, I., Dubash, R., and Bastani, F. (1993). Strategies for mapping Lee’s maze routing algorithm into parallel architectures. In International Parallel Processing Symposium.
Publicado
12/11/2019
Como Citar
TAVARES, William; MOREANO, Nahri.
Soluções Paralelas para o Problema de Roteamento Usando o Algoritmo de Lee. In: WORKSHOP DE INICIAÇÃO CIENTÍFICA - SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 20. , 2019, Campo Grande.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 1-8.
DOI: https://doi.org/10.5753/wscad_estendido.2019.8692.
