Data Oblivious Algorithms for Multicores
Data Oblivious Algorithms for Multicores
复制标题
多核数据遗忘算法
DOI：
10.1145/3409964.3461783
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Shi, Elaine
中科院分区：
文献类型：
--
作者：
Ramachandran, Vijaya;Shi, Elaine
数据无关算法是一种其存储器访问模式独立于输入值的算法。我们在现实的多核上启动了并行数据不经意算法的研究，最好的捕获是二进制分叉-连接计算模型。提出了一种数据无关的Crew二叉连接排序算法，该算法具有最优的总工作量和最优的(缓存无关)缓存复杂度，并且具有O(łog nłogłog n)跨度(即并行时间)；这些界与缓存高效的二叉叉连接不安全算法的已知界相匹配。使用我们的排序算法作为核心原语，我们展示了如何在二叉叉-连接模型中以非平凡的效率模拟一般的PRAM算法，并给出了几种应用的数据无关算法，包括列表排序、欧拉巡回、树收缩、连通分支和最小生成森林。我们所有的数据无关算法都有与不安全算法最好的界匹配或改进的界，为了补充这些渐近有效的结果，我们给出了一个实用的变种排序算法，它是自包含的，并且有可能实现。它具有最优的缓存成本，并且仅是最优工作的łog n倍和跨度方面的约łog n倍。%此外，它在其边界内实现了小的恒定因子。我们还提出了一个具有最优工作和缓存代价的EREW变体，并且具有相同的渐近跨度。
A data-oblivious algorithm is an algorithm whose memory access pattern is independent of the input values. We initiate the study of parallel data oblivious algorithms on realistic multicores, best captured by the binary fork-join model of computation. We present a data-oblivious CREW binary fork-join sorting algorithm with optimal total work and optimal (cache-oblivious) cache complexity, and in O(łog n łog łog n) span (i.e., parallel time); these bounds match the best-known bounds for binary fork-join cache-efficient insecure algorithms. Using our sorting algorithm as a core primitive, we show how to data-obliviously simulate general PRAM algorithms in the binary fork-join model with non-trivial efficiency, and we present data-oblivious algorithms for several applications including list ranking, Euler tour, tree contraction, connected components, and minimum spanning forest. All of our data oblivious algorithms have bounds that either match or improve over the best known bounds for insecure algorithms.Complementing these asymptotically efficient results, we present a practical variant of our sorting algorithm that is self-contained and potentially implementable. It has optimal caching cost, and it is only a łog łog n factor off from optimal work and about a łog n factor off in terms of span. %moreover, it achieves small constant factors in its bounds. We also present an EREW variant with optimal work and caching cost, and with the same asymptotic span.
登录
查看更多内容
外包外部存储器中的数据忽略图算法
DOI：
--
发表时间：
2014
期刊：
International Conference on Combinatorial Optimization and Applications
影响因子：
--
作者：
M. Goodrich;Joseph A. Simons
通讯作者：
Joseph A. Simons
DOI：
--
发表时间：
2012
期刊：
IEEE International Parallel and Distributed Processing Symposium
影响因子：
--
作者：
R. Cole;V. Ramachandran
通讯作者：
V. Ramachandran
DOI：
10.1145/1007912.1007948
发表时间：
2004-06
期刊：
--
影响因子：
--
作者：
G. Blelloch;Phillip B. Gibbons
通讯作者：
G. Blelloch;Phillip B. Gibbons
DOI：
10.1145/1378533.1378574
发表时间：
2008-06
期刊：
--
影响因子：
--
作者：
R. Chowdhury;V. Ramachandran
通讯作者：
R. Chowdhury;V. Ramachandran
云端绘图：使用小型工作存储私密地可视化关系数据
DOI：
--
发表时间：
2012
期刊：
International Symposium Graph Drawing and Network Visualization
影响因子：
--
作者：
M. Goodrich;O. Ohrimenko;R. Tamassia
通讯作者：
R. Tamassia