Segmented channel routing
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 12 (1) , 79-95
- https://doi.org/10.1109/43.184845
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
This publication has 5 references indexed in Scilit:
- Segmented channel routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An architecture for electrically configurable gate arraysIEEE Journal of Solid-State Circuits, 1989
- Dogleg Channel Routing is NP-CompleteIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- Two-dimensional stochastic model for interconnections in master slice integrated circuitsIEEE Transactions on Circuits and Systems, 1981
- Wire routing by optimizing channel assignment within large aperturesPublished by Association for Computing Machinery (ACM) ,1971