Shared-memory Graph Truss Decomposition

被引：27

作者：

Kabir, Humayun ^{[1
]}

Madduri, Kamesh ^{[1
]}

机构：

[1] Penn State Univ, Comp Sci & Engn, University Pk, PA 16802 USA

来源：

2017 IEEE 24TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING (HIPC) | 2017年

基金：

美国国家科学基金会;

关键词：

k-truss; k-core; multicore; graph analysis;

D O I：

10.1109/HiPC.2017.00012

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present PKT, a new shared-memory parallel algorithm and OpenMP implementation for the truss decomposition of large sparse graphs. A k-truss is a dense subgraph definition that can be considered a relaxation of a clique. Truss decomposition refers to a partitioning of all the edges in the graph based on their k-truss membership. The truss decomposition of a graph has many applications. We show that our new approach PKT consistently outperforms other truss decomposition approaches for a collection of large sparse graphs and on a 24-core shared-memory server. PKT is based on a recently proposed algorithm for k-core decomposition.

引用

页码：13 / 22

页数：10

共 46 条

[1] A study of shared-memory parallelism in a multifrontal solver
L'Excellent, Jean-Yves
Sid-Lakhdar, Wissam M.
PARALLEL COMPUTING, 2014, 40 (3-4) : 34 - 46
[2] Parallel Performance Problems on Shared-Memory Multicore Systems: Taxonomy and Observation
Atachiants, Roman
Doherty, Gavin
Gregg, David
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 2016, 42 (08) : 764 - 785
[3] A 16-Core Processor With Shared-Memory and Message-Passing Communications
Yu, Zhiyi
Xiao, Ruijin
You, Kaidi
Quan, Heng
Ou, Peng
Yu, Zheng
He, Maofei
Zhang, Jiajie
Ying, Yan
Yang, Haofan
Han, Jun
Cheng, Xu
Zhang, Zhang
Jing, Ming'e
Zeng, Xiaoyang
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS, 2014, 61 (04) : 1081 - 1094
[4] Parallel Shared-Memory Workloads Performance on Asymmetric Multi-core Architectures
Madruga, Felipe L.
Freitas, Henrique C.
Navaux, Philippe O. A.
PROCEEDINGS OF THE 18TH EUROMICRO CONFERENCE ON PARALLEL, DISTRIBUTED AND NETWORK-BASED PROCESSING, 2010, : 163 - 169
[5] Exploring Shared-memory Optimizations for an Unstructured Mesh CFD Application on Modern Parallel Systems
Mudigere, Dheevatsa
Sridharan, Srinivas
Deshpande, Anand
Park, Jongsoo
Heinecke, Alexander
Smelyanskiy, Mikhail
Kaul, Bharat
Dubey, Pradeep
Kaushik, Dinesh
Keyes, David
2015 IEEE 29TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS), 2015, : 723 - 732
[6] HYBRID MESSAGE-PASSING AND SHARED-MEMORY PROGRAMMING IN A MOLECULAR DYNAMICS APPLICATION ON MULTICORE CLUSTERS
Chorley, Martin J.
Walker, David W.
Guest, Martyn F.
INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS, 2009, 23 (03): : 196 - 211
[7] Parallel two-stage reduction to Hessenberg form using dynamic scheduling on shared-memory architectures
Karlsson, L.
Kagstrom, B.
PARALLEL COMPUTING, 2011, 37 (12) : 771 - 782
[8] An Asynchronously Alternative Stochastic Gradient Descent Algorithm for Efficiently Parallel Latent Feature Analysis on Shared-Memory
Qin, Wen
Luo, Xin
2022 IEEE INTERNATIONAL CONFERENCE ON KNOWLEDGE GRAPH (ICKG), 2022, : 217 - 224
[9] WavePipe: Parallel transient simulation of analog and digital circuits on multi-core shared-memory machines
Dong, Wei
Li, Peng
Ye, Xiaoji
2008 45TH ACM/IEEE DESIGN AUTOMATION CONFERENCE, VOLS 1 AND 2, 2008, : 238 - 243
[10] A Truss-Based Framework for Graph Similarity Computation
Zheng, Yanwei
Zhang, Zichun
Luo, Qi
Xie, Zhenzhen
Yu, Dongxiao
JOURNAL OF DATABASE MANAGEMENT, 2023, 34 (01)

← 1 2 3 4 5 →