EAGER: Transactional Memory Foundations for Distributed Multiprocessor Systems

EAGER：分布式多处理器系统的事务内存基础

• 批准号: 1936450
• 负责人: Gokarna Sharma
• 金额: $ 20万
• 依托单位: Kent State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1936450&HistoricalAwards=false
• 关键词: EAGER; Transactional; Memory; Foundations; Distributed

Being able to program with concurrency will be an important and necessary skill in the future. Processor speeds are no longer increasing as processors are hitting the ceiling of their physical limitations. The chip manufacturers avoided this problem by putting more cores in a single processor chip. Each new generation of processor chips are having an increasing number of cores. So in the future, in order to get a computation to run faster, the computation has to be split up into concurrent pieces and run in parallel as much as possible. The major challenge is concurrency control: (i) how to coordinate accesses to resources that are shared among concurrent pieces and (ii) how to ensure the correct sequencing of interactions between the computing cores. This project will explore the power and limitations of transactional memory which has emerged as a paradigm for concurrency control. Due to conceptual simplicity, it is believed that transactional memory will encourage non-expert users in writing concurrent programs, reaching beyond the current use of concurrent programming only among expert users. The outcomes of this project will have impacts on the practice of concurrent programming. Industry is also embracing transactional memory by incorporating it in their recent processor lines. The PI will make the prototype system publicly available. Some results will be incorporated in classes the PI teaches. The PI will also focus on the mentoring and education of K-12, undergraduate, and graduate students in concurrent computing, including female, minority, and first-generation computer science students. The PI and students will seek out broad dissemination of the progress of research through presentations at major conferences, workshops, and seminars. The PI will also participate in outreach events individually and in collaboration with the programs within Kent State University, such as K-12 science experience, summer undergraduate research experience (SURE), choose Ohio first (COF), summer bootcamp, Northeast Ohio Computer Science and Information Systems Colloquium, etc. Transactional memory has emerged as an appealing paradigm, addressing the downsides of traditional barriers and locks-based techniques to this problem. However, the past research has examined transactional memory mostly in the context of tightly-coupled systems, consisting of a set of processors that share the same physical main memory. The goal of this project is to study transactional memory in the context of loosely-coupled systems, consisting of a collection of relatively autonomous processors each having its own memory. Due to recent architectural and computational trends, loosely-coupled systems are becoming increasingly popular and transactional memory is predicted to be useful for concurrency control in these systems. Particularly, this project establishes solid theoretical as well as practical foundations under different execution models and practical scenarios, significantly advancing the current understanding of transactional memory in loosely-coupled systems. The specific goals of this project include: (i) establishing impossibility and lower bound results for transactional memory in loosely-coupled systems, (ii) designing and formally analyzing provably-efficient scheduling algorithms with (near-)optimal performance guarantees for both arbitrary and specialized workloads arise in practice, and (iii) implementing a prototype distributed transactional memory system employing the designed provably-efficient algorithms and evaluating it thoroughly using diverse real-world benchmarks and applications to inform theory from practice. The main challenge to overcome is that loosely-coupled systems have to deal with non-uniformity in memory-access latency for processors, which was of no concern in tightly-coupled systems. This non-uniformity affects the completion time of concurrent pieces of code as well as other related network parameters such as communication cost and congestion. The techniques for minimizing completion time may not necessarily minimize other parameters, and alternatively, the techniques for minimizing other parameters may result significantly worse completion time. Therefore, a major challenge of this project lies in developing tools and techniques to understand the effects of non-uniform latency in concurrency control.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

