A modular memory optimization for synchronous data-flow languages: application to arrays in a lustre compiler

Léonard Gérard 1 Adrien Guatto 1 Cédric Pasteur 1 Marc Pouzet 1
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 : The generation of efficient sequential code for synchronous data-flow languages raises two intertwined issues: control and memory optimization. While the former has been extensively studied, for instance in the compilation of Lustre and Signal, the latter has only been addressed in a restricted manner. Yet, memory optimization becomes a pressing issue when arrays are added to such languages. This article presents a two-level solution to the memory optimization problem. It combines a compile-time optimization algorithm, reminiscent of register allocation, paired with language annotations on the source given by the designer. Annotations express in-place modifications and control where allocation is performed. Moreover, they allow external functions performing in-place modifications to be safely imported. Soundness of annotations is guaranteed by a semilinear type system and additional scheduling constraints. A key feature is that annotations for well-typed programs do not change the semantics of the language: removing them may lead to less efficient code but will not alter the semantics. The method has been implemented in a new compiler for a LUSTRE-like synchronous language extended with hierarchical automata and arrays. Experiments show that the proposed approach removes most of the unnecessary array copies, resulting in faster code that uses less memory.
Type de document :
Communication dans un congrès
Proceedings of the 13th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, Tools and Theory for Embedded Systems, Jun 2012, Beijing, China. ACM, pp.51--60, 2012, 〈10.1145/2248418.2248426〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00728527
Contributeur : Cédric Pasteur <>
Soumis le : jeudi 6 septembre 2012 - 12:04:53
Dernière modification le : jeudi 30 novembre 2017 - 01:15:29

Identifiants

Collections

Citation

Léonard Gérard, Adrien Guatto, Cédric Pasteur, Marc Pouzet. A modular memory optimization for synchronous data-flow languages: application to arrays in a lustre compiler. Proceedings of the 13th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, Tools and Theory for Embedded Systems, Jun 2012, Beijing, China. ACM, pp.51--60, 2012, 〈10.1145/2248418.2248426〉. 〈hal-00728527〉

Partager

Métriques

Consultations de la notice

236