论文标题
超宽单词ram上的前身
Predecessor on the Ultra-Wide Word RAM
论文作者
论文摘要
我们考虑了超宽单词RAM计算模型上的前身问题，该模型通过$ w^2 $位的“ Ultrawords”扩展了RAM模型[TAMC，2015]。该模型还支持算术和布尔值操作，此外，除了“分散的”内存操作，这些内存操作同时访问或修改$ w $（潜在的无连锁）内存地址。超宽的单词RAM模型捕获（和理想化）现代矢量处理器体系结构。 我们的主要结果是一个简单的线性空间数据结构，该结构在恒定时间内支持前身，并在摊销，预期的恒定时间中进行更新。这改善了以前恒定时间解决方案的空间，该解决方案在宇宙大小的顺序上使用了空间。即使在较弱的模型中，我们的结果也成立，其中Ultrawords由$ W^{1+ε} $ BITS组成，任何$ε> 0 $。它基于Willard的经典$ x $ -fast Trie数据结构的新实现[Inform。过程。 Lett。 17（2），1983年]与支持快速并行查找的新词典数据结构相结合。
We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with 'ultrawords' consisting of $w^2$ bits [TAMC, 2015]. The model supports arithmetic and boolean operations on ultrawords, in addition to 'scattered' memory operations that access or modify $w$ (potentially non-contiguous) memory addresses simultaneously. The ultra-wide word RAM model captures (and idealizes) modern vector processor architectures. Our main result is a simple, linear space data structure that supports predecessor in constant time and updates in amortized, expected constant time. This improves the space of the previous constant time solution that uses space in the order of the size of the universe. Our result holds even in a weaker model where ultrawords consist of $w^{1+ε}$ bits for any $ε> 0 $. It is based on a new implementation of the classic $x$-fast trie data structure of Willard [Inform. Process. Lett. 17(2), 1983] combined with a new dictionary data structure that supports fast parallel lookups.
