The exact channel density and compound design for generic universal switch blocks

A switch block of k sides W terminals on each side is said to be universal (a (k, W)-USB) if it is routable for every set of 2-pin nets of channel density at most W. The generic optimum universal switch block design problem is to design a (k, W)-USB with the minimum number of switches for every pair of (k, W). This problem was first proposed and solved for k = 4 in Chang et al. [1996], and then solved for even W or for k ≤ 6 in Shyu et al. [2000] and Fan et al. [2002b]. No optimum (k, W)-USB is known for k ≥ 7 and odd W ≥ 3. But it is already known that when W is a large odd number, a near-optimum (k, W)-USB can be obtained by a disjoint union of (W - f2(k))/2 copies of the optimum (k, 2)-USB and a noncompound (k, f2(k))-USB, where the value of f2(k) is unknown for k ≥ 8. In this article, we show that f2(k) = k+3-i/3, where 1 ≤ i ≤ 6 and i ≡ k (mod 6), and present an explicit design for the noncompound (k, f2(k))-USB. Combining these two results we obtain the exact designs of (k, W)-USBs for all k ≥ 7 and odd W ≥ 3. The new (k, W)-USB designs also yield an efficient detailed routing algorithm. © 2007 ACM.