A Decoupled Local Memory Allocator

Boubacar Diouf 1 Can Hantaş Albert Cohen 1 Özcan Özturk Jens Palsberg
1 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, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : Compilers use software-controlled local memories to provide fast, predictable, and power efficient access to critical data. We show that the local-memory allocation for straight-line, or linearized programs is equivalent to a weighted interval-graph coloring problem. This problem is new when allowing a color interval to ''wrap around,'' and we call it the \submarine{} problem. This graph-theoretical decision problem differs slightly from the classical \ship{} problem, and exhibits very interesting and unusual complexity properties. We demonstrate that the \submarine{} problem is NP-complete, while it is solvable in linear time for not-so-proper interval graphs, an extension of the the class of proper interval graphs. We propose a clustering heuristic to approximate any interval graph into a not-so-proper interval graph, decoupling spill code generation from \spm{} assignment. We apply this heuristic to a large number of randomly generated interval graphs reproducing the statistical features of standard \spm{} allocation benchmarks, comparing with state-of-the-art heuristics.
Type de document :
Article dans une revue
ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2013, 9 (4), <10.1145/2400682.2400693>
Liste complète des métadonnées

https://hal.inria.fr/hal-00786676
Contributeur : Albert Cohen <>
Soumis le : dimanche 10 février 2013 - 01:20:20
Dernière modification le : jeudi 29 septembre 2016 - 01:22:06

Identifiants

Collections

Citation

Boubacar Diouf, Can Hantaş, Albert Cohen, Özcan Özturk, Jens Palsberg. A Decoupled Local Memory Allocator. ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2013, 9 (4), <10.1145/2400682.2400693>. <hal-00786676>

Partager

Métriques

Consultations de la notice

216