Triangle Counting Accelerations: From Algorithm to In-Memory Computing Architecture

Xueyan Wang

doi:10.1109/TC.2021.3131049

Triangle Counting Accelerations: From Algorithm to In-Memory Computing Architecture

2022-10-01

15

OA

AI

DOI：10.1109/TC.2021.3131049

Original

Original request for help

Save

Abstract

En 中文

Triangles are the basic substructure of networks and triangle counting (TC) has been a fundamental graph computing problem in numerous fields such as social network analysis. Nevertheless, like other graph computing problems, due to the high memory-computation ratio and random memory access pattern, TC involves a large amount of data transfers thus suffers from the bandwidth bottleneck in the traditional Von-Neumann architecture. To overcome this challenge, in this paper, we propose to accelerate TC with the emerging processingin-memory (PIM) architecture through an algorithm-architecture co-optimization manner. To enable the efficient in-memory implementations, we come up to reformulate TC with bitwise logic operations (such as AND), and develop customized graph compression and mapping techniques for efficient data flow management. With the emerging computational Spin-Transfer Torque Magnetic RAM(STT-MRAM) array, which is one of the most promising PIM enabling techniques, the device-to-architecture co-simulation results demonstrate that the proposed TC in-memory accelerator outperforms the state-of-the-art GPU and FPGA accelerations by 12.2 x and 31.8 x, respectively, and achieves a 34 x energy efficiency improvement over the FPGA accelerator.

Keywords:

Triangle counting acceleration

processing-in-memory

algorithm-architecture co-design

graph computing

Triangle Counting Accelerations: From Algorithm to In-Memory Computing Architecture

Abstract

Journal

Organization