Improved Distributed-memory Triangle Counting by Exploiting the Graph Structure
Improved Distributed-memory Triangle Counting by Exploiting the Graph Structure
复制标题
通过利用图结构改进分布式内存三角形计数
DOI：
10.1109/hpec55821.2022.9926376
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Sayan Ghosh
中科院分区：
文献类型：
--
作者：
Sayan Ghosh
图在复杂系统的建模和实体间的交互中无处不在，以揭示领域的结构信息。传统上，由于该方法的不规则内存访问驱动性质（很少或没有计算），图分析工作负载在分布式内存上有效扩展（无论是强情况还是弱情况）都具有挑战性。图的结构及其在处理元素上的相对分布构成了另一个复杂程度，使得难以实现跨平台的可持续可扩展性。在本文中，我们讨论了TriC的增强功能，TriC是一种使用消息传递接口（MPI）的图形三角形计数的分布式内存实现，它在2020年图形挑战赛中有特色。我们对TriC进行了一些增量增强，主要采用用户定义的缓冲策略来克服大型图的启动问题（通过固定中间数据的内存），并尝试使用布隆过滤器等概率数据结构来改善评估边缘存在的查询响应时间，代价是增加整体误报率。与前一版本相比，这些调整在大多数情况下都带来了适度的改进。
Graphs are ubiquitous in modeling complex systems and representing interactions between entities to uncover structural information of the domain. Traditionally, graph analytics workloads are challenging to efficiently scale (both strong and weak cases) on distributed memory due to the irregular memory-access driven nature (with little or no computations) of the meth-ods. The structure of graphs and their relative distribution over the processing elements poses another level of complexity, making it difficult to attain sustainable scalability across platforms. In this paper, we discuss enhancements to TriC, a distributed-memory implementation of graph triangle counting using Mes-sage Passing Interface (MPI), which was featured in the 2020 Graph Challenge competition. We have made some incremental enhancements to TriC, primarily adopting a user-defined buffering strategy to overcome the startup problem for large graphs (by fixing the memory for intermediate data), and experimenting with probabilistic data structures such as bloom filter to improve the query response time for assessing edge existence, at the expense of increasing the overall false positive rate. These adjustments have led to a modest improvements in most cases, as compared to the previous version.
DOI：
10.1145/3394486.3403073
发表时间：
2020-06
期刊：
Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
影响因子：
--
作者：
Suman Kalyan Bera;Seshadhri Comandur
通讯作者：
Suman Kalyan Bera;Seshadhri Comandur
A64FX 性能：Ookami 体验
DOI：
10.1109/cluster48925.2021.00106
发表时间：
2021
期刊：
2021 IEEE International Conference on Cluster Computing (CLUSTER
影响因子：
--
作者：
Bari, Md Abdullah;Chapman, Barbara;Curtis, Anthony;Harrison, Robert J.;Siegmann, Eva;Simakov, Nikolay A.;Jones, Matthew D.
通讯作者：
Jones, Matthew D.