Ingénierie de la spécialisation de programmes 1 : principes et applications (Coll. Logique et programmation)

Renaud Marlet

Description

La spécialisation de programmes, aussi appelée évaluation partielle, est une technique générale destinée à rendre les programmes plus performants (plus rapides et possiblement plus petits) quand certaines entrées peuvent être connues à l’avance. Du point de vue du génie logiciel, la spécialisation facilite aussi grandement l’écriture des programmes et leur maintenance.
Cet ouvrage, conçu à la fois pour les chercheurs et les ingénieurs logiciels, tant architectes que développeurs, en fait une large présentation pratique.
Ce volume pose la problématique de l’adaptation par la spécialisation. Il présente les grands principes de la spécialisation de programmes ainsi que les techniques de spécialisation, en se concentrant plus particulièrement sur la spécialisation dite hors ligne. À titre illustratif, il décrit aussi l’architecture de Tempo, spécialiseur hors ligne pour le langage C, capable d’effectuer des spécialisations en cours d’exécution.
Il est illustré de résultats chiffrés pour des applications concrètes dans différents domaines.
Avant-propos. Chapitre 1. Introduction : spécialiser pour adapter. Chapitre 2. Préliminaires sur les langages et les programmes. Chapitre 3. Les grands principes de la spécialisation de programmes. Chapitre 4. Techniques de spécialisation. Chapitre 5. Spécialisation hors ligne. Chapitre 6. Un spécialiseur pour C : Tempo. Chapitre 7. Applications de la spécialisation. Bibliographie. Table des figures. Index.

Sujets

• Informatique

Informations

• Publié par: Hermès - Editions Lavoisier
• Date de parution: 21 septembre 2011
• Nombre de lectures: 13
• EAN13: 9782746242098
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

