Browse Prior Art Database

Optimal All to All Communication Patterns for Parallel Processing

IP.com Disclosure Number: IPCOM000109554D
Original Publication Date: 1992-Sep-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 4 page(s) / 127K

Publishing Venue

IBM

Related People

Panda, RD: AUTHOR [+4]

Abstract

The following is a description of an all to all message scheduling procedure for use in a distributed parallel processing environment in which the processing elements (PEs) are interconnected through a crossbar switch. in such a system, it is possible for any PE to communicate with any other PE (by sending or receiving a message), as long as neither is currently engaged in any other communication. In many applications, it is necessary for each PE to communicate with every other PE by sending a fixed length message to every PE, and by receiving a similar message from every PE. Since no PE can communicate with more than one PE at any given time, it is important to choose a message scheduling procedure which avoids attempting to communicate with a PE which is "busy".

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Optimal All to All Communication Patterns for Parallel Processing

       The following is a description of an all to all message
scheduling procedure for use in a distributed parallel processing
environment in which the processing elements (PEs) are interconnected
through a crossbar switch.  in such a system, it is possible for any
PE to communicate with any other PE (by sending or receiving a
message), as long as neither is currently engaged in any other
communication.  In many applications, it is necessary for each PE to
communicate with every other PE by sending a fixed length message to
every PE, and by receiving a similar message from every PE.  Since no
PE can communicate with more than one PE at any given time, it is
important to choose a message scheduling procedure which avoids
attempting to communicate with a PE which is "busy".  It is also
desirable to maximize the utilization of the crossbar switch by
ensuring that as many PEs as possible are communicating at all times.
The following procedure solves both problems in a simple way.

      Terms used in description:
N -- total number of PEs
P -- current PE number
K -- communication period
T -- target PE (PE which processor P communicates with during period
K)

      Assuming that two PEs can exchange messages during a "full
exchange" period, and that no PE needs to communicate with itself,
the total number of periods needed for an all-to-all exchange is
derived as follows:
      Total number of communications = N(N-1)
      Number of simultaneous communications possible = N/2 N even
(N-1)/2 N odd
      Number of "simple exchange" periods needed = N(N-1)/(N/2) N
even N(N-1)/((N-1)/2 N odd
      Number of "full exchange" periods needed = N-1 N even N N odd

      The matrices shown in Fig. 1 represent solutions of the problem
form N=5 and N=6.  Each column represents one communicat...