  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.
