Efficient algorithms with asymmetric read and write costs

DOI10.4230/LIPICS.ESA.2016.14MaRDI QIDQ4606283zbMATH OpenOpenAlexFDO

Authors Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Julian Shun

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1511.01038

zbMATH Keywords

minimum spanning treeshortest pathslower boundsfast Fourier transformcomputational modelsorting networksnon-volatile memorydiamond DAG

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) General topics in the theory of algorithms (68W01)

Abstract: 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 $omegagg1$. For FFT and sorting networks we show a lower bound cost of $Omega(omeganlo{g}_{omegaM}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,logn)/log(omegaM)$) 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 $nimesn$ 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/(Mmin(omeg{a}^{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.

Recommendations

• Algorithms for parallel memory, I: Two-level memories
• scientific article; zbMATH DE number 1445384
• scientific article; zbMATH DE number 1263186
• Space-efficient basic graph algorithms
• Towards a theory of cache-efficient algorithms

Cited in

(2)

• Algorithmic Building Blocks for Asymmetric Memories
• scientific article; zbMATH DE number 1927561 (Why is no real title available?)

This page was built for publication: Efficient algorithms with asymmetric read and write costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606283)