Board-level multi-terminal net routing for FPGA-based logic emulation

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.