Net assignment for the FPGA-based logic emulation system in the folded-Clos network structure

摘要

In this paper, we study the net assignment problem for a logic emulation system in the folded-Clos network interconnection, also referred to as the "partial crossbar interconnection structure". 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 by Butts et al. (1992) has proposed a simple heuristic to perform net assignment for multiterminal nets. Its results showed that it failed to complete routing of 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 propose an exact algorithm to solve the net assignment problem. The exact algorithm will find a solution if one exists. However, the exact algorithm may take exponential time. Accordingly, a two-phase approach is taken in this paper. A time-efficient heuristic method is used first. The exact solver will be called only if the heuristic fails to deliver a solution.