VLSI layout and packaging of butterfly networks

ABSTRACT

We present a scheme for optimal VLSI layout and packaging of butterfly networks under the Thompson model, the multilayer grid model, and the hierarchical layout model. We show that when L layers of wires are available, an N-node butterfly network can be laid out with area 4N2/L2 log22 N + o (N2/L2 log2 N), maximum wire length 2N/L log2 N + o (N/L log N), and volume 4N2/L log22 N + o (N2/L log2 N) , under the multilayer 2-D grid model, where only one active layer (for network nodes) is required and L layers of wires are available. Our layout scheme allows us to partition an N-node butterfly network into &THgr;(N1-1/l N)-node clusters with an average of dic ≈ 4l-4/log2 N (=O(1/log N) for any constant integer l) inter-cluster links per node, leading to optimal layout and packaging at the same time under the hierarchical layout model. The scalability of our layouts are optimal in that we can allow each of O(N/ log N) nodes to occupy an area as large as o (N/L2 log N) and each of the remaining N - o(N) network nodes to occupy an area as large as o (N/L2 log2 N), without increasing the leading constants of layout area, volume, or maximum wire length.

REFERENCES

• 1: Avior, A., T. Calamoneri, S. Even, A. Litman, and A. Rosenberg, "A tight layout of the butterfly network," Theory Cornput. Sys., vol. 31, no. 4, 1998, pp. 475-488.
• 2: Debashis Basak , Dhabaleswar K. Panda, Designing Clustered Multiprocessor Systems under Packaging and Technological Advancements, IEEE Transactions on Parallel and Distributed Systems, v.7 n.9, p.962-978, September 1996 [doi>10.1109/71.536940 ]
• 3: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 4: Bhuyan, L.N. and D.P. Agrawal, "Generalized hypercube and hyperbus structures for a computer network," IEEE Trans. Cornput., vol. 33, no. 4, Apr. 1984, pp. 323-333.
• 5: M. L. Brady , M. Sarrafzadeh, Stretching a Knock-Knee Layout for Multilayer Wiring, IEEE Transactions on Computers, v.39 n.1, p.148-151, January 1990 [doi>10.1109/12.46293 ]
• 6: Chienhua Chen , Dharma P. Agrawal , J. Richard Burke, dBCube: A New Class of Hierarchical Multiprocessor Interconnection Networks with Area Efficient Layout, IEEE Transactions on Parallel and Distributed Systems, v.4 n.12, p.1332-1344, December 1993 [doi>10.1109/71.250115 ]
• 7: Guihai Chen , Francis C. M. Lau, Tighter Layouts of the Cube-Connected Cycles, IEEE Transactions on Parallel and Distributed Systems, v.11 n.2, p.182-191, February 2000 [doi>10.1109/71.841753 ]
• 8: Robert Cypher, Theoretical aspects of VLSI pin limitations, SIAM Journal on Computing, v.22 n.2, p.356-378, April 1993 [doi>10.1137/0222027]
• 9: William J. Dally , Steve Lacy, VLSI Architecture: Past, Present, and Future, Proceedings of the 20th Anniversary Conference on Advanced Research in VLSI, p.232, March 21-24, 1999
• 10: Yefim Dinitz , Shimon Even , Roni Kupershtok , Maria Zapolotsky, Some compact layouts of the butterfly, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.54-63, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305626]
• 11: Shimon Even , S. Muthukrishnan , Michael S. Paterson , Süleyman Cenk Sahinalp, Layout of the batcher bitonic sorter (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.172-181, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277683]
• 12: Antonio Fernández , Kemal Efe, Efficient VLSI Layouts for Homogeneous Product Networks, IEEE Transactions on Computers, v.46 n.10, p.1070-1082, October 1997 [doi>10.1109/12.628392 ]
• 13: Franklin, M.A., D.F. Warm, and W.J. Thomas, "Pin limitations and partitioning of VLSI interconnection networks," IEEE Trans. Computer, vol. C-31, Nov. 1982, pp. 1109-1116.
• 14: Kogge, P.M., "EXECUBE - a new architecture for scalable MPPs," Proc. Int'l Conf. Parallel Processing, vol. I, 1994, pp. 77-84.
• 15: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 16: S. Muthukrishnan , Mike Paterson , Süleyman Cenk Sahinalp , Torsten Suel, Compact grid layouts of multi-level networks, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.455-463, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301372]
• 17: Behrooz Parhami, Introduction to Parallel Processing: Algorithms and Architectures, Kluwer Academic Publishers, Norwell, MA, 1999
• 18: Thomas Sterling , Paul Messina , Paul H. Smith, Enabling technologies for petaflops computing, MIT Press, Cambridge, MA, 1995
• 19: 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]
• 20: Clark David Thompson, A complexity theory for vlsi, 1980
• 21: Wise, D.S., "Compact layouts of banyan/FFT networks," VLSI Systems and Computations, Computer Science Press, 1981, pp. 186-195.
• 22: Yeh, C.-H. and B. Parhami, "A class of parallel architectures for fast Fourier transform," Proc. Midwest Syrup. Circuits and Systems, Aug. 1996, pp. 856-859.
• 23: Chi-Hsiang Yeh , Behrooz Parhami, Recursive Hierarchical Swapped Networks: Versatile Interconnection Architectures for Highly Parallel Systems, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.453, October 23-26, 1996
• 24: Chi-Hsiang Yeh , Behrooz Parhami , Emmanouel (Manos) Varvarigos, Efficient low-degree interconnection networks for parallel processing: topologies, algorithms, vlsi layouts, and fault tolerance, 1998
• 25: Chi-Hsiang Yeh , Behrooz Parhami, VLSI layouts of complete graphs and star graphs, Information Processing Letters, v.68 n.1, p.39-45, Oct. 15, 1998 [doi>10.1016/S0020-0190(98)00133-1 ]
• 26: C. -H. Yeh , E. A. Varvarigos , B. Parhami, Efficient VLSI Layouts of Hypercubic Networks, Proceedings of the The 7th Symposium on the Frontiers of Massively Parallel Computation, p.98, February 21-25, 1999
• 27: Chi-Hsiang Yeh , Behrooz Parhami , Emmanouel A. Varvarigos, The Recursive Grid Layout Scheme for VLSI Layout of Hierarchical Networks, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.441, April 12-16, 1999
• 28: Yeh, C.-H. and B. Parhami, "A unified model for hierarchical networks based on an extension of Cayley graphs," IEEE Trans. Parallel Distrib. Sys., to appear.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout
  B.8 Performance and Reliability

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Measurement, Performance, Theory