The Coarse-grained Multi-external-memory I/O Management Strategy For Graph Processing

With the growing of graphs,graph processing systems using external-memory processing have become popular alternative to distributed in-memory Graph processing systems because of their low cost and high scalability,but I/O emerges as performance bottleneck.So when processing large-scale graphs that needs high I/O throughput,using multiple disks is a natural and common solution.However,some problems that existing multi-external-memory I/O management approaches applied to external-memory graph processing bring about,including low sequential bandwidth utilization,limited I/O parallelism and expensive management overhead and so on,make multi-external-memory I/O performance under-utilized and limit the achievement of optimal system performance.To solve the above problems,we have analyzed the conflict between sequential access of external memory and high I/O efficiency that are rules of optimizing I/O performance in external-memory processing,and chosen a compromise scheme including sequential access of external memory as higher-priority optimization rule and support of selective scheduling with graph partition as granularity.Analyzing the characteristics of graph data access under this optimization scheme,we present a coarse-granularity striping method matching sequential and large I/O to realize balanced distribution of graph data among multiple disks and improve I/O throughput.And an I/O management strategy based on multi-disk multiqueue is proposed,which realizes I/O management in application layer,such as address mapping,decomposition,merging and dispatching of I/O requests,and makes I/O threads dedicated to each disk,to further improve I/O throughput and give full play to parallelism of multiple disks.Then we have designed and developed CSMqGraph,a graph processing system based on coarse-grained multi-external-memory I/O management.The performance comparison test of CSMqGraph and GridGraph is carried out with different graph algorithms,different datasets and different amount of disks.The results show that comparing to GridGraph,CSMqGraph's performance is improved in all cases,and the speedup is 1.04×~1.40×,and increases with the increase of the number of disks.Then we carry out the comparison test of I/O throughput and device I/O times,and prove that the I/O management strategy we have proposed can effectively reduce device I/O times and improve I/O throughput,and improve system performance,so the validity is fully validated.