Characterizing and Inducing Memory Locality in Object-Oriented Programs via Static Analysis and Profiling

Open Access
Author:
Kinsey, John James
Area of Honors:
Computer Science
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
  • John Morgan Sampson, Thesis Supervisor
  • Jesse Louis Barlow, Honors Advisor
Keywords:
  • locality
  • near-data processing
  • llvm
  • static analysis
  • profiling
Abstract:
In recent years of computer processor development, outsized growth in compute power compared to the speed of data transfer have led some researchers in the field to consider alternative architectures that might afford performance improvements by avoiding the data movement problem. One such subfield of study is near-data processing, a class of architectures where compute and memory resources are far more co-located than in a typical architecture dominated by a large, single shared memory. Any distributed architecture of this type relies for its efficiency on memory locality, the potential tendency of data being used in a given computational context to be located in a single place in a memory. However, it is not obvious what kinds of programs might demonstrate these localities. This analysis attempts to develop a characterization of locality of types, specifically in object-oriented programming types in C++. Motivated by object-oriented programming principles like data hiding, we use LLVM to statically analyze and profile several Parsec benchmarks, constructing a graph network of types that experience simultaneous use in functions and deducing possible groupings of these types into localities via a K-means-based data processing algorithm. While our approach is hindered by the nature of the programs analyzed, some positive results suggest a motivation for future research along the lines of this approach.