GRAPHVINE: Exploiting Multicast for Scalable Graph Analytics
Leul Belayneha and Valeria Bertaccob
University of Michigan, Ann Arbor
aleulb@umich.edu
bvaleria@umich.edu
ABSTRACT
The proliferation of graphs as a key data structure for big-data analytics has heightened the demand for efficient graph processing. To meet this demand, prior works have proposed processing in memory (PIM) solutions in 3D-stacked DRAMs, such as Hybrid Memory Cubes (HMCs). However, PIM-based architectures, despite considerable improvement over conventional architectures, continue to be hampered by the presence of high inter-cube communication traffic. In turn, this trait has limited the underlying processing elements from fully capitalizing on the memory bandwidth an HMC has to offer. In this paper, we show that it is possible to combine multiple messages emitted from a source node into a single multicast message, thus reducing the inter-cube communication without affecting the correctness of the execution. Hence, we propose to add multicast support at source and in-network routers to reduce vertex-update traffic. Our experimental evaluation shows that, by combining multiple messages emitted at the source, it is possible to achieve an average speedup of 2:4⨯ over a highly optimized PIM-based solution and reduce energy consumption by 3:4⨯, while incurring a modest power overhead of 6:8%.
