Abstract

We investigate the network communication behavior of a three-dimensional (3D) multicomputer system using optical interconnection in which faulty nodes are left in place, a concept called "fail-in-place." We call this the percolation problem in which various amounts of missing nodes fixed in position in the network may have a dramatic effect on the network's ability to transport data effectively. As the number of failed nodes increases, data have to be rerouted through intermediate nodes creating potential "hot spots." These hot spots become the bottleneck that degrades performance. The ability to absorb rerouted data without ejecting it from the network is critical in massively parallel computing systems. Optical technology is a promising solution for internode communication with extraordinarily quick response time supporting enormous bandwidth. To adopt it in multiprocessor systems, efficient routing techniques are needed. We adapt self-routing strategies for all-optical packet routing in 3D mesh networks and investigate the percolation properties. To achieve percolation routing, we incorporate the features inherent in optics to achieve decoding and routing capability in real time. The objective is to develop a dynamic communication environment that adapts and evolves with a high density of missing units or nodes, and by employing analytical, experimental, and simulation methods, show that optical interconnection in a dense 3D system reduces considerably this percolation problem.

© 2004 Optical Society of America

PDF Article

References

  • View by:
  • |

  1. N. R. Adiga and researchers at IBM and the Lawrence Livermore National Laboratory, "An overview of the BlueGene∕L supercomputer," in Proceedings of the IEEE/ACM SC2002 Conference (IEEE, 2002).
  2. Cray Research Incorporated, Cray T3D System Architecture Overview (September 1993).
  3. Intel Corporation,Paragon XP∕S Product Overview (1991).
  4. W. J. Dally, "The J-machine: system support for actors," Actors: Knowledge-Based Concurrent Computing, Hewitt and Agha, eds. (MIT Press, 1989).
  5. R. K. Koeninger, M. Furtney, and M. Walker, "A shared memory MPP from Cray Research," Dig. Tech. J. 6(2), 8-21 (1994).
  6. A. V. Krishnamoorthy and D. A. B. Miller, "Firehose architectures for free-space optically interconnected VLSI circuits," J. Parallel Distrib. Comput. 41(1), 109-114 (1997).
  7. P. J. Marchand, A. V. Krishnamoorthy, G. I. Yayla, S. C. Esener, and U. Efron, "Optically augmented 3-D computer: system technology and architecture," J. Parallel Distrib. Comput., Special Issue on Optical Interconnects, 41(1), 20-35 (1997).
  8. G. A. Betzos and P. A. Mitkas, "Performance evaluation of massively parallel processing architectures with three-dimensional optical interconnections, Appl. Opt. 37, 315-25 (1998).
  9. J. W. Goodman, F. J. Leonberger, S. C. Kung, and R. A. Athale, "Optical interconnections for VLSI systems," Proc. IEEE 72, 850-66 (1984).
  10. C. B. Stunkel, "Commercial MPP networks: time for optics?" in Proceedings of the Fourth International Conference on Massively Parallel Processing Using Optical Interconnections (1997), pp. 90-95.
  11. R. Germann, H. W. M. Salemink, R. Beyeler, G. L. Bona, F. Horst, and B. J. Offrein, "Silicon-oxynitride layers for optical waveguide applications," J. Electrochem. Soc. 147, 2237-2241 (2000).
  12. G. L. Bona, R. Germann, F. Horst, B. J. Offrein, and H. W. M. Salemink, "Versatile silicon-oxynitride planar lightwave circuits for interconnect applications," in Proceedings of the 6th International Conference on Parallel Interconnects (IEEE, Los Alamitos, 2000), pp. 145-148.
  13. D. A. B. Miller, "Rationale and challenges for optical interconnects to electronic chips," Proc. IEEE 88, 728-749 (2000).
  14. S. Esener and P. Marchand, "Present and future needs of free-space optical interconnects," in IPDPS Workshop (2000), pp. 1104-1109.
  15. D. J. Goodwill, "Free-space optical interconnect for terabit network elements," in Proceedings of Optics in Computing Conference (1999).
  16. B. F. Almohammad and B. Bose, "Fault-tolerant communication algorithms in toroidal networks," IEEE Trans. Parallel Distrib. Syst. 10, 976-983 (1999).
  17. J. Wu, "A fault-tolerant adaptive and minimal routing approach in 3D meshes," IEEE Trans. Parallel Distrib. Syst. 11, 149-159 (2000).
  18. Z. Jiang and J. Wu, "A limited-global fault information model for dynamic routing in 3D meshes," in Second IEEE International Symposium on Network Computing and Applications (IEEE, 2003), pp. 333-340.
  19. H. Shen, F. Chin, and Y. Pan, "Efficient fault-tolerant routing in multi-hop optical WDM networks," IEEE Trans. Parallel Distrib. Syst. 10, 1012-1025 (1999).
  20. C. Ho and L. Stockmeyer, "A new approach to fault-tolerant wormhole routing for mesh-connected parallel computers," IEEE Trans. Comput. 53, 427-438 (2004).
  21. I. Glesk, K. I. Kang, and P. R. Prucnal, "All-optical address recognition and self-routing in a 250 Gbit∕s packet switched," Electron. Lett. 30, 1322-1323 (1994).
  22. A. E. Willne, D. Gurkan, A. B. Sahin, J. E. McGeehan, and M. C. Hauer, "All-optical address recognition for optically-assisted routing in next-generation optical networks," IEEE Commun. Mag. 41(5), S38-S44 (2003).
  23. N. Calabretta, Y. Liu, H. de Waardt, M. T. Hill, G. D. Khoe, and H. J. S. Dorren, "Multiple-output all-optical header processing technique based on two-pulse correlation principle," Electron. Lett. 37, 1238-1240 (2001).
  24. M. T. Hill, A. Srivatsa, N. Calabretta, Y. Liu, H. deWaardt, G. D. Khoe, and H. J. S. Dorren, "1X2 optical packet switch using all-optical header processing," Electron. Lett. 37, 774-775 (2001).
  25. P. Toliver, I. Glesk, R. J. Runser, K. L. Deng, B. Y. Yu, and P. R. Prucnal, "Routing of 100 Gb/s words in a packet-switched optical networking demonstration (POND) node," J. Lightwave Technol. 16, 2169-2180 (1998).
  26. K. L. Deng, R. J. Runser, P. Toliver, C. Coldwell, D. Zhou, I. Glesk, and P. R. Prucnal, "Demonstration of highly scalable 100Gbit/s OTDM computer interconnect with rapid interchannel switching capability," Electron. Lett. 34, 2418-2419 (1998).
  27. G. Castanon, "Optical packet switching with multiple path routing," Comput. Netw. 32, 653-662 (2000).
  28. H. Shi and J. Lin, "Theoretical analysis on polarization deviation and switch window optimization in nonlinear optical loop mirror demultiplexer," J. Lightwave Technol. 17, 2572-2576 (1999).
  29. L. Tangjun, P. Cuizhu, and Z. Yucheng, "Study on improving the performance of OTDM device," IEEE Photon. Technol. Lett. 11, 2572-2576 (1999).
  30. T. R. Mathies, "Percolation theory and computing with faulty arrays of processors," in Proceedings of the Third Annual Symposium on Discrete Algorithms (SODA) (1992), pp. 100-103.
  31. W. W. Wilcke, S. Kirkpatrick, R. B. Garner, and H. Huels, "Percolation in dense storage arrays," Physica A 314(1-4), 220-229 (2002).
  32. R. Gao, Z. Ghassemlooy, G. Swift, and P. Ball, "Simulation of all optical time division multiplexed router," in Proceedings of West Electronics 2001 (2001).

