Document Open Access Logo

Efficient Algorithms with Asymmetric Read and Write Costs

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

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.14.pdf
  • Filesize: 0.63 MB
  • 18 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun. Efficient Algorithms with Asymmetric Read and Write Costs. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.14

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 omega >> 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.  Moreover, 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, in which the asymptotic costs are the same. We also show a lower bound for computations on an n*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 minimum edit distance problem (and related problems), which would seem to be a diamond DAG, we can beat this lower bound with 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 that they require redundant computation and a tradeoff between reads and writes.

Subject Classification

Keywords
  • Computational Model
  • Lower Bounds
  • Shortest-paths
  • Non-Volatile Memory
  • Sorting Networks
  • Fast Fourier Transform
  • Diamond DAG
  • Minimum Spanning Tree

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alok Aggarwal and Jeffrey S. Vitter. The Input/Output complexity of sorting and related problems. Communications of the ACM, 31(9), 1988. URL: http://dx.doi.org/10.1145/48529.48535.
  2. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974. Google Scholar
  3. Miklós Ajtai, János Komlós, and Endre Szemerédi. An O(n log n) sorting network. In Proc. ACM Symposium on Theory of Computing (STOC), 1983. Google Scholar
  4. Deepak Ajwani, Andreas Beckmann, Riko Jacob, Ulrich Meyer, and Gabriel Moruz. On computational models for flash memory devices. In Proc. ACM International Symposium on Experimental Algorithms (SEA), 2009. Google Scholar
  5. Ameen Akel, Adrian M. Caulfield, Todor I. Mollov, Rajech K. Gupta, and Steven Swanson. Onyx: A prototype phase change memory storage array. In Proc. USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), 2011. Google Scholar
  6. Manos Athanassoulis, Bishwaranjan Bhattacharjee, Mustafa Canim, and Kenneth A. Ross. Path processing using solid state storage. In Proc. International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS), 2012. Google Scholar
  7. Avraham Ben-Aroya and Sivan Toledo. Competitive analysis of flash-memory algorithms. In Proc. European Symposium on Algorithms (ESA), 2006. Google Scholar
  8. Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, Charlie McGuffey, and Julian Shun. Parallel algorithms for asymmetric read-write costs. In Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016. Google Scholar
  9. Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun. Efficient algorithms with asymmetric read and write costs. arXiv preprint arXiv:1511.01038, 2015. Google Scholar
  10. Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu, and Julian Shun. Sorting with asymmetric read and write costs. In Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015. Google Scholar
  11. Erin Carson, James Demmel, Laura Grigori, Nicholas Knight, Penporn Koanantakool, Oded Schwartz, and Harsha V. Simhadri. Write-avoiding algorithms. In Proc. IEEE International Parallel &Distributed Processing Symposium (IPDPS), 2016. Google Scholar
  12. Shimin Chen, Phillip B. Gibbons, and Suman Nath. Rethinking database algorithms for phase change memory. In Proc. Conference on Innovative Data Systems Research (CIDR), 2011. Google Scholar
  13. Shimin Chen and Qin Jin. Persistent B^+-trees in non-volatile main memory. PVLDB, 8(7), 2015. Google Scholar
  14. Sangyeun Cho and Hyunjin Lee. Flip-N-Write: A simple deterministic technique to improve PRAM write performance, energy and endurance. In Proc. IEEE/ACM International Symposium on Microarchitecture (MICRO), 2009. Google Scholar
  15. Rezaul A. Chowdhury and Vijaya Ramachandran. Cache-oblivious dynamic programming. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006. Google Scholar
  16. Stephen Cook and Ravi Sethi. Storage requirements for deterministic polynomial time recognizable languages. Journal of Computer and System Sciences, 13(1), 1976. Google Scholar
  17. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd edition). MIT Press, 2009. Google Scholar
  18. Mark de Berg, Otfried Cheong, Mark van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2008. Google Scholar
  19. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 1959. Google Scholar
  20. Xiangyu Dong, Norman P. Jouupi, and Yuan Xie. PCRAMsim: System-level performance, energy, and area modeling for phase-change RAM. In Proc. ACM International Conference on Computer-Aided Design (ICCAD), 2009. Google Scholar
  21. Xiangyu Dong, Xiaoxia Wu, Guangyu Sun, Yuan Xie, Hai H. Li, and Yiran Chen. Circuit and microarchitecture evaluation of 3D stacking magnetic RAM (MRAM) as a universal memory replacement. In Proc. ACM Design Automation Conference (DAC), 2008. Google Scholar
  22. David Eppstein, Michael T. Goodrich, Michael Mitzenmacher, and Pawel Pszona. Wear minimization for cuckoo hashing: How not to throw a lot of eggs into one basket. In Proc. ACM International Symposium on Experimental Algorithms (SEA), 2014. Google Scholar
  23. Jittat Fakcharoenphol and Satish Rao. Planar graphs, negative weight edges, shortest paths, near linear time. In Proc. IEEE Symposium on Foundations of Computer Science (FOCS), 2001. Google Scholar
  24. Michael L. Fredman and Robert E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 1987. Google Scholar
  25. Eran Gal and Sivan Toledo. Algorithms and data structures for flash memories. ACM Computing Surveys, 37(2), 2005. Google Scholar
  26. Michael T. Goodrich. Zig-zag sort: A simple deterministic data-oblivious sorting algorithm running in O(n log n) time. In Proc. ACM Symposium on Theory of Computing (STOC), 2014. Google Scholar
  27. Jia-Wei Hong and H. T. Kung. I/O complexity: The red-blue pebble game. In Proc. ACM Symposium on Theory of Computing (STOC), 1981. Google Scholar
  28. John Hopcroft, Wolfgang Paul, and Leslie Valiant. On time versus space. Journal of the ACM, 24(2), 1977. Google Scholar
  29. HP, SanDisk partner on memristor, ReRAM technology. http://www.bit-tech.net/news/ hardware 10 hp-sandisk-reram-memristor, October 2015. Google Scholar
  30. Jingtong Hu, Qingfeng Zhuge, Chun Jason Xue, Wei-Che Tseng, Shouzhen Gu, and Edwin Sha. Scheduling to optimize cache utilization for non-volatile main memories. IEEE Transactions on Computers, 63(8), 2014. Google Scholar
  31. www.slideshare.net/IBMZRL/theseus-pss-nvmw2014, 2014. Google Scholar
  32. Intel and Micron produce breakthrough memory technology. http://newsroom.intel.com/ community/intel_newsroom/blog 07 intel-and-micron-produce-breakthrough-memory-technology, July 2015. Google Scholar
  33. Hyojun Kim, Sangeetha Seshadri, Clement L. Dickey, and Lawrence Chu. Evaluating phase change memory for enterprise storage systems: A study of caching and tiering approaches. In Proc. USENIX Conference on File and Storage Technologies (FAST), 2014. Google Scholar
  34. Philip N. Klein, Shay Mozes, and Oren Weimann. Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log² n)-time algorithm. ACM Transactions on Algorithms, 6(2), 2010. URL: http://dx.doi.org/10.1145/1721837.1721846.
  35. Benjamin C. Lee, Engin Ipek, Onur Mutlu, and Doug Burger. Architecting phase change memory as a scalable DRAM alternative. In Proc. ACM International Symposium on Computer Architecture (ISCA), 2009. Google Scholar
  36. Jagan S. Meena, Simon M. Sze, Umesh Chand, and Tseung-Yuan Tseng. Overview of emerging nonvolatile memory technologies. Nanoscale Research Letters, 9, 2014. Google Scholar
  37. Suman Nath and Phillip B. Gibbons. Online maintenance of very large random samples on flash storage. VLDB J., 19(1), 2010. Google Scholar
  38. Hyoungmin Park and Kyuseok Shim. FAST: Flash-aware external sorting for mobile database systems. Journal of Systems and Software, 82(8), 2009. URL: http://dx.doi.org/10.1016/j.jss.2009.02.028.
  39. Joon-Sang Park, Michael Penner, and Viktor K. Prasanna. Optimizing graph algorithms for improved cache performance. IEEE Transactions on Parallel and Distributed Systems, 15(9), 2004. Google Scholar
  40. Mike S. Paterson. Improved sorting networks with O(log n) depth. Algorithmica, 5(1), 1990. Google Scholar
  41. Moinuddin K. Qureshi, Sudhanva Gurumurthi, and Bipin Rajendran. Phase Change Memory: From Devices to Systems. Morgan &Claypool, 2011. Google Scholar
  42. Jeanette P. Schmidt. All shortest paths in weighted grid graphs and its application to finding all approximate repeats in strings. SIAM Journal on Computing, 27, 1998. Google Scholar
  43. Joel Seiferas. Sorting networks of logarithmic depth, further simplified. Algorithmica, 53(3), 2009. Google Scholar
  44. Robert E. Tarjan. Updating a balanced search tree in O(1) rotations. Information Processing Letters, 16(5), 1983. Google Scholar
  45. Stratis D. Viglas. Adapting the B^+-tree for asymmetric I/O. In Proc. East European Conference on Advances in Databases and Information Systems (ADBIS), 2012. Google Scholar
  46. Stratis D. Viglas. Write-limited sorts and joins for persistent memory. PVLDB, 7(5), 2014. Google Scholar
  47. Cong Xu, Xiangyu Dong, Norman P. Jouppi, and Yuan Xie. Design implications of memristor-based RRAM cross-point structures. In Proc. IEEE Design, Automation and Test in Europe (DATE), 2011. Google Scholar
  48. Byung-Do Yang, Jae-Eun Lee, Jang-Su Kim, Junghyun Cho, Seung-Yun Lee, and Byoung-Gon Yu. A low power phase-change random access memory using a data-comparison write scheme. In Proc. IEEE International Symposium on Circuits and Systems (ISCAS), 2007. Google Scholar
  49. Yole Developpement. Emerging non-volatile memory technologies, 2013. Google Scholar
  50. Ping Zhou, Bo Zhao, Jun Yang, and Youtao Zhang. A durable and energy efficient main memory using phase change memory technology. In Proc. ACM International Symposium on Computer Architecture (ISCA), 2009. Google Scholar
  51. Omer Zilberberg, Shlomo Weiss, and Sivan Toledo. Phase-change memory: An architectural perspective. ACM Computing Surveys, 45(3), 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact