An architecture independent study of parallel segment trees

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 2006

All Science Journal Classification (ASJC) codes

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

Keywords

  • Architecture independent parallel algorithms
  • Latency-tolerant algorithm
  • Parallel segment trees

Fingerprint

Dive into the research topics of 'An architecture independent study of parallel segment trees'. Together they form a unique fingerprint.

Cite this