All-to-All Communication on the Connection Machine CM-200

Article type: Research Article

Authors: MATHUR, KAPIL K. | JOHNSSON, S. LENNART

Affiliations: David Shaw & Co., New York, NY 10036; e-mail: [email protected] | Computer Science, Mathematics, and Electrical Engineering, University of Houston, 4800 Calhoun Rd., Houston, TX 77204-3475; e-mail: [email protected]

Abstract: Detailed algorithms for all-to-all broadcast and reduction are given for arrays mapped by binary or binary-reflected Gray code encoding to the processing nodes of binary cube networks. Algorithms are also given for the local computation of the array indices for the communicated data, thereby reducing the demand for the communications bandwidth. For the Connection Machine system CM-200, Hamiltonian cycle-based all-to-all communication algorithms yield a performance that is a factor of 2 to 10 higher than the performance offered by algorithms based on trees, butterfly networks, or the Connection Machine router. The peak data rate achieved for all-to-all broadcast on a 2,048-node Connection Machine system CM-200 is 5.4 Gbyte/s. The index order of the data in local memory depends on implementation details of the algorithms, but it is well defined. If a linear ordering is desired, then including the time for local data reordering reduces the effective peak data rate to 2.5 Gbyte/s.

Journal: Scientific Programming, vol. 4, no. 4, pp. 251-273, 1995