Browse Prior Art Database

Optimal Algorithm for Concatenating Data in Message-Passing Systems

IP.com Disclosure Number: IPCOM000106495D
Original Publication Date: 1993-Nov-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 28K

Publishing Venue

IBM

Related People

Bruck, J: AUTHOR [+3]

Abstract

Disclosed is an optimal algorithm for performing concatenation (i.e., all-to-all broadcasting) in a message-passing parallel system. Let n be the number of nodes among which the concatenation operation is to be performed and let k equals lbracket log sub 2 n rbracket. The disclosed concatenation algorithm treats the n processors P sub 0,P sub 1,...,P sub as being logically arranged on a circle in increasing order of their indices. Processor P sub i contains data block d lbracket i rbracket initially. Our algorithm is based on an n-node circulant graphs with the set of offsets being all the power-of-two numbers which are less than n

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

Optimal Algorithm for Concatenating Data in Message-Passing Systems

      Disclosed is an optimal algorithm for performing concatenation
(i.e., all-to-all broadcasting) in a message-passing parallel system.
Let n be the number of nodes among which the concatenation operation
is to be performed and let k equals lbracket log sub 2 n rbracket.
The disclosed concatenation algorithm treats the n processors P sub
0,P sub 1,...,P sub <n-1> as being logically arranged on a circle in
increasing order of their indices.  Processor P sub i contains data
block d lbracket i rbracket initially.  Our algorithm is based on an
n-node circulant graphs with the set of offsets being all the
power-of-two numbers which are less than n

      The algorithm finishes in k steps.  When n is a power of two,
then during step r, for 0 ge r ge k - 1, each processor P sub i sends
all its cumulated messages M to processor P sub <i minus 2 sup r> and
receive a message M prime from processor P sub <i plus 2 sup r>.  The
message M consists of the 2 sup r blocks of data d lbracket i
rbracket...d lbracket i plus 2 sup r minus 1 rbracket.  The message M
prime consists of the 2 sup r blocks of data d lbracket i plus 2 sup
r rbracket.  d lbracket i plus 2 sup <r plus 1> minus 1 rbracket.
When n is not a power of two, the first k minus 1 steps are the same
as before, except that for the last step only the necessary subset of
the local cumulated message is sent.