Abstract

Formulas are presented for the transformation of three-dimensional shuffle patterns into the two-dimensional domain. The results are applied to the transformation of the interstage patterns of three-dimensional multistage interconnection networks into their isomorphic two-dimensional patterns (and vice versa). This paper explains material in J. Giglmayr, “Classification scheme for 3-D shuffle interconnection patterns,” Appl. Opt. 28, 3120–3128 (1989) and corrects some algebraic results.

© 1992 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. T. J. Cloonan, F. B. McCormick, M. J. Herron, F. A. P. Tooley, G. W. Richards, E. Kerbis, J. L. Brubaker, A. L. Lentine, “A 3D crossover switching network based on S-SEED arrays,” in Photonics Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 196–199.
    [CrossRef]
  2. K. Padmanabhan, D. H. Lawrie, “A class of redundant multistage interconnection networks,” IEEE Trans. Comput. C-32, 1099–1108 (1983).
    [CrossRef]
  3. J. Giglmayr, “Classification scheme for 3-D shuffle interconnection patterns,” Appl. Opt. 28, 3120–3128 (1989).
    [CrossRef]
  4. M. Davio, “Kronecker products and shuffle algebra,” IEEE Trans. Comput. C-30, 116–125 (1981).
    [CrossRef]
  5. A. Graham, Kronecker Products and Matrix Calculus with Applications (Ellies Horwood, London, 1981), Chap. 1, pp. 24–25.
  6. M. C. Pease, “An adaption of the fast Fourier transform for parallel processing,” J. Assoc. Comput. Mach. 15, 252–264 (1968).
    [CrossRef]
  7. J. Giglmayr, “On the spatial extension of multistage interconnection networks,” in Technical Digest of the Topical Meeting on Photonic Switching (Optical Society of America, Washington, D.C., 1989), pp. 54–57.
  8. J. E. Eisele, R. M. Mason, Applied Matrix and Tensor Analysis (Wiley-Interscience, New York, 1970), Chap. 4, p. 216.
  9. J. Giglmayr, “Organization of k × k switches (k ≥ 4) interconnected by d-dimensional (d ≥ 2) regular optical patterns,” Appl. Opt. 30, 5119–5135.
  10. R. H. Bracewell, The Hartley Transform (Oxford U. Press, London, 1986), Chap. 7, p. 128 (German edition).

1989 (1)

1983 (1)

K. Padmanabhan, D. H. Lawrie, “A class of redundant multistage interconnection networks,” IEEE Trans. Comput. C-32, 1099–1108 (1983).
[CrossRef]

1981 (1)

M. Davio, “Kronecker products and shuffle algebra,” IEEE Trans. Comput. C-30, 116–125 (1981).
[CrossRef]

1968 (1)

M. C. Pease, “An adaption of the fast Fourier transform for parallel processing,” J. Assoc. Comput. Mach. 15, 252–264 (1968).
[CrossRef]

Bracewell, R. H.

R. H. Bracewell, The Hartley Transform (Oxford U. Press, London, 1986), Chap. 7, p. 128 (German edition).

Brubaker, J. L.

T. J. Cloonan, F. B. McCormick, M. J. Herron, F. A. P. Tooley, G. W. Richards, E. Kerbis, J. L. Brubaker, A. L. Lentine, “A 3D crossover switching network based on S-SEED arrays,” in Photonics Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 196–199.
[CrossRef]

Cloonan, T. J.

T. J. Cloonan, F. B. McCormick, M. J. Herron, F. A. P. Tooley, G. W. Richards, E. Kerbis, J. L. Brubaker, A. L. Lentine, “A 3D crossover switching network based on S-SEED arrays,” in Photonics Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 196–199.
[CrossRef]

Davio, M.

M. Davio, “Kronecker products and shuffle algebra,” IEEE Trans. Comput. C-30, 116–125 (1981).
[CrossRef]

Eisele, J. E.

J. E. Eisele, R. M. Mason, Applied Matrix and Tensor Analysis (Wiley-Interscience, New York, 1970), Chap. 4, p. 216.

Giglmayr, J.

J. Giglmayr, “Classification scheme for 3-D shuffle interconnection patterns,” Appl. Opt. 28, 3120–3128 (1989).
[CrossRef]

J. Giglmayr, “On the spatial extension of multistage interconnection networks,” in Technical Digest of the Topical Meeting on Photonic Switching (Optical Society of America, Washington, D.C., 1989), pp. 54–57.

J. Giglmayr, “Organization of k × k switches (k ≥ 4) interconnected by d-dimensional (d ≥ 2) regular optical patterns,” Appl. Opt. 30, 5119–5135.

Graham, A.

A. Graham, Kronecker Products and Matrix Calculus with Applications (Ellies Horwood, London, 1981), Chap. 1, pp. 24–25.

Herron, M. J.

