Rent's rule based switching requirements
Author:
Open Access
- 1 March 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 197-204
Abstract
A Rent's Rule characterization of recursive bisection captures a measure of the locality in a netlist or graph. From this characterization, we know we can establish a lower bound on layout area implied by wiring. When applying this lower bound to the design of programmable or switched networks, we are ultimately concerned for both the switching requirements and the wiring requirements. Switch requirements are particularly important in conventional VLSI where (a) a switchpoint consumes considerably more area than a wire crossing and (b) switchpoints must reside on the active surface, whereas wiring may take place on any of several wire layers. The most straight-forward, limited-bisection switching networks have switching requirements which grow as $O(N^{2p})$, similar to wiring requirements. In practice, however, this leaves switching dominating wiring. We show that there are limited-bisection networks with $O(N)$ switching growth and highlight some of the tradeoffs between wire utilization and switching, routing complexity, routing guarantees, and switch latency within this design space.
Keywords
This publication has 10 references indexed in Scilit:
- Compact, multilayer layout for butterfly fat-tree2000
- Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% LUT utilization)1999
- Design of minimum and uniform bipartites for optimum connection blocks of FPGAIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997
- Entropy, counting, and programmable interconnect1996
- Graph based analysis of 2-D FPGA routingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1996
- A framework for solving VLSI graph layout problemsJournal of Computer and System Sciences, 1984
- Area-time complexity for VLSI1979
- SuperconcentratorsSIAM Journal on Computing, 1977
- On a Pin Versus Block Relationship For Partitions of Logic GraphsIEEE Transactions on Computers, 1971
- Permutation Groups, Complexes, and Rearrangeable Connecting NetworksBell System Technical Journal, 1964