Browse Prior Art Database

Data Structures and Algorithms for Collective Communication Over a Dynamically Determined Set of Processors in Distributed Memory Parallel Computers

IP.com Disclosure Number: IPCOM000109418D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 6 page(s) / 352K

Publishing Venue

IBM

Related People

Balasundaram, V: AUTHOR [+2]

Abstract

The need for collective communication among processors often arises in parallel computation. In distributed-memory parallel computers, such communication can be realized using low-level point to point message-passing primitives, such as send and receive. Frequently, it is desirable to carry out collective communication over a subset of the processors that is dynamically determined at run-time. For efficiency considerations, it is preferable to have only processors belonging to the subset get involved in the realization of the collective communication. Disclosed are data structures and algorithms for collective communication over a dynamically determined set of processors in distributed-memory parallel computers.

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

Data Structures and Algorithms for Collective Communication Over a Dynamically Determined Set of Processors in Distributed Memory Parallel Computers

       The need for collective communication among processors
often arises in parallel computation.  In distributed-memory parallel
computers, such communication can be realized using low-level point
to point message-passing primitives, such as send and receive.
Frequently, it is desirable to carry out collective communication
over a subset of the processors that is dynamically determined at
run-time.  For efficiency considerations, it is preferable to have
only processors belonging to the subset get involved in the
realization of the collective communication.  Disclosed are data
structures and algorithms for collective communication over a
dynamically determined set of processors in distributed-memory
parallel computers.

      The parallel programming model is assumed to be Single Program
Multiple Data (SPMD).  An application program written in this model
consists of a single piece of code that is compiled into a single
executable image.  The same executable image is loaded into each
processor assigned to the application at load-time.  However, the
data domain is partitioned among the processors, so that each
processor has exclusive access to the data contained in its local
partition.

      At load-time, the number of processors assigned to an
application is saved in a pre-defined global variable nprocs, whose
value may be used within the application program itself.  Each of the
nprocs processors is assigned a unique Processor Identification (PID)
number ranging from 0 through nprocs-1, that is saved in the
pre-defined variable mypid in each processor.

      In the distributed-memory parallel computer, data can be
communicated between pairs of processors using the two complementary
primitives send and receive.  The source processor transmits data to
the destination processor using the send primitive, which is assumed
to be point to point and non-blocking.  The destination processor
accepts the data from the source processor using the receive
primitive, which is assumed to be point to point and blocking.  It is
assumed that processors other than the source and the destination of
the point to point communication do not get involved in the
communication.

      Disclosed are data structures and algorithms for collective
communication over a dynamically determined set of processors in
distributed-memory parallel computers.  The data structures are used
to keep information about the processors in the dynamically
determined set.  The algorithms use these data structures to
implement the collective communication routines broadcast and reduce.
The implementations of several other collective communication
routines are also described as variants of broadcast and reduce.
Data strucutres

      The basic data structure is an array member [0..n-1], whose
entries are t...