New layouts for the shuffle-exchange graph(Extended Abstract)

ABSTRACT

In this extended abstract, we present several new layouts for the shuffle-exchange graph, including one which requires only 0(n2/log2n) area. The optimal layout is described and analyzed in section 3. The analysis is heavily dependent on several combinatorial results which we state in section 2 and prove in the appendix. The other layouts are described in section 4. Although these layouts are not asymptotically optimal (most require 0(n2/log3/2n) area), the theory behind their development is interesting and may eventually lead to good practical layouts as well as other asymptotically optimal layouts.

REFERENCES

• 1: D. Hoey and C.E. Leiserson, "A Layout for the Shuffle-Exchange Network," Proceeding of the 1980 International Conference on Parallel Processing.
• 2: D. Kleitman, F.T. Leighton, G.L. Miller and M. Lepley are in the process of writing several MIT tech reports on layouts for the shuffle-exchange graph.
• 3: C.E. Leiserson, "Area-efficient graph layouts (for VLSI)," 21st Annual Symposium on Foundations of Computer Science, IEEE Computer Society. (October 1980).
• 4: D.S. Parker, "Notes on Shuffle-Exchange Type Switching Networks," IEEE Transactions on Computers, C-29, 3 (March 1980), pp. 213-222.
• 5: F.P. Preparata and J. Vuillemin, The cube-connected-cycles: a versatile network for parallel computation. Technical Report 356, Institut de Recherche d'Informatique et d'Automatique (June 1979).
• 6: M. Rodch and D. Steinberg, personal communication of a result submitted to IEEE Transactions on Computers.
• 7: H.S. Stone, "Parallel processing with the perfect shuffle," IEEE Transactions on Computers, C-20, 2 (February 1971), pp. 153-161.
• 8: Clark David Thompson, A complexity theory for vlsi, 1980

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  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
      G.2.1 Combinatorics
          Subjects: Permutations and combinations
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Design, Theory