Abstract

The need for d-dimensional (d ≥ 3) interconnection patterns occurs if d-dimensional data cubes have to be interconnected. The formal definition of such patterns, presented here, is based on the mixed radix numbering of the d-tuple data points. Because each coordinate of a d-dimensional data cube may be factorized in a different way, a family of interconnection patterns is obtained that increases with respect to the dimension of the data cubes. The properties of d-dimensional patterns are analyzed, and their realization in the frequency domain is described. Methods for the three-dimensional layout of the patterns are presented. The application of d-dimensional patterns within multistage interconnection networks is discussed.

© 1992 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. D. A. B. Miller, “Optoelectronic applications of quantum wells,” Opt. Photon. News 1(1), 7–14 (1990).
    [CrossRef]
  2. J. W. Goodman, “Optical interconnections in the ’80’s,” Opt. Photon. News 1(12), 21–23 (1990).
    [CrossRef]
  3. J. W. Goodman, “Integrated photonics and optical computing,” in Technical Digest on Integrated Photonics Research, Vol. 8 of OSA 1991 Technical Digest Series (Optical Society of America, Washington, D.C., 1991), paper WA1.
  4. J. Giglmayr, “Higher-dimensional interconnection patterns (dim ≥ 3), their topology and performance,” presented at the Tagung der Deutschen Gesellschaft für Angewandte Optik, 16–20 May 1989, Berlin.
  5. A. Aggarwal, J. Park, “Notes on searching in multidimensional monotone arrays,” in Proceedings of the 29th Annual Symposium on Foundations of Computer Science (Institute of Electrical and Electronics Engineers, New York, 1988), pp. 497–512.
    [CrossRef]
  6. B. K. Jenkins, P. Chavel, R. Forchheimer, A. A. Sawchuk, T. C. Strand, “Architectural implications of a digital optical processor,” Appl. Opt. 23, 3465–3474 (1984).
    [CrossRef] [PubMed]
  7. D. G. Antzoulatos, “Kronecker and array algebra for parallel image processing,” Ph.D. dissertation, Report 135 (University of Southern California, Los Angeles, Calif., 1988).
  8. A. A. Sawchuk, I. Glaser, “Geometries for optical implementations of the perfect shuffle,” in Optical Computing ’88, P. Chavel, J. W. Goodman, G. Roblin, eds., Proc. Soc. Photo-Opt. Instrum. Eng.963, 270–279 (1988).
    [CrossRef]
  9. S.-H. Lin, T. F. Krile, J. F. Walkup, “Two-dimensional optical Clos interconnection network and its uses,” Appl. Opt. 27, 1734–1741 (1988).
    [CrossRef] [PubMed]
  10. T. J. Cloonan, M. J. Herron, “Optical implementation and performance of one-dimensional and two-dimensional trimmed inverse augmented data manipulator networks for multiprocessor systems,” Opt. Eng. 28, 305–314 (1989).
  11. H. S. Hinton, “Overview of free-space photonic switching,” in Technical Digest of the 1990 International Topical Meeting on Photonic Switching (Institute of Electronics, Information, and Communication Engineers, Tokyo, 1990), paper 12D-1.
  12. T. J. Cloonan, F. B. McCormick, “Photonic switching applications of 2-D and 3-D crossover networks based on 2-input, 2-output switching nodes,” Appl. Opt. 30, 2309–2323 (1991).
    [CrossRef] [PubMed]
  13. A. W. Lohmann, “What classical optics can do for the digital optical computer,” Appl. Opt. 25, 1543–1549 (1986).
    [CrossRef] [PubMed]
  14. A. W. Lohmann, W. Stork, G. Stucke, “Optical perfect shuffle,” Appl. Opt. 25, 1530–1531 (1986).
    [CrossRef] [PubMed]
  15. G. E. Lohman, A. W. Lohmann, “Optical interconnection network utilizing diffraction gratings,” Opt. Eng. 27, 893–900 (1988).
  16. K.-H. Brenner, A. Huang, “Optical implementation of the perfect shuffle interconnection,” Appl. Opt. 27, 135–137 (1988).
    [CrossRef] [PubMed]
  17. C. W. Stirk, R. A. Athale, M. W. Haney, “Folded perfect shuffle optical processor,” Appl. Opt. 27, 202–203 (1988).
    [CrossRef] [PubMed]
  18. J. Jahns, M. J. Murdocca, “Crossover networks and their optical implementation,” Appl. Opt. 27, 3155–3160 (1988).
    [CrossRef] [PubMed]
  19. T. Kumagai, K. Ikegaya, “Organization of two-dimensional Omega networks,” Syst. Comput. Jpn. 17, 1–10 (1986).
    [CrossRef]
  20. J. Giglmayr, “Classification scheme for 3-D shuffle interconnection patterns,” Appl. Opt. 28, 3120–3128 (1989).
    [CrossRef]
  21. J. Giglmayr, “Transformation of three-dimensional shuffle patterns,” Appl. Opt. 31, 1709–1716 (1992).
    [CrossRef]
  22. T. H. Szymanski, V. C. Hamacher, “On the permutation capability of multistage interconnection networks,” IEEE Trans. Comput. C-36, 810–822 (1987).
    [CrossRef]
  23. S. C. Kothari, A. Jhunjhunwala, A. Mukherjee, “Performance analysis of multipath multistage interconnection networks,” in Performance Evaluation Review, Proceedings of the 1988 ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, (Association for Computing Machinery, New York, 1988), pp. 124–132.
    [CrossRef]
  24. K. Y. Lee, “Interconnection networks and compiler algorithms for multiprocessors,” Ph.D. dissertation (University of Illinois at Urbana–Champaign, Urbana–Champaign, Ill., 1983).
  25. H. H. Szu, H. J. Caulfield, “The mutual time-frequency content of two signals,” Proc. IEEE 72, 902–908 (1984).
    [CrossRef]
  26. J. Giglmayr, “Organization of k × k switches (k ≥ 4) interconnected by d-dimensional (d ≥ 2) regular optical patterns,” Appl. Opt. 30, 5119–5135 (1991).
    [CrossRef]
  27. J. Giglmayr, “Multistage interconnection networks and d-dimensional architectures,” in Photonic Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 220–224.
    [CrossRef]
  28. J. E. Midwinter, “Novel approach to the design of optically activated wideband switching matrices,” Proc. Inst. Electr. Eng. Part J 134, 261–268 (1987).
  29. N. Ling, M. A. Bayoumi, “Algorithms for high speed multi-dimensional arithmetic and DSP systolic arrays,” in Proceedings of the 1988 International Conference on Parallel Processing, F. A. Briggs, ed. (Pennsylvania State U. Press, University Park, Pa., 1988), pp. 367–374.
  30. D. H. Lawrie, “Access and alignment of data in an array processor,” IEEE Trans. Comput. C-24, 1145–1155 (1975).
    [CrossRef]
  31. L. N. Bhunyan, D. P. Agrawal, “Design and performance of generalized interconnection networks,” IEEE Trans. Comput. C-32, 1081–1090 (1983).
    [CrossRef]
  32. M. Davio, “Kronecker products and shuffle algebra,” IEEE Trans. Comput. C-30, 116–125 (1981).
    [CrossRef]
  33. J. Giglmayr, “Spatial extension of multistage interconnection networks,” in Proceedings on Photonic Switching, J. E. Midwinter, H. S. Hinton, eds., Vol. 3 of OSA 1989 Proceedings Series (Optical Society of America, Washington, D.C., 1989), pp. 170–179.
  34. K. Sapiecha, R. Jarocki, “Modular architecture for high performance implementation of FFT algorithm,” in Proceedings of the 13th Annual International Symposium on Computer Architecture (Institute of Electrical and Electronics Engineers, New York, 1986), pp. 261–270.
  35. S.-T. Huang, S. K. Tripathi, “Finite state model and compatibility theory: new analysis tools for permutation networks,” IEEE Trans. Comput. C-35, 591–601 (1986).
    [CrossRef]
  36. E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.
  37. G. Grosskopf, R. Ludwig, R. Schnabel, N. Schunk, H. G. Weber, “Frequency conversion by four-wave-mixing in LD amplifiers,” in Photonic Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 226–232.
    [CrossRef]
  38. M. G. Taylor, J. E. Midwinter, “Optically interconnected switching networks,” IEEE J. Lightwave Technol. 9, 791–798 (1991).
    [CrossRef]

