Back to search

University of British Columbia

Data-driven spatial locality

Abstract

dc:description

Over the past decades, core speeds have been improving at a much higher rate than memory bandwidth. This has caused the performance bottlenecks in modern software to shift from computation to data transfers. Hardware caches were designed to mitigate this problem, based on the principles of temporal and spatial locality. However, with the increasingly irregular access patterns in software, locality is difficult to preserve. Researchers and practitioners devote a lot of time and effort to improving memory performance from the software side. This is done either by restructuring the code to make access patterns more regular, or by changing the layout of data in memory to better accommodate caching policies. Experts often use correlations between the access pattern of an algorithm and properties of the objects it operates on to devise new ways to lay data out in memory. Prior work has shown the memory layout design process to be largely manual and difficult enough to result in high level publications. Our contribution is a set of tools, techniques and algorithms for automatic extraction of correlations between data and access patterns of programs. In order to collect a sufficient level of details about memory accesses, we present a compiler-based access instrumentation framework called DINAMITE. Further, we introduce access graphs, a novel way of representing spatial locality properties of programs which are generated from memory access traces. We use access graphs as a basis for Hierarchical Memory Layouts -- a novel algorithm for estimating performance improvements to be gained from better data layouts. Finally, we present our Data-Driven Spatial Locality techniques which use the information available from previous steps to automatically extract the correlations between data and access patterns commonly used by experts to inform better layout design.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Miucin, Svetozar

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/68188

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Miucin, Svetozar. Data-driven spatial locality. doctoral thesis, University of British Columbia, 2018. http://hdl.handle.net/2429/68188