Optimisation of Memory Reference Patterns in Dynamic Binary Translation Systems

Daniel Owen

Abstract

Currently dynamic memory disambiguation is utilised to improve instruction-level parallelism with the aim of re-ordering instructions to better utilise hardware. The aim of this research is to focus on exploiting dynamic memory disambiguation in the area of runtime optimisations.

To guide the development of the optimisations a knowledge of dependency behaviour is required. Hence the first part of the thesis explores the premise that extrapolating from a snapshot of current behaviour provides an accurate prediction of future dependencies. A snapshot technique was developed by analysing the general dependency behaviour of a test suite of programs. An implementation of the technique demonstrated that an accurate representation of future dependency behaviour could be obtained by observing only a small number of load and store executions.

The snapshot technique was extended to identify loads that repeatedly retrieve the same value. This additional information provided another avenue for optimisations which was exploited.

The second part of the thesis explores the utilisation of data provided by the snapshot technique through the use of an example dynamic optimisation. This optimisation was based on the classical technique of loop invariant code motion. The steps necessary to implement such an optimisation at runtime are described.

To evaluate the benefits of the example optimisation a practical implementation was undertaken. The improvement in performance varied widely depending on the particular program undergoing optimisation, with the greatest reduction in the dynamic instruction count being over 12%.

An exploratory review of the use of code duplication was undertaken to access the potential for further improvements. This demonstrated that pursuing this approach would be worthwhile.