On computational complexity of a detailed routing problem in two dimensional FPGAs

TitleOn computational complexity of a detailed routing problem in two dimensional FPGAs
Publication TypeConference Paper
Year of Publication1994
AuthorsWu, Y-L, Tsukiyama, S, Marek-Sadowska, M
Conference NameVLSI, 1994. Design Automation of High Performance VLSI Systems. GLSV '94, Proceedings., Fourth Great Lakes Symposium on
Date Publishedmar
Keywordsarbitrary fixed switch box topology, circuit layout CAD, computational complexity, connection flexibility, doglegs, global route mapping, logic arrays, logic CAD, network routing, network topology, NP-complete problem, routing problem, two dimensional FPGAs, Xilinx-4000-like routing architecture
AbstractIn this paper, we consider the problem of mapping a given global route to a detailed route for two dimensional homogeneous FPGAs. It has been shown that this problem is NP-complete on a popular Xilinx-4000-like routing architecture. Here, we further prove that this problem remains NP-complete for an arbitrary fixed switch box topology of the same connection flexibility, with or without doglegs allowed in detailed routes
DOI10.1109/GLSV.1994.289993