Abstract

A 2-D optical three-stage Clos interconnection network, which is made up of a number of feasible crossbars of medium size, is implemented for dynamic data communications. The network is nonblocking and can handle a large number of communication lines (compared with crossbar networks of realizable size). Both one-to-one and one-to-many routing algorithms are discussed. Applications based on the Clos network are proposed for SIMD (single instruction multiple data) parallel computations and four-level programmable logic arrays (PLAs).

© 1988 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. A. Sawchuk, B. K. Jenkins, “Dynamic Optical Interconnections for Parallel Processors,” Proc. Soc Photo-Opt. Instrum. Eng. 625, 143 (1986).
  2. C. Clos, “A Study of Non-Blocking Switching Networks,” Bell Syst. Tech. J. 32, 406 (1953).
  3. T. Y. Feng, “A Survey of Interconnection Networks,” in Computer Special Issue on Interconnection Networks (Dec.1981).
  4. A. W. Lohmann, W. Stork, G. Stucke, “Optical Perfect Shuffle,” Appl. Opt. 25, 1530 (1986).
    [CrossRef] [PubMed]
  5. S. H. Lin, T. F. Krile, J. F. Walkup, “A 2-D Optical Multistage Interconnection Network,” Proc. Soc. Photo-Opt. Instrum. Eng.752, (1987), in press.
  6. A network is nonblocking if, regardless of what state the network is currently in, any pair of idle input–output terminals can be connected without having to reroute any existing connections.
  7. A network is called a rearrangeable network if it can perform all possible connections between inputs and outputs by rearranging its existing connections. However a rearrangeable network can still be blocking.
  8. V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic (Academic, New York, 1968).
  9. H. J. Siegel, “A Model of SIMD Machines and a Comparison of Various Interconnection Networks,” IEEE Trans. Comput. C-28, 907 (1979).
    [CrossRef]
  10. M. C. Pease, “An Adaptation of the Fast Fourier Transform for Parallel Processing,” J. Assoc. Comput. Mach. 15, 252 (1968).
    [CrossRef]
  11. M. Karpovsky, “Multilevel Logic Networks,” IEEE Trans. Comput. C-36, 215 (1987).
    [CrossRef]
  12. A. C. Walker, “Application of Bistable Optical Logic Gate Arrays to All-Optical Digital Parallel Processing,” Appl. Opt. 25, 1578 (1986).
    [CrossRef] [PubMed]
  13. S. T. Hung, S. K. Tripathi, “Finite State Model and Compatibility Theory: New Analysis Tools for Permutation Networks,” IEEE Trans. Comput. C-35, 591 (1986).
    [CrossRef]

1987 (1)

M. Karpovsky, “Multilevel Logic Networks,” IEEE Trans. Comput. C-36, 215 (1987).
[CrossRef]

1986 (4)

A. A. Sawchuk, B. K. Jenkins, “Dynamic Optical Interconnections for Parallel Processors,” Proc. Soc Photo-Opt. Instrum. Eng. 625, 143 (1986).

S. T. Hung, S. K. Tripathi, “Finite State Model and Compatibility Theory: New Analysis Tools for Permutation Networks,” IEEE Trans. Comput. C-35, 591 (1986).
[CrossRef]

A. C. Walker, “Application of Bistable Optical Logic Gate Arrays to All-Optical Digital Parallel Processing,” Appl. Opt. 25, 1578 (1986).
[CrossRef] [PubMed]

A. W. Lohmann, W. Stork, G. Stucke, “Optical Perfect Shuffle,” Appl. Opt. 25, 1530 (1986).
[CrossRef] [PubMed]

1979 (1)

H. J. Siegel, “A Model of SIMD Machines and a Comparison of Various Interconnection Networks,” IEEE Trans. Comput. C-28, 907 (1979).
[CrossRef]

1968 (1)

M. C. Pease, “An Adaptation of the Fast Fourier Transform for Parallel Processing,” J. Assoc. Comput. Mach. 15, 252 (1968).
[CrossRef]

1953 (1)