1992 (1)

1991 (3)

1990 (2)

D. A. B. Miller, “Optoelectronic applications of quantum wells,” Opt. Photon. News 1(1), 7–14 (1990).
[CrossRef]

J. W. Goodman, “Optical interconnections in the ’80’s,” Opt. Photon. News 1(12), 21–23 (1990).
[CrossRef]

1989 (2)

T. J. Cloonan, M. J. Herron, “Optical implementation and performance of one-dimensional and two-dimensional trimmed inverse augmented data manipulator networks for multiprocessor systems,” Opt. Eng. 28, 305–314 (1989).

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

1988 (5)

1987 (2)

J. E. Midwinter, “Novel approach to the design of optically activated wideband switching matrices,” Proc. Inst. Electr. Eng. Part J 134, 261–268 (1987).

T. H. Szymanski, V. C. Hamacher, “On the permutation capability of multistage interconnection networks,” IEEE Trans. Comput. C-36, 810–822 (1987).
[CrossRef]

1986 (4)

A. W. Lohmann, “What classical optics can do for the digital optical computer,” Appl. Opt. 25, 1543–1549 (1986).
[CrossRef] [PubMed]

A. W. Lohmann, W. Stork, G. Stucke, “Optical perfect shuffle,” Appl. Opt. 25, 1530–1531 (1986).
[CrossRef] [PubMed]

T. Kumagai, K. Ikegaya, “Organization of two-dimensional Omega networks,” Syst. Comput. Jpn. 17, 1–10 (1986).
[CrossRef]

S.-T. Huang, S. K. Tripathi, “Finite state model and compatibility theory: new analysis tools for permutation networks,” IEEE Trans. Comput. C-35, 591–601 (1986).
[CrossRef]

1984 (2)

1983 (1)

