CAREER: Transactional Memory for Distributed Systems

并发编程的一个主要挑战是并发控制：(i)如何协调对并发执行任务之间共享的内存位置的访问；（ii）如何确保计算是正确的。传统的方法是使用屏障和锁，但是它们有一些缺点，会阻碍非专业用户编写并发程序。这个项目探索了最近出现的事务性记忆范式。本项目在日益流行的分布式多处理器系统环境中探索这种新范式，其中并发任务通过相互发送消息进行交互。该项目建立了理论和实践基础。在理论基础上的具体目标包括开发一套全面的导致不可能结果、下界和具有可证明性能保证的调度算法的技术。在实践基础上的具体目标包括开发一个称为GraphTM的系统，该系统足够健壮，可以根据广泛的基准应用程序评估设计的算法。以前，这种范式主要是在对称多处理器系统的背景下研究的，其中并发任务通过读写相同的主存储器进行交互。主要区别在于分布式多处理器系统中内存访问延迟的不均匀性。这种不均匀性是至关重要的，它不仅影响所有并发任务的总执行时间，还影响其他相关的网络参数，如通信成本和拥塞。因此，这个项目的技术优点是通过开发新的工具和技术来增强对并发控制中非均匀延迟影响的理解。这个项目的成果将对并发编程的原则和实践产生影响。由于最近的架构和计算趋势，每一代新多处理器系统都有越来越多的内核。因此，能够进行并发编程将是未来一项重要且必要的技能。事务性内存范式在概念上很简单，它将鼓励非专业用户编写并发程序，超越当前仅在专业用户中使用并发编程的情况。此外，该项目的一些成果将成为PI教授课程的一部分。开发的系统将向公众开放。研究结果将通过在主要会议、讲习班和研讨会上的演讲来传播。此外，该项目将指导和教育K-12、本科生和研究生并发编程，包括女性、少数族裔和第一代计算机科学专业的学生。最后，PI将单独或与K-12科学经验，夏季本科生研究经验（SURE）合作参加外展活动，并选择俄亥俄州第一（COF）项目。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A major challenge in concurrent programming is concurrency control: (i) how to coordinate accesses to memory locations shared among concurrently executing tasks and (ii) how to ensure that the computation is correct. The traditional approach is to use barriers and locks but they have several drawbacks that discourage non-expert users from writing concurrent programs. This project explores the recently emerged paradigm of transactional memory. This project explores this new paradigm in the context of the increasingly popular distributed multiprocessor systems, where concurrent tasks interact by sending messages to each other. This project establishes both theoretical as well as practical foundations. The specific goals on the theoretical foundations include developing a comprehensive set of techniques leading to impossibility results, lower bounds, and scheduling algorithms with provable performance guarantees. The specific goals on the practical foundations include developing a system, called GraphTM, that is robust enough to evaluate the designed algorithms against a wide range of benchmark applications. Previously, this paradigm was studied mostly in the context of the symmetric multiprocessor systems, where concurrent tasks interact through reading and writing the same main memory. The main difference is the non-uniformity in memory access latency in the distributed multiprocessor systems. This non-uniformity is vital and affects not only the total execution time of all concurrent tasks but also other related network parameters such as communication cost and congestion. Therefore, the technical merit of this project is based on enhancing understanding of the effects of non-uniform latency in concurrency control through the development of new tools and techniques. The outcomes of this project will have impacts on the principles and practice of concurrent programming. Due to recent architectural and computational trends, each new generation of multiprocessor systems is having an increasing number of cores. Therefore, being able to program with concurrency will be an important and necessary skill in the future. The transactional memory paradigm is conceptually simple and it will encourage non-expert users in writing concurrent programs, reaching beyond the current use of concurrent programming only among expert users. Moreover, some results of this project will be a part of courses the PI teaches. The developed system will be made publicly available. The research results will be disseminated through presentations in major conferences, workshops, and seminars. Additionally, this project will mentor and educate K-12, undergraduate, and graduate students in concurrent programming, including female, minority, and first-generation computer science students. Finally, the PI will participate in outreach events individually and in collaboration with K-12 science experience, summer undergraduate research experience (SURE), and choose Ohio first (COF) programs.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.