Detailed Information

Competition-based adaptive caching for out-of-core graph processing

Cited 1 time in Web of Science Cited 1 time in Scopus

Myung, Kihyeon; Kim, Hwajung; Lee, Yunjae; Yeom, Heon Young

Issue Date
Institute of Electrical and Electronics Engineers Inc.
Proceedings - 21st IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing, CCGrid 2021, pp.31-40
© 2021 IEEE.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 of memory usage. 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.
Files in This Item:
There are no files associated with this item.
Appears in Collections:


Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.