A yoke of oxen and a thousand chickens for heavy lifting graph processing
Abdullah Gharaibeh, Lauro Beltrão Costa, Elizeu Santos‐Neto, Matei Ripeanu · 2012
Large, real-world graphs are famously difficult to process efficiently. Not only they have a large memory footprint but most graph processing algorithms entail memory access patterns with poor locality, data-dependent parallelism, and a low compute-to- memory access ratio. Additionally, most real-world graphs have a low diameter and a highly heterogeneous node degree distribution. Partitioning these graphs and simultaneously achieve access locality and load-balancing is difficult if not impossible.