ABSTRACT

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.

Please report errors in award information by writing to: awardsearch@nsf.gov.