Computer Science – Data Structures and Algorithms
Scientific paper
2012-03-26
Computer Science
Data Structures and Algorithms
Work in progress
Scientific paper
Mining large graphs for information is becoming an increasingly important workload due to the plethora of graph structured data becoming available. An aspect of graph algorithms that has hitherto not received much interest is the effect of memory hierarchy on accesses. A typical system today has multiple levels in the memory hierarchy with differing units of locality; ranging across cache lines, TLB entries and DRAM pages. We postulate that it is possible to allocate graph structured data in main memory in a way as to improve the spatial locality of the data. Previous approaches to improving cache locality have focused only on a single unit of locality, either the cache line or virtual memory page. On the other hand cache oblivious algorithms can optimise layout for all levels of the memory hierarchy but unfortunately need to be specially designed for individual data structures. In this paper we explore hierarchical blocking as a technique for closing this gap. We require as input a specification of the units of locality in the memory hierarchy and lay out the input graph accordingly by copying its nodes using a hierarchy of breadth first searches. We start with a basic algorithm that is limited to trees and then extend it to arbitrary graphs. Our most efficient version requires only a constant amount of additional space. We have implemented versions of the algorithm in various environments: for C programs interfaced with macros, as an extension to the Boost object oriented graph library and finally as a modification to the traversal phase of the semispace garbage collector in the Jikes Java virtual machine. Our results show significant improvements in the access time to graphs of various structure.
No associations
LandOfFree
Memory Hierarchy Sensitive Graph Layout does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Memory Hierarchy Sensitive Graph Layout, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory Hierarchy Sensitive Graph Layout will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-642111