Efficient Algorithms with Asymmetric Read and Write Costs-猫眼课题宝

DOI：

10.4230/lipics.esa.2016.14

发表时间：

2015-11

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Julian Shun

在几种用于计算机记忆的新兴技术（主要内存）中，阅读成本明显比写作成本便宜。记忆成本中的不对称性构成了与算法设计的RAM的根本不同的模型。在本文中，我们研究了在不对称读取和写作成本下的各种问题的下限和上限。我们认为，除$ o（1）$内存都具有不对称的成本以及少量对称内存的情况下，所有其他情况下，所有其他情况都具有不对称的成本。我们使用$（m，\ omega）$ - ARAM对两种情况进行建模大存储器的单位成本，但写作成本$ \ omega \ gg 1 $。对于FFT和排序网络，我们显示$ \ omega的下限成本（\ omega n \ log _ {\ omega m} n）$，这表明当$ \ omemaga $ IS时，不可能通过廉价读取渐近改进来实现渐近改进由$ m $的多项式界限。另外，在模型中分类网络的成本与比较分类之间存在渐近间隙（$ \ min（\ omega，\ log n）/\ log（\ omega m）$）。这与RAM和大多数其他模型形成鲜明对比。我们还显示了$ \ omega（\ omega n^2/m）$成本的$ n \ times n $ diamond dag的计算下限，这表明快速读取无法实现渐近改进。但是，我们表明，对于编辑距离问题（及相关问题），似乎是钻石dag，存在只有$ o的算法（\ omemaga n^2/（m \ min（\ omega^{1） /3}，m^{1/2}）））$成本。为了实现这一目标，我们利用严格的DAG计算中禁止的“路径草图”技术。最后，我们显示了几个有趣的上限，以解决最短路径问题，最小跨越树和其他问题。在许多上范围内，一个共同的主题是在读取和写入之间具有冗余的计算来折衷。

In several emerging technologies for computer memory (main memory), the cost of reading is significantly cheaper than the cost of writing. Such asymmetry in memory costs poses a fundamentally different model from the RAM for algorithm design. In this paper we study lower and upper bounds for various problems under such asymmetric read and write costs. We consider both the case in which all but $O(1)$ memory has asymmetric cost, and the case of a small cache of symmetric memory. We model both cases using the $(M,\omega)$-ARAM, in which there is a small (symmetric) memory of size $M$ and a large unbounded (asymmetric) memory, both random access, and where reading from the large memory has unit cost, but writing has cost $\omega\gg 1$. For FFT and sorting networks we show a lower bound cost of $\Omega(\omega n\log_{\omega M} n)$, which indicates that it is not possible to achieve asymptotic improvements with cheaper reads when $\omega$ is bounded by a polynomial in $M$. Also, there is an asymptotic gap (of $\min(\omega,\log n)/\log(\omega M)$) between the cost of sorting networks and comparison sorting in the model. This contrasts with the RAM, and most other models. We also show a lower bound for computations on an $n\times n$ diamond DAG of $\Omega(\omega n^2/M)$ cost, which indicates no asymptotic improvement is achievable with fast reads. However, we show that for the edit distance problem (and related problems), which would seem to be a diamond DAG, there exists an algorithm with only $O(\omega n^2/(M\min(\omega^{1/3},M^{1/2})))$ cost. To achieve this we make use of a "path sketch" technique that is forbidden in a strict DAG computation. Finally, we show several interesting upper bounds for shortest path problems, minimum spanning trees, and other problems. A common theme in many of the upper bounds is to have redundant computation to tradeoff between reads and writes.

Efficient Algorithms with Asymmetric Read and Write Costs

文献摘要

相似文献