Design of minimum and uniform bipartites for optimum connection blocks of FPGA

The design of optimum connection blocks of field programmable gate arrays (FPGA's) in number and in distribution of switches is formulated as a bipartite graph design problem and solved. A bipartite with vertex sets R and L (|R|/spl les/|L|) is called totally perfect if there is a perfect matching from L/sub s/ to R for any L/sub s//spl sub/L with |L/sub s/|/spl les/|R|. The difference of maximum and minimum degrees of the vertices in L or R is called the skew of the respective vertex set. The problem is to construct a minimum totally perfect bipartite graph with the minimum skew. The result shows that a method, biscattering, can construct such a matrix in O(|R|/spl times/|L|) time where the lower bound is attained for both skews. This construction also solves the problem of designing optimum direct-concentrators.