L. N. Bhunyan, D. P. Agrawal, “Design and performance of generalized interconnection networks,” IEEE Trans. Comput. C-32, 1081–1090 (1983).
[CrossRef]

1981 (1)

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

1975 (1)

D. H. Lawrie, “Access and alignment of data in an array processor,” IEEE Trans. Comput. C-24, 1145–1155 (1975).
[CrossRef]

Aggarwal, A.

A. Aggarwal, J. Park, “Notes on searching in multidimensional monotone arrays,” in Proceedings of the 29th Annual Symposium on Foundations of Computer Science (Institute of Electrical and Electronics Engineers, New York, 1988), pp. 497–512.
[CrossRef]

Agrawal, D. P.

L. N. Bhunyan, D. P. Agrawal, “Design and performance of generalized interconnection networks,” IEEE Trans. Comput. C-32, 1081–1090 (1983).
[CrossRef]

Antzoulatos, D. G.

D. G. Antzoulatos, “Kronecker and array algebra for parallel image processing,” Ph.D. dissertation, Report 135 (University of Southern California, Los Angeles, Calif., 1988).

Athale, R. A.

Bachus, E.-J.

E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.

Bayoumi, M. A.

N. Ling, M. A. Bayoumi, “Algorithms for high speed multi-dimensional arithmetic and DSP systolic arrays,” in Proceedings of the 1988 International Conference on Parallel Processing, F. A. Briggs, ed. (Pennsylvania State U. Press, University Park, Pa., 1988), pp. 367–374.

Bhunyan, L. N.

L. N. Bhunyan, D. P. Agrawal, “Design and performance of generalized interconnection networks,” IEEE Trans. Comput. C-32, 1081–1090 (1983).
[CrossRef]

Braun, R.-P.

E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.

Brenner, K.-H.

Caspar, C.

E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.

Caulfield, H. J.

H. H. Szu, H. J. Caulfield, “The mutual time-frequency content of two signals,” Proc. IEEE 72, 902–908 (1984).
[CrossRef]

Chavel, P.

Cloonan, T. J.

T. J. Cloonan, F. B. McCormick, “Photonic switching applications of 2-D and 3-D crossover networks based on 2-input, 2-output switching nodes,” Appl. Opt. 30, 2309–2323 (1991).
[CrossRef] [PubMed]

T. J. Cloonan, M. J. Herron, “Optical implementation and performance of one-dimensional and two-dimensional trimmed inverse augmented data manipulator networks for multiprocessor systems,” Opt. Eng. 28, 305–314 (1989).

Davio, M.

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

Foisel, H.-M.

E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.

Forchheimer, R.

Giglmayr, J.

J. Giglmayr, “Transformation of three-dimensional shuffle patterns,” Appl. Opt. 31, 1709–1716 (1992).
[CrossRef]

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

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

J. Giglmayr, “Multistage interconnection networks and d-dimensional architectures,” in Photonic Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 220–224.
[CrossRef]

J. Giglmayr, “Spatial extension of multistage interconnection networks,” in Proceedings on Photonic Switching, J. E. Midwinter, H. S. Hinton, eds., Vol. 3 of OSA 1989 Proceedings Series (Optical Society of America, Washington, D.C., 1989), pp. 170–179.

J. Giglmayr, “Higher-dimensional interconnection patterns (dim ≥ 3), their topology and performance,” presented at the Tagung der Deutschen Gesellschaft für Angewandte Optik, 16–20 May 1989, Berlin.

Glaser, I.

A. A. Sawchuk, I. Glaser, “Geometries for optical implementations of the perfect shuffle,” in Optical Computing ’88, P. Chavel, J. W. Goodman, G. Roblin, eds., Proc. Soc. Photo-Opt. Instrum. Eng.963, 270–279 (1988).
[CrossRef]

Goodman, J. W.

J. W. Goodman, “Optical interconnections in the ’80’s,” Opt. Photon. News 1(12), 21–23 (1990).
[CrossRef]

J. W. Goodman, “Integrated photonics and optical computing,” in Technical Digest on Integrated Photonics Research, Vol. 8 of OSA 1991 Technical Digest Series (Optical Society of America, Washington, D.C., 1991), paper WA1.

Grosskopf, G.

G. Grosskopf, R. Ludwig, R. Schnabel, N. Schunk, H. G. Weber, “Frequency conversion by four-wave-mixing in LD amplifiers,” in Photonic Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 226–232.
[CrossRef]

Hamacher, V. C.

T. H. Szymanski, V. C. Hamacher, “On the permutation capability of multistage interconnection networks,” IEEE Trans. Comput. C-36, 810–822 (1987).
[CrossRef]

Haney, M. W.

Heimes, K.

E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.

Herron, M. J.

T. J. Cloonan, M. J. Herron, “Optical implementation and performance of one-dimensional and two-dimensional trimmed inverse augmented data manipulator networks for multiprocessor systems,” Opt. Eng. 28, 305–314 (1989).

Hinton, H. S.

H. S. Hinton, “Overview of free-space photonic switching,” in Technical Digest of the 1990 International Topical Meeting on Photonic Switching (Institute of Electronics, Information, and Communication Engineers, Tokyo, 1990), paper 12D-1.

