Graph based analysis of 2-D FPGA routing

TitleGraph based analysis of 2-D FPGA routing
Publication TypeJournal Article
Year of Publication1996
AuthorsWu, Y-L, Tsukiyama, S, Marek-Sadowska, M
JournalComputer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Pagination33 -44
Date Publishedjan
Keywords2D FPGA routing, 2D interval packing problem, circuit layout CAD, computational complexity, constant bounded mapping ratios, field programmable gate arrays, global routing channel density, graph based analysis, graph theory, integrated circuit layout, logic CAD, mapping ratio, network routing, network topology, NP-complete problem, polynomial time mapping solutions, switch box connection topology, two-dimensional FPGA, Xilinx-like routing architectures
AbstractIn this paper, we study the two-dimensional FPGA, Xilinx-like routing architectures and present the first known computational complexity results for them. The routing problem is formulated as a two-dimensional interval packing problem and is proved to be NP-complete with or without doglegs. Next, we consider other routing structures obtained from the industrial one by arbitrarily changing switch box connection topology while maintaining the same connection flexibility. There is an exponentially large number of such routing structures. We further prove that there does not exist a better routing architecture among the members of this large domain. In addition, we prove that there is no constant bound on the mapping ratio of a track number required by a detailed routing to a global routing channel density for the studied architectures. Finally, we show two directions of changing the routing architectures which yield polynomial time mapping solutions and constant bounded mapping ratios. Our theoretical analysis is intended to give some insight to, and understanding of this new routing problem's fundamental properties