Communication primitives for BSP computers

The bulk-synchronous parallel (BSP) model is based on two parameters of g and L that characterize the hardware of a machine. A set of communication primitives is studied that have been found useful when implementing scientific and engineering applications. The following problems are considered: 1. s...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1996-06, Vol.58 (6), p.303-310
Main Authors: Juurlink, Ben H.H., Wijshoff, Harry A.G.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Communication
Communication operations
Communications processors
Computer programming
Computer science
control theory
systems
Exact sciences and technology
Mathematical models
Network topologies
Parallel algorithms
Parallel computation models
Parallel processing
Routing
Studies
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The bulk-synchronous parallel (BSP) model is based on two parameters of g and L that characterize the hardware of a machine. A set of communication primitives is studied that have been found useful when implementing scientific and engineering applications. The following problems are considered: 1. single-item broadcast, 2. k-item broadcast, 3. prefix, 4. 2D prefix, 5. sorting P elements, where P is the number of processors, and 6. duplication. The values of g and L that can be obtained in practice depend on: 1. the network topology, 2. the routing algorithm, and 3. technological factors such as the channel capacities and the network cycle time. It is possible to perform a single item broadcast/prefix operation on a P-processor hypercube in O(log P) time. There is a gap of log P/log log P between the network implementation and the BSP implementation. In general, a single communication step of the network model can be simulated on the BSP model in time less than or equal to L.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(96)00073-7