On Activity Based Layout For Graph Processing With Memory Access Optimization

Along with the rapid development of graph processing,many factors including data size,graph type,and graph application significantly affect the access characteristics of CPU.Graph processing generally contains multiple iterations,and there are both active data and inactive data in each iteration.The main research direction of current graph processing is to improve the I/O speed by trying to obtain data locality and reduce random access requests.This is mainly for the optimization of active data,but the graph data that is not involved in processing will bring a heavy burden for the storage system,which leads to lots of redundant data switching between layers of storage and drags the speed of graph processing.It is also affected by the high randomness of graph data,which is difficult to be reduced in the graph processing.So it is necessary to simultaneously reducing inactive data.By combining the characteristics of active and inactive data,we proposed a generic graph data layout strategy,VAL,based on vertex activeness.It takes into account the distribution of active data and inactive data,so that they could be organized by different methods.It not only puts active data in cache efficiently,but also schedules inactive data flexibly.First of all,based on the betweeness centricity,the active and inactive vertices are divided.Then the active vertex set is arranged locally,it could aggregate the storage and improve the locality.Then,the inactive vertex set is organized according to the degree centricity and direct adjacency relationships,it could improve the locality of inactive data.Finally,we design a filtering method for inactive data according to the data access characteristics.VAL not only improves data locality but also removes redundancy during graph processing.By combining the proposed layout strategies on SNAP and GridGraph,we have proved that VAL can effectively help the graph processing.The optimization effect is better than the existing Gorder layout.VAL improves the efficiency of SNAP by 9.10%-34.12%,and the efficiency of GridGraph increases by 4.18%-28.57%.