On optimal board-level routing for FPGA-based logic emulation
Wai-Kei Mak, Martin D. F. Wong · 1995
In this paper, we consider a board-level routing problem which is applicable to FPGA-based logic emulation systems such as the Realizer system [5] and the Enterprise Emulation System [3] manufactured by Quickturn Systems. For the case where all nets are two-terminal nets, we present an O(n 2 )-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 multiterminal nets is NP-complete. 1 Introduction Introduced in the mid-1980's, FPGAs [1,2] combine the programmability of programmable logic devices and the scalable interconnection structure of traditional gate arrays. This combination results in programmable devices with much higher logic density. Compared with tradition...