A Study of a Transactional Parallel Routing Algorithm
A Study of a Transactional Parallel Routing Algorithm
复制标题
一种事务并行路由算法的研究
DOI：
10.1109/pact.2007.11
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Luján
中科院分区：
文献类型：
--
作者：
I. Watson;C. Kirkham;M. Luján
事务性内存为传统锁提供了另一种同步原语。它的承诺是简化多线程应用程序的软件开发，同时使用（复杂且容易出错的）细粒度锁提供并行应用程序的性能。本研究报告了我们使用事务性内存（TM）实现实际应用程序的经验。该应用程序是Lee的路由算法，之所以被选中，是因为它具有丰富的并行性，但难以用锁来表达。网格中源点和目的点之间的每条路由都可以看作是一个并行度单位。从这个简单的方法开始，我们评估事务性并行实现的可利用并行性，并探讨如何调整它以提供更好的性能。这种调整不会引入锁，也不会改变所实现算法的本质，而是提供高达20倍的并行性。这些调整源于对应用程序本身和TM的理解。该评估模拟了一个抽象的TM系统，因此，结果独立于特定的软件或硬件TM实现，并描述了应用程序的属性。
Transactional memory proposes an alternative synchronization primitive to traditional locks. Its promise is to simplify the software development of multi-threaded applications while at the same time delivering the performance of parallel applications using (complex and error prone) fine grain locking. This study reports our experience implementing a realistic application using transactional memory (TM). The application is Lee's routing algorithm and was selected for its abundance of parallelism but difficulty of expressing it with locks. Each route between a source and a destination point in a grid can be considered a unit of parallelism. Starting from this simple approach, we evaluate the exploitable parallelism of a transactional parallel implementation and explore how it can be adapted to deliver better performance. The adaptations do not introduce locks nor alter the essence of the implemented algorithm, but deliver up to 20 times more parallelism. The adaptations are derived from understanding the application itself and TM. The evaluation simulates an abstracted TM system and, thus, the results are independent of specific software or hardware TM implemented, and describe properties of the application.