C. Clos, “A Study of Non-Blocking Switching Networks,” Bell Syst. Tech. J. 32, 406 (1953).

Benes, V. E.

V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic (Academic, New York, 1968).

Clos, C.

C. Clos, “A Study of Non-Blocking Switching Networks,” Bell Syst. Tech. J. 32, 406 (1953).

Feng, T. Y.

T. Y. Feng, “A Survey of Interconnection Networks,” in Computer Special Issue on Interconnection Networks (Dec.1981).

Hung, S. T.

S. T. Hung, S. K. Tripathi, “Finite State Model and Compatibility Theory: New Analysis Tools for Permutation Networks,” IEEE Trans. Comput. C-35, 591 (1986).
[CrossRef]

Jenkins, B. K.

A. A. Sawchuk, B. K. Jenkins, “Dynamic Optical Interconnections for Parallel Processors,” Proc. Soc Photo-Opt. Instrum. Eng. 625, 143 (1986).

Karpovsky, M.

M. Karpovsky, “Multilevel Logic Networks,” IEEE Trans. Comput. C-36, 215 (1987).
[CrossRef]

Krile, T. F.

S. H. Lin, T. F. Krile, J. F. Walkup, “A 2-D Optical Multistage Interconnection Network,” Proc. Soc. Photo-Opt. Instrum. Eng.752, (1987), in press.

Lin, S. H.

S. H. Lin, T. F. Krile, J. F. Walkup, “A 2-D Optical Multistage Interconnection Network,” Proc. Soc. Photo-Opt. Instrum. Eng.752, (1987), in press.

Lohmann, A. W.

Pease, M. C.

M. C. Pease, “An Adaptation of the Fast Fourier Transform for Parallel Processing,” J. Assoc. Comput. Mach. 15, 252 (1968).
[CrossRef]

Sawchuk, A. A.

A. A. Sawchuk, B. K. Jenkins, “Dynamic Optical Interconnections for Parallel Processors,” Proc. Soc Photo-Opt. Instrum. Eng. 625, 143 (1986).

Siegel, H. J.

H. J. Siegel, “A Model of SIMD Machines and a Comparison of Various Interconnection Networks,” IEEE Trans. Comput. C-28, 907 (1979).
[CrossRef]

Stork, W.

Stucke, G.

Tripathi, S. K.

S. T. Hung, S. K. Tripathi, “Finite State Model and Compatibility Theory: New Analysis Tools for Permutation Networks,” IEEE Trans. Comput. C-35, 591 (1986).
[CrossRef]

Walker, A. C.

Walkup, J. F.

S. H. Lin, T. F. Krile, J. F. Walkup, “A 2-D Optical Multistage Interconnection Network,” Proc. Soc. Photo-Opt. Instrum. Eng.752, (1987), in press.

Appl. Opt. (2)

Bell Syst. Tech. J. (1)

C. Clos, “A Study of Non-Blocking Switching Networks,” Bell Syst. Tech. J. 32, 406 (1953).

IEEE Trans. Comput. (3)

H. J. Siegel, “A Model of SIMD Machines and a Comparison of Various Interconnection Networks,” IEEE Trans. Comput. C-28, 907 (1979).
[CrossRef]

S. T. Hung, S. K. Tripathi, “Finite State Model and Compatibility Theory: New Analysis Tools for Permutation Networks,” IEEE Trans. Comput. C-35, 591 (1986).
[CrossRef]

M. Karpovsky, “Multilevel Logic Networks,” IEEE Trans. Comput. C-36, 215 (1987).
[CrossRef]

J. Assoc. Comput. Mach. (1)

M. C. Pease, “An Adaptation of the Fast Fourier Transform for Parallel Processing,” J. Assoc. Comput. Mach. 15, 252 (1968).
[CrossRef]

Proc. Soc Photo-Opt. Instrum. Eng. (1)

A. A. Sawchuk, B. K. Jenkins, “Dynamic Optical Interconnections for Parallel Processors,” Proc. Soc Photo-Opt. Instrum. Eng. 625, 143 (1986).

Other (5)

T. Y. Feng, “A Survey of Interconnection Networks,” in Computer Special Issue on Interconnection Networks (Dec.1981).

