Title :
Graph based analysis of FPGA routing
Author :
Wu, Y.-L. ; Marek-Sadowska, M.
Author_Institution :
Dept. of Electr. & Comput. Eng., California Univ., Santa Barbara, CA, USA
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.<>
Keywords :
circuit layout CAD; computational complexity; field programmable gate arrays; graph theory; logic CAD; network routing; programmable logic arrays; FPGA routing; Xilinx-like routing model; array type architectures; field programmable gate array; global routing; graph based analysis; mapping; multi-pin net lists; optimal detailed routing; predictable detailed routing; routing architecture; two-pin net lists; Computer architecture; EPROM; Field programmable gate arrays; Logic arrays; Multiplexing; Pins; Random access memory; Routing; Switches; Table lookup;
Conference_Titel :
Design Automation Conference, 1993, with EURO-VHDL '93. Proceedings EURO-DAC '93., European
Conference_Location :
Hamburg, Germany
Print_ISBN :
0-8186-4350-1
DOI :
10.1109/EURDAC.1993.410623
