Using static program analysis to compile fast cache simulators

Thumbnail Image

Files

isbn9512270137.pdf (571.01 KB)

URL

Journal Title

Journal ISSN

Volume Title

Doctoral thesis (monograph)
Checking the digitized thesis and permission for publishing
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2004-03-26

Department

Department of Computer Science and Engineering
Tietotekniikan osasto

Major/Subject

Mcode

Degree programme

Language

en

Pages

118

Series

Helsinki University of Technology, Department of Computer Science and Engineering, Laboratory of Information Processing Science, Teknillinen korkeakoulu, tietotekniikan osasto, tietojenkäsittelyopin laboratorio. A, 41

Abstract

This thesis presents a generic approach towards compiling fast execution-driven simulators, and applies this to cache simulation of programs. The resulting cache simulation method reduces the time needed for cache performance evaluations without losing the accuracy of the results. Fast cache simulators are needed in the performance analysis of software systems. To properly understand the cache behavior caused by a program, simulations must be performed with a sufficient number of inputs. Traditional simulation of memory operations of a program can be orders of magnitude slower than the execution of the program. This leads to simulation times that are often infeasible in software development. The approach of this thesis is based on using static cache analysis to guide partial evaluation and slicing of simulators. Because of redundancy in memory access patterns of typical programs, an execution-driven cache simulator program can be partially evaluated during its compilation. Program slicing can be used to remove the computations that have no effect on the simulation result. The static cache analysis presented in this thesis is generic. The analysis is designed especially for programs that use dynamic addressing. The thesis assumes an address analysis that gives the cache analysis static information about cache aliases and cache conflicts between accessed memory lines. To determine the memory references that always cause cache hits or cache misses, the thesis describes both must and may analyses of cache states. The cache state analysis is built by using abstract interpretation. Based on the use of abstract interpretation, the soundness of the analysis is proved. The potential performance of the method was experimentally evaluated. The thesis describes both a tool set implementing the cache analysis method and experiments done with the tool set. The experiments indicate that a simple implementation is capable of significantly speeding up the simulations.

Description

Keywords

static analysis, program analysis, performance analysis, cache simulation, program slicing

Other note

Citation

Permanent link to this item

https://urn.fi/urn:nbn:fi:tkk-003431

Collections

[diss] Perustieteiden korkeakoulu / SCI