Using Complex-Network properties For Efficient Graph Analysis

International audienceComplex networks are set of entities in a relationship, modeled by graphs where nodes represent entities and edges between nodes represent relationships. Graph algorithms have inherent characteristics, including data-driven computations and poor locality. These characteristics expose graph algorithms to several challenges; this is because most well studied (parallel) abstractions and implementation are not suitable for them. This work shows how we use some complex-network properties, including community structure and heterogeneity of node degree, to tackle one of the main challenges: improving performance, by improving memory location and by providing proper thread scheduling. In this paper, we firstly formalize complex-network ordering for cache misses reducing as a well known NP-Complete problem, the optimal linear arrangement problem; we then propose cn-order an heuristic that outperforms very recent graph orders. Secondly, we formalize degree-aware scheduling problem as another well known NP-Complete problem, the multiple knapsack problem; then we propose two degree-aware heuristics to solve it. We finally validate our theoretical observations with experiments on a 32 cores NUMA machine with some graph algorithms and some stanford graph datasets. For example, some results with Pagerank algorithm and livejournal dataset show that using cn-order improves performance by reducing cache misses and hence time by 41%; and when cn-order is combined with degree-aware scheduling, time is reduced by 50% due to load balancing among threads