Rent's rule based switching requirements

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.

REFERENCES

• 1: V.Benes Permutation groups,complexes,and rearrangeable multistage connecting networks.Bell System Technical Journal ,43:1619-1640,July 1964.
• 2: V.Benes Mathematical Theory of Connecting Networks and Telephone Tra .c .Academic Press,New York,NY,1965.
• 3: S.Bhatt and F.T.Leighton.Afamewokforsolving vlsi graph layout problems.Journal of Computer System Sciences ,28:300-343,1984.
• 4: André DeHon, Entropy, counting, and programmable interconnect, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.73-79, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228381]
• 5: André DeHon, Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% LUT utilization), Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.69-78, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296431]
• 6: André DeHon, Compact, multilayer layout for butterfly fat-tree, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.206-215, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341824]
• 7: K.Fujiyoshi,Y.Kajitani,and H.Niitsu.Design of minimum and uniform bipartites fo optimum connection blocks of fpga.IEEE Transactions on Computer-Aided Design of Integrated Circuits , 16(11):1377-1383,November 1997.
• 8: R.I.Greenberg and C.E.Leiserson.Randomness in Computation ,volume 5 of Advances in Computing Research ,chapte Randomized Routing on Fat-T ees. JAI Press,1988.Earlier version MIT/LCS/TM-307.
• 9: B.S.Landman and R .L.Russo.On pinvesus block relationship for partitions of logic circuits.IEEE Transactions on Computers ,20:1469-1479,1971.
• 10: F.T.Leighton.New lowe bound techniques fo vlsi. In Twenty-Second Annual Symposium on the Foundations of Computer Science .IEEE,1981.
• 11: N.Pippenger.Superconcent ators.SIAM Journal of Computing ,6(2):298-304,1977.
• 12: C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
• 13: Y.-L.Wu,D.Chang,M.Marek-Sadowska, and S.Tsukiyama.Not necessarily more switches more routability.In Proceedings of the 1996 Asia Paci .c Design Automation Conference ,1996.
• 14: Y.-L.Wu,S.Tsukiyama,and M.Marek-Sadowska. Graph based analysis of 2-d fpga outing.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems ,15(1):33-44,January 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Design, Performance, Theory

Keywords:
Rent's rule, hierarchical networks, switching requirements