Procedure placement using temporal-ordering information: dealing with code size expansionin

Instruction cache performance is one of the bottle-necks of processor performance. In this paper, we study the effects of procedure placement in memory on a direct-mapped instruction cache. These caches differ from associative memory caches by the fact that each address in the memory is assigned to one and only one address in the cache. This means that two procedures with addresses that share the same place in the cache, and that are called alternatively will create a conflict-miss: one will overwrite the other in the cache. The goal of procedure placement is to minimize these cache-misses. Pettis and Hansen give in [PH] a greedy algorithm that doesn't increase the code size. The Gloy and Smith algorithm [TRG] greatly decreases the number of cache-misses but authorizes gaps between procedures, hence it increases the code size. The latter comprises of two main stages: in the ``cache-placement'' phase, the procedures are given the location they will occupy in the instruction cache; in the ``memory-placement'' phase, procedures are placed in memory in such a way that code expansion is minimized, with the constraints of their cache placement. In this article, we prove the NP-completeness of the first stage, and the polynomiality of the second stage of [TRG]. Indeed, we show that our algorithm provides the optimal solution in a time complexity ofCet article traite du problème de placement de procédures en mémoire pour optimiser l’utilisation d’un cache d’instructions “direct-mapped”. Ce type de mémoire cache se distingue des mémoires dites “associatives” par le fait qu’` a chaque adresse de la mémoire est associée une unique adresse dans le cache. Ainsi, deux procédures dont les adresses mémoire partagent la même adresse dans le cache et appelées consécutivement créent un “conflit” ou “défaut de cache” : le code de la seconde va écraser le celui de la première. Le but du placement de procédures est de minimiser le nombre de défauts de cache. Pettis et Hansen ont donné dans [ 7] un algorithme glouton qui n’augmente pas la taille du code ; l’algorithme de Gloy et Smith [3] diminue de beaucoup le nombre de défauts de cache par rapport `a[ 7] mais autorise l’existence de mémoire inutilisée entre les procédures, et donc augmente la taille du code. Ce dernier algorithme est constitué de deux parties principales : la première est une phase de placement dans le cache : chaque procédure se voit attribuer la place qu’elle occupera quand elle sera chargée dans le cache d’instructions ; la seconde partie est une phase de placement en mémoire : les procédures sont placées en mémoire en respectant les contraintes liées au placement dans le cache et de manière `a minimiser l’expansion de code. Dans cet article, nous prouvons la NP-complétude de la première partie et la polynomialité de la seconde. En effet, nous exhibons un algorithme qui renvoie la solution optimale au problème de minimisation de l’expansion de code. Sa complexité en temps est en O(nLlog∗(L + n)) o` u n est le nombre de procédures, et L la taille du cache. L’algorithme est donc presque linéaire pour une taille de cache fixée. Nous donnons aussi un outil qui fournit rapidement une approximation de l’expansion de code qui résulte d’un placement dans le cache donné. Ceci permet de prendre en compte la taille finale du programme dans la phase de placement dans le cache. Les modifications apportées `a l’algorithme de Gloy et Smith font que celui-ci augmente la taille du code d’environ 8% en moyenne, contre une expansion de code originale d’environ 177%. La réduction du nombre de défauts de cache est quasiment la même que dans l’algorithme original, environ 35% de conflits en moins