On The Np-completeness Of Regular 2-d Fpga Routing Architectures And A Novel Solution
- 24 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Several industrial FPGA routing architectures have been shown to have no efficient routing algorithms (unless P=NP). Here, we further investigate if the intractability of the routing problem on a regular 2-D FPGA routing architecture can be alleviated by adding routing switches. We show that on this routing architecture, even with a substantial increase in switching flexibility, a polynomial time, predictable routing algorithm is still not likely to exist, and there is no constant ratio bound of the detailed over global routing channel densities. We also show that a perfect routing is unachievable on this architecture even with near complete (maximum) switching flexibility.We also discuss a new, greedy routing architecture, that possesses predictable and other desired routing properties, yet requires fewer routing resources than regular architectures. This theoretical result may suggest an alternative approach in routing architecture designs.Keywords
This publication has 5 references indexed in Scilit:
- Graph based analysis of FPGA routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An efficient router for 2-D field programmable gate arrayPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A stochastic model to predict the routability of field-programmable gate arraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Segmented channel routingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- A detailed router for field-programmable gate arraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992