A ReRAM Based Graph Traversal System With Low Communication Cost

Graph traversal algorithms are typical I/O-intensive graph applications,and there is a large amount of random data access and data movement under conventional systems.Besides,in the multi-accelerator graph processing system,the unbalanced data distribution and the unordered,irregular and unpredictable communication messages among computing units all bring huge communication cost to the computing system.Memristor,or ReRAM is an emerging non-volatile memory(Non-Volatile Memory,NVM),which is non-volatile and has high storage density.ReRAM crossbar structure can provide efficient memory access.In addition,PIM(Process-In-Memory)technology puts computing units into storage units to provide large memory capacity and bandwidth,and provides a direction for solving the issues of data movement and bandwidth shortage in graph traversal.However,the issue of random communication among multiple accelerators needs to be further resolved.ReGra is proposed as a ReRAM-based graph traversal processing system.It uses PIM technology to provide large memory capacity and large bandwidth,and it solves the issue of heavy communication cost.First,according to the feature of memory access in graph traversal algorithms and the feature that ReRAM crossbar can read the entire row of data at one operation,a compact continuous data storage form based on the compressed sparse row form is used.Next,a graph partition algorithm called Interval Block Hash Balance is proposed.It divides graph data into multiple processing units with low cost and promotes a reduction of the overall communication time.For a large number of unordered and random messages among multiple processing units(cubes),messages are first aggregated and compressed according to the data distribution interval to reduce the number of messages.Furthermore,messages are transferred in a concentrated time period by an organized way through the Circular Round Communication mechanism.This mechanism effectively reduces the communication and processing overheads caused by random and unordered messages.In addition,ReGra applies several different cache.On the one hand it improves the locality of the data.On the other hand,it also reduces the frequency of access to the ReRAM crossbar and improves the processing efficiency.A ReGra system simulation environment is built using zSim and NVMain tools.Breadth First Search and Single Source Shortest Paths are tested using real graph data sets.The experiment results show that ReGra can significantly improve the time of graph traversal processing,and has a significant reduction in communication cost.In addition,the energy consumption of the entire system is reduced significantly.