An ReRAM-based Accelerator For Sparse Graph Analytics Application

The traditional computer processing architecture is facing a severe "storage wall" challenge,and with the rapid expansion of the scale of graph data in the real world,it is difficult to meet the real needs of graph computing with high bandwidth,low latency,and large capacity.Resistive random access memory(ReRAM),an in-memory computing hardware,provides the possibility to solve the above problems by integrating the computing unit into the memory unit.Considering that the Re RAM adopts the matrix structure as the element granularity of organization,therefore,when processing real-world graph data with power law distribution,there will be a lot of invalid storage(for example,zero elements and inactive elements,causing sparseness problems,and the storage unit idling rate will be high,resulting in a lot of invalid calculation,so the parallelism and energy efficiency ratio are not ideal.By observing the internal mechanism of the large number of zero elements mentioned above,it is found that the source node and the destination node of the graph are mapped to the word line and the bit line of the memristor by continuous mapping,which causes the sparseness problem.The underlying cause is the physical properties of the memristor are mismatched with existing memristor-graph calculation data mapping schemes.Based on this discovery,a novel Re RAM-based graph analytics accelerator,named Spara,which focuses on solving the data mapping and corresponding scheduling problems,is further proposed.Specifically,in this accelerator: 1)a graph data mapping strategy for random wordlines and sequential bitlines is proposed to greatly reduce the number of invalid zero elements;2)a tightly-coupled bank parallel architecture,which can maximize the workload density of crossbars dynamically,is further proposed.The experimental results show that,compared with Graph R and Graph SAR,the best memristor graph computing accelerators in the world,Spara can obtain an average performance improvement of 8.21 x and 5.01 x,and an energy efficiency improvement of 8.97 x and 5.68x(on average),while incurring a reasonable(<9.98%)pre-processing overhead.