Routing for array-type FPGA's

TitleRouting for array-type FPGA's
Publication TypeJournal Article
Year of Publication1997
AuthorsWu, Y-L, Marek-Sadowska, M
JournalComputer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Pagination506 -518
Date Publishedmay
Keywordsalgorithm, array-type FPGA, decaying effect, deterministic routing, field programmable gate arrays, greedy coupling heuristics, logic design, network routing, optimization cost function, routing, two-dimensional field programmable gate array, Xilinx architecture
AbstractIn this paper, the routing problem for two-dimensional (2-D) field programmable gate arrays of a Xilinx-like architecture is studied. We first propose an efficient one-step router that makes use of the main characteristics of the architecture. Then we propose an improved approach of coupling two greedy heuristics designed to avoid an undesired decaying effect, a dramatically degenerated router performance on the near completion stages. This phenomenon is commonly observed on results produced by the conventional deterministic routing strategies using a single optimization cost function. Consequently, our results are significantly improved on both the number of routing tracks and routing segments by just applying low-complexity algorithms. On the tested MCNC and industrial benchmarks, the total number of tracks used by the best known two-step global/detailed router is 28% more than that used by our proposed method