2101-Marlet:Layout 1 28/06/11 15:57 Page 1
collection Logique et programmation dirigée par Marc Pouzet collection Logique et programmation dirigée par Marc Pouzet
La spécialisation de programmes, aussi appelée évaluation partielle,
est une technique générale destinée à rendre les programmes plus
performants (plus rapides et possiblement plus petits) quand certaines
entrées peuvent être connues à l’avance. Du point de vue du génie
logiciel, la spécialisation facilite aussi grandement l’écriture des
programmes et leur maintenance. Cet ouvrage, conçu à la fois pour les
chercheurs et les ingénieurs logiciels, tant architectes que
développeurs, en fait une large présentation pratique. Ingénierie
Ce volume pose la problématique de l’adaptation par la spécialisation.
Il présente les grands principes de la spécialisation de programmes
ainsi que les techniques de spécialisation, en se concentrant plus
particulièrement sur la spécialisation dite hors ligne. A titre illustratif, de la spécialisation
il décrit aussi l’architecture de Tempo, spécialiseur hors ligne pour le
langage C, capable d’effectuer des spécialisations en cours d’exécution.
Il est illustré de résultats chiffrés pour des applications concrètes dans de programmes 1différents domaines.
L’auteur
principes et applicationsIngénieur de l’Ecole polytechnique et docteur en informatique,
Renaud Marlet a occupé des postes dans la recherche publique
(INRIA) et l’industrie logicielle (PME, startup). Multidisciplinaire, il est
actuellement chercheur senior à l’Ecole des Ponts ParisTech, où il
dirige le pôle de recherche IMAGINE.
Renaud Marlet
978-2-7462-2101-7
Z(7ic7e6-CCBABH(
www.hermes-science.com
Renaud Marlet
Ingénierie de la spécialisation de programmes 116






Ingénierie de la spécialisation de programmes 1



































© LAVOISIER, 2011
LAVOISIER
11, rue Lavoisier
75008 Paris

www.hermes-science.com
www.lavoisier.fr

ISBN 978-2-7462-2101-7



Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une part,
que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non
destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations
dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
d’identification et sont des marques de leurs détenteurs respectifs.


Printed and bound in England by CPI Group (UK) Ltd, Croydon, CR0 4YY, September 2011.








Ingénierie


de la spécialisation

de programmes 1

principes et applications









Renaud Marlet







Collection logique et programmation
dirigée par Marc Pouzet




Ingénierie de la spécialisation de programmes 2 : techniques avancées –
Renaud Marlet, 2011

Tabledesmatières
Avant-propos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Entrerechercheetingénierie . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Publicpourcetouvrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Organisationdel’ouvrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
RendreàCésar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Chapitre1.Introduction:spécialiserpouradapter . . . . . . . . . . . . . . 17
1.1. Paramètresdeproductionetéquationéconomiquedulogiciel . . . . . 18
1.2. Variabilitéetlignesdeproduits . . . . . . . . . . . . . . . . . . . . . . 24
1.3. Réutilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4. Génielogicieldel’adaptation . . . . . . . . . . . . . . . . . . . . . . . 30
Chapitre2.Préliminairessurleslangagesetlesprogrammes . . . . . . . . 33
2.1. Langagesdeprogrammation . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2. Sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3. Équivalencedeprogrammes . . . . . . . . . . . . . . . . . . . . . . . . 57
2.4. Exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.5. Performancedesprogrammes . . . . . . . . . . . . . . . . . . . . . . . 74
2.6. Analysesdeprogrammes . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.7. Transformationsdeprogrammes . . . . . . . . . . . . . . . . . . . . . 82
Chapitre3.Lesgrandsprincipesdelaspécialisationdeprogrammes . . . 87
3.1. Programmespécialisé. . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.2. Spécialiserpouraméliorerlaperformance . . . . . . . . . . . . . . . . 103
3.3. Spécialisationautomatique . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.4. Lesgrandesapplicationsdelaspécialisation . . . . . . . . . . . . . . . 113
3.5. Momentsdespécialisation . . . . . . . . . . . . . . . . . . . . . . . . . 119
56 Ingénieriede laspécialisation -I
3.6. Rentabilitédelaspécialisation . . . . . . . . . . . . . . . . . . . . . . . 124
Chapitre4.Techniquesdespécialisation . . . . . . . . . . . . . . . . . . . . . 131
4.1. Lestransformationsdeprogrammesdelaspécialisation . . . . . . . . 132
4.2. Terminaisondelaspécialisation . . . . . . . . . . . . . . . . . . . . . . 146
4.3. Correctiondelaspécialisation . . . . . . . . . . . . . . . . . . . . . . . 148
4.4. Autresformesdespécialisation . . . . . . . . . . . . . . . . . . . . . . 154
Chapitre5.Spécialisationhorsligne . . . . . . . . . . . . . . . . . . . . . . . 161
5.1. Lesgrandsprincipesdelaspécialisationhorsligne . . . . . . . . . . . 162
5.2. Intérêtscomparésdelaspécialisationhorsligne . . . . . . . . . . . . . 183
5.3. Principauxingrédientsdel’analysedetempsdeliaison. . . . . . . . . 191
5.4. Casdesentréesstatiquesdevenantdynamiques . . . . . . . . . . . . . 200
Chapitre6.UnspécialiseurpourC:Tempo . . . . . . . . . . . . . . . . . . 209
6.1. Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
6.2. Technologiesenrupture . . . . . . . . . . . . . . . . . . . . . . . . . . 213
6.3. Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
6.4. Économiedel’ingénierie . . . . . . . . . . . . . . . . . . . . . . . . . . 225
6.5. AutourdeTempo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
6.6. AutresspécialiseurspourlelangageC . . . . . . . . . . . . . . . . . . 235
Chapitre7.Applicationsdelaspécialisation . . . . . . . . . . . . . . . . . . 239
7.1. Applicationsdanslessystèmesd’exploitationetlesréseaux . . . . . . 241
7.2. Applicationsaucalculnumérique . . . . . . . . . . . . . . . . . . . . . 253
7.3. Applicationsàlacompilationàpartird’interprète . . . . . . . . . . . . 254
7.4. Applicationsàl’optimisationd’architectureslogicielles . . . . . . . . 259
7.5. Laspécialisationcommeoutildegénielogiciel . . . . . . . . . . . . . 276
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Tabledesfigures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313Avant-propos
Iln’yapasd’effortsinutiles,Sisyphesefaisaitdesmuscles.
—RogerCaillois
Entrerechercheetingénierie
J’ai eu la chance dans ma vie d’informaticiende ne pas devoir irrémédiablement
1choisirentrerechercheetingénierie .Etc’estaucontactdecesdeuxmondes,chacun
campé sur ses convictionsmais moins hermétiquesl’un à l’autrequ’onne le dit, que
je me suis souvent posé cette double question : comment mieux écrire de meilleurs
programmes?
Cet ouvrage présente un élément de réponse, à la fois technique et
méthodologique : la spécialisation de programmes (aussi appelée évaluation partielle). En tant
que technique, la spécialisation est un moyen de rendre les programmes plus
performants(plusrapidesetparfoispluspetits).Etmiseauserviced’uneméthodologie,sous
l’angledugénielogiciel,ellefacilited’écrituredesprogrammesetleurmaintenance.
1. Aprèsundiplômed’ingénieur (Écolepolytechnique, Palaiseau), j’aiétédoctorant àl’INRIA(Sophia
Antipolis), assistant de recherche au LFCS (Université d’Édimbourg), ingénieur puis directeur du pôle
informatique d’une agence de Simulog (Toulouse), ingénieur puis chargé de recherche INRIA à l’IRISA
(Rennes), directeur technique adjoint de Trusted Logic (Versailles), chargé de recherche INRIA au LaBRI
(Bordeaux), etactuellement chercheur sénior àl’École desPontsParisTech (Marne-la-Vallée).
-INRIA:Institut National deRecherche enInformatique et enAutomatique.
-IRISA:Institut deRecherche en Informatique et SystèmesAléatoires.
-LaBRI :Laboratoire Bordelais de Recherche enInformatique.
-LFCS:Laboratory forFoundations ofComputer Science.
-Simulog :société spécialisée dans lesproduits et services decalcul scientifique et génie logiciel.
- Trusted Logic : société spécialisée dans les produits et services de très haute sécurité pour les petits
systèmesembarqués (cartes àpuce, téléphones mobiles, terminaux depaiement, domotique, etc.).
78 Ingénieriede laspécialisation -I
Notations.
Lesrenvoisauxsectionsetsous-sectionsdansletextesontnotésprécédés d’un signe « § ». Par exemple, « cf. §3.4.5 » renvoie à la section 4.5 du
chapitre 3. Les renvois d’un volume de cet ouvrage à un autre sont précédés du
numéro de l’autre volume et d’un tiret. Par exemple, à l’intérieur du volume
I,
«cf.II-§3.4.5»renvoieàlasection4.5duchapitre3duvolumeII.Maisàl’intérieurduvolumeII,cemêmerenvoiapparaîtrasimplementcomme«cf.§3.4.5».
2L’idée de la spécialisation de programmesre