Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Scheduling collective communications (CC) in networks based on optimal graphs and digraphs has been done with the use of the evolutionary techniques. Inter-node communication patterns scheduled in the minimum number of time slots have been obtained. Numerical values of communication times derived for illustration can be used to estimate speedup of typical applications that use CC frequently. The results show that evolutionary techniques often lead to ultimate scheduling of CC that reaches theoretical bounds on the number of steps. Analysis of fault tolerance by the same techniques revealed graceful CC performance degradation for a single link fault. Once the faulty link is located, CC can be re-scheduled during a recovery period.

REFERENCES

• 1: van der Steen, A. J., Dongarra, J. J. Overview of Recent Supercomputers. TOP 500Ò Supercomputer Sites, Nov. 2007 Edition, http://www.arcade-eu.org/overview/.
• 2: Stewart, L. C., Gingold, D. A New Generation of Cluster Interconnect. White Paper, SiCortex Inc., Dec. 2006.
• 3: Jiri Jaros , Milos Ohlidal , Vaclav Dvorak, An evolutionary approach to collective communication scheduling, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277358]
• 4: Miller, M., Širán, J. Moore graphs and beyond: A survey of the degree/diameter problem. The Electronic Journal of Combinatorics, 2005, Dynamic Survey #DS14.
• 5: The (Degree, Diameter) problem for graphs. World Combinatorics Exchange, www-mat.upc.es /grup_de_grafs/grafs/taula_delta_d.html.
• 6: Jose Duato , Sudhakar Yalamanchili , Ni Lionel, Interconnection Networks: An Engineering Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2002
• 7: John L. Hennessy , David A. Patterson, Computer Architecture, Fourth Edition: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2006
• 8: Faraydon Karim , Anh Nguyen , Sujit Dey, An Interconnect Architecture for Networking Systems on Chips, IEEE Micro, v.22 n.5, p.36-45, September 2002 [doi>10.1109/MM.2002.1044298]
• 9: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 10: Jaroš J., Dvorák, V. Speeding-up OAS and AAS Communication in Networking System on Chips, In: Proc. of 8th IEEE Workshop on Design and Diagnostic of Electronic Circuits and Systems, Sopron, HU, UWH, 2005, pp. 4, ISBN 9639364487.
• 11: Ohlídal, M., Jaroš, J., Dvorák, V., Schwarz, J. Evolutionary Design of OAB and AAB Communication Schedules for Interconnection Networks, In: Lecture Notes in Computer Science, 2006, no. 3907, DE, pp. 267--278, ISSN 0302-9743.
• 12: Larrañaga, P., Lozano, J. A. Estimation of Distribution Algorithms. Kluwer Academic Publishers, London 2002, ISBN 0-7923-7466-5.
• 13: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 14: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Design, Performance

Keywords:
collective communications, communication scheduling, evolutionary design, interconnection networks