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科学经验，夏季本科研究经验（当然），选择俄亥俄州第一（COF），夏季训练营，俄亥俄州的夏季计算机科学和信息系统Colloquium等。交易记忆已成为一种有吸引力的态度，以较大的范围为基础，该范围是传统的范围。但是，过去的研究主要在紧密耦合的系统的背景下检查了交易内存，这些系统由共享相同物理主内存的一组处理器组成。该项目的目的是在松散耦合的系统的背景下研究交易记忆，由相对自主的处理器集合组成，每个处理器都有自己的内存。由于最近的架构和计算趋势，松散耦合的系统变得越来越流行，预计交易记忆将可用于这些系统中的并发控制。特别是，该项目在不同的执行模型和实际场景下建立了坚实的理论和实践基础，从而显着提高了对松散耦合系统中交易记忆的当前理解。该项目的具体目标包括：（i）在松散耦合的系统中建立不可能的和下限的结果，（ii）设计和正式分析可证实的调度调度算法，并具有（接近 - 最佳的最佳性能保证），以在实践中及其实现的特定型号，以及（III），以及（III），以及（iii），以及（iii），以及（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

Byzantine Geoconsensus

拜占庭地理共识

• DOI: 10.1007/978-3-030-91014-3_2
• 发表时间: 2021
• 期刊: The 9th International Conference on Networked Systems (NETYS
• 作者: Oglio, Joseph;Hood, Kendric;Sharma, Gokarna;Nesterenko, Mikhail
• 通讯作者: Nesterenko, Mikhail