Graph based analysis of FPGA routing
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The experimental results of FPGA (field programmable gate array) routing suggest that there are difficulties in mapping global routing to a predictable detailed routing for array type architectures. The authors develop a graph theoretical formulation of this mapping problem and show that it is NP-complete for both multi-pin net lists and two-pin net lists for the Xilinx-like routing model. They present two changes in the routing architecture such that each of them yields a predictable mapping of global routing to the optimal detailed routing. The results suggest a novel approach to array type FPGA routing.Keywords
This publication has 10 references indexed in Scilit:
- Routable technology mapping for LUT FPGAsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Routability-driven technology mapping for lookup table-based FPGAsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Improving FPGA routing architectures using architecture and CAD interactionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Optimization of field-programmable gate array logic block architecture for speedPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The effect of switch box flexibility on routability of field programmable gate arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Third-generation architecture boosts speed and density of field-programmable gate arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Segmented channel routingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An FPGA family optimized for high densities and reduced routing delayPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A detailed router for field-programmable gate arraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- The intersection graphs of subtrees in trees are exactly the chordal graphsJournal of Combinatorial Theory, Series B, 1974