Appl. Opt. (1)

Comput. Netw. (1)

G. Castanon, "Optical packet switching with multiple path routing," Comput. Netw. 32, 653-662 (2000).

Dig. Tech. J. (1)

R. K. Koeninger, M. Furtney, and M. Walker, "A shared memory MPP from Cray Research," Dig. Tech. J. 6(2), 8-21 (1994).

Electron. Lett. (4)

K. L. Deng, R. J. Runser, P. Toliver, C. Coldwell, D. Zhou, I. Glesk, and P. R. Prucnal, "Demonstration of highly scalable 100Gbit/s OTDM computer interconnect with rapid interchannel switching capability," Electron. Lett. 34, 2418-2419 (1998).

I. Glesk, K. I. Kang, and P. R. Prucnal, "All-optical address recognition and self-routing in a 250 Gbit∕s packet switched," Electron. Lett. 30, 1322-1323 (1994).

N. Calabretta, Y. Liu, H. de Waardt, M. T. Hill, G. D. Khoe, and H. J. S. Dorren, "Multiple-output all-optical header processing technique based on two-pulse correlation principle," Electron. Lett. 37, 1238-1240 (2001).

M. T. Hill, A. Srivatsa, N. Calabretta, Y. Liu, H. deWaardt, G. D. Khoe, and H. J. S. Dorren, "1X2 optical packet switch using all-optical header processing," Electron. Lett. 37, 774-775 (2001).

IEEE Commun. Mag. 41 (1)

