Enhancing Scalability and Performance in Influence Maximization with Optimized Parallel Processing
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909389483409408 |
|---|---|
| author | Wu, Hanjiang Xu, Huan Park, Joongun Tithi, Jesmin Jahan Checconi, Fabio Wolfson-Pou, Jordi Petrini, Fabrizio Krishna, Tushar |
| author_facet | Wu, Hanjiang Xu, Huan Park, Joongun Tithi, Jesmin Jahan Checconi, Fabio Wolfson-Pou, Jordi Petrini, Fabrizio Krishna, Tushar |
| contents | Influence Maximization (IM) is vital in viral marketing and biological network analysis for identifying key influencers. Given its NP-hard nature, approximate solutions are employed. This paper addresses scalability challenges in scale-out shared memory system by focusing on the state-of-the-art Influence Maximization via Martingales (IMM) benchmark. To enhance the work efficiency of the current IMM implementation, we propose EFFICIENTIMM with key strategies, including new parallelization scheme, NUMA-aware memory usage, dynamic load balancing and fine-grained adaptive data structures. Benchmarking on a 128-core CPU system with 8 NUMA nodes, EFFICIENTIMM demonstrated significant performance improvements, achieving an average 5.9x speedup over Ripples across 8 diverse SNAP datasets, when compared to the best execution times of the original Ripples framework. Additionally, on the Youtube graph, EFFICIENTIMM demonstrates a better memory access pattern with 357.4x reduction in L1+L2 cache misses as compared to Ripples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_09473 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Enhancing Scalability and Performance in Influence Maximization with Optimized Parallel Processing Wu, Hanjiang Xu, Huan Park, Joongun Tithi, Jesmin Jahan Checconi, Fabio Wolfson-Pou, Jordi Petrini, Fabrizio Krishna, Tushar Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Influence Maximization (IM) is vital in viral marketing and biological network analysis for identifying key influencers. Given its NP-hard nature, approximate solutions are employed. This paper addresses scalability challenges in scale-out shared memory system by focusing on the state-of-the-art Influence Maximization via Martingales (IMM) benchmark. To enhance the work efficiency of the current IMM implementation, we propose EFFICIENTIMM with key strategies, including new parallelization scheme, NUMA-aware memory usage, dynamic load balancing and fine-grained adaptive data structures. Benchmarking on a 128-core CPU system with 8 NUMA nodes, EFFICIENTIMM demonstrated significant performance improvements, achieving an average 5.9x speedup over Ripples across 8 diverse SNAP datasets, when compared to the best execution times of the original Ripples framework. Additionally, on the Youtube graph, EFFICIENTIMM demonstrates a better memory access pattern with 357.4x reduction in L1+L2 cache misses as compared to Ripples. |
| title | Enhancing Scalability and Performance in Influence Maximization with Optimized Parallel Processing |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.09473 |