An architecture independent study of parallel segment trees

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1-24
Number of pages24
JournalJournal of Discrete Algorithms
Volume4
Issue number1
DOIs
StatePublished - Mar 1 2006

Fingerprint

Models of Computation
Sequential Algorithm
Distributed Memory
Parallel algorithms
Parallel Algorithms
Latency
Synchronization
Query
Data storage equipment
Communication
Requirements
Architecture
Model
Context

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Cite this

@article{6e29e45ef1214ffda3d57e094c978cdd,
title = "An architecture independent study of parallel segment trees",
abstract = "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.",
author = "Alexandros Gerbessiotis",
year = "2006",
month = "3",
day = "1",
doi = "https://doi.org/10.1016/j.jda.2005.01.001",
language = "English (US)",
volume = "4",
pages = "1--24",
journal = "Journal of Discrete Algorithms",
issn = "1570-8667",
publisher = "Elsevier",
number = "1",

}

An architecture independent study of parallel segment trees. / Gerbessiotis, Alexandros.

In: Journal of Discrete Algorithms, Vol. 4, No. 1, 01.03.2006, p. 1-24.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An architecture independent study of parallel segment trees

AU - Gerbessiotis, Alexandros

PY - 2006/3/1

Y1 - 2006/3/1

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.

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 - https://doi.org/10.1016/j.jda.2005.01.001

DO - https://doi.org/10.1016/j.jda.2005.01.001

M3 - Article

VL - 4

SP - 1

EP - 24

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

SN - 1570-8667

IS - 1

ER -