CSR: Medium: A Smart Runtime System for Parallel Programming

CSR：Medium：用于并行编程的智能运行时系统

• 批准号: 1563544
• 负责人: Vijay Garg
• 金额: $ 50.98万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-06-01 至 2020-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1563544&HistoricalAwards=false
• 关键词: CSR; Medium; Smart; Runtime; System

Since the clock speed of computers is not increasing, the only way to speed up processing is by exploiting multiple cores. Programming these multicore processors is a challenging task due to bugs resulting from concurrency and synchronization. This project is developing new synchronization mechanisms that address three aspects of concurrent systems --- programmability, scalability and fault-tolerance. Programmability refers to the ease of developing concurrent applications. Scalability refers to the performance of the program when the number of threads in the system increase. Fault-tolerance refers to the ability of the system to cope with failure of a thread holding a lock.Currently, the most prevalent synchronization mechanism is based on monitors with condition variables. Monitors or lock based systems are hard to use for multi object operations, usually have poor scalability and low tolerance for faults. Lock-free mechanisms may have good scalability and fault-tolerance, but are notoriously hard to write and debug. Software Transactional Memory systems hold most promise for programmability. However, it is difficult to get efficient conditional synchronization in current transactional memory systems. This project is developing new synchronization techniques that address global conditional synchronization aspects of monitor or transactional memory systems. In particular, it is developing scalable mechanisms to detect global or multi object conditions and automatically notify threads waiting on these conditions. The only way to simulate this mechanism in current systems is by using a global lock or busy wait which results in a large number of context switches and slower performance. The mechanisms developed in this project will result in more concise and faster programs.For scalability and fault-tolerance, the project is developing methods that enable asynchronous and parallel execution of certain object methods. Asynchronous execution is carried out by keeping a monitor thread that can execute methods on behalf of threads that make the monitor call. This technique improves cache locality and concurrency. For objects with high-contention, the project is studying methods that enable parallel execution of read operations by keeping read-only copies of objects. However, maintaining copies of every monitor object or creating an additional thread for asynchronous execution is inefficient. The project is developing efficient techniques to determine which objects to replicate at runtime.The project will result in improving programmer productivity and reducing concurrency errors in development of multicore programs. It will also lead to better understanding of how global conditions in a multithreaded program can be evaluated efficiently. As a result, the concurrent programming systems will become more reliable and faster. In addition, the graduate students supported by the project will be trained in fundamentals of multicore computing.

由于计算机的时钟速度没有提高，加快处理速度的唯一方法是利用多核。由于并发和同步导致的错误，对这些多核处理器进行编程是一项具有挑战性的任务。这个项目正在开发新的同步机制，以解决并发系统的三个方面-可编程性、可伸缩性和容错。可编程性是指开发并发应用程序的简单性。可伸缩性是指当系统中的线程数量增加时程序的性能。容错是指系统对持有锁的线程发生故障的处理能力，目前最流行的同步机制是基于带条件变量的监控器。基于监视器或锁的系统很难用于多对象操作，通常可扩展性差，容错能力低。无锁机制可能具有良好的可伸缩性和容错性，但其编写和调试的难度是出了名的。软件事务存储系统在可编程性方面有着最大的希望。然而，在当前的事务存储系统中，很难获得有效的条件同步。该项目正在开发新的同步技术，以解决监控或事务存储系统的全局条件同步方面的问题。特别是，它正在开发可伸缩的机制来检测全局或多对象条件，并自动通知等待这些条件的线程。在当前系统中模拟这种机制的唯一方法是使用全局锁或繁忙等待，这会导致大量的上下文切换和较慢的性能。该项目开发的机制将产生更简洁、更快的程序。为了实现可伸缩性和容错性，该项目正在开发支持某些对象方法的异步和并行执行的方法。异步执行是通过保持一个监视器线程来执行的，该监视器线程可以代表进行监视器调用的线程执行方法。该技术提高了缓存的局部性和并发性。对于争用程度较高的对象，该项目正在研究通过保留对象的只读副本来实现并行执行读取操作的方法。然而，维护每个监视器对象的副本或为异步执行创建额外的线程效率很低。该项目正在开发有效的技术来确定在运行时复制哪些对象。该项目将提高程序员的生产力，并减少多核程序开发中的并发错误。它还将有助于更好地理解如何有效地评估多线程程序中的全局条件。因此，并发编程系统将变得更加可靠和快速。此外，该项目支持的研究生将接受多核计算基础知识的培训。

项目成果

Predicate Detection to Solve Combinatorial Optimization Problems

谓词检测解决组合优化问题

• DOI: 10.1145/3350755.3400235
• 发表时间: 2020
• 期刊: Symposium on Parallel Algorithms and Architectures
• 作者: Garg, Vijay K.

Linearizable Replicated State Machines With Lattice Agreement

具有格协议的线性化复制状态机

• DOI: 10.4230/lipics.opodis.2019.29
• 发表时间: 2019
• 期刊: OPODIS 2019
• 作者: Zheng, Xiong;Garg, Vijay K;Kaippallimalil, John
• 通讯作者: Kaippallimalil, John

Byzantine Lattice Agreement in Synchronous Message Passing Systems

同步消息传递系统中的拜占庭格协议

• DOI: 10.4230/lipics.disc.2020.32
• 发表时间: 2020
• 期刊: International Symposium on Distributed Computing (DISC 2020
• 作者: Zheng, Xiong;Garg, Vijay
• 通讯作者: Garg, Vijay

Parallel and Distributed Algorithms for the Housing Allocation Problem

住房分配问题的并行分布式算法

• DOI: 10.4230/lipics.opodis.2019.23
• 发表时间: 2019
• 期刊: International Conference on Principles of Distributed Systems (OPODIS 2019
• 作者: Zheng, Xiong;Garg, Vijay K
• 通讯作者: Garg, Vijay K

NC Algorithms for Popular Matchings in One-Sided Preference Systems and Related Problems

单边偏好系统中热门匹配的数控算法及相关问题

• DOI: 10.1109/ipdps47924.2020.00083
• 发表时间: 2020
• 期刊: IEEE International Parallel and Distributed Processing Symposium (IPDPS
• 作者: Hu, Changyong;Garg, Vijay K.
• 通讯作者: Garg, Vijay K.