MessageFusion: On-path Message Coalescing for Energy Efficient and Scalable Graph Analytics

The natural ability of graphs to capture complex relationships within a large amount of data makes graph-based algorithms critical kernels for a wide range of data-analytics applications. Recent processing-in-memory solutions based on a network of 3D-stacked memory, such as Hybrid Memory Cubes (HMCs), have been shown to be a good fit to run graph-based algorithms. However, the communication bandwidth of the network limits their energy and performance efficiencies. In this work, we propose MessageFusion, a domain-specific architecture that greatly reduces network traffic by computing many vertex-updates at the source node, as well as in the network. To this end, we observe that, for many algorithms, vertex-updates need not be atomic, but can be decomposed and computed in a distributed manner. MessageFusion leverages a novel edge-reordering mechanism to boost the number of partial update operations that can be completed before reaching their destination. In addition, to counteract the power overhead introduced by Message-Fusion’s edge-reordering mechanism, our solution employs module-level utilization-based, power-gating techniques. Our experimental evaluation shows that MessageFusion achieves a 3× energy savings over a highly-optimized processing-in-memory solution, while also improving performance by 2.1×, on average.