Name
Abstract | ||
|---|---|---|
A k-side switch block with W terminals per side is said to be a universal switch block ((k, W)-USB) if every set of the nets satisfying the routing constraint (i.e., the number of nets on each side is at most W) is simultaneously routable through the switch block. The (4, W)-USB was originated by designing better switch modules for 2-D FPGAs, such as Xilinx XC4000-type FPGAs, whereas the generic USBs can be applied in multidimensional or some nonconventional 2-D FPGA architectures. The problem we study in this article is to design (k, W)-USBs with the minimum number of switches for any given pair of (k, W). We provide graph models for routing requirements and switch blocks and develop a series of decomposition theorems for routing requirements with the help of a new graph model. The powerful decomposition theory leads to the automatic generation of routing requirements and a detailed routing algorithm, as well as the reduction design method of building large USBs by smaller ones. As a result, we derive a class of well-structured and highly scalable optimum (k, W)-USBs for k ≤ 6, or even Ws, and near-optimum (k, W)-USBs for k ≥ 7 and odd Ws. We also give routing experiments to justify the routing improvement upon the entire chip using the USBs. The results demonstrate the usefulness of USBs. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1145/605440.605443 | ACM Trans. Design Autom. Electr. Syst. |
Keywords | Field | DocType |
2-d fpgas,routing improvement,routing,generic usbs,switch module,detailed routing algorithm,routing constraint,switch block,fpga architecture design,reduction design,decomposition,generic universal switch block,routing requirement,universal switch block,large usbs,better switch module,k-side switch block,satisfiability,chip,design method | Graph,Link-state routing protocol,Computer science,Parallel computing,Field-programmable gate array,Chip,Real-time computing,Graph model,USB,Routing algorithm,Scalability | Journal |
Volume | Issue | ISSN |
7 | 4 | 1084-4309 |
Citations | PageRank | References |
10 | 0.69 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hongbing Fan | 1 | 189 | 19.69 |
| Jiping Liu | 2 | 216 | 18.47 |
| Yu-liang Wu | 3 | 316 | 37.60 |
| C. K. Wong | 4 | 1459 | 513.44 |