Skip to Main content Skip to Navigation
Reports

Variables d'induction généralisées pour l'analyse par instances de programmes récursifs

Pierre Amiranoff 1 Albert Cohen 1 Paul Feautrier 1
1 A3 - Advanced analysis to code optimization
UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Résumé : La sophistication croissante des microprocesseurs et des architectures ouvre la voie de nouvelles techniques d'optimisation dont il est souhaitable de décharger le programmeur. La parallélisation automatique consiste en une phase préalable d'analyse des dépendances, suivie de l'extraction du parallélisme puis de la génération du code parallèle. Nous nous attachons à des programmes, éventuellement récursifs, qui manipulent des structures de données combinant arbres et tableaux. Ce rapport a pour objet le calcul statique, c.-à-d. lors de la compilation, des adresses dans les structures de données. Ces adresses sont les informations de base pour l'analyse de dépendances. Nous introduisons le concept de \textitvariable d'induction généralisée, qui étend la notion classique attachée aux nids de boucles. Ce concept formalise le suivi des adresses au travers d'un balisage original de l'exécution. Ainsi, nous dégageons la notion d'instance pour nommer avec exactitude une instruction au cours de l'exécution. L'analyse par instances conjugue la finesse des traces d'exécution et la richesse du formalisme des langages réguliers. Nous présentons ici un modèle de programme qui permet le calcul exact de l'adressage pour chaque instance. Deux technique- s sont exposées, en étroite référence à la théorie des automates finis. La première est développée sous forme matricielle, tandis que la seconde fait appel à la théorie des transducteurs.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00072336
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 8:25:44 PM
Last modification on : Wednesday, September 16, 2020 - 4:57:21 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:04:19 PM

Identifiers

  • HAL Id : inria-00072336, version 1

Collections

Citation

Pierre Amiranoff, Albert Cohen, Paul Feautrier. Variables d'induction généralisées pour l'analyse par instances de programmes récursifs. [Rapport de recherche] RR-4252, INRIA. 2001. ⟨inria-00072336⟩

Share

Metrics

Record views

164

Files downloads

654