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

Author

Wu, Yu-Liang ; Tsukiyama, Shuji ; Marek-Sadowska, Malgomta

Author_Institution

Dept. of Electr. & Comput. Eng., California Univ., Santa Barbara, CA, USA

fYear

1994

fDate

4-5 Mar 1994

Firstpage

70

Lastpage

75

Abstract

In 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

Keywords

circuit layout CAD; computational complexity; logic CAD; logic arrays; network routing; network topology; NP-complete problem; Xilinx-4000-like routing architecture; arbitrary fixed switch box topology; computational complexity; connection flexibility; doglegs; global route mapping; routing problem; two dimensional FPGAs; Computational complexity; Costs; Field programmable gate arrays; Hardware; Production; Prototypes; Routing; Switches; Systems engineering and theory; Topology;

fLanguage

English

Publisher

ieee

Conference_Titel

VLSI, 1994. Design Automation of High Performance VLSI Systems. GLSV '94, Proceedings., Fourth Great Lakes Symposium on

Conference_Location

Notre Dame, IN

Print_ISBN

0-8186-5610-7

Type

conf

DOI

10.1109/GLSV.1994.289993

Filename

289993