General models and a reduction design technique for FPGA switch box designs
Authors:
- Hongbing FanHFHongbing Fan
- Jiping LiuJLJiping Liu
- Yu-Liang WuYWYu-Liang Wu
- 1 January 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 52 (1) , 21-30
Abstract
An FPGA switch box is said to be hyper-universal if it is detailed-routable for any set of multipin nets specifying a routing requirement over the switch box. Comparing with the known "universal switch modules", where only 2-pin nets are considered, the hyper-universal switch box model is more general and powerful. This paper studies the generic problem and proposes a systematic designing methodology for hyper-universal (k, W)-switch boxes, where k is the number of sides and W is the number of terminals on each side. We formulate this hyper-universal (k, W)-switch box design problem as a k-parfite graph design problem and propose an efficient reduction design technique. Applying this technique, we can design hyper-universal (k, W)-switch boxes with low O(W) switches for any fixed k. For illustration, we provide optimum hyper-universal (2, W) and (3, W)-switch boxes and a hyper-universal (4, W)-switch box with switch number quite close to the lower bound 6W, which is used in a well-known commercial design without hyper-universal routability. We also conclude that the proposed reduction method can yield an efficient detailed routing algorithm for any given routing requirement as well.Keywords
This publication has 14 references indexed in Scilit:
- Generic universal switch blocksIEEE Transactions on Computers, 2000
- Architecture and CAD for Deep-Submicron FPGAS1999
- Routing for array-type FPGA'sIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997
- Universal switch modules for FPGA designACM Transactions on Design Automation of Electronic Systems, 1996
- Graph based analysis of 2-D FPGA routingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996
- New Performance-Driven FPGA Routing AlgorithmsProceedings of the 39th conference on Design automation - DAC '02, 1995
- A performance and routablity driven router for FPGAs considering path delays1995
- A detailed router for field-programmable gate arraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- Field-Programmable Gate Arrays1992
- Flexibility of interconnection structures for field-programmable gate arraysIEEE Journal of Solid-State Circuits, 1991