Electrical computers and digital processing systems: multicomput – Multicomputer data transferring via shared memory
Reexamination Certificate
1999-06-21
2003-07-29
Jean, Frantz B. (Department: 2155)
Electrical computers and digital processing systems: multicomput
Multicomputer data transferring via shared memory
C709S214000, C709S215000
Reexamination Certificate
active
06601089
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of digital computer systems, and more particularly to mechanisms for facilitating transfer of information between and among a plurality of processes.
BACKGROUND OF THE INVENTION
Computers typically execute programs in one or more processes or threads (generally “processes”) on one or more processors. If a program comprises a number of cooperating processes which can be processed in parallel on a plurality of processors, sometimes groups of those processes need to communicate to cooperatively solve a particular problem. Two basic architectures have been for multi-processor computer systems, namely, distributed memory systems and shared memory systems. In a computer system constructed according to the distributed memory architecture, processors and memory are allocated to processing nodes, with each processing node typically having a processor and an associated “node memory” portion of the system memory. The processing nodes are typically interconnected by a fast network to facilitate transfer of data from one processing node to another when needed for, for example, processing operations performed by the other processing node. Typically in a computer constructed according to the distributed memory architecture, a processor is able to access data stored in its node memory faster that it would be able to access data stored in node memories on other processing nodes. However, contention for the node memory on each processing node is reduced since there is only one processor, that is, the processor on the processing node, which accesses the node memory for its processing operations, and perhaps a network interface which can access the node memory to store therein data which it received from another processing node, or to retrieve data therefrom for transfer to another processing node.
Typically, in a computer system constructed according to the shared memory architecture, the processors share a common memory, with each processor being able to access the entire memory in a uniform manner. This obviates the need for a network to transfer data, as is used in a computer system constructed according to the distributed memory architecture; however, contention for the shared memory can be greater than in a computer system constructed according to the distributed memory architecture. To reduce contention, each processor can be allocated a region of the shared memory which it uses for most of its processing operations. Although each processor's region is accessible to the other processors so that they (that is, the other processors) can transfer data thereto for use in processing by the processor associated with the respective region, typically most accesses of a region will be by the processor associated with the region.
A computer system can be constructed according to a combination of the distributed and shared memory architectures. Such a computer system comprises a plurality of processing nodes interconnected by a network, as in a computer system constructed according to the distributed memory architecture. However, each processing node can have a plurality of processors which share the memory on the respective node, in a manner similar to a computer constructed according to the shared memory architecture.
Several mechanisms have been developed to facilitate transfer of data among processors, or more specifically, between processing node memories, in the case of a computer system constructed according to the distributed memory architecture, and/or memory regions, in the case of a computer system constructed according to the shared memory architectures. In one popular mechanism, termed “message passing,” processors transfer information by passing messages therearnong. Several well-known message passing specifications have been developed, including MPI and PVM. Generally, in message passing, to transfer data from one processor to another, the transferring processor generates a message including the data and transfers the message to the other processor. On the other hand, when one processor wishes to retrieve data from another processor, the retrieving processor generates a message including a retrieval request and transfers the message to the processor from which the data is to be retrieved; thereafter, the processor which receives the message executes the retrieval request and transfers the data to the requesting processor in a message as described above.
In a computer system constructed according to the distributed memory architecture, the messages using the message passing mechanism are transferred between processing nodes over the network and processed or otherwise handled by the respective processing node when they arrive at the respective destination. In a computer system constructed according to the shared memory architecture, several buffer arrangements have been developed to facilitate message transfer. In one arrangement, each process is provided with a plurality of buffers, each associated with one of the other processes. When an “i-th” process wishes to transfer a message to another “j-th” process, it (that is, the “i-th” process) deposits the message in a buffer B(i,j) that is maintained therefor. Similarly, when the “j-th” process wishes to transfer a message to the “i-th” process, it (that is, the “j-th” process), will deposit the message in another buffer B(j,i) maintained therefor. Thereafter, the “j-th” process can retrieve the message by copying it to its region of memory, after which the “i-th” process can again transfer a message to the “j-th” process. Allocating buffers in this manner ensures that there will be no contention for buffers as among processes attempting to transmit messages to the same process; thus, after the “i-th” process has deposited a message for the “j-th” process in buffer B(i,j), the “k-th” process can also transfer a message to the “j-th” process by depositing the message in the buffer B(k,j) before the “j-th” process has copied the “i-th” process's message from the buffer B(i,j). However, since each buffer is typically relatively large, generally sufficiently large as to be able to accommodate a relatively large message, it will be appreciated that a significant portion of the memory address space may be required for the buffers, and further that the portion will increase, with increasing numbers of processes, on the order of N
2
, where “N” is the number of processes.
In another mechanism, instead of providing relatively large buffers B(i,j) for the respective processes, a buffer pool is provided comprising a plurality of buffers available to all of the processes, with the buffers B(x) in the pool having sizes on the order of the sizes of the buffers B(i,j). In addition, each process is provided with a relatively small buffer, referred to as a postbox P. When the “i-th” process wishes to transfer a message to the “j-th” process, if the message will fit into the postbox, it (that is, the “i-th” process) will store the message in its postbox P(i,j) for the “j-th” process. On the other hand, if the message will not fit into the postbox, the “i-th” process will allocate a buffer B(x) from the pool, load the message into the buffer B(x) and load a pointer to the buffer B(x) in its postbox P(i,j) for the “j-th” process. Thereafter, the “j-th” process can detect that a message or pointer has been loaded into its postbox P(i,j) and retrieve it (that is, the message or pointer) therefrom. If the postbox P(i,j) contains a pointer, the “j-th” process can use the pointer to identify the buffer B(x) which contains the message and retrieve it (that is, the message) therefrom by copying it to its region of memory. After the “j-th” process has retrieved the message from the buffer B(x), it can return the buffer to the buffer pool. This mechanism provides the advantage that it reduces the amount of memory space which is needed to be provided from that described above, since the postboxes P(i,j) require far less space than the buffers B(i,j), and the number of buffers B(x) can be bo
Dontje Terry D.
Sistare Steven J.
Jean Frantz B.
Kivlin B. Noäl
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sun Microsystems Inc.
LandOfFree
System and method for allocating buffers for message passing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for allocating buffers for message passing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for allocating buffers for message passing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3082472