iPregel: Strategies to Deal with an Extreme Form of Irregularity in Vertex-Centric Graph Processing
| Autor: | Ludovic Anthony Richard Capelli, Nick Brown, Jonathan M. Bull |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Vertex (graph theory)
FOS: Computer and information sciences vertex-centric Theoretical computer science Computer science Computation cache efficiency 010103 numerical & computational mathematics 02 engineering and technology 01 natural sciences tructure externalisation load-balancing edge-centric workload 0202 electrical engineering electronic engineering information engineering 0101 mathematics Software prefetching 020203 distributed computing Computer Science - Performance Locality Workload Graph Performance (cs.PF) Computer Science - Distributed Parallel and Cluster Computing Programming paradigm Distributed Parallel and Cluster Computing (cs.DC) Performance improvement hybrid combiner MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Capelli, L, Brown, N & Bull, J 2019, iPregel: Strategies to Deal with an Extreme Form of Irregularity in Vertex-Centric Graph Processing . in 2019 IEEE/ACM 9th Workshop on Irregular Applications: Architectures and Algorithms (IA3) . Association for Computing Machinery (ACM), pp. 45-50, 9th Workshop on Irregular Applications: Architectures and Algorithms, Denver, United States, 18/11/19 . https://doi.org/10.1109/IA349570.2019.00013 IA3@SC |
| Popis: | Over the last decade, the vertex-centric programming model has attracted significant attention in the world of graph processing, resulting in the emergence of a number of vertex-centric frameworks. Its simple programming interface, where computation is expressed from a vertex point of view, offers both ease of programming to the user and inherent parallelism for the underlying framework to leverage. However, vertex-centric programs represent an extreme form of irregularity, both inter and intra core. This is because they exhibit a variety of challenges from a workload that may greatly vary across supersteps, through fine-grain synchronisations, to memory accesses that are unpredictable both in terms of quantity and location. In this paper, we explore three optimisations which address these irregular challenges; a hybrid combiner carefully coupling lock-free and lock-based combinations, the partial externalisation of vertex structures to improve locality and the shift to an edge-centric representation of the workload. The optimisations were integrated into the iPregel vertex-centric framework, enabling the evaluation of each optimisation in the context of graph processing across three general purpose benchmarks common in the vertex-centric community, each run on four publicly available graphs covering all orders of magnitude from a million to a billion edges. The result of this work is a set of techniques which we believe not only provide a significant performance improvement in vertex-centric graph processing, but are also applicable more generally to irregular applications. Preprint of paper submitted to 9th Workshop on Irregular Applications: Architectures and Algorithms (IA3) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|