Segmented channel routing

Author

Roychowdhury, Vwani P. ; Greene, Jonathan W. ; El Gamal, Abbas

Author_Institution

Sch. of Electr. Eng., Purdue Univ., West Lafayette, IN, USA

Volume

12

Issue

1

fYear

1993

fDate

1/1/1993 12:00:00 AM

Firstpage

79

Lastpage

95

Abstract

Novel problems concerning routing in a segmented routing channel are introduced. These problems are fundamental to routing and design automation for field programmable gate arrays (FPGAs), a new type of electrically programmable VLSI. The first known theoretical results on the combinatorial complexity and algorithm design for segmented channel routing are presented. It is shown that the segmented channel routing problem is in general NP-complete. Efficient polynomial time algorithms for a number of important special cases are presented

Keywords

VLSI; circuit layout CAD; computational complexity; logic CAD; logic arrays; network routing; FPGA; NP-complete; combinatorial complexity; design automation; electrically programmable VLSI; field programmable gate arrays; polynomial time algorithms; segmented channel routing; Algorithm design and analysis; Design automation; Field programmable gate arrays; Heuristic algorithms; Polynomials; Programmable logic arrays; Routing; Switches; Very large scale integration; Wiring;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.184845

Filename

184845