ROUTING FOR SYMMETRICAL FPGAS AND FPICS

A new class of routing structures with fixed orthogonal wire segments and field programmable switches at the intersections of the wire segme nts is proposed, In comparison with the conventional two-dimensional h eld-programmable gate array (FPGA) routing structure, this class of ro uting structures has the advantage of using a smaller number of active programmable switches, An existing field-programmable interconnect ch ip (FPIC) routing structure can be included as a special case in our c lass of routing structures, 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 ea ch channel approaches the lower bound asymptotically. We present a seq uential routing algorithm based on the solution of the single net rout ing problem, We take into account the delay introduced by the active p rogrammable switches on a routing path and formulate the single net ro uting problem as a node-weighted Steiner minimum tree (NWSMT) problem in a bipartite graph G. Since our single net routing problem is NP-com plete, a polynomial time approximate algorithm is proposed. We prove t hat our single net routing algorithm produces an optimal solution for some special classes of bipartite graphs, In general, the solution obt ained by our algorithm has a performance bound of min{Delta(V\Z), \Z\ - 1}. In addition, we also prove that it is NP-complete to determine a solution that approximates the optimal solution within any constant b ound. Experimental results for several industrial circuits show a redu ction of up to 41% in tile number of active programmable switches when compared with corresponding results for the conventional FPGA routing structure.