T. J. Cloonan, F. B. McCormick, M. J. Herron, F. A. P. Tooley, G. W. Richards, E. Kerbis, J. L. Brubaker, A. L. Lentine, “A 3D crossover switching network based on S-SEED arrays,” in Photonics Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 196–199.
[CrossRef]

Kerbis, E.

T. J. Cloonan, F. B. McCormick, M. J. Herron, F. A. P. Tooley, G. W. Richards, E. Kerbis, J. L. Brubaker, A. L. Lentine, “A 3D crossover switching network based on S-SEED arrays,” in Photonics Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 196–199.
[CrossRef]

Lawrie, D. H.

K. Padmanabhan, D. H. Lawrie, “A class of redundant multistage interconnection networks,” IEEE Trans. Comput. C-32, 1099–1108 (1983).
[CrossRef]

Lentine, A. L.

T. J. Cloonan, F. B. McCormick, M. J. Herron, F. A. P. Tooley, G. W. Richards, E. Kerbis, J. L. Brubaker, A. L. Lentine, “A 3D crossover switching network based on S-SEED arrays,” in Photonics Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 196–199.
[CrossRef]

Mason, R. M.

J. E. Eisele, R. M. Mason, Applied Matrix and Tensor Analysis (Wiley-Interscience, New York, 1970), Chap. 4, p. 216.

McCormick, F. B.

T. J. Cloonan, F. B. McCormick, M. J. Herron, F. A. P. Tooley, G. W. Richards, E. Kerbis, J. L. Brubaker, A. L. Lentine, “A 3D crossover switching network based on S-SEED arrays,” in Photonics Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 196–199.
[CrossRef]

Padmanabhan, K.

K. Padmanabhan, D. H. Lawrie, “A class of redundant multistage interconnection networks,” IEEE Trans. Comput. C-32, 1099–1108 (1983).
[CrossRef]

Pease, M. C.

M. C. Pease, “An adaption of the fast Fourier transform for parallel processing,” J. Assoc. Comput. Mach. 15, 252–264 (1968).
[CrossRef]

Richards, G. W.

T. J. Cloonan, F. B. McCormick, M. J. Herron, F. A. P. Tooley, G. W. Richards, E. Kerbis, J. L. Brubaker, A. L. Lentine, “A 3D crossover switching network based on S-SEED arrays,” in Photonics Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 196–199.
[CrossRef]

Tooley, F. A. P.

T. J. Cloonan, F. B. McCormick, M. J. Herron, F. A. P. Tooley, G. W. Richards, E. Kerbis, J. L. Brubaker, A. L. Lentine, “A 3D crossover switching network based on S-SEED arrays,” in Photonics Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 196–199.
[CrossRef]

Appl. Opt. (2)

IEEE Trans. Comput. (2)

M. Davio, “Kronecker products and shuffle algebra,” IEEE Trans. Comput. C-30, 116–125 (1981).
[CrossRef]

K. Padmanabhan, D. H. Lawrie, “A class of redundant multistage interconnection networks,” IEEE Trans. Comput. C-32, 1099–1108 (1983).
[CrossRef]

J. Assoc. Comput. Mach. (1)

M. C. Pease, “An adaption of the fast Fourier transform for parallel processing,” J. Assoc. Comput. Mach. 15, 252–264 (1968).
[CrossRef]

Other (5)

J. Giglmayr, “On the spatial extension of multistage interconnection networks,” in Technical Digest of the Topical Meeting on Photonic Switching (Optical Society of America, Washington, D.C., 1989), pp. 54–57.

J. E. Eisele, R. M. Mason, Applied Matrix and Tensor Analysis (Wiley-Interscience, New York, 1970), Chap. 4, p. 216.

T. J. Cloonan, F. B. McCormick, M. J. Herron, F. A. P. Tooley, G. W. Richards, E. Kerbis, J. L. Brubaker, A. L. Lentine, “A 3D crossover switching network based on S-SEED arrays,” in Photonics Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 196–199.
[CrossRef]

R. H. Bracewell, The Hartley Transform (Oxford U. Press, London, 1986), Chap. 7, p. 128 (German edition).

A. Graham, Kronecker Products and Matrix Calculus with Applications (Ellies Horwood, London, 1981), Chap. 1, pp. 24–25.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (7)

Fig. 1
Fig. 1

Interconnection of two 4 × 4 data arrays according to Eqs. (3)(5): (a) The interconnection pattern in Eq. (3). [Four columns (rows) on the lhs and four rows (columns) on the rhs are shuffled according to the S(2, 2) pattern. Then the first element of each column (row) is interconnected with the first row (column) shuffle, the second element of each column (row) is interconnected with the second row (column) shuffle, etc. The corresponding interconnection pattern that is transformed into the plane is an S(4, 4) pattern that is located in the center. The dotted interconnection pattern shows the relationship with Fig. 1(b).] (b) The derivation of the patterns in Eqs. (4) and (5). [The pattern on the lhs is obtained by applying Eq. (1). The pattern on the rhs is obtained by applying Eq. (2).]