S. H. Lin, T. F. Krile, J. F. Walkup, “A 2-D Optical Multistage Interconnection Network,” Proc. Soc. Photo-Opt. Instrum. Eng.752, (1987), in press.

A network is nonblocking if, regardless of what state the network is currently in, any pair of idle input–output terminals can be connected without having to reroute any existing connections.

A network is called a rearrangeable network if it can perform all possible connections between inputs and outputs by rearranging its existing connections. However a rearrangeable network can still be blocking.

V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic (Academic, New York, 1968).

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

Clos (p,q,r) network.

Fig. 2
Fig. 2

Clos (3,5,3) network.

Fig. 3
Fig. 3

One-to-one routing scheme.

Fig. 4
Fig. 4

Alternative one-to-one routing scheme.

Fig. 5
Fig. 5

One-to-many routing algorithm for a Clos (3,5,3) network.

Fig. 6
Fig. 6

Optical implementation of one stage of a Clos (4,4,4) network.

Fig. 7
Fig. 7

(a) Replicated 4 × 4 input array (2 × 2 times); (b),(c),(d) outputs of the first stage of the Clos (4,4,4) network with randomly chosen switching functions.

Fig. 8
Fig. 8

A 6 × 6 matrix transposition based on a Clos (9,9,4) network.

Fig. 9
Fig. 9

Bivariate polynomial evaluation based on the Clos (4,4,6) network.

Fig. 10
Fig. 10

FFT based on the Clos network.

Fig. 11
Fig. 11

Four-level PLA based on the Clos network.

Fig. 12
Fig. 12

Four-level PLA with nine products and six functions based on the Clos network.

Fig. 13
Fig. 13

One-to-one routing algorithm for a Clos (5,5,5) network, starting from g13.

Fig. 14
Fig. 14

One-to-one routing algorithm for a Clos (5,9,5) network, starting from g11.

Fig. 15
Fig. 15

One-to-one routing algorithm for a Clos (5,9,5) network, starting from g11.

Fig. 16
Fig. 16

One-to-many routing algorithm for a Clos (5,9,5) network.

Tables (1)

Tables Icon

Table I Comparison of the Crossbar, Clos, and Multistage Interconnection Networks

Equations (8)

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

y 1 j , y 2 j , and y 3 j must belong to different input groups .
{ y 1 j , y 2 j , y 3 j } belong to ( i ) different input groups or ( ii ) two of the three are identical and the last one is from a different input group or ( iii ) all of them are identical .
X ( j ) = k = 0 N 1 A ( k ) W j k , j = 0 , 1 , , N 1 and W = exp ( i 2 π / N ) .
j = j 1 p 1 + j 0 p 0 , k = k 1 p 1 + k 0 p 0 .
X ( j 1 , j 0 ) = k 0 k 1 A ( k 1 , k 0 ) W j k = B 2 ( j 0 , j 1 ) ,
B 2 ( j 0 , j 1 ) = k 0 B 1 ( j 0 , k 0 ) W ( j 1 p 1 + j 0 p 0 ) k 0 ,
B 1 ( j 0 , k 0 ) = k 1 A ( k 1 , k 0 ) W ( j 0 k 1 ) p 1
p 1 = x 1 x 2 , p 2 = x 1 x 3 x 4 , p 3 = x 2 x 3 x 4 . p 4 = x 1 x 3 x 4 x 5 , p 5 = x 2 x 5 x 6 , p 6 = x 3 x 4 x 6 p 7 = x 2 x 3 x 4 x 6 , p 8 = x 3 x 4 x 5 x 6 , p 9 = x 1 x 3 x 4 x 5 f 1 = p 1 + p 2 + p 4 + p 9 f 2 = p 1 + p 2 + p 3 + p 7 f 3 = p 1 + p 2 + p 4 + p 5 + p 7 f 4 = p 2 + p 5 + p 6 + p 7 + p 8 f 5 = p 1 + p 6 + p 7 + p 9 f 6 = p 2 + p 3 + p 4 + p 9 .

Metrics