Home | deutsch  | Legals | KIT

Call Graph Based Instruction Prefetching on Precompiled Executables

Call Graph Based Instruction Prefetching on Precompiled Executables
Type:Bachelor Thesis

Prof. Dr. Frank Bellosa
Mathias Gottschlag

Graduand:Joshua Bachmeier


The performance of scale-out and online transaction processing workloads, often found in modern datacenters, suffer from high instruction cache miss rates. These are caused by large instruction working sets and irregular, non-sequential execution flow patterns that are typical for these applications.

Past research has suggested many approaches to reduce instruction cache miss rates. However, most existing solutions are either implemented in hardware or require special compiler or operating system support.

In this work, we present Call Graph Prefetching on Precompiled Exe- cutables (CGPoPE) as a system to reduce instruction cache misses caused by function calls. CGPoPE builds the call graph of an application by intercepting and recording function calls. It then extracts the most frequent callee of each function and injects prefetch instructions into the ordinarily compiled binary of the application. The mechanism we use to inject prefetch instructions can be applied to insert arbitrary instructions into the machine code of an application. This design enables the implementation of live patching via the operating system, which is able to perform the binary augmentation automatically when restarting an application.

We evaluate CGPoPE using a prototypical implementation for ELF files and the x86 architecture. Although we find that CGPoPE does not improve the performance of our benchmarks, we show that all injected prefetches are effective. Our analysis also reveals that the injection of instructions into unmodified binaries does not cause significant additional run time overhead, and that the effectivity of CGPoPE can likely be increased by more aggressive prefetching.


  author = {Joshua Bachmeier},
  title = {Call Graph Based Instruction Prefetching on Precompiled Executables},
  type = {Bachelor Thesis},
  year = 2017,
  month = sept # "04",
  school = {Operating Systems Group, Karlsruhe Institute of Technology (KIT), Germany}