Huang, A.

Huang, S.-T.

S.-T. Huang, S. K. Tripathi, “Finite state model and compatibility theory: new analysis tools for permutation networks,” IEEE Trans. Comput. C-35, 591–601 (1986).
[CrossRef]

Ikegaya, K.

T. Kumagai, K. Ikegaya, “Organization of two-dimensional Omega networks,” Syst. Comput. Jpn. 17, 1–10 (1986).
[CrossRef]

Jahns, J.

Jarocki, R.

K. Sapiecha, R. Jarocki, “Modular architecture for high performance implementation of FFT algorithm,” in Proceedings of the 13th Annual International Symposium on Computer Architecture (Institute of Electrical and Electronics Engineers, New York, 1986), pp. 261–270.

Jenkins, B. K.

Jhunjhunwala, A.

S. C. Kothari, A. Jhunjhunwala, A. Mukherjee, “Performance analysis of multipath multistage interconnection networks,” in Performance Evaluation Review, Proceedings of the 1988 ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, (Association for Computing Machinery, New York, 1988), pp. 124–132.
[CrossRef]

Keil, N.

E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.

Kothari, S. C.

S. C. Kothari, A. Jhunjhunwala, A. Mukherjee, “Performance analysis of multipath multistage interconnection networks,” in Performance Evaluation Review, Proceedings of the 1988 ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, (Association for Computing Machinery, New York, 1988), pp. 124–132.
[CrossRef]

Krile, T. F.

Kumagai, T.

T. Kumagai, K. Ikegaya, “Organization of two-dimensional Omega networks,” Syst. Comput. Jpn. 17, 1–10 (1986).
[CrossRef]

Lawrie, D. H.

D. H. Lawrie, “Access and alignment of data in an array processor,” IEEE Trans. Comput. C-24, 1145–1155 (1975).
[CrossRef]

Lee, K. Y.

K. Y. Lee, “Interconnection networks and compiler algorithms for multiprocessors,” Ph.D. dissertation (University of Illinois at Urbana–Champaign, Urbana–Champaign, Ill., 1983).

Lin, S.-H.

Ling, N.

N. Ling, M. A. Bayoumi, “Algorithms for high speed multi-dimensional arithmetic and DSP systolic arrays,” in Proceedings of the 1988 International Conference on Parallel Processing, F. A. Briggs, ed. (Pennsylvania State U. Press, University Park, Pa., 1988), pp. 367–374.

Lohman, G. E.

G. E. Lohman, A. W. Lohmann, “Optical interconnection network utilizing diffraction gratings,” Opt. Eng. 27, 893–900 (1988).

Lohmann, A. W.

Ludwig, R.

G. Grosskopf, R. Ludwig, R. Schnabel, N. Schunk, H. G. Weber, “Frequency conversion by four-wave-mixing in LD amplifiers,” in Photonic Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 226–232.
[CrossRef]

McCormick, F. B.

Midwinter, J. E.

M. G. Taylor, J. E. Midwinter, “Optically interconnected switching networks,” IEEE J. Lightwave Technol. 9, 791–798 (1991).
[CrossRef]

J. E. Midwinter, “Novel approach to the design of optically activated wideband switching matrices,” Proc. Inst. Electr. Eng. Part J 134, 261–268 (1987).

Miller, D. A. B.

D. A. B. Miller, “Optoelectronic applications of quantum wells,” Opt. Photon. News 1(1), 7–14 (1990).
[CrossRef]

Mukherjee, A.

S. C. Kothari, A. Jhunjhunwala, A. Mukherjee, “Performance analysis of multipath multistage interconnection networks,” in Performance Evaluation Review, Proceedings of the 1988 ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, (Association for Computing Machinery, New York, 1988), pp. 124–132.
[CrossRef]

Murdocca, M. J.

Park, J.

A. Aggarwal, J. Park, “Notes on searching in multidimensional monotone arrays,” in Proceedings of the 29th Annual Symposium on Foundations of Computer Science (Institute of Electrical and Electronics Engineers, New York, 1988), pp. 497–512.
[CrossRef]

Sapiecha, K.

K. Sapiecha, R. Jarocki, “Modular architecture for high performance implementation of FFT algorithm,” in Proceedings of the 13th Annual International Symposium on Computer Architecture (Institute of Electrical and Electronics Engineers, New York, 1986), pp. 261–270.

Sawchuk, A. A.

B. K. Jenkins, P. Chavel, R. Forchheimer, A. A. Sawchuk, T. C. Strand, “Architectural implications of a digital optical processor,” Appl. Opt. 23, 3465–3474 (1984).
[CrossRef] [PubMed]

A. A. Sawchuk, I. Glaser, “Geometries for optical implementations of the perfect shuffle,” in Optical Computing ’88, P. Chavel, J. W. Goodman, G. Roblin, eds., Proc. Soc. Photo-Opt. Instrum. Eng.963, 270–279 (1988).
[CrossRef]

Schnabel, R.

G. Grosskopf, R. Ludwig, R. Schnabel, N. Schunk, H. G. Weber, “Frequency conversion by four-wave-mixing in LD amplifiers,” in Photonic Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 226–232.
[CrossRef]

