An empirical study on how program layout affects cache miss rates

ABSTRACT

Cache miss rates are quoted for a specific program, cache configuration, and input set; the effect of program layout on the miss rate has largely been ignored. This paper examines the miss variation, that is, the variation in the miss rate for instruction and data caches resulting from randomly generated layouts; the layouts were generated by changing the order of the modules on the command line when linking. This analysis is performed for several cache sizes, lines sizes, set-associativities, input sets, compiler versions, and optimization levels for five programs in the SPEC92 benchmark suite. Miss rates were observed that varied from 60% to 180% of the mean miss rate. We did not observe any consistently good layouts across different parameters; in contrast, several layouts were consistently bad. Overall, cache line size and input set has little effect on the miss variation, while increasing the cache size (i.e. decreasing the miss rate), decreasing the set-associativity, or increasing the optimization level increases the miss variation. For a direct-mapped cache, the results in this paper call into question the validity of using a single layout (i) to determine the miss rate of a given program, (ii) to determine how a given compiler optimization affects the miss rate, and (iii) to make architecture design decisions based on the miss rate.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Design, Experimentation, Measurement, Performance, Standardization, Theory