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

fYear

1993

Firstpage

104

Lastpage

109

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/EURDAC.1993.410623

Filename

410623