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 […]
locality
12 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 […]
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, […]
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.
https://doi.org/10.1145/3293883.3295703 This work proposes Vertex- and Edge-Balanced Ordering (VEBO): balance the number of edges and the number of unique destinations of those edges. VEBO balances edges and vertices for graphs with a power-law degree distribution, and ensures an equal degree distribution between partitions. Experimental evaluation on three shared-memory graph processing […]
https://arxiv.org/abs/1806.06576 Graph partitioning drives graph processing in distributed, disk-based and NUMA-aware systems. A commonly used partitioning goal is to balance the number of edges per partition in conjunction with minimizing the edge or vertex cut. While this type of partitioning is computationally expensive, we observe that such topology-driven partitioning nonetheless […]
Thesis on QUB Pure PortalThesis in PDF Format Author: Jiawen Sun, https://www.linkedin.com/in/jiawen-sun-33b368103/ As shared memory systems support terabyte-sized main memory, they provide an opportunity to perform efficient graph analytics on a single machine. Graph analytics is characterised by frequent synchronisation, which is addressed in part by shared memory systems. However, […]