PrefEdge: SSD prefetcher for large-scale graph traversal

Mining large graphs has now become an important aspect of mul-tiple diverse applications and a number of computer systems have been proposed to provide runtime support. Recent interest in this area has led to the construction of single machine graph computa-tion systems that use solid state drives (SSDs) to store the graph. This approach reduces the cost and simplifies the implementation of graph algorithms, making computations on large graphs avail-able to the average user. However, SSDs are slower than main memory, and making full use of their bandwidth is crucial for ex-ecuting graph algorithms in a reasonable amount of time. In this paper, we present PrefEdge, a prefetcher for graph algorithms that parallelises requests to derive maximum throughput from SSDs. PrefEdge combines a judicious distribution of graph state between main memory and SSDs with an innovative read-ahead algorithm to prefetch needed data in parallel. This is in contrast to existing approaches that depend on multi-threading the graph algorithms to saturate available bandwidth. Our experiments on graph algo-rithms using random access show that PrefEdge not only is capa-ble of maximising the throughput from SSDs but is also able to almost hide the effect of I/O latency. The improvements in run-time for graph algorithms is up to 14 × when compared to a single threaded baseline. When compared to multi-threaded implemen-tations, PrefEdge performs up to 80 % faster without the program complexity and the programmer effort needed for multi-threaded graph algorithms