Early experiences on accelerating Dijkstra's algorithm using transactional memory
Early experiences on accelerating Dijkstra's algorithm using transactional memory
复制标题
使用事务内存加速 Dijkstra 算法的早期经验
DOI：
10.1109/ipdps.2009.5161103
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
N. Koziris
中科院分区：
文献类型：
--
作者：
Nikos Anastopoulos;K. Nikas;G. Goumas;N. Koziris
在本文中，我们使用Dijkstra的算法作为一个具有挑战性的，难以并行化的范例来测试多核架构中的几种并行化技术的有效性。我们认为应用程序的transmittance内存（TM）作为一种手段，并发访问共享数据，并比较其性能与简单的并行版本的算法的基础上，传统的同步原语。为了增加并行的粒度和避免过度的同步，我们将联合收割机TM和辅助线程（HT）结合起来。我们的模拟结果表明，直接并行化的Dijkstra的算法与传统的锁和障碍，如预期的那样，令人失望的性能。另一方面，TM本身是能够提供一些性能改善在几种情况下，而基于TM和HT的版本表现出显着的性能改善，可以达到1.46的加速比。
In this paper we use Dijkstra's algorithm as a challenging, hard to parallelize paradigm to test the efficacy of several parallelization techniques in a multicore architecture. We consider the application of Transactional Memory (TM) as a means of concurrent accesses to shared data and compare its performance with straightforward parallel versions of the algorithm based on traditional synchronization primitives. To increase the granularity of parallelism and avoid excessive synchronization, we combine TM with Helper Threading (HT). Our simulation results demonstrate that the straightforward parallelization of Dijkstra's algorithm with traditional locks and barriers has, as expected, disappointing performance. On the other hand, TM by itself is able to provide some performance improvement in several cases, while the version based on TM and HT exhibits a significant performance improvement that can reach up to a speedup of 1.46.