Partial Sums on the Ultra-Wide Word RAM

Philip Bille; Inge Li Gørtz; Frederik Rye Skjold Jensen

doi:10.1007/978-3-030-59267-7_2

Partial Sums on the Ultra-Wide Word RAM

Philip Bille^*, Inge Li Gørtz, Frederik Rye Skjold Jensen

^*Corresponding author for this work

Department of Applied Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

66 Downloads (Orbit)

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 language	English
Title of host publication	Theory and Applications of Models of Computation
Editors	Jianer Chen, Qilong Feng, Jinhui Xu
Publisher	Springer
Publication date	2020
Pages	13-24
ISBN (Print)	9783030592660
DOIs	https://doi.org/10.1007/978-3-030-59267-7_2
Publication status	Published - 2020
Event	16th Annual Conference on Theory and Applications of Models of Computation - Changsha, China Duration: 18 Oct 2020 → 20 Oct 2020 Conference number: 16

Conference

Conference	16th Annual Conference on Theory and Applications of Models of Computation
Number	16
Country/Territory	China
City	Changsha
Period	18/10/2020 → 20/10/2020

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12337 LNCS
ISSN	0302-9743

Keywords

Fenwick tree
Partial sums
Ultra-wide word RAM model

Access to Document

10.1007/978-3-030-59267-7_2

FulltextAccepted author manuscript, 940 KB

OpenUrl availability

Full text

Cite this

Bille, Philip ; Gørtz, Inge Li ; Jensen, Frederik Rye Skjold. / Partial Sums on the Ultra-Wide Word RAM. Theory and Applications of Models of Computation. editor / Jianer Chen ; Qilong Feng ; Jinhui Xu. Springer, 2020. pp. 13-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12337 LNCS).

@inproceedings{fd62891079974fbba41193f49cbdf728,

title = "Partial Sums on the Ultra-Wide Word RAM",

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.",

keywords = "Fenwick tree, Partial sums, Ultra-wide word RAM model",

author = "Philip Bille and G{\o}rtz, {Inge Li} and Jensen, {Frederik Rye Skjold}",

year = "2020",

doi = "10.1007/978-3-030-59267-7_2",

language = "English",

isbn = "9783030592660",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "13--24",

editor = "Jianer Chen and Qilong Feng and Jinhui Xu",

booktitle = "Theory and Applications of Models of Computation",

note = "16th Annual Conference on Theory and Applications of Models of Computation, TAMC 2020 ; Conference date: 18-10-2020 Through 20-10-2020",

}

Bille, P , Gørtz, IL & Jensen, FRS 2020, Partial Sums on the Ultra-Wide Word RAM. in J Chen, Q Feng & J Xu (eds), Theory and Applications of Models of Computation. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12337 LNCS, pp. 13-24, 16th Annual Conference on Theory and Applications of Models of Computation, Changsha, China, 18/10/2020. https://doi.org/10.1007/978-3-030-59267-7_2

Partial Sums on the Ultra-Wide Word RAM. / Bille, Philip ; Gørtz, Inge Li; Jensen, Frederik Rye Skjold.
Theory and Applications of Models of Computation. ed. / Jianer Chen; Qilong Feng; Jinhui Xu. Springer, 2020. p. 13-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12337 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Partial Sums on the Ultra-Wide Word RAM

AU - Bille, Philip

AU - Gørtz, Inge Li

AU - Jensen, Frederik Rye Skjold

N1 - Conference code: 16

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Fenwick tree

KW - Partial sums

KW - Ultra-wide word RAM model

U2 - 10.1007/978-3-030-59267-7_2

DO - 10.1007/978-3-030-59267-7_2

M3 - Article in proceedings

AN - SCOPUS:85093863572

SN - 9783030592660

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 24

BT - Theory and Applications of Models of Computation

A2 - Chen, Jianer

A2 - Feng, Qilong

A2 - Xu, Jinhui

PB - Springer

T2 - 16th Annual Conference on Theory and Applications of Models of Computation

Y2 - 18 October 2020 through 20 October 2020

ER -

Bille P , Gørtz IL, Jensen FRS. Partial Sums on the Ultra-Wide Word RAM. In Chen J, Feng Q, Xu J, editors, Theory and Applications of Models of Computation. Springer. 2020. p. 13-24. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 12337 LNCS). doi: 10.1007/978-3-030-59267-7_2