A. E. Willne, D. Gurkan, A. B. Sahin, J. E. McGeehan, and M. C. Hauer, "All-optical address recognition for optically-assisted routing in next-generation optical networks," IEEE Commun. Mag. 41(5), S38-S44 (2003).

IEEE Photon. Technol. Lett. (1)

L. Tangjun, P. Cuizhu, and Z. Yucheng, "Study on improving the performance of OTDM device," IEEE Photon. Technol. Lett. 11, 2572-2576 (1999).

IEEE Trans. Comput. (1)

C. Ho and L. Stockmeyer, "A new approach to fault-tolerant wormhole routing for mesh-connected parallel computers," IEEE Trans. Comput. 53, 427-438 (2004).

IEEE Trans. Parallel Distrib. Syst. (1)

H. Shen, F. Chin, and Y. Pan, "Efficient fault-tolerant routing in multi-hop optical WDM networks," IEEE Trans. Parallel Distrib. Syst. 10, 1012-1025 (1999).

J. Electrochem. Soc. (1)

R. Germann, H. W. M. Salemink, R. Beyeler, G. L. Bona, F. Horst, and B. J. Offrein, "Silicon-oxynitride layers for optical waveguide applications," J. Electrochem. Soc. 147, 2237-2241 (2000).

J. Lightwave Technol. (2)

J. Parallel Distrib. Comput. (2)

A. V. Krishnamoorthy and D. A. B. Miller, "Firehose architectures for free-space optically interconnected VLSI circuits," J. Parallel Distrib. Comput. 41(1), 109-114 (1997).

P. J. Marchand, A. V. Krishnamoorthy, G. I. Yayla, S. C. Esener, and U. Efron, "Optically augmented 3-D computer: system technology and architecture," J. Parallel Distrib. Comput., Special Issue on Optical Interconnects, 41(1), 20-35 (1997).

Physica A (1)

W. W. Wilcke, S. Kirkpatrick, R. B. Garner, and H. Huels, "Percolation in dense storage arrays," Physica A 314(1-4), 220-229 (2002).

Proc. IEEE (2)

J. W. Goodman, F. J. Leonberger, S. C. Kung, and R. A. Athale, "Optical interconnections for VLSI systems," Proc. IEEE 72, 850-66 (1984).

D. A. B. Miller, "Rationale and challenges for optical interconnects to electronic chips," Proc. IEEE 88, 728-749 (2000).

Other (13)

S. Esener and P. Marchand, "Present and future needs of free-space optical interconnects," in IPDPS Workshop (2000), pp. 1104-1109.

D. J. Goodwill, "Free-space optical interconnect for terabit network elements," in Proceedings of Optics in Computing Conference (1999).

B. F. Almohammad and B. Bose, "Fault-tolerant communication algorithms in toroidal networks," IEEE Trans. Parallel Distrib. Syst. 10, 976-983 (1999).

J. Wu, "A fault-tolerant adaptive and minimal routing approach in 3D meshes," IEEE Trans. Parallel Distrib. Syst. 11, 149-159 (2000).

Z. Jiang and J. Wu, "A limited-global fault information model for dynamic routing in 3D meshes," in Second IEEE International Symposium on Network Computing and Applications (IEEE, 2003), pp. 333-340.

C. B. Stunkel, "Commercial MPP networks: time for optics?" in Proceedings of the Fourth International Conference on Massively Parallel Processing Using Optical Interconnections (1997), pp. 90-95.

G. L. Bona, R. Germann, F. Horst, B. J. Offrein, and H. W. M. Salemink, "Versatile silicon-oxynitride planar lightwave circuits for interconnect applications," in Proceedings of the 6th International Conference on Parallel Interconnects (IEEE, Los Alamitos, 2000), pp. 145-148.

N. R. Adiga and researchers at IBM and the Lawrence Livermore National Laboratory, "An overview of the BlueGene∕L supercomputer," in Proceedings of the IEEE/ACM SC2002 Conference (IEEE, 2002).

Cray Research Incorporated, Cray T3D System Architecture Overview (September 1993).

Intel Corporation,Paragon XP∕S Product Overview (1991).

W. J. Dally, "The J-machine: system support for actors," Actors: Knowledge-Based Concurrent Computing, Hewitt and Agha, eds. (MIT Press, 1989).

R. Gao, Z. Ghassemlooy, G. Swift, and P. Ball, "Simulation of all optical time division multiplexed router," in Proceedings of West Electronics 2001 (2001).

T. R. Mathies, "Percolation theory and computing with faulty arrays of processors," in Proceedings of the Third Annual Symposium on Discrete Algorithms (SODA) (1992), pp. 100-103.

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.