Title :
Board-level multi-terminal net routing for FPGA-based logic emulation
Author :
Wai-Kei Mak ; Wong, D.F.
Author_Institution :
Dept. of Comput. Sci., Texas Univ., Austin, TX, USA
Abstract :
We consider a board-level routing problem applicable to FPGA-based logic emulation systems such as the Realizer System (Varghese et al., (1993)) and the Enterprise Emulation System (Maliniak (1992)) manufactured by Quickturn Systems. Optimal algorithms have been proposed for the case where all nets are two-terminal nets. In this paper, we show how multi-terminal nets can be handled by decomposition into two-terminal nets. We show that the multi-terminal net decomposition problem can be modelled as a bounded-degree hypergraph-to-graph transformation problem where hyper-edges are transformed to spanning trees. A network flow-based algorithm that solves both problems is proposed. It determines if there is a feasible decomposition and gives one whenever such a decomposition exists.
Keywords :
field programmable gate arrays; logic CAD; logic design; network routing; FPGA-based logic emulation; board-level routing problem; hypergraph-to-graph transformation; logic emulation; multi-terminal nets; net routing; spanning trees; Computer aided manufacturing; Digital systems; Emulation; Field programmable gate arrays; Logic arrays; Logic design; Pins; Prototypes; Routing; Software prototyping;
Conference_Titel :
Computer-Aided Design, 1995. ICCAD-95. Digest of Technical Papers., 1995 IEEE/ACM International Conference on
Conference_Location :
San Jose, CA, USA
Print_ISBN :
0-8186-8200-0
DOI :
10.1109/ICCAD.1995.480138