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 条

[31] EXPLOITING DIRECT ACCESS SHARED MEMORY FOR MPI ON MULTI-CORE PROCESSORS
Brightwell, Ron
INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS, 2010, 24 (01) : 69 - 77
[32] A Case Study of Complex Graph Analysis in Distributed Memory: Implementation and Optimization
Slota, George M.
Rajamanickam, Sivasankaran
Madduri, Kamesh
2016 IEEE 30TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2016), 2016, : 293 - 302
[33] SDSM: Fast and Scalable Security Support for Directory-Based Distributed Shared Memory
Shwartz, Ofir
Birk, Yitzhak
PROCEEDINGS OF THE 2016 IEEE INTERNATIONAL SYMPOSIUM ON HARDWARE ORIENTED SECURITY AND TRUST (HOST), 2016, : 114 - 119
[34] A Left-Looking Selected Inversion Algorithm and Task Parallelism on Shared Memory Systems
Jacquelin, Mathias
Lin, Lin
Jia, Weile
Zhao, Yonghua
Yang, Chao
PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING IN ASIA-PACIFIC REGION (HPC ASIA 2018), 2018, : 54 - 63
[35] Thread Mapping using System-level Throughput Prediction Model for Shared Memory Multicores
Mitra, Reshmi
Joshi, Bharat S.
Adams, Ryan S.
2014 IEEE INTERNATIONAL PERFORMANCE COMPUTING AND COMMUNICATIONS CONFERENCE (IPCCC), 2014,
[36] Novel parallel method for association rule mining on multi-core shared memory systems
Vu, Lan
Alaghband, Gita
PARALLEL COMPUTING, 2014, 40 (10) : 768 - 785
[37] CYCLIC: A LOCALITY-PRESERVING LOAD-BALANCING ALGORITHM FOR PDES ON SHARED MEMORY MULTIPROCESSORS
Garcia-Dopico, Antonio
Perez, Antonio
Rodriguez, Santiago
Isabel Garcia, Maria
COMPUTING AND INFORMATICS, 2012, 31 (06) : 1255 - 1278
[38] PyGim : An Efficient Graph Neural Network Library for Real Processing-In-Memory Architectures
Giannoula, Christina
Yang, Peiming
Fernandez, Ivan
Yang, Jiacheng
Durvasula, Sankeerth
Li, Yu xin
Sadrosadati, Mohammad
Luna, Juan gomez
Mutlu, Onur
Pekhimenko, Gennady
PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS, 2024, 8 (03)
[39] vGraph: Memory-Efficient Multicore Graph Processing for Traversal-Centric Algorithms
Jia, Menghan
Zhang, Yiming
Gan, Xinbiao
Li, Dongsheng
Xu, Erci
Wang, Ruibo
Lu, Kai
SC22: INTERNATIONAL CONFERENCE FOR HIGH PERFORMANCE COMPUTING, NETWORKING, STORAGE AND ANALYSIS, 2022,
[40] Analyzing MPI-3.0 Process-Level Shared Memory: A Case Study with Stencil Computations
Zhu, Xiaomin
Zhang, Junchao
Yoshii, Kazutomo
Li, Shigang
Zhang, Yunquan
Balaji, Pavan
2015 15TH IEEE/ACM INTERNATIONAL SYMPOSIUM ON CLUSTER, CLOUD AND GRID COMPUTING, 2015, : 1099 - 1106

← 1 2 3 4 5 →