Abstract
A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segments is proposed. In comparison with the conventional two dimensional Field-Programmable Gate Array (FPGA) routing structure, this class of routing structures has the advantage of using a smaller number of programmable switches. Using a probabilistic model, we prove that complete routing can be achieved with a high degree of probability in a routing structure of this class in which the number of tracks in each channel approaches the lower bound asymptotically. A sequential routing algorithm which is based on the solution of the single net routing problem is presented. We take into account the delay introduced by the programmable switches on a routing path and formulate the single net routing problem as a Node-Weighted Steiner Minimum Tree (NWSMT) problem in a bipartite graph G. Since our single net routing problem is NP-complete, a polynomial time approximate algorithm is proposed. We prove that our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs. In general, the solution obtained by our algorithm has a performance bound of min{Δ(V/Z),|Z|-1}. On the other hand, we also prove that it is NP-complete to determine a solution which approximates the optimal solution within any constant bound. Experimental results show a reduction of up to 41% in the number of programmable switches when compared with corresponding results for the conventional FPGA routing structure.