TY - GEN

T1 - Direct bulk-synchronous parallel algorithms

AU - Gerbessiotis, Alexandrosv

AU - Valiant, Leslieg

N1 - Funding Information:
The parameters of such a machine are p, the number of processor/memory components, L, the minimal time (measured in terms of basic local computation steps) *This research was supported in part by the National Science Foundation under grant CCR-89-02500 and by the Of[ice of Naval Research under grant N00014-85-K-0445.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.

PY - 1992

Y1 - 1992

N2 - We describe a methodology for constructing parallel algorithms that are transportable among parallel computers having different numbers of processors, different bandwidths of interprocessor communication and different periodicity of global synchronisation. We do this for the bulk-synchronous parallel (BSP) model, which abstracts the characteristics of a parallel machine into three numerical parametersp, g, andL, corresponding to processors, bandwidth, and periodicity respectively. The model differentiates memory that is local to a processor from that which is not, but, for the sake of universality, does not differentiate network proximity. The advantages of this model in supporting shared memory or PRAM style programming have been treated elsewhere. Here we emphasise the viability of an alternative direct style of programming where, for the sake of efficiency the programmer retains control of memory allocation. We show that optimality to within a multiplicative factor close to one can be achieved for the problems of Gauss-Jordan elimination and sorting, by transportable algorithms that can be applied for a wide range of values of the parametersp, g, andL. We also give some simulation results for PRAMs on the BSP to identify the level of slack at which corresponding efficiencies can be approached by shared memory simulations, provided the bandwidth parametergis good enough.

AB - We describe a methodology for constructing parallel algorithms that are transportable among parallel computers having different numbers of processors, different bandwidths of interprocessor communication and different periodicity of global synchronisation. We do this for the bulk-synchronous parallel (BSP) model, which abstracts the characteristics of a parallel machine into three numerical parametersp, g, andL, corresponding to processors, bandwidth, and periodicity respectively. The model differentiates memory that is local to a processor from that which is not, but, for the sake of universality, does not differentiate network proximity. The advantages of this model in supporting shared memory or PRAM style programming have been treated elsewhere. Here we emphasise the viability of an alternative direct style of programming where, for the sake of efficiency the programmer retains control of memory allocation. We show that optimality to within a multiplicative factor close to one can be achieved for the problems of Gauss-Jordan elimination and sorting, by transportable algorithms that can be applied for a wide range of values of the parametersp, g, andL. We also give some simulation results for PRAMs on the BSP to identify the level of slack at which corresponding efficiencies can be approached by shared memory simulations, provided the bandwidth parametergis good enough.

UR - http://www.scopus.com/inward/record.url?scp=84947911139&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947911139&partnerID=8YFLogxK

U2 - 10.1007/3-540-55706-7_1

DO - 10.1007/3-540-55706-7_1

M3 - Conference contribution

AN - SCOPUS:84947911139

SN - 9783540557067

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 18

BT - Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Nurmi, Otto

A2 - Ukkonen, Esko

PB - Springer Verlag

T2 - 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992

Y2 - 8 July 1992 through 10 July 1992

ER -