Algorithmic Building Blocks for Asymmetric Memories
Algorithmic Building Blocks for Asymmetric Memories
复制标题
DOI：
10.4230/lipics.esa.2018.44
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Yan Gu;Yihan Sun;G. Blelloch
中科院分区：
文献类型：
--
作者：
Yan Gu;Yihan Sun;G. Blelloch
主内存的未来似乎朝着新的非易失性记忆技术的方向，这些记忆技术提供了强大的性能比率，但在能量，带宽和延迟方面，写操作比阅读要贵得多。这种不对称性可能会对算法设计产生重大影响，在许多情况下，有可能以更多的读取为代价减少写作。本文研究哪种算法技术可用于设计实用的写入算法。我们专注于几种基本算法构建块，包括使用哈希表，比较排序和图形遍历算法实现的无序集/地图，包括广度优先搜索和Dijkstra的算法。我们介绍了可以减少写入的新算法和实现，并使用软件模拟器对性能进行分析。最后，我们总结了在设计可能有价值的书写效率算法时进行的有趣的课程和指示。
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.