Partial Sums on the Ultra-Wide Word RAM

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 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
Title of host publicationTheory and Applications of Models of Computation
EditorsJianer Chen, Qilong Feng, Jinhui Xu
PublisherSpringer
Publication date2020
Pages13-24
ISBN (Print)9783030592660
DOIs
Publication statusPublished - 2020
Event16th Annual Conference on Theory and Applications of Models of Computation - Changsha, China
Duration: 18 Oct 202020 Oct 2020

Conference

Conference16th Annual Conference on Theory and Applications of Models of Computation
CountryChina
CityChangsha
Period18/10/202020/10/2020
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12337 LNCS
ISSN0302-9743

Keywords

  • Fenwick tree
  • Partial sums
  • Ultra-wide word RAM model

Fingerprint Dive into the research topics of 'Partial Sums on the Ultra-Wide Word RAM'. Together they form a unique fingerprint.

Cite this