Partial sums on the ultra-wide word RAM

Philip Bille*, Inge Li Gørtz, Frederik Rye Skjoldjensen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

We consider the classic partial sums problem on the ultra-wide word RAM model of computation. This model extends the classic w-bit word RAM model with special ultrawords of length w2 bits that support standard arithmetic and boolean operation and scattered memory access operations that can access w (non-contiguous) locations in memory. The ultra-wide word RAM model captures (and idealizes) modern vector processor architectures. Our main result is a new in-place data structure for the partial sum problem that only stores a constant number of ultrawords in addition to the input and supports operations in doubly logarithmic time. This matches the best known time bounds for the problem (among polynomial space data structures) while improving the space from superlinear to a constant number of ultrawords. Our results are based on a simple and elegant in-place word RAM data structure, known as the Fenwick tree. Our main technical contribution is a new efficient parallel ultra-wide word RAM implementation of the Fenwick tree, which is likely of independent interest.

Original languageEnglish
JournalTheoretical Computer Science
Volume905
Pages (from-to)99-105
ISSN0304-3975
DOIs
Publication statusPublished - 22 Feb 2022

Keywords

  • Partial sums
  • Ultra-wide word RAM
  • Word-level parallelism

Fingerprint

Dive into the research topics of 'Partial sums on the ultra-wide word RAM'. Together they form a unique fingerprint.

Cite this