Acelerador Modular para Roteamento

• J. S. Aude UFRJ
• E. B. M. O. Paiva UFRJ
• E. P. L. Aude UFRJ
• E. P. L. Filho UFRJ
• M. F. Martins UFRJ
• S. B. Pinto UFRJ

DOI: https://doi.org/10.5753/sbac-pad.1988.23523

Resumo

Este artigo descreve uma arquitetura modular dedicada à implementação do algoritmo proposto por Lee para roteamento automático de conexões elétricas em circuitos eletrônicos. O algoritmo de Lee é descrito brevemente e as arquiteturas já propostas para sua implementação em hardware são discutidas. A arquitetura proposta no artigo é baseada em duas estruturas pipeline e num esquema especial de organização da memória que armazena informação sobre a superfície a ser roteada. As modificações do algoritmo de Lee implementadas na arquitetura são discutidas e o funcionamento do hardware é descrito, mostrando-se os algoritmos implementados para execução das diferentes fases do algoritmo de Lee. A arquitetura encontra-se em fase final de detalhamento e resultados de simulação indicam que seu desempenho na execução do algoritmo de Lee serão pelo menos 40 vezes melhor do que o de mainframes.

Referências

"Sistema de Geração Automática de Layout com Acelerador de Roteamento", Aude,J. S., Paiva,E.B.M.O., Aude,E.P. L.,Lopes,E. P., Martins,M.F., Pinto,S.B., Trabalho a ser publicado nos anais do VIII Congresso da SBC 1988;

"A Parallel Bit Map Processor Architecture for DA Algorithm", Blank,T.,Stefik,M., VanCleemput, W., Proceedings of the 18th Design Automation Conference, Junho, 1981, pp. 837-845;

"A Hardware Router", Breuer,M.A.,Shamsa,K., Journal of Digital Systems, Vol.4, no. 4, 1981, pp. 393-408;

"A Class of Array Architectures for Hardware Grid Routers", Iosupovici,A., IEEE Transactions on Computer-Aided Design, Vol. CAD-5, No. 2, Abril, 1986, pp. 245-255;

"An Algorithm for Path Connections and its Applications", Lee,C. Y., IRE Transactions on Electronic Computers, Vol. EC-10, Setembro, 1961, pp. 346-365;

"A Class of Cellular Architectures to Support Physical Design Automation", Rutenbar,R.A., Mudge,T.N., Atkins,D.E., IEEE Transactions on Computer-Aided Design, Vol. CAD-3, No. 4, Outubro, 1984, pp. 264-278;

"Multiprocessor Based Placement by Simulated Annealing", Kravitz,S.A., Rutenbar,R.A., Proceedings of the 23rd Design Automation Conference, Junho, 1986, pp. 567-573;

"The IBM Yorktown Simulation Engine", Pfister,G.F., Proceedings IEEE, Junho,1986, pp. 850-860;

"An ISMA Lee Router Accelerator, Ryan,T., Rogers,E., IEEE Design and Test of Computers, Outubro, 1987, pp. 38-45;

"A Hardware Assisted Design Rule Check Architecture", Seiler, L., Proceedings of the 19th Design Automation Conference,Junho, 1982, pp. 232-238;

"A Hardware Accelerator for Maze Routing", Won,Y., Sahni,S., El-Ziq,Y., Proceedings of the 24th Design Automation Conference, Junho, 1987, pp. 800-806.