On optimum designs of universal switch blocks

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

1 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationField-Programmable Logic and Applications: Reconfigurable Computing is Going Mainstream
Subtitle of host publication12th International Conference, FPL 2002, Proceedings
PublisherSpringer Verlag
Pages142-151
Volume2438 LNCS
ISBN (Print)3540441085, 9783540441083
Publication statusPublished - 2002
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2438 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title12th International Conference on Field-Programmable Logic and Applications, FPL 2002
PlaceFrance
CityMontpellier
Period2 - 4 September 2002

Abstract

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.

Research Area(s)

  • FPGA architecture, Routing, Universal switch block

Citation Format(s)

On optimum designs of universal switch blocks. / Fan, Hongbing; Liu, Jiping; Wu, Yu-Liang; Cheung, Chak-Chung.

Field-Programmable Logic and Applications: Reconfigurable Computing is Going Mainstream: 12th International Conference, FPL 2002, Proceedings. Vol. 2438 LNCS Springer Verlag, 2002. p. 142-151 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2438 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review