Fast Scheduling in Distributed Transactional Memory
Fast Scheduling in Distributed Transactional Memory
复制标题
DOI：
10.1145/3087556.3087565
复制
发表时间：
2017-07
影响因子：
0.5
通讯作者：
C. Busch;Maurice Herlihy;M. Popovic;Gokarna Sharma
中科院分区：
文献类型：
--
作者：
C. Busch;Maurice Herlihy;M. Popovic;Gokarna Sharma
我们研究分布式事务存储器系统的调度算法，其中事务驻留在通信图的节点上操作共享的移动的对象。一个事务请求它需要的对象，一旦这些对象被组装好就执行，然后可能将这些对象转发给其他等待的事务。在这个模型中，最小化执行时间对于任意通信图都是NP困难的，并且很难在小于图的大小的任何因子内近似。然而，片上网络、多核系统和集群并不是任意的。在这里，我们探讨了在实践中可能出现的特殊图形中的高效执行调度：团，线，网格，集群，超立方体，蝴蝶和星星。在大多数情况下，当单个事务请求k个对象时，我们获得的解接近最优解的一个因子O（k），从而产生常数k的近似最优解。这些执行时间近似于图中对象的TSP行程长度。我们表明，对于一般的网络，即使是两个对象（k = 2），它是不可能获得的执行时间接近对象的最佳TSP巡回长度，这就是为什么它是有用的，考虑更现实的网络模型。据我们所知，这是第一次尝试获得分布式事务内存的可证明的快速调度。
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 possibly forwards those objects to other waiting transactions. Minimizing execution time in this model is known to be NP-hard for arbitrary communication graphs, and also hard to approximate within any factor smaller than the size of the graph. Nevertheless, networks on chips, multi-core systems, and clusters are not arbitrary. Here, we explore efficient execution schedules in specialized graphs likely to arise in practice: Clique, Line, Grid, Cluster, Hypercube, Butterfly, and Star. In most cases, when individual transactions request k objects, we obtain solutions close to a factor O(k) from optimal, yielding near-optimal solutions for constant k. These execution times approximate the TSP tour lengths of the objects in the graph. We show that for general networks, even for two objects (k = 2), it is impossible to obtain execution time close to the objects’ optimal TSP tour lengths, which is why it is useful to consider more realistic network models. To our knowledge, this is the first attempt to obtain provably fast schedules for distributed transactional memory.