Repository https://github.com/DIPSA-QUB/MS-BioGraphs-Validation Explanation We provide a Shell script, validation.sh, and a Java program, EdgeBlockSHA.java, to verify the the correctness of the graphs. Each graph has a .ojson file whose shasum is verified by the value retreived from our server. Files such as offsets.bin, wcc.bin, n2o.bin, trans_offsets.bin, and edges_shas.txt have shasum […]
Graph Algorithms
57 posts
Syed Tauhidi presented a poster on “Graphlet-based Filtering for High-Performance Subgraph Isomorphism Search” at the 19th International Summer School on Advanced Computer Architecture and Compilation for High-performance Embedded Systems, organised by HiPEAC at Fiuggi, Italy, between July 9 – 15, 2023. Summary Introduction Graphs are powerful tools for representing complex […]
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 […]
DOI: 10.1145/3524059.3532360 This paper proposes software-defined floating-point number formats for graph processing workloads, which can improve performance in irregular workloads by reducing cache misses. Efficient arithmetic on software-defined number formats is challenging, even when based on conversion to wider, hardware-supported formats. We derive efficient conversion schemes that are tuned to […]
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, […]
Finally got around to this: publishing the Graptor source code. With time passing, the code has changed quite a bit compared to that used in the paper: Graptor: efficient pull and push style vectorized graph processing. The evolution of the code has advantages: it’s faster. There are also disadvantages: not […]