Wk. Mak et Df. Wong, ON OPTIMAL BOARD-LEVEL ROUTING FOR FPGA-BASED LOGIC EMULATION, IEEE transactions on computer-aided design of integrated circuits and systems, 16(3), 1997, pp. 282-289
In this paper, we consider a board-level routing problem which is appl
icable to held-programmable gate arrays (FPGA)-based logic emulation s
ystems such as the Realizer System [3] and the Enterprise Emulation Sy
stem [5] manufactured by Quickturn Design Systems. For the case where
all nets are two-terminal nets, we present an O(n(2))-time optimal alg
orithm where n is the number of nets. Our algorithm guarantees 100% ro
uting completion if the number of interchip signal pins on each FPGA c
hip 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 iterative computati
on of Euler circuits in graphs. We also prove that the routing problem
with multiterminal nets is NP-complete. And we suggest one way to han
dle multiterminal nets using some additional resources.