Browse Prior Art Database

Efficient Broadcasting in the Postal Model for Synchronous Message Passing Systems

IP.com Disclosure Number: IPCOM000110135D
Original Publication Date: 1992-Oct-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 6 page(s) / 262K

Publishing Venue

IBM

Related People

Bar-Noy, A: AUTHOR [+2]

Abstract

Disclosed are algorithms PARTITION and D-D-TREES for broadcasting multiple messages in synchronous message-passing systems with communication latencies.

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

Efficient Broadcasting in the Postal Model for Synchronous Message Passing Systems

       Disclosed are algorithms PARTITION and D-D-TREES for
broadcasting multiple messages in synchronous message-passing systems
with communication latencies.

      In message-passing systems processors submit messages to and
receive messages from an underlying communication network, which
delivers messages from sources to destinations.  Several
distributed-memory parallel computers (e.g., MIT J-machine (1)) and
several high-speed communication networks (e.g., PARIS (2), plaNET
(3)) ignore the exact structure of the network and assume that the
network creates a complete point-to-point communication graph.  In
these systems, sending a message is a send-and-forget event, and
passing a message between any pair of processors takes roughly the
same time.

      This article uses the postal model introduced in (4), for
communication in message-passing systems.  This model addresses the
issue of communication latencies in such systems by employing a
latency parameter g > 1 that measures the inverse of the ratio
between the time it takes an originator of a message to send it and
the time that passes until the recipient of that message receives it.
To model the situation in synchronous message-passing systems, a
variation of the postal model is used.  It is assumed that there is a
system-wide notion of rounds and that each processor can send and
receive at most one message in any given round.  If processor p sends
a message M to processor q in round t, then p is busy sending M
between the clock reading of t-1 and the clock reading of t.  In
subsequent rounds, after p had sent M, it is free to perform other
functions including sending other messages.  Passing M is associated
with a communication latency of g  >, which is assumed to be an
integral number.  This means that M arrives at q in round t+g-1
(i.e., by the clock reading of t+g-1).  The notation MPS (n,g) is
used to refer to a synchronous message-passing system with n
processors and communication latency g.

      The broadcasting problem of m > 1 messages in MPS (n,g) is
defined as follows.  At time t=0, processor p0 has m messages
M1,M2,...,Mm to broadcast to the other n-1 processors.  One goal is
the design of algorithms that minimize the arrival time of the last
message to the last processor.  Another goal is the design of
algorithms that achieve a perfect pipelining, that is, algorithms
that enable the originator of a broadcasting process to submit a new
message to the network in every round.  Other variants of
broadcasting algorithms were investigated for both parallel computers
and distributed-processing environments (see (5,6)).
Background Tools
Broadcasting one message

      First defined is the generalized Fibonacci function Fg(t) and
its index function fg(n).

                            (Image Omitted)

Fg(t) is defined from non-negative r...