Schunk, N.

G. Grosskopf, R. Ludwig, R. Schnabel, N. Schunk, H. G. Weber, “Frequency conversion by four-wave-mixing in LD amplifiers,” in Photonic Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 226–232.
[CrossRef]

Stirk, C. W.

Stork, W.

Strand, T. C.

Strebel, B.

E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.

Stucke, G.

Szu, H. H.

H. H. Szu, H. J. Caulfield, “The mutual time-frequency content of two signals,” Proc. IEEE 72, 902–908 (1984).
[CrossRef]

Szymanski, T. H.

T. H. Szymanski, V. C. Hamacher, “On the permutation capability of multistage interconnection networks,” IEEE Trans. Comput. C-36, 810–822 (1987).
[CrossRef]

Taylor, M. G.

M. G. Taylor, J. E. Midwinter, “Optically interconnected switching networks,” IEEE J. Lightwave Technol. 9, 791–798 (1991).
[CrossRef]

Tripathi, S. K.

S.-T. Huang, S. K. Tripathi, “Finite state model and compatibility theory: new analysis tools for permutation networks,” IEEE Trans. Comput. C-35, 591–601 (1986).
[CrossRef]

Vathke, J.

E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.

Walkup, J. F.

Weber, H. G.

G. Grosskopf, R. Ludwig, R. Schnabel, N. Schunk, H. G. Weber, “Frequency conversion by four-wave-mixing in LD amplifiers,” in Photonic Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 226–232.
[CrossRef]

Weickhmann, M.

E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.

Appl. Opt. (11)

B. K. Jenkins, P. Chavel, R. Forchheimer, A. A. Sawchuk, T. C. Strand, “Architectural implications of a digital optical processor,” Appl. Opt. 23, 3465–3474 (1984).
[CrossRef] [PubMed]

S.-H. Lin, T. F. Krile, J. F. Walkup, “Two-dimensional optical Clos interconnection network and its uses,” Appl. Opt. 27, 1734–1741 (1988).
[CrossRef] [PubMed]

T. J. Cloonan, F. B. McCormick, “Photonic switching applications of 2-D and 3-D crossover networks based on 2-input, 2-output switching nodes,” Appl. Opt. 30, 2309–2323 (1991).
[CrossRef] [PubMed]

A. W. Lohmann, “What classical optics can do for the digital optical computer,” Appl. Opt. 25, 1543–1549 (1986).
[CrossRef] [PubMed]

A. W. Lohmann, W. Stork, G. Stucke, “Optical perfect shuffle,” Appl. Opt. 25, 1530–1531 (1986).
[CrossRef] [PubMed]

K.-H. Brenner, A. Huang, “Optical implementation of the perfect shuffle interconnection,” Appl. Opt. 27, 135–137 (1988).
[CrossRef] [PubMed]

C. W. Stirk, R. A. Athale, M. W. Haney, “Folded perfect shuffle optical processor,” Appl. Opt. 27, 202–203 (1988).
[CrossRef] [PubMed]

J. Jahns, M. J. Murdocca, “Crossover networks and their optical implementation,” Appl. Opt. 27, 3155–3160 (1988).
[CrossRef] [PubMed]

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

J. Giglmayr, “Transformation of three-dimensional shuffle patterns,” Appl. Opt. 31, 1709–1716 (1992).
[CrossRef]

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

IEEE J. Lightwave Technol. (1)

M. G. Taylor, J. E. Midwinter, “Optically interconnected switching networks,” IEEE J. Lightwave Technol. 9, 791–798 (1991).
[CrossRef]

IEEE Trans. Comput. (5)

S.-T. Huang, S. K. Tripathi, “Finite state model and compatibility theory: new analysis tools for permutation networks,” IEEE Trans. Comput. C-35, 591–601 (1986).
[CrossRef]

D. H. Lawrie, “Access and alignment of data in an array processor,” IEEE Trans. Comput. C-24, 1145–1155 (1975).
[CrossRef]

L. N. Bhunyan, D. P. Agrawal, “Design and performance of generalized interconnection networks,” IEEE Trans. Comput. C-32, 1081–1090 (1983).
[CrossRef]

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

T. H. Szymanski, V. C. Hamacher, “On the permutation capability of multistage interconnection networks,” IEEE Trans. Comput. C-36, 810–822 (1987).
[CrossRef]

Opt. Eng. (2)

G. E. Lohman, A. W. Lohmann, “Optical interconnection network utilizing diffraction gratings,” Opt. Eng. 27, 893–900 (1988).

T. J. Cloonan, M. J. Herron, “Optical implementation and performance of one-dimensional and two-dimensional trimmed inverse augmented data manipulator networks for multiprocessor systems,” Opt. Eng. 28, 305–314 (1989).

Opt. Photon. News (2)

D. A. B. Miller, “Optoelectronic applications of quantum wells,” Opt. Photon. News 1(1), 7–14 (1990).
[CrossRef]

J. W. Goodman, “Optical interconnections in the ’80’s,” Opt. Photon. News 1(12), 21–23 (1990).
[CrossRef]

Proc. IEEE (1)

