News Column

Patent Issued for Implementing Asyncronous Collective Operations in a Multi-Node Processing System

July 29, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- International Business Machines Corporation (Armonk, NY) has been issued patent number 8782164, according to news reporting originating out of Alexandria, Virginia, by VerticalNews editors.

The patent's inventors are Chen, Dong (Yorktown Heights, NY); Eisley, Noel A. (Yorktown Heights, NY); Heidelberger, Philp (Yorktown Heights, NY); Kumar, Sameer (Yorktown Heights, NY); Salapura, Valentina (Yorktown Heights, NY); Steinmacher-Burow, Burkhard (Boeblingen, DE).

This patent was filed on January 29, 2010 and was published online on July 15, 2014.

From the background information supplied by the inventors, news correspondents obtained the following quote: "The present invention, generally, relates to collective operations in data processing systems, and more specifically, to asynchronous collective operations in multimode data processing systems.

"Parallel computer applications often use message passing to communicate between processors. Message passing utilities such as the Message Passing Interface (MPI) support two types of communication: point-to-point and collective. In point-to-point messaging, a processor sends a message to another processor that is ready to receive it. In a collective communication operation, however, many processors participate together in the communication operation.

"Collective communication operations play a very important role in high performance computing. In collective communication, data are redistributed cooperatively among a group of processes. Sometimes the redistribution is accompanied by various types of computation on the data and it is the results of the computation that are redistributed. MPI, which is the de facto message passing programming model standard, defines a set of collective communication interfaces, including MPI_BARRIER, MPI_EBCAST, MPI_REDUCE, MPI_ALLREDUCE, MPI_ALLGATHER, MPI_ALLTOALL etc. These are application level interfaces and are more generally referred to as APIs. In MPI, collective communications are carried out on communicators which define the participating processes and a unique communication context.

"Functionally, each collective communication is equivalent to a sequence of point-to-point communications, for which MPI defines MPI_SEND, MPI_RECEIVE and MPI_WAIT interfaces (and variants). MPI collective communication operations are implemented with a layered approach in which the collective communication routines handle semantic requirements and translate the collective communication function call into a sequence of SFND/RECV/WAIT operations according to the algorithms used. The point-to-point communication protocol layer guarantees reliable communication.

"Collective communication operations can be synchronous or asynchronous. In a synchronous collective operation all processors have to reach the collective before any data movement happens on the network. For example, all processors need to make the collective API or function call before any data movement happens on the network. Synchronous collectives also ensure that all processors are participating in one or more collective operations that can be determined locally. In an asynchronous collective operation, there are no such restrictions and processors can start sending data as soon as the processors reach the collective operation. With asynchronous collective operations, several collectives can be happening simultaneously at the same time.

"Asynchronous one-sided collectives that do not involve participation of the intermediate and destination processors are critical for achieving good performance in a number of programming paradigms. For example, in an async one-sided broadcast, the root initiates the broadcast and all destination processors receive the broadcast message without any intermediate nodes forwarding the broadcast message to other nodes."

Supplementing the background information on this patent, VerticalNews reporters also obtained the inventors' summary information for this patent: "Embodiments of the invention provide a method, system, and computer program product for implementing an asynchronous collective operation in a multi-node data processing system. In one embodiment, the method comprises sending data to a plurality of nodes in the data processing system, broadcasting a remote get to said plurality of nodes, and using said remote get to implement asynchronous collective operations on said data by the plurality of nodes.

"In an embodiment, each of said plurality of nodes sets up a base address table with an entry for the source memory buffer associated with said each node's contribution to the global sum.

"In an embodiment, each of said plurality of nodes sets up a base address table with an entry for the address to the destination memory buffer on the target where the summed output is copied to.

"In an embodiment, all the nodes have the same physical address for the source buffer and this address is placed once in the remote get descriptor payload (this is an optimization to reduce of the base address table by eliminating injection source buffers from it).

"In an embodiment, each compute node has N processes and the root node initiates N remote get operations (one for each process) to complete the one-sided reduce operation and then does a local sum to complete the one-sided reduce.

"In an embodiment, the invention provides a mechanism for a Messaging Unit to initiate a one-sided allreduce operation by injecting a remote get descriptor that is broadcast to all the compute nodes and initiates a global-sum operation back to the initiating node or an arbitrary target node.

"In one embodiment, each of said plurality of nodes sets up a base address table with an entry for a base address of a memory buffer associated with said each node. In an embodiment, said broadcasting includes sending a defined communication to said plurality of destination nodes, and injecting a remote get descriptor into said defined communication. In an embodiment, said remote get descriptor includes a put that reduces data back to a root node during said asynchronous collective operations. In an embodiment, each of said plurality of nodes performs only one task in the asynchronous collective operation.

"In one embodiment, each of the plurality of destination nodes performs a plurality of tasks in the collective operations, and each of the tasks of each of said plurality of nodes sets up a base address table with an entry for a base address of a memory buffer associated with said each task. In an embodiment, said broadcasting includes sending a communication to said plurality of destination nodes, and injecting a remote get descriptor into said communication. In an embodiment, said descriptor includes a put that reduces data back to a root node. In one embodiment, said put reduces data back to the root node from a first of the tasks performed by each of the nodes during the collective operation, and said broadcasting includes sending a put to each of the tasks of each of the nodes to reduce data from said each task to the root node.

"In one embodiment, the invention uses the remote get collective to implement one-sided operations. The compute node kernel (CNK) operating system allows each MPI task to map the virtual to physical addresses of all the other tasks in the booted partition. Moreover the remote-get and direct put descriptors take physical address of the input buffers."

For the URL and additional information on this patent, see: Chen, Dong; Eisley, Noel A.; Heidelberger, Philp; Kumar, Sameer; Salapura, Valentina; Steinmacher-Burow, Burkhard. Implementing Asyncronous Collective Operations in a Multi-Node Processing System. U.S. Patent Number 8782164, filed January 29, 2010, and published online on July 15, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8782164.PN.&OS=PN/8782164RS=PN/8782164

Keywords for this news article include: Information Technology, Information and Data Processing, International Business Machines Corporation.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters