EAGER: Transactional Memory Foundations for Distributed Multiprocessor Systems

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

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.