H. H. Szu, H. J. Caulfield, “The mutual time-frequency content of two signals,” Proc. IEEE 72, 902–908 (1984).
[CrossRef]

Proc. Inst. Electr. Eng. Part J (1)

J. E. Midwinter, “Novel approach to the design of optically activated wideband switching matrices,” Proc. Inst. Electr. Eng. Part J 134, 261–268 (1987).

Syst. Comput. Jpn. (1)

T. Kumagai, K. Ikegaya, “Organization of two-dimensional Omega networks,” Syst. Comput. Jpn. 17, 1–10 (1986).
[CrossRef]

Other (14)

J. W. Goodman, “Integrated photonics and optical computing,” in Technical Digest on Integrated Photonics Research, Vol. 8 of OSA 1991 Technical Digest Series (Optical Society of America, Washington, D.C., 1991), paper WA1.

J. Giglmayr, “Higher-dimensional interconnection patterns (dim ≥ 3), their topology and performance,” presented at the Tagung der Deutschen Gesellschaft für Angewandte Optik, 16–20 May 1989, Berlin.

A. Aggarwal, J. Park, “Notes on searching in multidimensional monotone arrays,” in Proceedings of the 29th Annual Symposium on Foundations of Computer Science (Institute of Electrical and Electronics Engineers, New York, 1988), pp. 497–512.
[CrossRef]

H. S. Hinton, “Overview of free-space photonic switching,” in Technical Digest of the 1990 International Topical Meeting on Photonic Switching (Institute of Electronics, Information, and Communication Engineers, Tokyo, 1990), paper 12D-1.

D. G. Antzoulatos, “Kronecker and array algebra for parallel image processing,” Ph.D. dissertation, Report 135 (University of Southern California, Los Angeles, Calif., 1988).

A. A. Sawchuk, I. Glaser, “Geometries for optical implementations of the perfect shuffle,” in Optical Computing ’88, P. Chavel, J. W. Goodman, G. Roblin, eds., Proc. Soc. Photo-Opt. Instrum. Eng.963, 270–279 (1988).
[CrossRef]

N. Ling, M. A. Bayoumi, “Algorithms for high speed multi-dimensional arithmetic and DSP systolic arrays,” in Proceedings of the 1988 International Conference on Parallel Processing, F. A. Briggs, ed. (Pennsylvania State U. Press, University Park, Pa., 1988), pp. 367–374.

J. Giglmayr, “Multistage interconnection networks and d-dimensional architectures,” in Photonic Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 220–224.
[CrossRef]

S. C. Kothari, A. Jhunjhunwala, A. Mukherjee, “Performance analysis of multipath multistage interconnection networks,” in Performance Evaluation Review, Proceedings of the 1988 ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, (Association for Computing Machinery, New York, 1988), pp. 124–132.
[CrossRef]

K. Y. Lee, “Interconnection networks and compiler algorithms for multiprocessors,” Ph.D. dissertation (University of Illinois at Urbana–Champaign, Urbana–Champaign, Ill., 1983).

E.-J. Bachus, R.-P. Braun, C. Caspar, H.-M. Foisel, K. Heimes, N. Keil, B. Strebel, J. Vathke, M. Weickhmann, “Coherent optical multicarrier switching node,” in Technical Digest on Optical Fiber Communications, Vol. 5 of OSA 1989 Technical Digest Series (Optical Society of America, Washington, D.C., 1989), pp. PD13–1/PD13–3.

G. Grosskopf, R. Ludwig, R. Schnabel, N. Schunk, H. G. Weber, “Frequency conversion by four-wave-mixing in LD amplifiers,” in Photonic Switching II, K. Tada, H. S. Hinton, eds., Vol. 29 of Springer Series on Electronics and Photonics (Springer-Verlag, Berlin, 1990), pp. 226–232.
[CrossRef]

J. Giglmayr, “Spatial extension of multistage interconnection networks,” in Proceedings on Photonic Switching, J. E. Midwinter, H. S. Hinton, eds., Vol. 3 of OSA 1989 Proceedings Series (Optical Society of America, Washington, D.C., 1989), pp. 170–179.

K. Sapiecha, R. Jarocki, “Modular architecture for high performance implementation of FFT algorithm,” in Proceedings of the 13th Annual International Symposium on Computer Architecture (Institute of Electrical and Electronics Engineers, New York, 1986), pp. 261–270.

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 (16)

Fig. 1
Fig. 1

Shuffle interconnection of two 3-D data cubes of size 43. The interconnection of the 64 data elements of each 3-D cube by a 3-D shuffle pattern is partially shown (solid lines and dashed lines). Each of the interconnected elements is indicated by its MRN.

Fig. 2
Fig. 2

Hierarchical scheme of shuffle interconnection patterns and its dependence on the dimension d (≥ 1) of the interconnected data cubes. Notations: GPS (generalized perfect shuffle); GIS (generalized inverse shuffle); SGPS (symmetric GPS); NSGPS (nonsymmetric GPS); SGMS (symmetric generalized mixed shuffle); NSGMS (nonsymmetric GMS); SGIS (symmetric GIS); NSGIS (nonsymmetric GIS). We may factorize the two coordinates of an array (second row), or the three coordinates of a 3-D cube (third row), etc. equally (symmetric case) or differently (nonsymmetric case), and we may apply the GPS or/and GIS pattern with regard to these coordinates, which provides the GMS pattern.

