Abstract
In this thesis, we will study the net assignment problem in partial crossbar interconnection architecture [1,4]. Net assignment of two-terminal nets in this interconnection structure is guaranteed to be completed in polynomial time. However, net assignment of multi-terminal nets becomes NP-complete. Previous paper [1] has proposed a simple heuristic to perform net assignment for multi-terminal nets. Its results showed that it failed to complete routing all nets for many cases. It is inadequate to have net assignment algorithm which does not guarantee an exact solution, for the failure of interconnecting FPGAs will result in the failure of whole mapping to the computing engine or 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 research. A time-efficient heuristic method [14,15] will be called first. The exact solver will be called only if the heuristic fails to deliver a solution.