TY - JOUR
T1 - An architecture independent study of parallel segment trees
AU - Gerbessiotis, Alexandros V.
N1 - Funding Information:
This work was supported in part by NJIT SBR Grant 421350. Some preliminary work was performed while the author was with the University of Oxford, Oxford, UK, and supported in part by EPSRC under grant GR/K16999. The author would like to thank the referees for their comments, suggestions, and criticisms.
PY - 2006/3
Y1 - 2006/3
N2 - We study the computation, communication and synchronization requirements related to the construction and search of parallel segment trees in an architecture independent way. Our proposed parallel algorithms are optimal in space and time compared to the corresponding sequential algorithms utilized to solve the introduced problems and are described in the context of the bulk-synchronous parallel (BSP) model of computation. Our methods are more scalable and can thus be made to work for larger values of processor size p relative to problem size n than other segment tree related algorithms that have been described on other realistic distributed-memory parallel models and also provide a natural way to approach searching problems on latency-tolerant models of computation that maintains a balanced query load among the processors.
AB - We study the computation, communication and synchronization requirements related to the construction and search of parallel segment trees in an architecture independent way. Our proposed parallel algorithms are optimal in space and time compared to the corresponding sequential algorithms utilized to solve the introduced problems and are described in the context of the bulk-synchronous parallel (BSP) model of computation. Our methods are more scalable and can thus be made to work for larger values of processor size p relative to problem size n than other segment tree related algorithms that have been described on other realistic distributed-memory parallel models and also provide a natural way to approach searching problems on latency-tolerant models of computation that maintains a balanced query load among the processors.
KW - Architecture independent parallel algorithms
KW - Latency-tolerant algorithm
KW - Parallel segment trees
UR - http://www.scopus.com/inward/record.url?scp=33644589177&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33644589177&partnerID=8YFLogxK
U2 - 10.1016/j.jda.2005.01.001
DO - 10.1016/j.jda.2005.01.001
M3 - Article
AN - SCOPUS:33644589177
SN - 1570-8667
VL - 4
SP - 1
EP - 24
JO - Journal of Discrete Algorithms
JF - Journal of Discrete Algorithms
IS - 1
ER -