ON OPTIMAL BOARD-LEVEL ROUTING FOR FPGA-BASED LOGIC EMULATION

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.