.png){kind=icon}
Return
Triangle Counting Accelerations: From Algorithm to In-Memory Computing Architecture
.png){kind=icon}
OA
AI
DOI：10.1109/TC.2021.3131049.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
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
Journal
IF:
3.8
Papers:
5.4K
Citations:
9.8K
Organization
View more organizations
Cited Papers
Current-induced magnetization switching in atom-thick tungsten engineered perpendicular magnetic tunnel junctions with large tunnel magnetoresistance.png)
NATURE COMMUNICATIONS
OAAI
NATURE COMMUNICATIONSIF15.7
OAAIShareSaveImplementation of a ZCT soft switching technique in a 100 kW PEBB based three-phase PFC rectifier
PREAI
ShareSaveShareSaveShareSaveShareSaveShareSave View more