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

Abstract : 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 of
Document type :
Reports
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101989
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:11:28 AM
Last modification on : Monday, April 29, 2019 - 11:38:04 AM

File

RR2004-16.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101989, version 1

Collections

Citation

Thierry Bidault, Christophe Guillon, Florent Bouchez, Fabrice Rastello. Procedure placement using temporal-ordering information: dealing with code size expansionin. [Research Report] LIP RR-2004-16, Laboratoire de l'informatique du parallélisme. 2004, 3+25p. ⟨hal-02101989⟩

Share

Metrics

Record views

9

Files downloads

15