AutoGMap: Learning to Map Large-Scale Sparse Graphs on Memristive Crossbars.

Area of Science:

• Computer Engineering
• Artificial Intelligence
• Materials Science

Background:

• Sparse graph representation accelerates computation on traditional architectures (CPU, GPU, TPU).
• Large-scale sparse graph computing on processing-in-memory (PIM) platforms, especially memristive crossbars, remains underexplored.
• Existing block partition schemes for PIM are coarse-grained, static, and not sparsity-aware, leading to inefficient resource utilization.

Purpose of the Study:

• To propose a dynamic sparsity-aware mapping scheme for efficient large-scale sparse graph computing on PIM.
• To optimize the mapping process using reinforcement learning (RL) for improved resource utilization.
• To demonstrate the effectiveness of the proposed scheme on both small-scale and large-scale graph/matrix data.

Main Methods:

• Modeling the mapping problem as a sequential decision-making problem.
• Utilizing a reinforcement learning (RL) algorithm, specifically REINFORCE, for optimization.
• Developing a generating model combining long short-term memory (LSTM) with a dynamic-fill scheme.

Main Results:

• The dynamic sparsity-aware mapping scheme achieved remarkable performance.
• Complete mapping cost was reduced to 43% of the original matrix area for small-scale data.
• Significant area reduction was observed for large-scale matrices: 22.5% for qh882 and 17.1% for qh1484.

Conclusions:

• The proposed dynamic sparsity-aware mapping scheme offers a highly efficient approach for sparse graph computing on PIM.
• The method significantly reduces storage and computational resource waste on memristive crossbars.
• This approach is extensible to other PIM architectures beyond memristive devices.