Effective padding of multidimensional arrays to avoid cache conflict misses

Changwan Hong 1 Wenlei Bao 1 Albert Cohen 2 Sriram Krishnamoorthy 3 Louis-Noël Pouchet 1 Fabrice Rastello 4 J. Ramanujam 5 Sadayappan Ponnuswany 1
2 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
4 CORSE - Compiler Optimization and Run-time Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Caches are used to significantly improve performance. Even with high degrees of set associativity, the number of accessed data elements mapping to the same set in a cache can easily exceed the degree of associativity. This can cause conflict misses and lower performance, even if the working set is much smaller than cache capacity. Array padding (increasing the size of array dimensions) is a well-known optimization technique that can reduce conflict misses. In this paper, we develop the first algorithms for optimal padding of arrays aimed at a set-associative cache for arbitrary tile sizes. In addition, we develop the first solution to padding for nested tiles and multi-level caches. Experimental results with multiple benchmarks demonstrate a significant performance improvement from padding.
Type de document :
Communication dans un congrès
PLDI 2016: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun 2016, Santa Barbara, United States
Liste complète des métadonnées

https://hal.inria.fr/hal-01335346
Contributeur : Fabrice Rastello <>
Soumis le : mardi 21 juin 2016 - 20:35:48
Dernière modification le : samedi 21 octobre 2017 - 20:10:13

Identifiants

  • HAL Id : hal-01335346, version 1

Collections

Citation

Changwan Hong, Wenlei Bao, Albert Cohen, Sriram Krishnamoorthy, Louis-Noël Pouchet, et al.. Effective padding of multidimensional arrays to avoid cache conflict misses. PLDI 2016: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, Jun 2016, Santa Barbara, United States. 〈hal-01335346〉

Partager

Métriques

Consultations de la notice

285