Pattern matching on large graphs is the foundation for a variety of application domains. The continuously increasing size of the underlying graphs requires highly parallel in-memory graph processing engines that need to consider non-uniform memory access (NUMA) and concurrency issues to scale up on modern multiprocessor systems. To tackle these aspects, a fine-grained graph partitioning becomes increasingly important. Hence, we present a classification of graph partitioning strategies and evaluate representative algorithms on medium and large-scale NUMA systems in this paper. As a scalable pattern matching processing infrastructure, we leverage a data-oriented architecture that preserves data locality and minimizes concurrency-related bottlenecks on NUMA systems. Our in-depth evaluation reveals that the optimal partitioning strategy depends on a variety of factors and consequently, we derive a set of indicators for selecting the optimal partitioning strategy suitable for a given graph and workload.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:86492 |
| Date | 19 July 2023 |
| Creators | Krause, Alexander, Kissinger, Thomas, Habich, Dirk, Voigt, Hannes, Lehner, Wolfgang |
| Publisher | Springer |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/acceptedVersion, doc-type:conferenceObject, info:eu-repo/semantics/conferenceObject, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 978-3-319-64203-1, 10.1007/978-3-319-64203-1_11, info:eu-repo/grantAgreement/Deutsche Forschungsgemeinschaft/Sonderforschungsbereiche/164481002//HAEC - Highly Adaptive Energy-Efficient Computing/SFB 912 |
Page generated in 0.0016 seconds