EAGER: Transactional Memory Foundations for Distributed Multiprocessor Systems

Kent State University, Kent OH

Investigators

Abstract

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.