Partitioning of complex networks for heterogeneous computing: A methodological approach
Alberto Garcia‐Robledo, Arturo Díaz-Pérez, Guillermo B. Morales-Luna · 2016
We present a methodology that guides the design of a multilevel-like unbalanced complex network partitioning framework for load-balance in a graph heterogeneous computing context. Throughout the paper we describe: (1) the design of a topology-aware complex network coarsening process that preserves non-redundant complex network properties, (2) the multilevel partitioning of coarse graphs by the centrality of nodes, and (3) the demonstration of the benefits of the proposed partitioning framework by empirically studying the performance of a BSP-based CPU+GPU heterogeneous computing platform when accelerating the traversal of large real-world and synthetic complex networks.