The spectral method can lead to a high quality of multi-way partition due to its ability to capture global netlist information. For spectral partition, n netlist modules are mapped to n points in d-dimensional space, and then a linear ordering of these n modules is constructed to be used as a basis for partitioning. In this paper, we propose two clustering based linear ordering algorithms taking into consideration the objective function presented.

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.