Dynamic scheduling in distributed transactional memory
Dynamic scheduling in distributed transactional memory
复制标题
DOI：
10.1109/ipdps47924.2020.00094
复制
发表时间：
2020-05
影响因子：
1.3
通讯作者：
C. Busch;Maurice Herlihy;M. Popovic;Gokarna Sharma
中科院分区：
文献类型：
--
作者：
C. Busch;Maurice Herlihy;M. Popovic;Gokarna Sharma
我们研究分布式事务存储器系统的调度算法，其中事务驻留在通信图的节点上操作共享的移动的对象。一个事务请求它需要的对象，一旦这些对象被组装好就执行，然后将这些对象发送给其他等待的事务。我们研究调度算法与可证明的性能保证。以前，只有离线批调度设置被认为是在文献中的交易是已知的先验。最小化执行时间，即使是离线批处理调度，已知是NP-困难的任意通信图。在本文中，我们分析了非常第一次调度算法的在线动态调度设置中的交易是不知道的先验和交易可能会随着时间的推移在线。我们提供了有效的和接近最佳的执行时间表，在许多专门的网络架构的动态调度。我们的技术的核心是一种方法，将离线时间表转换为在线。我们首先描述了一个集中式调度器，然后我们适应一个纯粹的分布式调度。据我们所知，这些是第一次尝试获得分布式事务内存的可证明有效的在线执行计划。
We investigate scheduling algorithms for distributed transactional memory systems where transactions residing at nodes of a communication graph operate on shared, mobile objects. A transaction requests the objects it needs, executes once those objects have been assembled, and then sends the objects to other waiting transactions. We study scheduling algorithms with provable performance guarantees. Previously, only the offline batch scheduling setting was considered in the literature where transactions are known a priori. Minimizing execution time, even for the offline batch scheduling, is known to be NP-hard for arbitrary communication graphs. In this paper, we analyze for the very first time scheduling algorithms in the online dynamic scheduling setting where transactions are not known a priori and the transactions may arrive online over time. We provide efficient and near-optimal execution time schedules for dynamic scheduling in many specialized network architectures. The core of our technique is a method to convert offline schedules to online. We first describe a centralized scheduler which we then adapt to a purely distributed scheduler. To our knowledge, these are the first attempts to obtain provably efficient online execution schedules for distributed transactional memory.