Analysis of temporal-based program behavior for improved instruction cache performance

• Published in: IEEE transactions on computers 1999-02, Vol.48 (2), p.168-175
• Main Authors: Kalamatianos, J., Khalafi, A., Kaeli, D.R., Meleis, W.
• Format: Article
• Language: English
• Subjects: Acceleration; Algorithms; Benchmarks; Coloring; Construction; Frequency; Graphs; Mathematical models; Merging; Microprocessors; Operating systems; Performance analysis; Streams; Temporal logic
• ISSN: 0018-9340; 1557-9956
• DOI: 10.1109/12.752658

In this paper, we examine temporal-based program interaction in order to improve layout by reducing the probability that program units will conflict in an instruction cache. In that context, we present two profile-guided procedure reordering algorithms. Both techniques use cache line coloring to arrive at a final program layout and target the elimination of first generation cache conflicts (i.e., conflicts between caller/callee pairs). The first algorithm builds a call graph that records local temporal interaction between procedures. We will describe how the call graph is used to guide the placement step and present methods that accelerate cache line coloring by exploring aggressive graph pruning techniques. In the second approach, we capture global temporal program interaction by constructing a Conflict Miss Graph (CMG). The CMG estimates the worst-case number of misses two competing procedures can inflict upon one another and reducing higher generation cache conflicts. We use a pruned CMG graph to guide cache line coloring. Using several C and C++ benchmarks, we show the benefits of letting both types of graphs guide procedure reordering to improve instruction cache hit rates. To contrast the differences between these two forms of temporal interaction, we also develop new characterization streams based on the Inter-Reference Gap (IRG) model.