Fig. 3
Fig. 3

Flow chart for the (sequential) generation of d-dimensional (d ≥ 3) shuffle patterns for the interconnection of d-dimensional data cubes of size Nd = N(1) × N(2) × ⋯; × N(d). The factorization N(i) = n1(i)n2(i) is assumed. The feedback arc describes shuffling of the order of the d-j-dimensional cubes (d ≥ 3, j ≥ 1).

Fig. 4
Fig. 4

Flow chart for the transformation of d-dimensional (d ≥ 3) shuffle patterns. The d-dimensional shuffle pattern is transformed into the 2-D domain (forward transformation). The paths of the transformed pattern are reordered to preserve the switches (reordering). The 1-D interstage pattern together with the switches is mapped into the 3-D physical space (backward transformation) or remains in the 2-D domain for the purpose of analysis.

Fig. 5
Fig. 5

Numbering of the 8 × 8 switches (A–H) within a 3-D switching cube of size 43. I–IV indicate the arrays of the cube.

Fig. 6
Fig. 6

Organization of the switch-preserving transformation. The original 3-D pattern is stretched into a 1-D pattern according to the dashed line, or vice versa, the 1-D pattern is filled into the 3-D physical space according to this line. I–IV indicate the arrays of the 3-D cube.

Fig. 7
Fig. 7

Transformed 3-D shuffle pattern and its relation to the 8 × 8 switches (A–H). Two paths are indicated by one single letter (A–H). For example, by running through the first row of the first array, switches A and B are passed, and, by running through the third row of the first array, switches C and D are passed (Fig. 5). The transformation subdivides each 8 × 8 switch into four parts. I–IV indicate the arrays of the 3-D cube.

Fig. 8
Fig. 8

Sequence of 2 × 2 ports (4 inputs/outputs) of the 8 × 8 switches (8 inputs/outputs) passed by the dashed line in Fig. 6. Mapping of the 3-D (1-D) pattern into the equivalent 1-D (3-D) pattern means running through the consecutively ordered sequence.

Fig. 9
Fig. 9

Interconnection of the first 8 × 8 switch of a 3-D switching cube of size 43 (left-hand side) with the corresponding elements of the second cube (right-hand side). For the legend see example 4 in the text.

Fig. 10
Fig. 10

Switch-preserving transformation of a 3-D shuffle pattern. The numbers refer to the data elements in Fig. 6 and the particular ordering is in accordance with the dashed line there. The ordering of the 8 × 8 switches refers to Fig. 5. The S(8, 8) pattern is obtained from the transformed pattern in Fig. 7 by reordering the paths in a way that completes the 8 × 8 switches.

Fig. 11
Fig. 11

Reordering of the 1-D interstage pattern. The 8 × 8 switches are prepared for the reordering of the pattern by the subdivision of each switch into two 4 × 4 switches. Shuffling the order of the 8 × 8 switches (left-hand side) by S(2, 4) and shuffling the order of the 4 × 4 switches (right-hand side) by S(8, 2) produce the interconnection pattern in Fig. 12.

Fig. 12
Fig. 12

Remapping with 4 × 4-switches (switch preserving). Remapping of S(4, 16) into the 3-D physical space according to Fig. 13 (left-hand side) completes the task.

Fig. 13
Fig. 13

Equivalence between 3-D and 2-D shuffle patterns. The original 3-D shuffle pattern on a cube of size 43 is transformed and reordered into a 2-D shuffle pattern on an array of size 8 × 8 (left-hand side) and on a rectangle of size 4 × 16 (right-hand side). The arrows express the (algebraic) equivalence of the patterns. The original 3-D pattern interconnects 8 × 8 switches. The 2-D patterns interconnect 4 × 4 switches (left-hand side) and 8 × 8 switches (right-hand side), respectively.

Fig. 14
Fig. 14

Remapping with 8 × 8 switches (switch size preserving). The S(8, 8) interstage pattern with the 8 × 8 switches in Fig. 11 is mapped into a 2-D shuffle pattern with 8 × 8 switches (switch size preserving) if the 1-D pattern is filled into the 4 × 16 array according to the dashed line. The resulting pattern is presented at the right-hand side of Fig. 13. The numbering of the data elements is in accord with the numbering in Fig. 6. I–IV indicate the arrays of the original 3-D cube.

Fig. 15
Fig. 15

System of algebraic bases related to d-dimensional shuffle patterns. The algebraic bases arise from the factorization N(i) = n1(i)n2(i) of the data length N(i). For d = 1 the arguments of the permutation matrix equal the algebraic bases n1 and n2, respectively. A d-dimensional (d ≥ 2) pattern is completely determined by the number of 2d bases.

Fig. 16
Fig. 16

