| Title | Graph based analysis of FPGA routing |
| Publication Type | Conference Paper |
| Year of Publication | 1993 |
| Authors | Wu, Y-L, Marek-Sadowska, M |
| Conference Name | Design Automation Conference, 1993, with EURO-VHDL '93. Proceedings EURO-DAC '93. European |
| Date Published | sep |
| Keywords | array type architectures, circuit layout CAD, computational complexity, field programmable gate array, field programmable gate arrays, FPGA routing, global routing, graph based analysis, graph theory, logic CAD, mapping, multi-pin net lists, network routing, optimal detailed routing, predictable detailed routing, programmable logic arrays, routing architecture, two-pin net lists, Xilinx-like routing model |
| Abstract | The experimental results of FPGA (field programmable gate array) routing suggest that there are difficulties in mapping global routing to a predictable detailed routing for array type architectures. The authors develop a graph theoretical formulation of this mapping problem and show that it is NP-complete for both multi-pin net lists and two-pin net lists for the Xilinx-like routing model. They present two changes in the routing architecture such that each of them yields a predictable mapping of global routing to the optimal detailed routing. The results suggest a novel approach to array type FPGA routing |
| DOI | 10.1109/EURDAC.1993.410623 |
