Book chapter · Conference paper
Partial Sums on the Ultra-Wide Word RAM
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.
| Language: | English |
|---|---|
| Publisher: | Springer |
| Year: | 2020 |
| Pages: | 13-24 |
| Proceedings: | 16th Annual Conference on Theory and Applications of Models of Computation |
| Series: | Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Journal subtitle: | 16th International Conference, Tamc 2020, Changsha, China, October 18–20, 2020, Proceedings |
| ISBN: | 3030592669 , 3030592677 , 9783030592660 and 9783030592677 |
| ISSN: | 03029743 and 16113349 |
| Types: | Book chapter and Conference paper |
| DOI: | 10.1007/978-3-030-59267-7_2 |
| ORCIDs: | Bille, Philip and Gørtz, Inge Li |
