Title :
On Optimal Board-Level Routing for FPGA-based Logic Emulation
Author :
Wai-Kei Mak, D.F. Wong
Author_Institution :
Department of Computer Sciences, University of Texas at Austin, Austin, TX
Abstract :
In this paper, we consider a board-level routing problem which is applicable to FPGA-based logic emulation systems such as the Realizer system [3] and the Enterprise Emulation System [5] manufactured by Quickturn Systems. For the case where all nets are two-terminal nets, we present an O(n2)-time optimal algorithm where n is the number of nets. Our algorithm guarantees 100% routing completion if the number of inter-chip signal pins on each FPGA chip in the logic emulation system is less than or equal to the number of I/O pins on the chip. Our algorithm is based on iteratively finding Euler circuits in graphs. We also prove that the routing problem with multi-terminal nets is NP-complete.
Keywords :
Design automation; Digital systems; Emulation; Field programmable gate arrays; Integrated circuit interconnections; Iterative algorithms; Logic design; Pins; Programmable logic arrays; Routing;
Conference_Titel :
Design Automation, 1995. DAC '95. 32nd Conference on
Conference_Location :
San Francisco, CA
Print_ISBN :
0-89791-725-1
DOI :
10.1109/DAC.1995.250008