Phillip B. Gibbons
ABSTRACT
We are on the cusp of the emergence of a new wave of nonvolatile memory technologies that are projected to become the dominant type of main memory in the near future. A key property of these new memory technologies is their asymmetric read-write costs: Writes can be an order of magnitude or more higher energy, higher latency, and lower (per-module) bandwidth than reads. This high cost for writes motivates a rethinking of algorithm design towards "write-efficient" algorithms and data structures that reduce their number of writes. Many popular techniques for sequential, distributed, and parallel algorithms are tuned to the setting where reads and writes cost the same, and hence need to be revisited. Prior work on reducing writes to contended cache lines in shared memory algorithms can be useful here, but with the new technologies, even writes to uncontended memory is costly. Moreover, the new technologies are unlikely to replace the fastest cache memory, motivating the study of a multi-level memory hierarchy comprised of smaller symmetric level(s) and a larger asymmetric level. Lower bounds, too, need to be revisited in light of asymmetric costs. This talk provides background on these emerging memory technologies, highlights the progress to date on these exciting research questions, and touches on a few of the many open problems.
- N. Ben-David, G. E. Blelloch, J. T. Fineman, P. B. Gibbons, Y. Gu, C. McGuffey, and J. Shun. Parallel algorithms for asymmetric read-write costs. In ACM SPAA, 2016. Google Scholar
Digital Library
- G. E. Blelloch, J. T. Fineman, P. B. Gibbons, Y. Gu, and J. Shun. Efficient algorithms under asymmetric read and write costs. arXiv:1511.01038, 2015.Google Scholar
- G. E. Blelloch, J. T. Fineman, P. B. Gibbons, Y. Gu, and J. Shun. Sorting with asymmetric read and write costs. In ACM SPAA, 2015. Google ScholarDigital Library
- E. Carson, J. Demmel, L. Grigori, N. Knight, P. Koanantakool, O. Schwartz, and H. V. Simahdri. Write-avoiding algorithms. In IEEE IPDPS, 2016.Google ScholarCross Ref
- S. Chen, P. B. Gibbons, and S. Nath. Rethinking database algorithms for phase change memory. In CIDR, 2011.Google Scholar
- S. D. Viglas. Write-limited sorts and joins for persistent memory. Proc. VLDB Endowment, 7(5), 2014. Google ScholarDigital Library
Index Terms
- How Emerging Memory Technologies Will Have You Rethinking Algorithm Design
Recommendations
Efficient memory management of a hierarchical and a hybrid main memory for MN-MATE platform
PMAM '12: Proceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and ManycoresThe advent of manycore in computing architecture causes severe energy consumption and memory wall problem. Thus, emerging technologies such as on-chip memory and nonvolatile memory (NVRAM) have led to a paradigm shift in computing architecture era. For ...
Sorting with Asymmetric Read and Write Costs
SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and ArchitecturesEmerging memory technologies have a significant gap between the cost, both in time and in energy, of writing to memory versus reading from memory. In this paper we present models and algorithms that account for this difference, with a focus on write-...
Modeling, Architecture, and Applications for Emerging Memory Technologies
Editor's note:Spin-transfer torque RAM and phase-change RAM are vying to become the next-generation embedded memory, offering high speed, high density, and nonvolatility. This article discusses new opportunities and challenges presented by these two ...
Comments