XPS: FULL: FP: Write-Efficient Parallel Algorithms for Emerging Memory Technologies

XPS：FULL：FP：用于新兴内存技术的写高效并行算法

• 批准号: 1533858
• 负责人: Guy Blelloch
• 金额: $ 84.5万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1533858&HistoricalAwards=false
• 关键词: XPS; FULL; FP; Write; Efficient

Chip manufacturers in the past ten years have been enhancing computing performance by including multiple processor cores per chip. Given that all the cores have to access a shared memory, however, this access has increasingly become a bottleneck in terms of energy, latency, and bandwidth. To help deal with these and other problems, industry has been developing a variety of new memory technologies such as phase-change memory, Spin-Torque Transfer Magnetic RAM, and Memristor-based Resistive RAM. These technologies offer the promise of significantly lower energy and higher density than standard DRAM memory technology. One of the key issues, however, is that writing to memory based on the technologies is significantly more costly than reading from memory, suffering from higher latency, lower per-chip bandwidth, and higher energy costs.The goal of this project is to develop new sequential and parallel algorithms and algorithm design techniques that are efficient in terms of the number of writes they perform, and hence make better use of these new technologies by reducing energy consumption and improving performance. This contrasts with 50 years of research on algorithms in which writes are assumed to be no more costly than reads. If successful the research will have a broad impact on future users of such technologies, which could be very many, as well as on the models and approaches for future algorithm design. The PIs also plan to develop efficient implementations of algorithms that they will make freely and openly available. The project includes an educational outreach component in which, as part of courses on databases and applied algorithms, the PIs will teach students about the new memory technologies and algorithms that can take advantage of them.Within the scope of work the PIs will (1) develop appropriate abstract models for capturing the asymmetric costs in memories, (2) develop and analyze algorithms in the models, (3) prove lower bounds, (4) develop programming abstractions that help express such algorithms, (5) develop working applications (e.g., in graph analytics and databases) based on the algorithms developed, and (6) experimentally verify the utility of the models and abstractions in guiding the development of efficient algorithms. The intellectual challenge within this context will be in developing such models, algorithms, and programming abstractions that are simultaneously simple, elegant, and practical, while at the same time gaining insights into fundamental limits and trade-offs.

过去十年里，芯片制造商一直在通过在每个芯片上包含多个处理器内核来增强计算性能。 然而，考虑到所有内核都必须访问共享内存，这种访问日益成为能源、延迟和带宽方面的瓶颈。 为了帮助解决这些问题和其他问题，业界一直在开发各种新的存储器技术，例如相变存储器、自旋扭矩传递磁性 RAM 和基于忆阻器的电阻 RAM。 与标准 DRAM 内存技术相比，这些技术有望显着降低能耗并提高密度。 然而，关键问题之一是，基于该技术写入内存的成本明显高于从内存中读取的成本，存在更高的延迟、更低的每芯片带宽和更高的能源成本。该项目的目标是开发新的顺序和并行算法以及算法设计技术在执行写入次数方面非常高效，因此可以通过降低能耗和提高性能来更好地利用这些新技术。 这与 50 年的算法研究形成鲜明对比，其中假设写入的成本不比读取高。 如果成功，这项研究将对此类技术的未来用户（可能会很多）以及未来算法设计的模型和方法产生广泛的影响。 PI 还计划开发高效的算法实现，并将其免费公开。 该项目包括教育推广部分，作为数据库和应用算法课程的一部分，PI 将向学生传授可以利用这些技术和算法的新内存技术和算法。在工作范围内，PI 将 (1)开发适当的抽象模型来捕获存储器中的不对称成本，(2) 开发和分析模型中的算法，(3) 证明下限，(4) 开发有助于表达此类算法的编程抽象，(5) 开发工作应用程序（例如，在图形分析中和数据库）基于所开发的算法，（6）通过实验验证模型和抽象在指导高效算法开发方面的实用性。 在这种背景下，智力挑战将在于开发这样的模型、算法和编程抽象，它们既简单、优雅又实用，同时深入了解基本限制和权衡。

项目成果

The Parallel Persistent Memory Model

• DOI: 10.1145/3210377.3210381
• 发表时间: 2018-05
• 期刊: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
• 作者: G. Blelloch;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun

Algorithmic Building Blocks for Asymmetric Memories

• DOI: 10.4230/lipics.esa.2018.44
• 发表时间: 2018-06
• 期刊: ArXiv
• 作者: Yan Gu;Yihan Sun;G. Blelloch

Efficient Algorithms with Asymmetric Read and Write Costs

• DOI: 10.4230/lipics.esa.2016.14
• 发表时间: 2015-11
• 作者: G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Julian Shun

Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry

• DOI: 10.1145/3210377.3210380
• 发表时间: 2018-05
• 期刊: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
• 作者: G. Blelloch;Yan Gu;Yihan Sun;Julian Shun

Implicit Decomposition for Write-Efficient Connectivity Algorithms

• DOI: 10.1109/ipdps.2018.00081
• 发表时间: 2017-10
• 期刊: 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
• 作者: N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun