Procedure placement using temporal-ordering information: Dealing with code size expansion

Issue title: Cache exploitation in embedded systems

Article type: Research Article

Authors: Guillon, Christophe | Rastello, Fabrice | Bidault, Thierry | Bouchez, Florent

Affiliations: STMicroelectronics in France | École Normale Supérieure de Lyon in France

Note: [] Corresponding author. E-mail: fabrice.rastello@ens-lyons.fr

Abstract: In a direct-mapped instruction cache, all instructions that have the same memory address modulo the cache size share a common and unique cache slot. Instruction cache conflicts can be partially handled at linked time by procedure placement. Pettis and Hansen give in [1] an algorithm that reorders procedures in memory by aggregating them in a greedy fashion. The Gloy and Smith algorithm [2] greatly decreases the number of conflict-misses but increases the code size by allowing gaps between procedures. The latter contains two main stages: the cache-placement phase assigns modulo addresses to minimizes cache-conflicts; the memory-placement phase assigns final memory addresses under the modulo placement constraints, and minimizes the code size expansion. In this paper: (1) we prove the NP-completeness of the cache-placement problem; (2) we provide an optimal algorithm to the memory-placement problem with complexity O(nmin(n,L)ack(n)) (n is the number of procedures, L the cache size, α is the inverse Ackermann's function that is lower than 4 in practice); (3) we take final program size into consideration during the cache-placement phase. Our modifications to the Gloy and Smith algorithm gives on average a code size expansion of 8% over the original program size, while the initial algorithm gave an expansion of 177%. The cache miss reduction is nearly the same as the Gloy and Smith solution with 35% cache miss reduction.

Keywords: Instruction cache, code placement, code size, cache miss, min-matching, Hamiltonian-path, profiling

Journal: Journal of Embedded Computing, vol. 1, no. 4, pp. 437-459, 2005