能够并发编程将是未来一项重要且必要的技能。处理器速度不再增加，因为处理器正在触及其物理限制的上限。芯片制造商通过在单个处理器芯片中放置更多的内核来避免这个问题。每一代新的处理器芯片都具有越来越多的内核。所以在未来，为了让计算运行得更快，计算必须被分成并发的部分，并尽可能并行地运行。主要的挑战是并发控制：（i）如何协调对并发片段之间共享的资源的访问，以及（ii）如何确保计算核心之间的交互的正确顺序。这个项目将探讨事务内存的能力和局限性，它已经成为并发控制的范例。由于概念上的简单性，人们相信事务内存将鼓励非专家用户编写并发程序，超越目前仅在专家用户中使用的并发编程。该项目的成果将对并行编程的实践产生影响。工业界也通过将其纳入最近的处理器系列来拥抱事务内存。PI将公开原型系统。一些结果将被纳入PI教授的课程中。PI还将专注于K-12，本科生和研究生在并发计算方面的指导和教育，包括女性，少数民族和第一代计算机科学学生。PI和学生将通过在主要会议，研讨会和研讨会上的演讲寻求研究进展的广泛传播。PI还将单独参加外展活动，并与肯特州立大学内的项目合作，如K-12科学体验、夏季本科生研究体验（SURE）、选择俄亥俄州优先（COF）、夏季训练营、东北俄亥俄州计算机科学和信息系统研讨会等。解决了传统的基于屏障和锁的技术对该问题的不利影响。然而，过去的研究主要是在紧耦合系统的上下文中研究事务内存，该系统由一组共享相同物理主存的处理器组成。这个项目的目标是在松耦合系统的背景下研究事务内存，松耦合系统由一组相对自治的处理器组成，每个处理器都有自己的内存。由于最近的架构和计算的趋势，松耦合的系统变得越来越流行，事务存储器被预测为在这些系统中的并发控制是有用的。特别是，该项目建立了坚实的理论和实践基础，在不同的执行模型和实际情况下，显着推进松耦合系统中的事务内存的理解。该项目的具体目标包括：（i）在松耦合系统中建立事务存储器的不可能性和下限结果，（ii）设计和形式化分析可证明有效的调度算法，其对于实践中出现的任意和专用工作负载具有（接近）最佳性能保证，以及（iii）采用所设计的可证明有效的算法来实现原型分布式事务存储器系统，并且使用不同的真实的-世界基准和应用，从实践中了解理论。 要克服的主要挑战是松耦合系统必须处理处理器的存储器访问延迟的非均匀性，这在紧耦合系统中是不需要考虑的。这种不一致性会影响并发代码段的完成时间以及其他相关的网络参数，如通信成本和拥塞。用于最小化完成时间的技术可能不一定最小化其他参数，并且可替代地，用于最小化其他参数的技术可能导致显著更差的完成时间。因此，该项目的主要挑战在于开发工具和技术，以了解并发控制中的非均匀延迟的影响。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Processing Distributed Transactions in a Predefined Order

按预定义顺序处理分布式事务

• DOI: 10.1145/3427796.3427819
• 发表时间: 2021
• 期刊: The 22nd International Conference on Distributed Computing and Networking (ICDCN
• 作者: Poudel, Pavan;Rai, Shishir;Sharma, Gokarna
• 通讯作者: Sharma, Gokarna

GraphTM: An Efficient Framework for Supporting Transactional Memory in a Distributed Environment

GraphTM：分布式环境中支持事务内存的高效框架

• DOI: 10.1145/3369740.3369774
• 发表时间: 2020
• 期刊: The 21st International Conference on Distributed Computing and Networking (ICDCN
• 作者: Poudel, Pavan;Sharma, Gokarna
• 通讯作者: Sharma, Gokarna

Load balanced distributed directories

负载平衡的分布式目录

• DOI: 10.1016/j.ic.2021.104700
• 发表时间: 2021
• 期刊: Information and Computation
• 影响因子: 1
• 作者: Rai, Shishir;Sharma, Gokarna;Busch, Costas;Herlihy, Maurice
• 通讯作者: Herlihy, Maurice

Adaptive Versioning in Transactional Memories

事务内存中的自适应版本控制

• DOI: 10.1007/978-3-030-34992-9_22
• 发表时间: 2019
• 期刊: and Security of Distributed Systems (SSS
• 作者: Poudel, Pavan;Sharma, Gokarna
• 通讯作者: Sharma, Gokarna

Adaptive Versioning in Transactional Memory Systems

• DOI: 10.3390/a14060171
• 发表时间: 2021-05
• 期刊: Algorithms
• 影响因子: 2.3
• 作者: Pavan Poudel;Gokarna Sharma