Scheme for the realization of a 3-D shuffle pattern on a 3-D data cube of size 43. The space pattern is assumed to be a 2-D shuffle; the arrays of the 3-D cube are simultaneously established by frequency division multiplexing techniques. Frequency conversion (FC) is applied to shuffle the order of the arrays [insertion of S(2, 2)] that completes the 3-D shuffle. The patterns may also be generated by time division multiplexing techniques. ×× describes the discrete frequencies and means 00, 01, 10, or 11.

Tables (3)

Tables Icon

Table I Switch-Preserving Transformations for 2d × 2d Switches (d ≥ 2)

Tables Icon

Table II Interconnection Patterns and the Related System of Bases

Tables Icon

Table III Multistage Interconnection of d-Dimensional Data Cubes and Dimension-Dependent Switch Size

Equations (16)

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

( X , Y , Z ) = ( i u i x i , j v j y j , k w k z k , ) .
σ SGPS ( X , Y , Z ) = ( x 2 x 3 x 1 x r ,             y 2 y 3 y 1 y r ,             z 2 z 3 z 1 z r ) m 2 m 3 m r m 1 .
σ SGPS [ X ( 1 ) , X ( 2 ) , , X ( d ) ] = [ x 2 ( 1 ) x 3 ( 1 ) x r ( 1 ) x 1 ( 1 ) , x 2 ( 2 ) x 3 ( 2 ) x r ( 2 ) x 1 ( 2 ) , , x 2 ( d ) x 3 ( d ) x r ( d ) x 1 m 2 m 3 m r m 1 ( d ) .
S 3 - D NSGPS ( l 1 , l 2 ; m 1 , m 2 ; n 1 , n 2 ) = S ( l 1 , l 2 ) S 2 - D NSGPS ( m 1 , m 2 ; n 1 , n 2 ) ,
= S ( l 1 , l 2 ) S ( m 1 , m 2 ) S ( n 1 , n 2 ) .
S 3 - D SGMS ( n 1 , n 2 ; n 1 , n 2 ; n 1 , n 2 ) = S ( n 1 , n 2 ) S 2 - D GMS ( n 1 , n 2 ; n 1 , n 2 ) ,
S 3 - D NSGMS ( l 1 , l 2 ; m 1 , m 2 ; n 1 , n 2 ) = S ( l 2 , l 1 ) S 2 - D GMS ( m 1 , m 2 ; n 1 , n 2 ) ,
S 4 - D NSGPS ( k 1 , k 2 ; l 1 , l 2 ; m 1 , m 2 ; n 1 , n 2 ) = S ( k 1 , k 2 ) S 3 - D NSGPS ( l 1 , l 2 ; m 1 , m 2 ; n 1 , n 2 ) ,
= S ( k 1 , k 2 ) S ( l 1 , l 2 ) S 2 - D NSGPS ( m 1 , m 2 ; n 1 , n 2 ) .
S d - dim NSGPS [ n 1 ( 1 ) , n 2 ( 1 ) ; n 1 ( 2 ) , n 2 ( 2 ) ; ; n 1 ( d ) , n 2 ( d ) ] = S [ n 1 ( d ) , n 2 ( d ) ] S [ n 1 ( d - 1 ) , n 2 ( d - 1 ) ] S [ n 1 ( 3 ) , n 2 ( 3 ) ] S 2 - D NSGPS [ n 1 ( 1 ) , n 2 ( 1 ) ; n 1 ( 2 ) , n 2 ( 2 ) ] ,
S 3 - D NSGPS ( l 1 , l 2 ; m 1 , m 2 ; n 1 , n 2 ) = [ 1 l 1 l 2 S ( m 1 , m 2 ) S ( n 1 , n 2 ) ] [ S ( l 1 , l 2 ) 1 m 1 m 2 1 n 1 n 2 ] .
S d - dim NSGPS [ n 1 ( 1 ) , n 2 ( 1 ) ; n 1 ( 2 ) , n 2 ( 2 ) ; ; n 1 ( d ) , n 2 ( d ) ] = S [ i = 1 d n 1 ( i ) , i = 1 d n 2 ( i ) ] .
S 3 - D NSGPS ( l 1 , l 2 ; m 1 , m 2 ; n 1 , n 2 ) = [ 1 l 1 l 2 S 2 - D NSGPS ( m 1 , m 2 ; n 1 , n 2 ) ] × S 2 - D ( l 1 , l 2 ; m 1 , m 2 ; n 1 , n 2 ) [ 1 m 1 m 2 n 1 n 2 S ( l 1 , l 2 ) ] .
S 3 - D SGPS ( 2 , 2 ; 2 , 2 ; 2 , 2 ) = [ 1 4 S ( 2 , 2 ) S ( 2 , 2 ) ] × { S ( 2 , 2 ) [ 1 4 S ( 2 , 2 ) ] } [ 1 16 S ( 2 , 2 ) ] ,
S 2 - D NSGPS ( 2 , 2 ; 4 , 4 ) = [ 1 4 S ( 4 , 4 ) ] S ( 4 , 16 ) [ 1 16 S ( 2 , 2 ) ] .
f × × , × × , σ ( z 1 z 2 z r ) l 1 l 2 l r = f × × , × × , ( z 2 z 3 z r z 1 ) l 2 l 3 l r l 1 .

Metrics