TY - JOUR
T1 - Ordered h-Level Graphs on the BSP Model
AU - Gerbessiotis, Alexandros V.
AU - Siniolakis, Constantinos J.
N1 - Funding Information:
1The work of the first author was supported in part by EPSRC(UK) under Grant GR/K16999 and the second author was supported in part by a Bodossaki Foundation graduate scholarship. A short abstract describing part of this work appeared in EUROPAR ’96, Lyons, France.
PY - 1998/2/25
Y1 - 1998/2/25
N2 - The implementation of data structures on distributed memory models such as the bulk-synchronous parallel model, rather than shared memory ones such as the parallel random access machine, offers a serious challenge. In this work we undertake the architecture independent study of the computation and communication requirements of searchingordered h-level graphs, which include many of the standard data structures. Our methods are within a 1 +o(1) multiplicative factor of the respective sequential methods. While our methods are fairly simple themselves, description of their performance in terms of the BSP parameters is somewhat complicated. The main reward for quantifying these complications is that it enables software to be written once and for all that can be migrated efficiently among a variety of parallel machines.
AB - The implementation of data structures on distributed memory models such as the bulk-synchronous parallel model, rather than shared memory ones such as the parallel random access machine, offers a serious challenge. In this work we undertake the architecture independent study of the computation and communication requirements of searchingordered h-level graphs, which include many of the standard data structures. Our methods are within a 1 +o(1) multiplicative factor of the respective sequential methods. While our methods are fairly simple themselves, description of their performance in terms of the BSP parameters is somewhat complicated. The main reward for quantifying these complications is that it enables software to be written once and for all that can be migrated efficiently among a variety of parallel machines.
UR - http://www.scopus.com/inward/record.url?scp=0039496773&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0039496773&partnerID=8YFLogxK
U2 - 10.1006/jpdc.1998.1430
DO - 10.1006/jpdc.1998.1430
M3 - Article
AN - SCOPUS:0039496773
SN - 0743-7315
VL - 49
SP - 98
EP - 110
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - 1
ER -