AutoGMap: Learning to Map Large-scale Sparse Graphs on Memristive
  Crossbars
  The sparse representation of graphs has shown its great potential for
accelerating the computation of the graph applications (e.g. Social Networks,
Knowledge Graphs) on traditional computing architectures (CPU, GPU, or TPU).
But the exploration of the large-scale sparse graph computing on
processing-in-memory (PIM) platforms (typically with memristive crossbars) is
still in its infancy. As we look to implement the computation or storage of
large-scale or batch graphs on memristive crossbars, a natural assumption would
be that we need a large-scale crossbar, but with low utilization. Some recent
works have questioned this assumption to avoid the waste of the storage and
computational resource by "block partition", which is fixed-size, progressively
scheduled, or coarse-grained, thus is not effectively sparsity-aware in our
view. This work proposes the dynamic sparsity-aware mapping scheme generating
method that models the problem as a sequential decision-making problem which is
solved by reinforcement learning (RL) algorithm (REINFORCE). Our generating
model (LSTM, combined with our dynamic-fill mechanism) generates remarkable
mapping performance on a small-scale typical graph/matrix data (43% area of the
original matrix with fully mapping), and two large-scale matrix data (22.5%
area on qh882, and 17.1% area on qh1484). Moreover, our coding framework of the
scheme is intuitive and has promising adaptability with the deployment or
compilation system.
