In applications such as graph processing, it is important how threads are pinned on CPU cores as the threads that share resources (such as memory and cache) can accelerate the performance by processing consecutive blocks of input dataset, especially, when the dataset has a high-level of locality. In LaganLighter, we […]
LaganLighter
10 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 […]
2021 IEEE International Symposium on Workload Characterization (IISWC’21)November 7-9, 2021Acceptance Rate: 39.5%DOI: 10.1109/IISWC53511.2021.00020 Authors’ Copy (PDF Format) Graph reordering algorithms try to improve locality of graph algorithms by assigning new IDs to vertices that ultimately changes the order of random memory accesses. While graph relabeling algorithms such as SlashBurn, GOrder, […]
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 […]
Relabeling (reordering) algorithms aim to improve the poor memory locality of graph processing by changing the order of vertices. This paper analyses the functionality of three state-of-the-art relabeling algorithms: SlashBurn, GOrder, and Rabbit-Order for real-world graphs. We use a number of techniques to explain how locality is affected by relabeling algorithms and how locality of different datasets (like social networks, web graphs) is enhanced by relabeling algorithms. This paper also investigates why different push and pull traversal of different datasets show different behaviours by introducing push locality and pull locality.