Title :
Detailed-routability of FPGAs with extremal switch-block structures
Author :
Takashima, Yasuhiro ; Takahashi, Atsushi ; Kajitani, Yoji
Author_Institution :
Dept. of Electr. & Electron. Eng., Tokyo Inst. of Technol., Japan
Abstract :
The architecture of FPGAs is discussed to see trade-offs between programmable-switch resources in switch-blocks and detailed-routability. For the purpose, FPGAs are assumed to have certain extremal structures. A polynomial time detailed-routing for a given global-routing presented if the switch-block consists of two or parallel switch-sets or three that form a cycle. While, the corresponding decision problem is proved to be 𝒩𝒫-complete for other FPGAs. A best compromise between switch resources and detailed-routability is offered
Keywords :
circuit layout CAD; computational complexity; field programmable gate arrays; integrated circuit layout; logic CAD; network routing; FPGA architecture; detailed-routability; extremal switch-block structures; global routing; polynomial time routing; Electronic mail; Field programmable gate arrays; Joining processes; Polynomials; Proposals; Routing; Switches; Wire;
Conference_Titel :
European Design and Test Conference, 1996. ED&TC 96. Proceedings
Conference_Location :
Paris
Print_ISBN :
0-8186-7424-5
DOI :
10.1109/EDTC.1996.494142
