DOI: 10.48550/arXiv.2501.06872PDF version This paper investigates the shared-memory Graph Transposition (GT) problem, a fundamental graph algorithm that is widely used in graph analytics and scientific computing. Previous GT algorithms have significant memory requirements that are proportional to the number of vertices and threads which obstructs their use on large graphs. […]
structure-aware algorithms
8 posts
Mohsen Koohi EsfahaniSupervisors: Hans Vandierendonck and Peter Kilpatrick Thesis in PDF formatThesis on QUB Pure Portal Graph algorithms find several usages in industry, science, humanities, and technology. The fast-growing size of graph datasets in the context of the processing model of the current hardware has resulted in different bottlenecks such […]
Repository https://github.com/DIPSA-QUB/LaganLighter Documentation https://github.com/DIPS-QUB/LaganLighter/tree/main/docs Algorithms in This Repo Cloning git clone https://github.com/MohsenKoohi/LaganLighter.git --recursive Graph Types LaganLighter supports the following graph formats: Measurements In addition to execution time, we use the PAPI library to measure hardware counters such as L3 cache misses, hardware instructions, DTLB misses, and load and store memory […]
36th ACM International Conference on Supercomputing 2022June 27-30, 2022Acceptance Rate: 25% DOI: 10.1145/3524059.3532365Authors’ Copy (PDF Format) The Minimum Spanning Forest (MSF) problem finds usage in many different applications. While theoretical analysis shows that linear-time solutions exist, in practice, parallel MSF algorithms remain computationally demanding due to the continuously increasing size […]
2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS 2022)May 22-24, 2022 DOI: 10.1109/ISPASS55109.2022.00015 Authors’ Copy (PDF) While counting sort has a better complexity than comparison-based sorting algorithms, its parallelization suffers from high performance overhead and/or has a memory complexity that depends on the numbers of threads […]
27th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP 2022)April 2-6, 2022Acceptance Rate: 31% DOI: 10.1145/3503221.3508402Authors’ Copy (PDF Format) Triangle Counting (TC) is a basic graph algorithm and is widely used in different fields of science, humanities and technology. The great size of real-world graphs with […]
IEEE CLUSTER 20217-10 SeptemberAcceptance rate: 29.4% DOI: 10.1109/Cluster48925.2021.00042IEEE XplorePDF Version (Authors’ Copy) Thrifty introduces four optimization techniques to Label Propagation Connected Components: 1) Unified Labels Array accelerates label propagation by allowing the latest label of each vertex to be read in processing other vertices. 2) Zero Convergence optimizes work-efficiency in […]
50th International Conference on Parallel Processing (ICPP’21)August 9-12, 2021Acceptance Rate: 26.4% DOI:10.1145/3472456.3472462ACM Digital LibraryPDF Version (Authors’ Copy) This paper investigates the implications made by the structure of real-world graphs with power-law degree distribution on the locality of SpMV graph analytics, and by considering the efficacy of locality optimizing graph reordering […]