On optimum designs of universal switch blocks

This paper presents a breakthrough decomposition theorem on routing topology and its applications in the designing of universal switch blocks. A switch block of k sides and 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 with channel density at most W. The optimum USB design problem is to design a (k, W)-USB with the minimum number of switches for every pair of (k, W). The problem was originated from designing better k sides switch modules for 2D-FPGAs, such as Xilinx XC4000-type FPGAs, where k > 4. The interests in the generic USBs come from their potential usages in multi-dimensional and some non-conventional 2D-FPGA architectures, and as an individual switch components. The optimum (k, W)-USB was solved previously for even W, but left open for odd W. Our new decomposition theorem states that when W (> +3-i), a (k, W) routing requirement ((k, W)-RR) can be decomposed into one (k,k+3-i/3)-RR and 3W-k+i-3/6(k, 2)-RRs, where 1 > i > 6 and k = i (mod 6). By this theorem and the previously established reduction design scheme, the USB design problem is reduced to its minimum kernel designs, that enables us to design the best approximated (k, W)-USBs for all odd W. We also run extensive routing experiments using the currently best known FPGA router VPR, and the MCNC circuits with the conventional disjoint switch blocks and two kinds of universal switch blocks. The experimental results show that both kinds of USBs consistently improve the entire chip routability by over 6% than the conventional switch blocks. © Springer-Verlag Berlin Heidelberg 2002.