Graph based analysis of FPGA routing

TitleGraph based analysis of FPGA routing
Publication TypeConference Paper
Year of Publication1993
AuthorsWu, Y-L, Marek-Sadowska, M
Conference NameDesign Automation Conference, 1993, with EURO-VHDL '93. Proceedings EURO-DAC '93. European
Date Publishedsep
Keywordsarray 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
AbstractThe 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