Heterogeneous Memory Subsystem for Natural Graph Analytics

As graph applications become more popular and diverse, it is important to design efficient hardware architectures that maintain the flexibility of high-level graph programming frameworks. Prior works have identified the memory subsystem of traditional chip multiprocessors (CMPs) as a key source of inefficiency; however, these solutions do not exploit locality that exists in the structure of many real-world graphs. In this work, we target graphs that follow a power-law distribution, for which there is a unique opportunity to significantly boost the overall performance of the memory subsystem. We note that many natural graphs, derived from web, social networks, even biological networks, follow the power law, that is, 20% of the vertices are linked to 80% of the edges. Based on this observation, we propose a novel memory subsystem architecture that leverages this structural graph locality. Our architecture is based on a heterogeneous cache/scratchpad memory subsystem and a lightweight compute engine, to which the cores can offload atomic graph operations. Our architecture provides 2x speedup, on average, over a same-sized baseline CMP running the Ligra framework, while requiring no modification to the Ligra programming interface.