Abstract:
An inter-processor communication approach is applicable to a message passing pattern called iterative exchange. In such patterns, two processors exchange messages, then perform a computation, and then this process is repeated. If two sets of send and receive buffers are used, then it is possible to guarantee that a receive buffer on the receiver&#39;s side is always available to receive the message. A message passing system controls which buffers are used for sending and receiving. These buffers are registered beforehand, thereby avoiding repeated registration at the time messages are sent. The sender is initially informed of all the possible receive buffers that the receiver will use, and the sender then uses these receive buffers alternately. Examples of this approach can avoid the use of multiple-step rendezvous protocols, memory copies, and memory registrations when a message needs to be sent.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Application No. 60/827,558, filed on Sep. 29, 2006, titled “Iterative Exchange Communication,” which is incorporated herein by reference. 
    
    
     This application is also related to PCT Application No. PCT/US2006/032498, titled “ARCHITECTURES FOR COMPUTATION OF PARTICLE INTERACTIONS,” filed on Aug. 18, 2006, which is incorporated herein by reference. 
     BACKGROUND 
     This invention relates to a communication approach. 
     In a distributed computing system, such as in a distributed memory parallel computer system, messages may be sent from one processor (the sender) to another (the receiver) so that they can work cooperatively to solve a computational problem. The processors are connected, for example, via a communication network. In general, the problem can be solved more quickly if messages can be sent and received more quickly or otherwise transferred in a way that reduces the amount of time processors are idle waiting for messages. Communication via sending and receiving messages is called message passing. 
     Implementations of message passing systems can face a number of technical constraints which, depending on the implementation, can reduce the efficiency of the system. These technical constraints can include: 
     1) the sender must make sure that the receiver has memory to receive the message 
     2) the sender must know where to put the message on the receiver&#39;s side 
     3) memory for the message&#39;s send buffer (on the sender&#39;s side) and receive buffer (on the receiver&#39;s side) must be registered, which can be a costly process. 
     One approach to addressing the first two constraints involves a rendezvous protocol. In such a protocol, the sender first sends a short “request” message. (The message is short and uses reserved space on the receiver&#39;s side.) The receiver responds with a short “reply” message containing the address of the receive buffer after the receiver is ready to receive the message. Finally, the sender sends the actual message. It is desirable to avoid using a rendezvous protocol since the overhead involved in the initial request and reply exchange can render it less efficient than sending a message directly. 
     To address the third technical constraint, the message passing system can keep track of what send and receive buffers have been registered. Further messages using these buffers do not need to be re-registered, thus saving the memory registration cost. Messages using buffers that have not been registered still need to be registered. 
     Another approach to addressing the third constraint can be used when the messages are short. The message passing system reserves several send and receive buffers and registers them. A short message is copied into one of these pre-registered buffers and sent to another pre-registered buffer on the receiver&#39;s side. The message is then copied to the receiver&#39;s actual message destination. The overhead associated with copying the message to its actual destination can render this approach less efficient that transferring the message directly into its actual destination. Therefore, this mechanism is generally most applicable to short messages. The approach can also suffer from the possibility that reserved buffers may run out. 
     SUMMARY 
     In one aspect, in general, the first constraint is addressed for a message passing pattern called iterative exchange. In such patterns, two processors exchange messages, then perform a computation, and then this process is repeated. If two sets of send and receive buffers are used, then it is possible to guarantee that a receive buffer on the receiver&#39;s side is always available to receive the message. 
     In another aspect, in general, the second and third constraints are addressed by a message passing system that controls which buffers are used for sending and receiving. These buffers are registered beforehand. Therefore, no memory registrations needs to happen at the time messages are sent. The second constraint is addressed by telling the sender all the possible receive buffers that the receiver will use, and agreeing that the receive buffers will be used alternately. 
     In another aspect, in general, message communication in a multiple processor system, includes, at each of a plurality of processors, maintaining multiple receive buffers and multiple send buffers for communication with another of the plurality of processors. Each send buffer is associated with a corresponding receive buffer on the same processor. Data is exchanged between a first of the processors and a second of the processors. This exchange includes, at the first processor repeatedly using multiple send buffers for passing data to the second processor including at each repetition delaying transmission from a send buffer until data is received in the corresponding receive buffer. 
     Aspects can include one or more of the following features. 
     The delaying of transmission from a send buffer includes further delaying until it is permissible to receive data in the corresponding receive buffer. 
     The further delaying includes delaying until it is permissible for the data received in the corresponding receive data to be overwritten by further transmissions from the second processor. 
     Maintaining the send and receive buffers includes registering said buffers with a communication interface. 
     The exchanging of the data is performed without requiring repeated exchanges between the processors for the purpose of establishing a state of a receive buffer. 
     The state of a receive buffer identifies when it is permissible to send data to that receive buffer. 
     The state of a receive buffer identifies a location of the receive buffer. 
     In another aspect, in general, a multiple processor communication system includes multiple processors and communication links coupling pairs of the processors. For each of the pairs of processors, multiple send buffers and multiple receive buffers are at each of the processors of the pair. Each send buffer is configured for passing data to a corresponding receive buffer at the other processor of the pair, and is associated with a corresponding receive buffer at the same processor. Each of the processors of the pairs of processors is configured to delay passing of data from a send buffer to a corresponding receive buffer at another processor until processing of data is completed for the corresponding receive buffer on the sending processor. 
     Aspects can have one or more of the following advantages. 
     Aspects can avoid the use of multiple-step rendezvous protocols, memory copies, and memory registrations that occur when a message needs to be sent. 
     Messages can be sent faster and thus computational problems on distributed memory parallel computers can be solved faster. 
     Other features and advantages of the invention are apparent from the following description, and from the claims. 
    
    
     
       DESCRIPTION OF DRAWINGS 
         FIG. 1  is a diagram of a message passing system. 
         FIG. 2  is a timing diagram that illustrates exchanges between processors in a message passing system. 
         FIG. 3  is a diagram that illustrates an alternative message passing approach. 
     
    
    
     DESCRIPTION 
     Referring to  FIG. 1 , a message passing system  100  includes a number of processors  110 . In  FIG. 1 , only two processors are illustrated. In general, the approaches described here are applicable to two or more processor systems or single processor systems running two or more communicating programs. Each processor includes a number of data buffers  120 . Some of the buffers are used as send buffers and some are used as receive buffers. In addition, each send buffer at one processor is associated with a particular receive buffer at the other processor. In  FIG. 1 , each processor  110  has four buffers, two send buffers (labeled A and C) and two receive buffers (labeled B and D). Send buffers A and C are associated with receive buffers B and D, respectively, at the other processor. In some implementations, a software application executing at each processor registers the send and receive buffers with the operating system, thereby making them available for inter-processor communication services implemented with the aid of the operating system. For example, such registration establishes a mapping between a physical address space and the virtual address space of the application, and ensures that the buffers remain at a fixed location in the physical memory. 
     In some example of a system  100 , an iterative computation is performed such that at each iteration of the computation, data is first exchanged between the processors, a first computation is performed at each processor, and then the results of the computations are then exchanged, and further computation is performed. In some examples, the computation relates to a dynamics simulation system in which processors first exchange data related to locations of particles, each processor computes forces on particles based on the received data, the processors exchange force data for the particles, and then each processor computes updated locations for the particles using the exchanged forces. A detailed example of such an iterative exchange computation in the context of a molecular simulation system is described in copending PCT Application No. PCT/US2006/032498, “ARCHITECTURES FOR COMPUTATION OF PARTICLE INTERACTIONS.” 
     In some examples, a send module  132  at each processor  110  has data to send to a receive module  134  at the other processor. Initially, each processor can assume that the receive buffers B and D at the other processor are free. The send module  132  alternates between sending data via send buffer A and send buffer C. Therefore, it first sends the data from buffer A to buffer B at the other processor (transmissions  140  and  142  from processor  0  and processor  1 , respectively). 
     Before sending data via the C send buffer  120 , each processor  110  waits until the data has been received in its receive buffer B, and the data has been used and the receive buffer is free to receive a further message. These timing constraints are illustrated by broken arrows  156  and  158 . At that point, the sending module  132  uses the C send buffer to send a further message to the other processor (transmissions  144  and  146  from processors  0  and  1 , respectively). Because these transmissions were delayed until after receive buffer B on the same processor was free, the processor receiving the transmission to its D receive buffer can allow a transmission from its A buffer to the other B buffer without the possibility of overwriting the data in the B buffer. These constraints are illustrated using broken arrows  152  and  154 . This cycle continues, with the sender module  132  alternating between using send buffers A and C and the receive module  134  alternating between using receive buffers B and D. 
     Referring to  FIG. 2 , a series of exchanges between two processors is illustrated in timing flow charts, with time generally flowing from top to bottom of the figure. Actions at processor  0  are shown on the left of the figure and actions at processor  1  are shown on the right of the figure. Initially, each processor sends from its A send buffer  120  (step  210 ), with the other processor receiving the sent data in its B receive buffer (step  212 ). After a processor receives the data in its B receive buffer (step  212 ) it uses the data in place (step  214 ). That is, the processor does not have to copy the data to an actual destination location because the processor can be guaranteed that the other processor will not send more data to that buffer until the data in that buffer is no longer needed. When the data is no longer needed, the B receive buffer is free (step  216 ). Note that in the example illustrated in  FIG. 2 , processor  1  uses receive buffer B for a longer period of time than does processor  0 . After processor  0  finished using its buffer B, which is at a point that processor  1 &#39;s buffer B is not yet free, processor  0  sends data from its C send buffer (step  218 ) which is received at the destination processor&#39;s D receive buffer (step  220 ). At a later point, processor  1  has completed its use of the data in buffer B, and sends data from its C send buffer (step  218 ). Note that at processor  1 , use of buffer D can occur concurrently with transmission from buffer C, as illustrated in this example. After sending data from the C send buffers, the roles of B and C buffers are essentially taken by buffers D and A, respectively, with steps  220 ,  222 ,  224 , and  210  corresponding to steps  212 ,  214 ,  216 , and  218 , respectively. That is, when processor  0  receives a message into buffer D (step  220 ), it implies that the communication from processor  0 &#39;s buffer A to processor  1 &#39;s buffer B has completed and that the associated send buffer A and the receive buffer B are available. The next communication steps  210  and  212  then use these buffers without needing to synchronize with the receiver, and the communication process continues with further repetitions of the steps illustrated in  FIG. 2 . 
     At initialization time, an application specifies which pairs of processors will communicate, as well as the maximum buffer sizes required for each message. Two sets of buffers (two receive and two send buffers) for each connection are allocated and registered at this time. The application uses these buffers directly, alternating between the two sets of buffers as described. 
     In some implementations, for example in some implementations of the system described in the copending PCT application PCT/US2006/032498 of a system using multiple general purpose computers coupled by communication links (e.g., serial communication links or a communication network), the communication techniques described herein may be used to provide communication services. In such an implementation, the receive buffers may be in a memory that is essentially loaded by direct writes from memory associated with another processor without intervention by the processor performing computation. The communication links between the processors use, for example, InfiniBand use a Verbs interface provided by Mellanox Technologies. Transfers of messages use a remote direct memory access (RDMA) write operations, which are faster than RDMA read operations with this hardware. In some implementations, each processor polls its read buffer to know when a message has arrived, since it is inefficient for RDMA writes to generate a completion signal on the receive side. 
     Referring to  FIG. 3 , an alternative embodiment uses more than two pairs of buffers  120 , in the general case N pairs of buffers. For example, the approach described above can be considered as two sets of send and receive buffers  120 : A and D, and C and B, which in  FIG. 3  would be labeled from N=2 as T 1 , R 1 , T 2 , R 2 , respectively, on processor  0  and labeled as T 2 ′, R 2 ′, T 1 ′, R 1 ′, respectively, on processor  1 . In each set, use of the send buffer (Tn) is delayed (other than initially) until after receipt and processing of the transmission into the receive buffer (Rn) of the set. In the general case, a set of send and receive buffers Tn, Rn at processor  0  are associated with Rn′, Tn′ at processor  1 . The send module  132  at processor  0  then, after an initial set of transmissions, essentially conducts a round robin between the send buffers T 1 , T 2 , . . . , TN, T 1 , . . . , waiting to send using send buffer Tn until processing of data received in buffer Rn (sent from buffer Tn′ at processor  1 ). As an initialization, processor  0  sends without waiting using buffers T 1 , . . . , Tk, while processor  1  sends without waiting using buffers T(k+1), . . . , TN. So in general, the ith transmission from send buffer Tn waits for the (i−1)st reception in receive buffer Rn. One advantage of this approach is that more overlap of transmission and computation times may be achievable. 
     In some embodiments, a corresponding pair of send and receive buffers share the same memory region (e.g., address ranges). For example, referring to  FIG. 1 , a pair of buffers  120  labeled A (send) and D (receive) on processor  0  uses a single memory region and a pair of buffers  120  labeled B (receive) and C (send) on processor  0  uses a different single memory region. In these embodiments, a processor may receive data, use the data in place, and send the data from the same memory region from which it just received data. Because two or more corresponding pairs of send and receive buffers are used, a buffer is guaranteed to be available to receive data when used in conjunction with the iterative exchange protocol described above. 
     Embodiments of approaches described above can be implemented in hardware, in software, or in a combination of hardware and software. For example, the iterative exchange protocol can be implemented in special purpose hardware, which may include processor or controller elements that make use of instructions that cause the elements to perform steps of the protocol. The approaches are applicable to a variety of interconnections of processors (or more generally processing nodes), including shared communication media, as well as dedicated communication media, for example, with a dedicated medium for each pair of communicating processors. 
     Other embodiments are within the scope of the following claims.