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 条

[21] Discovering DNA Motifs with a Parallel Shared Memory Differential Evolution
Gonzalez-Alvarez, David L.
Vega-Rodriguez, Miguel A.
Gomez-Pulido, Juan A.
Sanchez-Perez, Juan M.
COMPUTER AIDED SYSTEMS THEORY - EUROCAST 2011, PT I, 2012, 6927 : 232 - 239
[22] Efficient Parallel GCD Algorithms for Multicore Shared Memory Architectures
Pathirana, Gihan Tharaka
Sotheeswaran, Sittampalam
Ratnarajah, Nagulan
2020 20TH INTERNATIONAL CONFERENCE ON ADVANCES IN ICT FOR EMERGING REGIONS (ICTER-2020), 2020, : 272 - 273
[23] Pairwise sequence alignment method for distributed shared memory systems
Montanola, Alberto
Roig, Concepcio
Hernandez, Porfidio
PROCEEDINGS OF THE 2013 21ST EUROMICRO INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED, AND NETWORK-BASED PROCESSING, 2013, : 432 - 436
[24] A Study on Influence of Design Pattern in Shared Memory Multiprocessor Application
Liu Wenjun
2010 INTERNATIONAL CONFERENCE ON BIO-INSPIRED SYSTEMS AND SIGNAL PROCESSING (ICBSSP 2010), 2010, : 191 - 193
[25] Performance Issues of SYRK implementations in Shared Memory Environments for Edge Cases
Hossain, Mosharaf
Hines, Thomas M.
Ghafoor, Sheikh K.
Marshall, Ryan J.
Amanzholov, Muzakhir S.
Kannan, Ramakrishnan
2018 21ST INTERNATIONAL CONFERENCE OF COMPUTER AND INFORMATION TECHNOLOGY (ICCIT), 2018,
[26] Prediction and Bounds on Shared Cache Demand from Memory Access Interleaving
Brock, Jacob
Ding, Chen
Lavaee, Rahman
Liu, Fangzhou
Yuan, Liang
ACM SIGPLAN NOTICES, 2018, 53 (05) : 96 - 108
[27] Prediction and Bounds on Shared Cache Demand from Memory Access Interleaving
Brock, Jacob
Ding, Chen
Lavaee, Rahman
Liu, Fangzhou
Yuan, Liang
PROCEEDINGS OF THE 2018 ACM SIGPLAN INTERNATIONAL SYMPOSIUM ON MEMORY MANAGEMENT (ISMM'18), 2018, : 96 - 108
[28] I/O Efficient Core Graph Decomposition: Application to Degeneracy Ordering
Wen, Dong
Qin, Lu
Zhang, Ying
Lin, Xuemin
Yu, Jeffrey Xu
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2019, 31 (01) : 75 - 90
[29] Redesigning MPI shared memory communication for large multi-core architecture
Luo, Miao
Wang, Hao
Vienne, Jerome
Panda, Dhabaleswar K.
COMPUTER SCIENCE-RESEARCH AND DEVELOPMENT, 2013, 28 (2-3): : 137 - 146
[30] Architectural support for efficient message passing on shared memory multi-cores
Titos-Gil, Ruben
Palomar, Oscar
Unsal, Osman
Cristal, Adrian
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2016, 95 : 92 - 106

← 1 2 3 4 5 →