I/O Method Based On Active Vertex For Semi-external Memory Graph Computation System

The existing design of the external storage system is focused on the general approach to the processing of various types of applications on the method,through the complete traversal of the graph data to complete the calculation of the iterative process.In fact the application often does not need to travel the complete graph data,but according to their own needs to access some of the "active vertex".Based on this feature,access to external storage only access to the "active vertex" related data,we can significantly reduce the actual calculation of the I/O process,and thus significantly improve performance.In order to get the offset of the vertex in the external storage in just run-time,we presents a method of I/O access based on active vertices in the external storage graph processing system.The data is reorganized by vertex so that the same vertex-related edges are stored together for easy reading and indexing in vertices so that they can be quickly positioned when the specified vertices are taken.We have improved the computational model so that the system can operate efficiently without constructing all subgraphs.The method reduces the amount of data that needs to be accessed by I/O,but a new problem is that the original sequential access becomes random access.So how to weigh the large amount of data with sequential access with a small amount of data with random access to I/O performance is the key to achieving performance improvement.Based on the above problems,we proposes an I/O access selection strategy based on benefit evaluation.Execute application updates by pre-analyzing and calculating the overhead of I/O access for different policies,choosing less costly.By combining these two methods,the application can always perform an iterative update process in an optimal way,resulting in improved efficiency and performance.In the different types of applications and data testing,have shown a different range of performance optimization,low-performance applications in the acceleration ratio can reach 1.2 to 1.6,and high-performance applications in the acceleration ratio can reach more than 20.Finally,according to the characteristics of the application,the reasons for the optimization and the difference in amplitude are summarized and analyzed.