Abstract
In this paper, we will study the net assignment problem for logic emulation system in the folded-Clos network interconnection [1], also referred to as the partial crossbar interconnection structure in [2] and [3]. Net assignment of two-terminal nets in this interconnection structure is guaranteed to be completed in polynomial time. However, net assignment of multiterminal nets becomes NP-complete. A previous paper [2] has proposed a simple heuristic to perform net assignment for multiterminal nets. Its results showed that it failed to complete routing all nets for many cases. It is inadequate to have a net assignment algorithm which does not guarantee an exact solution, as the failure of interconnecting field programmable gate arrays (FPGA's) will result in the failure of mapping to the computing engine as a whole and will result in redoing the previous steps, e.g., partitioning of circuits. Therefore, we will propose an exact algorithm to solve the net assignment problem. The exact algorithm will find a solution if there exists one. However, the exact algorithm may take exponential time. Accordingly, a two-phase approach will be taken in this paper. A time-efficient heuristic method will be used first. The exact solver will be called only if the heuristic fails to deliver a solution. © 1997 IEEE.