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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations



Original languageEnglish
Article number1230811
Journal / PublicationACM Transactions on Design Automation of Electronic Systems
Issue number2
Publication statusPublished - 1 Apr 2007
Externally publishedYes


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.

Research Area(s)

  • FPGA architecture, Routing algorithm, Universal switch block