Exploring accelerator and parallel graph algorithmic choices for temporal graphs
Exploring accelerator and parallel graph algorithmic choices for temporal graphs
复制标题
DOI：
10.1145/3380536.3380540
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Akif Rehman;Masab Ahmad;O. Khan
中科院分区：
文献类型：
--
作者：
Akif Rehman;Masab Ahmad;O. Khan
许多现实世界中的系统都利用了时间变化的图形，边缘会出现并消失。此外，不同边缘的权重也是时间的函数。已开发了各种常规的图形算法，例如单源最短路径（SSSP），已为时变图开发。但是，这些算法本质上是顺序的，它们的平行对应物在很大程度上被忽略了。另一方面，静态图的并行算法作为有序和无序变体实现。无序的实现并未执行并行处理任务的本地或全球订单，而是会产生冗余的任务处理以收集其解决方案。这些实现以高冗余工作为代价暴露了并行性。放松订购的实现通过每核优先级排队维护本地秩序，以减少冗余工作的数量，同时暴露并行性。最后，严格订购的实现通过以高线程同步为代价实施全球订单来实现顺序版本的工作效率。这些并行实现是为了探索在不同并行加速器上提供最佳性能的选择。这项工作表明，在英特尔Xeon-40核心上选择最佳平行实现提取物的几何性能增益为46.38％，NVIDIA GTX-1080 GPU上的几何性能增益为20.30％。还表明，时间图的最佳实现选择并不总是与它们各自的静态图相同。
Many real-world systems utilize graphs that are time-varying in nature, where edges appear and disappear with respect to time. Moreover, the weights of different edges are also a function of time. Various conventional graph algorithms, such as single source shortest path (SSSP) have been developed for time-varying graphs. However, these algorithms are sequential in nature and their parallel counterparts are largely overlooked. On the other hand, parallel algorithms for static graphs are implemented as ordered and unordered variants. Unordered implementations do not enforce local or global order for processing tasks in parallel, but incur redundant task processing to converge their solutions. These implementations expose parallelism at the cost of high redundant work. Relax-ordered implementations maintain local order through per-core priority queues to reduce the amount of redundant work, while exposing parallelism. Finally, strict-ordered implementations achieve the work efficiency of sequential version by enforcing a global order at the expense of high thread synchronizations. These parallel implementations are adopted for temporal graphs to explore the choices that provide optimal performance on different parallel accelerators. This work shows that selecting the optimal parallel implementation extracts geometric performance gain of 46.38% on Intel Xeon-40 core and 20.30% on NVidia GTX-1080 GPU. It is also shown that optimal implementation choices for temporal graphs are not always the same as their respective static graphs.