Fig. 2
Fig. 2

Patterns for the interconnection of two 6 × 6 data arrays: (a) The 2-D SGPS. (b) The 2-D SGIS. (c) The 2-D GMS. [On the lhs (rhs) the shuffle is defined on the second (first) coordinate and the inverse shuffle is defined on the first (second) coordinate.]

Fig. 3
Fig. 3

Transformed patterns for the interconnection of two 6 × 6 data arrays. (The arrows indicate the interconnections that are discussed in Example 3.) (a) The transformed S2-DSGPS(2, 3; 2, 3) pattern. (b) The transformed S2-DSGIS(2, 3; 2, 3) pattern. (c) The transformed S2-DGMS(2, 3; 2, 3) patterns. [The lhs (rhs) corresponds with the lhs (rhs) in Fig. 3(c).]

Fig. 4
Fig. 4

Equivalence between the original 3-D patterns and the transformed patterns for the interconnection of 6 × 6 data arrays. (a) Input (output) MRN data array for an S2-DSGPS(2, 3; 2, 3) [S2-DSGIS(2, 3; 2, 3)] pattern. (b) Output (input) MRN data array for a S2-DSGIS(2, 3; 2, 3) [S2-DSGPS(2, 3; 2, 3)] pattern. (c) Row-major numbered data array. (d) Column-major numbered data array.

Fig. 5
Fig. 5

Switch-preserving transformation of a 3-D shuffle pattern for the interconnection of two 4 × 4 data arrays. (a) S2-DSGPS(2, 2; 2, 2) and the row-major numbering of the switches from A to D. (b) The transformed SGPS pattern and its relationship to the 4 × 4 switches (A–D). (c) Row-major numbering of the 4 × 4 data array. (The 3-D pattern is transformed into the 2-D domain by being stretched into the equivalent 1-D pattern shown by the dashed curve or, alternatively, the 1-D pattern overlaps into the 3-D physical space shown by the dashed curve.) (d) The transformed pattern that preserves the 4 × 4 switches (A–P). [The numbers refer to the data array in (c).]

Fig. 6
Fig. 6

Switch-preserving transformation of a 3-D shuffle pattern for the interconnection of two 8 × 8 data arrays. (a) Row-major numbering of the 4 × 4 switches (A–P) for the interconnection of two data arrays of 8 × 8 size. (b) Row-major numbering of the 8 × 8 data array. (The 3-D pattern is transformed into the 2-D domain by being stretched into the equivalent 1-D pattern shown by the dashed curve or, alternatively; the 1-D pattern overlaps into the 3-D physical space shown by the dashed curve.) (c) The transformed S2-DSGPS(2, 4; 2, 4) pattern and its relationship to the 4 × 4 switches (A–P). (The assignment of a switch to two lines indicates that the switch is subdivided.) (d) The transformed pattern that preserves the 4 × 4 switches (A–P). [The decimal numbers refer to the data array in (b). If the same procedure is applied to S2-DSGIS(2, 4; 2, 4) = S(4, 2) ⊗ S(4, 2), the transformed switch-preserving pattern is S(16, 4), which is the same pattern as seen from the rhs.]

Fig. 7
Fig. 7

Kronecker products AB (top) and BA (bottom) of 2 × 2 matrices that show the validity of Eq. (1). [S2-D(2, 2; 2, 2) indicates that the elements in the four corners remain unchanged, the second and third elements in the first and fourth rows (columns) are simply exchanged, and the inner four elements are exchanged diagonally [see Fig. 5(a)].

Equations (10)

Equations on this page are rendered with MathJax. Learn more.

A B = S 2 - D SGPS ( r a , r b ; c a , c b ) ( B A ) = ( B A ) S 2 - D SGPS ( r a , r b ; c a c b ) ,
1 2 M = [ M 0 0 M ] ,
M 1 2 = ( m 11 1 2 m 12 1 2 m 21 1 2 m 22 1 2 ) .
( A 1 m ) ( 1 n B ) = A B
S 2 - D NSGPS ( m 1 , m 2 ; n 1 , n 2 ) = [ 1 n 1 n 2 S ( m 1 , m 2 ) ] × S ( n 1 n 2 , m 1 m 2 ) [ 1 m 1 m 2 S ( n 1 , n 2 ) ] .
S 2 - D NSGPS ( m 1 , m 2 ; n 1 , n 2 ) = S ( n 1 , n 2 ) S ( m 1 , m 2 )
= S ( m 1 , m 2 ) S ( n 1 , n 2 ) .
S 2 - D NSGIS ( m 1 , m 2 ; n 1 , n 2 ) = S ( m 2 , m 1 ) S ( n 2 , n 1 ) ,
S 2 - D GMS ( m 1 , m 2 ; n 1 , n 2 ) = S ( m 1 , m 2 ) S ( n 2 , n 1 ) ,
= S ( m 2 , m 1 ) S ( n 2 , n 1 ) .

Metrics