Performance analysis of the connection machine

ABSTRACT

This paper presents an analysis of the performance of the Connection Machine, with special emphasis on estimating the effect of its interprocessor communication architecture. A queueing model of the network architecture, including the NEWS and ROUTER networks, is used to compute the slow-down induced by message exchange between processors. Locality of the message exchanges is modelled by message sending probabilities which depend on whether a message is sent by a processor to another processor placed on the same NEWS network, or on the same ROUTER, or at a “remote” location which is only accessible via the ROUTER network. The specific slotted TDMA structure of the ROUTER Network communications is taken into account. The performance degradation of the Connection Machine as a function of the communication and architecture parameters is derived.

REFERENCES

• 1: W. Daniel Hillis, The connection machine, MIT Press, Cambridge, MA, 1986
• 2: Hillis, W.D., 'The Connection Machine: A Computer Architecture Based on Cellular Automata', Physica, 10, 213-228, (1984).
• 3: Karen A. Frenkel, Evaluating two massively parallel machines, Communications of the ACM, v.29 n.8, p.752-758, Aug. 1986 [doi>10.1145/6424.6427]
• 4: Kenneth E. Batcher, Architecture of a massively parallel processor, Proceedings of the 7th annual symposium on Computer Architecture, p.168-173, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801922]
• 5: BBN Laboratories, 'Butterfly Parallel Processor Overview', BBN, Cambridge, Massachusetts, (December 1985).
• 6: Intel Corporation, iPSC System Overview, (October 1985).
• 7: Flanders, P.M., Hunt S.F., Reddaway, S.F. and Parkinson D., 'Efficient High Speed Computing with the Distributed Array Processor', Proceedings of the Syrup. on High Speed Computer and Algorithm Organization, University of Illinois, Academic Press, (1977).
• 8: 'Connection Machine Model CM-2 Technical Summary', Thinking Machines Technical Report HA87- 4, Thinking Machines Corporation, Cambridge, Mass., (April 1987}.
• 9: George Broomell , J. Robert Heath, Classification Categories and Historical Development of Circuit Switching Topologies, ACM Computing Surveys (CSUR), v.15 n.2, p.95-133, June 1983 [doi>10.1145/356909.356912]
• 10: Levitan, S.P., 'Measuring Communication Structures in Parallel Architectures and Algorithms', in The Characteristics of Parallel Algorithms, pp. 101-137, Jamieson, L.H., Gannon, D.B. and Douglas, R.J. (eds), MIT Press, Cambridge, Mass., (1987).
• 11: James J. Little, Parallel Algorithms for Computer Vision on the Connection Machine, Massachusetts Institute of Technology, Cambridge, MA, 1986
• 12: Flynn, A.M. and Harris, J.G., 'Recognition Algorithms for the Connection Machine', Proceedings of the 9th Int. Joint Conf. on Artificial Intelligence, Los Angeles, CA, 57-60, (August 1985).
• 13: Harris, J.G. and Flynn, A.M., 'Object Recognition Using the Connection Machine's Router', Proceedings IEEE 1986 Conf. Computer Vision and Pattern Recognition, 134-139, (May 1986).
• 14: Craig Stanfill , Brewster Kahle, Parallel free-text search on the connection machine system, Communications of the ACM, v.29 n.12, p.1229-1239, Dec. 1986 [doi>10.1145/7902.7907]
• 15: Craig Stanfill , David Waltz, Toward memory-based reasoning, Communications of the ACM, v.29 n.12, p.1213-1228, Dec. 1986 [doi>10.1145/7902.7906]
• 16: Upton, R.A. and Tripathi, S.K., 'On the Performance Evaluation of Fine-Grained SIMD Computer Architectures: an Analysis of the Connection Machine', High Performance Computer Systems, Gelenbe,E. (ed.), Elsevier Science Publishers, North-Holland, Amsterdam, (1988).
• 17: Gelenbe, E. and Mitrani, I., Analysis and Synthesis of Computer Systems, Academic Press, London and New York,(1980).
• 18: Gelenbe, E. and Iasnogorodsky, R. 'A Queue with Server of Walking Type', Annales de l'Institut Henri Poincarg, Sdrie B (Probabilitg et Statistiques), Vol. XVI, No. 1, 63-73, (1980).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

General Terms:
Algorithms, Design, Performance, Theory