Blog
About

19
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Efficient Algorithms under Asymmetric Read and Write Costs

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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 ARAM, in which there is a small (symmetric) memory of size \(M\), a large unbounded (asymmetric) memory, both random access, and the cost of reading from the large memory is unit, but the cost of writing is \(w \geq 1\). For FFT and sorting networks we show a lower bound cost of \(\Omega(w(n \log_{w M} n))\). For the FFT we show a matching upper bound, which indicates it is only possible to achieve asymptotic improvements with cheaper reads when \(w > M\). For sorting networks we show an asymptotic gap between the cost of sorting networks and comparison sorting in the model. We also show a lower bound for computations on an \(n \times n\) diamond DAG of \(\Omega(w n^2/M)\) cost, which indicates no asymptotic improvement is achievable with fast reads. However, we show that for the minimum edit distance problem (and related problems), which would seem to be a diamond DAG, we can improve on this lower bound getting \(O(w n^2/ (M \min(w^{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 that they require redundant computation and a tradeoff between reads and writes.

          Related collections

          Author and article information

          Journal
          1511.01038

          Data structures & Algorithms

          Comments

          Comment on this article