文章基本信息

标题：Algorithmic Building Blocks for Asymmetric Memories
本地全文：下载
作者：Yan Gu ; Yihan Sun ; Guy E. Blelloch 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：112
页码：1-15
DOI：10.4230/LIPIcs.ESA.2018.44
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The future of main memory appears to lie in the direction of new non-volatile memory technologies that provide strong capacity-to-performance ratios, but have write operations that are much more expensive than reads in terms of energy, bandwidth, and latency. This asymmetry can have a significant effect on algorithm design, and in many cases it is possible to reduce writes at the cost of more reads. This paper studies which algorithmic techniques are useful in designing practical write-efficient algorithms. We focus on several fundamental algorithmic building blocks including unordered set/map implemented using hash tables, comparison sort, and graph traversal algorithms including breadth-first search and Dijkstra's algorithm. We introduce new algorithms and implementations that can reduce writes, and analyze the performance experimentally using a software simulator. Finally, we summarize interesting lessons and directions in designing write-efficient algorithms that can be valuable to share.
关键词：Asymmetric Memory; I/O Cost; Write-Efficient Algorithms; Hash Tables; Graph-Traversal Algorithms