Competition-Based Adaptive Caching for Out-of-core Graph Processing

Abstract

A graph engine should possess adaptability to ensure efficient processing despite a variety of graph data and algorithms. In terms of out-of-core graph engines, which exploit a hierarchical memory structure, an adaptive caching scheme is necessary to sustain effectiveness. A caching policy selectively stores data likely to be used in the upper-layer memory based on its own expectation about the future workload. However, the graph workload contains a complexity of memory access according to graph data, algorithm, and configurations. This makes it difficult for a static caching policy to respond to the changes in workload. In this paper, we propose a graph-adaptive caching scheme which ensures consistent effectiveness under the changing workloads. Our caching scheme employs an adaptive policy that responds to changes in real-time workloads. To detect the changes, we adopt the competition procedures between two contrasting properties—locality and regularity—that appear in graph workloads. In addition, we combine two window adjustment techniques to alleviate the overhead from competition procedures. The proposed caching scheme is applicable to different types of graph engines, achieving better efficiency in memory usage. Our experimental results prove that our scheme improves the performance of graph processing by up to 65% compared to existing schemes.

그래프 엔진은 다양한 그래프 알고리즘과 데이터 하에서 효율적인 처리 능력을 보장하는 적응력을 갖춰야 한다. 외장형 그래프 엔진은 특히 위계적 메모리 구조를 활용하므로, 적응력 있는 캐시의 사용이 메모리 사용의 효용성을 유지하는 데에 결정적이다. 캐시 정책은 미래의 메모리 접근 워크로드에 대한 예측을 바탕으로, 사용될 것 같은 데이터를 상위 계층의 메모리에 보관한다. 하지만, 그래프 워크로드는 그래프 데이터, 알고리즘, 그리고 다양한 환경변수에 따라 메모리 접근 패턴이 변화하는 복잡성을 갖고있다. 따라서, 고정적 캐시 정책을 사용하는 것으로는 워크로드의 변화에 적절하게 대응하기 힘들다. 이 논문에서 우리는 그래프 적응력 있는 캐시 스킴을 제안하여, 변화하는 워크로드 하에서 일관성 있는 효용성을 제공하고자 한다. 우리의 캐시 스킴은 실시간 워크로드의 변화에 적응할 수 있는 캐시 정책을 채택한다. 그 변화를 감지하기 위해, 우리는 그래프 워크로드에 나타나는 대표적인 두 개의 상반된 속성—지역성 및 규칙성—사이의 경쟁 알고리즘을 도입했다. 뿐만 아니라, 경쟁 과정을 운영하는 오버헤드를 줄이기 위해 접근 범위를 조절하는 기법들을 결합한다. 우리가 제안하는 캐시 스킴은 다른 종류의 그래프 엔진에 접목되어,메모리 사용의 효율을 높이는 데 기여한다. 실험 결과에서 이 스킴은 기존의 스킴과 비교했을 때 그래프 처리의 성능을 최대 65%까지 향상시키는 것으로 드러났다.