Développement d'un bibliothèque de calcul SIMD - Application au traitement d'images

U.F.R. SCIENTIFIQUE

ET TECHNIQUE

ECOLE DOCTORALE

SCIENCES POUR

L’I NGÉNIEUR

UNIVERSITÉ BLAISE PASCAL

CLERMONT-FERRAND

MEMOIREprésenté par

Joël FALCOU

en vue de l’obtention du

D.E.A.«COMPOSANTS ETSYSTÈMES POUR LETRAITEMENT DE

L’I NFORMATION »

Option “Vision pour la Robotique”

LABORATOIRE DESSCIENCES ETMATÉRIAUX POUR

L’ELECTRONIQUE, ET D’A UTOMATIQUE

(U.M.R. 6602DU C.N.R.S.)

Développement d’une bibliothèque de calcul SIMD.Application au traitement d’image.

le 9 septembre 2003

Remerciements

Je tiens tout d’abord à remercier Jocelyn SEROT pour son soutien et l’interêt porté auprojet.

Je remercie aussi Christophe DUHAMEL pour son écoute et ses conseils avisés.

je tiens aussi à remercier Eric ROYER, Maxime FIANDINO et Lucie MASSON pourleurs aides diverses et variées.

2

Résumé

Les divers algorithmes mis en oeuvre dans letraitement d’image deviennent de plusen plus coûteux en terme de temps de calcul au fur et à mesure que leur complexités’accroît. Pour pallier ce problème, diverses solutions basées sur l’utilisation de machineparallèle ont vu le jour. Un cas particulier de ces machines est l’ unité de calculSIMDAltiVec , intégré au processeur PowerPC G4, qui permet d’obtenir surun de ces seul pro-cesseur des performances équivalentes à celle de machines multiprocesseurs. Pourtant,l’utilisation de cette unité de calcul reste marginale du fait de sa complexité.

La bibliothèque E.V.E utilise une approche basée sur laprogrammation orienté ob-jet pour fournir aux développeurs d’application de traitementd’image un moyen simpled’utiliser le potentiel de l’unité de calcul SIMD Altivec. E.V.E utilise diverses techniquesde meta-programmation template pour fournir une interface de programmation intui-tive. Les premiers résultats ont montré que E.V.E permet d’exprimer un grand nombred’algorithmes detraitement d’images en fournissant des facteurs d’accélération com-pris entre 2 et 12.

Mots-clés: Traitement d’image, SIMD, AltiVec, programmation orienté objet, meta-programamtion template.

Abstract

As image processingalgorithms become more complex, their need in computing po-wer increases. To solve this problem, parallel machines canbe employed. An exampleis AltiVec SIMD unit - embedded in the PPC G4 chip - which allows performancesequivalent to multiprocessors machines on a single processor CPU. However AltiVec unitremains marginaly used because of their relative complexity.

The E.V.E library aims to ease the development of Altivec application by using an ob-ject oriented framework and to provide significant performance gains. E.V.E library relieson template meta-programming techniques to expose a intuitive API. First tests haveshown a speedup factor of 2 to 12 on variousimage processingalgorithms.

Keywords : Image processing, SIMD, AltiVec, object oriented programming, Tem-plate meta-programming.

Table des figures

1.1 Vision macroscopique du modèle à parallélisme de données . . . . . . . . 101.2 Vision microscopique du modèle à parallélisme de données . . . . . . . . 101.3 Exécution de la primitivemap . . . . . . . . . . . . . . . . . . . . . . . 121.4 Exécution d’une primitivefoldl . . . . . . . . . . . . . . . . . . . . . . . 121.5 Une Machine MIMD-SM . . . . . . . . . . . . . . . . . . . . . . . . . . 141.6 Une Machine MIMD-DM . . . . . . . . . . . . . . . . . . . . . . . . . . 141.7 Une Machine SIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.8 Déroulement d’une opérationSWAR . . . . . . . . . . . . . . . . . . . . 161.9 Les types de données AltiVec . . . . . . . . . . . . . . . . . . . . . . . .161.10 Structure interne du PowerPC 74xx . . . . . . . . . . . . . . . . . .. . . 171.11 Filtre 1x3 en C ANSI classique . . . . . . . . . . . . . . . . . . . . . .. 181.12 Principe du filtre 1x3 en AltiVec . . . . . . . . . . . . . . . . . . . .. . 181.13 Algorithme du filtre 1x3 en C AltiVec . . . . . . . . . . . . . . . . .. . 191.14 Performances du Filtre 1x3 . . . . . . . . . . . . . . . . . . . . . . . .. 20

2.1 Transtypage erroné de vecteur AltiVec. . . . . . . . . . . . . . .. . . . . 222.2 Transtypage de vecteur AltiVec. . . . . . . . . . . . . . . . . . . . .. . 222.3 Calcul de l’inverse en AltiVec . . . . . . . . . . . . . . . . . . . . . .. 232.4 Filtre 1x3 utilisant la classe AVector . . . . . . . . . . . . . . .. . . . . 242.5 Performances du Filtre 1x3 en C++ AltiVec . . . . . . . . . . . . .. . . 252.6 Expression simple utilisant une classe définie par l’utilisateur. . . . . . . 252.7 Code "précompilé" du filtre 1x3 utilisant AVector. . . . . .. . . . . . . . 26

3.1 Fonction integrate utilisant un pointeur de foncton . . .. . . . . . . . . . 283.2 Exemple simple d’Expressions Templates. . . . . . . . . . . . .. . . . . 293.3 la fonction integrate "déroulée" . . . . . . . . . . . . . . . . . . .. . . . 293.4 Arbre syntaxique de x/(1+x) . . . . . . . . . . . . . . . . . . . . . . . .303.5 Vue éclatée de l’arbre syntaxique de x/(1+x) . . . . . . . . . .. . . . . . 303.6 Une fonction template simple : min . . . . . . . . . . . . . . . . . . .. . 313.7 Utilisation d’une fonction template . . . . . . . . . . . . . . . .. . . . . 323.8 Grammaire simplifiée des expressions arithmétiques . . .. . . . . . . . . 323.9 Classe template BinaryNode . . . . . . . . . . . . . . . . . . . . . . . .333.10 Classe template Expr . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.11 Reconstruction du type associé à x/(1+x) . . . . . . . . . . . .. . . . . . 34

TABLE DES FIGURES

3.12 Classe template OpAdd . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.13 Classe template Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.14 Classe template Const . . . . . . . . . . . . . . . . . . . . . . . . . . . .363.15 Opérateur + générateur de donnée statique . . . . . . . . . . .. . . . . . 363.16 Code de la fonction integrate . . . . . . . . . . . . . . . . . . . . . .. . 373.17 Chaîne d’évaluation d’une expression . . . . . . . . . . . . . .. . . . . 373.18 Squelette d’une classe mêlant vecteur numérique et E.T. . . . . . . . . . 383.19 Classe template BinaryNode modifiée . . . . . . . . . . . . . . . .. . . 393.20 Classe template Var modifiée . . . . . . . . . . . . . . . . . . . . . . .. 393.21 Classe template Const modifiée . . . . . . . . . . . . . . . . . . . . .. . 403.22 Opérateur + modifié . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.1 Initialisation de E.V.E . . . . . . . . . . . . . . . . . . . . . . . . . . .. 424.2 Option de compilation de E.V.E . . . . . . . . . . . . . . . . . . . . . .424.3 Utilisation dearray . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.4 Fonctions et opérateurs dearray . . . . . . . . . . . . . . . . . . . . . 444.5 Fonctions inter-éléments . . . . . . . . . . . . . . . . . . . . . . . . .. 454.6 Exemple d’utilisation de E.V.E . . . . . . . . . . . . . . . . . . . . .. . 454.7 Liste d’initialisation dearray . . . . . . . . . . . . . . . . . . . . . . . 464.8 array et la notation indicielle . . . . . . . . . . . . . . . . . . . . . . . 464.9 Prototype de la fonctionwhere . . . . . . . . . . . . . . . . . . . . . . 474.10 Exemple d’utilisation de la fonctionwhere . . . . . . . . . . . . . . . . 474.11 Prototype de la fonctionfold . . . . . . . . . . . . . . . . . . . . . . . 474.12 Exemple d’utilisation de la fonctionfold . . . . . . . . . . . . . . . . 484.13 Exemple d’utilisation de filter . . . . . . . . . . . . . . . . . . . .. . . 484.14 Exemple d’utilisation des filtres constants . . . . . . . . .. . . . . . . . 494.15 Exemple d’utilisation des itérateurs de E.V.E. . . . . . .. . . . . . . . . 494.16 Utilisation conjointe de EVE et des fonctions de la STL.. . . . . . . . . 504.17 Utilisation conjointe de EVE et des flux standards. . . . .. . . . . . . . 514.18 Méthodesprint_on et read_from . . . . . . . . . . . . . . . . . . . 514.19 Comparaisonprint_on etcout . . . . . . . . . . . . . . . . . . . . . 52

5.1 Inverseur d’image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.2 Soustracteur d’image . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.3 Performances des algorithmes simples. . . . . . . . . . . . . . .. . . . . 545.4 Performances du produit-somme interne. . . . . . . . . . . . . .. . . . . 555.5 Application du détecteur de Harris . . . . . . . . . . . . . . . . . .. . . 575.6 Filtrage et Evaluation du détecteur de Harris . . . . . . . . .. . . . . . . 575.7 Performances du détecteur de Harris - Filtrage. . . . . . . .. . . . . . . 585.8 Performances du détecteur de Harris - Evaluation de H. . .. . . . . . . . 585.9 Comparaison de performances PPC G4/Pentium IV. . . . . . . .. . . . . 58

5

Table des matières

Remerciements 2

Table des matières

Introduction 8

1 Contexte de l’Etude 91.1 Le Parallélisme de données . . . . . . . . . . . . . . . . . . . . . . . . .9

1.1.1 Modèle de programmation . . . . . . . . . . . . . . . . . . . . . 91.1.2 Modèle d’exécution . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2 Cas Particulier : le SWAR . . . . . . . . . . . . . . . . . . . . . . . . . . 151.2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.2.2 Un exemple : la Technologie AltiVec . . . . . . . . . . . . . . . 161.2.3 Développer avec AltiVec . . . . . . . . . . . . . . . . . . . . . . 18

2 Position du Problème 212.1 Difficulté du développement utilisant AltiVec . . . . . . . .. . . . . . . 21

2.1.1 Gestion des types . . . . . . . . . . . . . . . . . . . . . . . . . . 212.1.2 Autres difficultés . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2 Solution envisagée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.2.1 Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.2.2 Analyse de la situation . . . . . . . . . . . . . . . . . . . . . . . 25

3 lesExpressions Templates 273.1 Technique d’évaluation partielle . . . . . . . . . . . . . . . . . .. . . . 31

3.1.1 Rappel sur les templates . . . . . . . . . . . . . . . . . . . . . . 313.1.2 Application à l’évaluation partielle . . . . . . . . . . . . .. . . . 323.1.3 Evaluation des données dynamiques . . . . . . . . . . . . . . . .37

3.2 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4 La bibliothèque E.V.E 414.1 Présentation de l’interface . . . . . . . . . . . . . . . . . . . . . . .. . 41

4.1.1 Mise en place de E.V.E . . . . . . . . . . . . . . . . . . . . . . . 414.1.2 Fonctionnalités de base . . . . . . . . . . . . . . . . . . . . . . . 42

4.2 Algorithmes et primitives de plus haut-niveau . . . . . . . .. . . . . . . 464.3 Utilisation conjointe de E.V.E et de la STL . . . . . . . . . . . .. . . . . 49

4.3.1 Gestions des itérateurs . . . . . . . . . . . . . . . . . . . . . . . 494.3.2 Fonctions classiques de la STL . . . . . . . . . . . . . . . . . . . 504.3.3 E.V.E et les flux standards . . . . . . . . . . . . . . . . . . . . . 50

5 Performances de E.V.E 535.1 Opérations élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . .. 53

5.1.1 Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.1.2 Code E.V.E . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.1.3 Performance : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.2 Algorithmes de la STL . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.2.1 Produit-somme interne . . . . . . . . . . . . . . . . . . . . . . . 555.2.2 Analyse : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5.3 Un Détecteur de point d’intérêt . . . . . . . . . . . . . . . . . . . . .. . 565.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.3.2 Mise en oeuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.3.3 Performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.3.4 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Conclusion 60

Références bibliographiques

Introduction

Le traitement d’image est une technique dont les progrès sont fortement liés à ceuxde l’informatique et de l’électronique. Depuis son émergence dans les années 70, le trai-tement d’images n’a cessé de se diversifier et de réclamer de plus en plus de ressources àla fois techniques et humaines. En outre, la complexité des algorithmes mis en oeuvre necesse d’augmenter, demandant des machines toujours plus puissantes pour être exécutés.Les machines parallèles ont permis de pallier cette demandecroissante de puissance enoffrant des puissances de calcul que ne peuvent fournir les ordinateurs séquentiels.

Le groupe GRAVIR du LASMEA s’est positionné sur ce créneau des machines pa-rallèles et à notamment développé depuis plusieurs années des machines de vision artifi-cielle parallèles. Grâce à des réalisations comme la machine TransVision ou le BeowulfOSSIAN, divers types d’algorithmes et d’applications de traitement d’image et de visionartificielle ont pu être implantés de manière efficace. Récemment des travaux portant surl’utilisation d’unité de calcul SIMD au sein de processeurs"classiques" mirent en évi-dence le potentiel d’une telle technologie. Les études effectuées sur l’unité AltiVec duPPC G4 de Motorola par Lionel Damez ont notamment montré que l’utilisation d’unetelle unité de calcul fournissait un moyen efficace d’implanter des algorithmes de visiongourmands en temps de calcul sur une machine monoprocesseur. les mêmes travaux onttoutefois montré que l’utilisation d’une telle extension SIMD restait complexe pour lesnon-spécialistes.

L’objet de cette étude est de démontré qu’il est possible de développer une biblio-thèque (unframework) permettant à un développeur familier des bibliothèques standardsdu langage C++ ou à un algorithmicien de développer rapidement une application tirantpartie de l’accélération fournie par AltiVec. Le but ultimeétant de pouvoir écrire un codehumainement lisible, très proche du formalisme mathématique et algorithmique, qui soitinterprété de manière optimale par les machines équipées deprocesseur doté d’une unitéAltiVec.

Nous présenterons donc dans le chapitre 1 de cette étude un historique du parallélismede donnée et des extensions SIMD. Nous verrons au chapitre 2 quel solutions furent envi-sagées pour résoudre notre problèmes et aux chapitre 3 quelles techniques furent utilisée.Finalement, le chapitre 4 présentera le résultat de nos travaux, la bibliothèque E.V.E, et lechapitre 5 les performances obtenues sur divers algorithmes de traitement d’images.

8

Chapitre 1

Contexte de l’Etude

1.1 Le Parallélisme de données

1.1.1 Modèle de programmation

1.1.1.1 Principe du modèle de programmation à parallélismede données

En programmation parallèle, on distingue globalement deuxclasses de modèles deprogrammation : les modèles à parallélisme de contrôle et les modèles à parallélisme dedonnées. Dans les premiers, le parallélisme provient de l’exécution parallèle de processusséquentiels. On parle alors de modèle "PAR of SEQ" [1]. Un exemple est le modèleCSP1 [2] introduit par Hoare et utilisé par exemple dans le langage Occam [3] ou lemodèle dit "à passage de message" sur lequel repose la bibliothèque MPI [4]. Dans lesseconds modèles, le parallélisme provient de l’exécution séquentielle d’actions opérantsur des structures de données parallèles. On parle alors de modèle "SEQ of PAR" [1].

Les modèles à parallélisme de données fournissent deux points de vues différents etcomplémentaires sur un même programme :

– un point de vue macroscopique :ce point de vue correspond à la vision de l’uti-lisateur final. Un programme est considéré comme une séquence d’opérations surun ensemble de données à accès parallèles (cf fig. 1.1). On ramène alors les pro-grammes à une suite de ré-arrangement d’éléments d’un tableau. Il apparait alorsqu’un grand nombre d’algorithme peuvent être exprimés à partir de telles opérations[5]. Des langages comme HPF [6, 7] sont essentiellement fondés sur cette vision duparallélisme.

1Communicating Sequential Processes

9

1.1. LE PARALLÉLISME DE DONNÉES

Processeur Mémoire

@

Tableau de données

FIG. 1.1 – Vision macroscopique du modèle à parallélisme de données

– un point de vue microscopique :il correspond au point de vue bas-niveau du com-pilateur. Le programme est une composition parallèle d’opérations séquentiellesmenées sur des données parallèles locales et est soumis à un mécanisme de synchro-nisation de ces traitements asynchrones. Tout se passe comme si l’on avait affaireà un tableau de processeurs (cf fig.1.2). On retrouve une telle approche dans deslangages comme POMPC [8].

Séquenceur

Tableau de processeursinterconnectés

FIG. 1.2 – Vision microscopique du modèle à parallélisme de données

L’idée sous-jacente de la programmation à parallélisme de données est donc d’effec-tuer une suite d’opérations sur des structures de données degrande taille. Lors de cestraitements, les opérations menées sur des éléments indépendants de cette structure sonteffectuées simultanément. Par rapport aux modèles à parallélisme de contrôle, les mo-dèles à parallélismes de données présentent trois principaux avantages :

10


– le parallélisme de données conduit à une exécution déterministe des programmes.Il élimine donc les problèmes de développement et de mise au point liés à au non-determinisme (inter-blocages,race conditions).

– l’expression du parallélisme au sein du programme est explicite et apparaît à traversle choix des structures de données alors que l’ensemble de lastructure algorith-mique du code reste celle d’un programme séquentielle. Ainsi l’écriture du codereste simple et ne demande pas au développeur de changer radicalement de façonde penser.

– Le degré de parallélisme potentiel d’une machine utilisant le modèle à parallélismede données est directement lié à la taille des structure de données parallèles utili-sées. Le parallélisme peut être augmenté simplement en augmentant la taille desstructures de données. L’organisation du code reste identique et aucune réorgani-sation de l’algorithme n’est nécessaire. Pour le parallélisme de contrôle, ce degréest lié au nombre de tâches exécutables simultanément au sein de l’algorithme. Enpratique, les ordres de grandeur de ces degrés sont très différents2.

1.1.1.2 Primitives de bases

L’écriture de programme à parallélisme de données suppose l’existence d’un certainnombre de primitives classiques que nous allons décrire ici. Dans la suite de cette exposé,nous utiliserons une notation simplifié pour expliciter la sémantique de ces primitives :

1. [x0, ..., xn] représente une séquence de valeurs3.[] représente la séquence vide.

2. Le symbole⊕ représente un opérateur ou une fonction binaire quelconque.

3. Le symbole⊙ représente un opérateur ou une fonction unaire quelconque.

4. L’application d’un opérateur ou d’une fonction à un ou plusieurs arguments se noterespectivement(⊙ x) et (x ⊕ y) ;

A partir de ces considérations structurelle, on peut définirun certain nombre de primi-tives pour le parrallélisme de données.

– Primitive applicative : map .La primitive map permet d’appliquer une fonction à un ensemble de données. Ils’agit d’une primitive très simple et très employée. Elle sedéfinit ainsi (fig. 1.3) :

map ⊙ [x0, ..., xn] = [⊙x0, ...,⊙xn]

2Typiquement inférieure à la dizaine pour le parallélisme decontrôle, jusqu’à plusieurs dizaines de milliers pour leparallélisme de données.

3En pratique, ces séquences correspondent à des tableaux ou des listes

11


Exemple :map abs [-1.2, -2.3, 3.4, -4.5 ] = [1.2, 2.3, 3.4, 4.5 ]

0 1 2 3 4 5

F(0) F(1) F(2) F(3) F(4) F(5)

F(.) F(.) F(.) F(.) F(.) F(.)

FIG. 1.3 – Exécution de la primitivemap

– Primitive de réduction : fold .La primitive fold se décline en deux versions :foldl et foldr qui effectuent res-pectivement une réductionà gaucheet à droite. La primitive foldl par exemple estillustrée sur le figure 1.4 :

X0 X1 X2 X3 X4 X5

Z foldl Z + [X0, ... X5]

FIG. 1.4 – Exécution d’une primitivefoldl

foldl ⊕ z[x0, ..., xn] = [...(z ⊕ x0) ⊕ x1)... ⊕ xn]

Exemple :foldl (+) 0 [1,2,3,4 ] = 10

– Primitive de reduction des préfixes : scan.La primitive scanpermet de réduire successivement tout les préfixes d’une liste.Tout commefold, elle admet deux versions :scanret scanl. Pour l’exemple de laprimitive scanl, on a ainsi :

scanl ⊕ z[x0, ..., xn] = [z, z ⊕ x0, z ⊕ x0 ⊕ x1, ..., z ⊕ x0... ⊕ xn]

12


Exemple :scanl (*) 1 [1,2,3,4,5 ] = [1,1,2,6,24,120 ]

De nombreux travaux ont permis d’établir des règles et des théorèmes sur la composi-tion de telles primitives. Le formalisme dit deBird-Meertens[9, 10] par exemple permetde raisonner formellement sur des équations utilisant ces primitives pour permettre desimplifier l’expression algorithmique de ces équations et de réduire dans certains cas letemps d’exécution des programmes.

1.1.2 Modèle d’exécution

Si le modèle de programmation renvoie à la vision du programmeur, le modèle d’exé-cution concernel’organisation physiquedes machines à même d’exécuter ces programmes.Si on se restreint au parallélisme de données, deux modèles architecturaux sont suscep-tibles de le supporter :

1. Le modèle MIMD :Dans ce modèle, la machine est formée de N processeurs, chaque processeur étantcomposé d’une unité de séquencement des instructions (unité de contrôle) et d’uneunité de traitement. Chaque processeur peut disposer de sonpropre espace mémoire(MIMD à mémoire distribuée, fig. 1.6) ou cette mémoire peut être partagée parl’ensemble des processeurs (MIMD à mémoire partagée, fig. 1.5). Dans le premiercas, un réseau de communication permet l’échange de donnéesinter-processeurs.Les machines MIMD se prêtent bien à l’implantation de programme à parallélismede contrôle, chaque processeur prenant alors en charge l’exécution d’un ou plu-sieurs processus séquentiels. Elles peuvent aussi être utiliser pour implanter desprogrammes à parallélisme de données en forçant chaque processeur à exécuterle mêmeprogramme mais sur des données différentes. On parle alors de modèleSPMD (Single Program, Multiple Data).

13


Mém

oire

UC1

UT1

UC2

UT2

UCN

UTN

...

Flot d'instruction

Flot de données

FIG. 1.5 – Une Machine MIMD-SM

Rése

au d

e co

mm

unica

tion UC

1UT1

MEM 1

UC 2

UT2

MEM2

UC N

UTN

MEM N

...

Flot de données

Flot d'instructions

FIG. 1.6 – Une Machine MIMD-DM

14

1.2. CAS PARTICULIER : LE SWAR

2. Le modèle SIMD :Dans ce modèle, une seule unité de contrôle fournit le flot d’instructions pour unensemble d’unité de traitement opérant en parallèle (cf fig.1.7). Si ce modèle aconnu son heure de gloire dans les années 80 avec des machinescomme la CM-2 [11], il est resté en pratique peu utilisé car il suppose unearchitecture dédiée(contrairement au machines MIMD qui peuvent être construite en inter-connectantdes ordinateurs séquentiels). Il est réapparu toutefois sous une forme particulière àla fin des années 90 en donnant naissance auSWAR.

UC

UT1

...

UTP

UTN

Flot d'instruction

Flot de données

Mém

oire

FIG. 1.7 – Une Machine SIMD

1.2 Cas Particulier : le SWAR

1.2.1 Principe

Le SWAR (SIMD Within A Register) est une spécialisation du modèle SIMD consistantà fournir au sein d’unprocesseur classiqueune unité de traitement SIMD permettant degérer des programmes à parallélisme de donnés en utilisant un jeu de registres spécifiquesstockant en leur sein plusieurs données de même type. L’application d’opérations sur detels registres revient donc à effectuer la même opérationen parallèlesur l’ensemble desdonnées contenues dans le registre (cf fig. 1.8). Parmi les différentes incarnations de ceprincipe, on retrouve les extensions dites "multimédia" présentes sur certains processeur

15


généraliste : l’extension MAX[12] de HP, les extensions MMX[13],SSE et SSE2 des pro-cesseurs Intel ou l’extension AltiVec des PowerPC.

UC UT

Flot d'instruction

Flot de données

Mém

oire

FIG. 1.8 – Déroulement d’une opérationSWAR

1.2.2 Un exemple : la Technologie AltiVec

AltiVec est le nom de l’extension SIMD intégré au processeurMPC 74xx de Motorola[14,15]. L’unité de calcul AltiVec qui est intégrée à l’architecture du PowerPC repose sur unearchitecture vectorielle permettant le traitement simultané de plusieurs données en paral-lèle [15]. Elle se distingue des autres unités de calcul parallèle concurrentes [13, 12] enplusieurs points :

Une arithmétique polyvalente.L’unité de base des calculs effectués par AltiVec est levector. Un vectorest une struc-

ture de données de 128 bits pouvant contenir des données de plusieurs types (cf. figure1.9) :

C C C C C C C C C C C C C C C C1.

2.

3.

4.

5.

6.

Short Short Short Short Short Short ShortShort

Int Int Int Int

Float Float Float Float

16 Entiers 8 bits

8 Entiers 16 bits

4 Entiers 32 bits

4 Flottants 32 bits

8 Pixels RGBA 16 bits

16 pixels RGBA 32 bitsA A A A

FIG. 1.9 – Les types de données AltiVec

16


Outre cette diversité de type, AltiVec gère aussi bien l’arithmétique classique quel’arithmétique saturante. L’utilisateur peut donc choisir de gérer à sa convenance les er-reurs de dépassements lors de ses calculs.

Un parfaite intégration au sein du processeur.L’unité AltiVec est complètement indépendante des unités de calculs classiques (cf.

figure 1.10).

IU

GPR

Unité Vectorielle

Registres Vectoriels

Flo

t d’in

stru

ctio

ns

Decodeur / Répartiteur

FPU

FPR

Mémoire cache

32 bits 64 bits 128 bits

FIG. 1.10 – Structure interne du PowerPC 74xx

Deux unités de traitement numérique indépendantes lui permettent de traiter à la foisles opérations sur les entiers et sur les flottants. Ainsi, contrairement aux architecturesMMX, on peut générer du code mélangeant à la fois des instructions manipulant destypes de données classiques (int , float ) et des instructions manipulant des types vec-toriels (vector float, vector int ). L’unité AltiVec peut aussi traiter simultané-ment desvector int et desvector float . De part les limitations matérielles del’extension AltiVec, le processeur ne peut toutefois réorganiser que deux niveaux d’ins-tructions. On parle alors de processeur super-scalaire de degré 2. Le programmeur a doncla possibilité d’utiliser tous les registres scalaires qu’il souhaite et les 32 registres vecto-riels fournit par AltiVec. C’est cette spécificité qui a permis de développer un compilateurC gérant l’utilisation des registres vectoriels et donc de fournir un outil de développementfacile à appréhender et à utiliser (contrairement au MMX où l’utilisation de l’assembleurest requise [16, 13]).

17


1.2.3 Développer avec AltiVec

Pour illustrer les capacités d’AltiVec, nous allons considérer un problème simple, l’ap-plication d’un filtre 1X3 sur une image en niveau de gris. L’image est stockée sous laforme d’un tableau d’entiers 8 bits non signés Pour conserver une précision maximale,nous utilisons un masque de filtre et un tableau d’entier 16 bits signés pour les calculsintermédiaires. L’algorithme séquentiel appliqué s’exprime en C de la manière suivante :

unsigned char* img;signed short m[3],* res;

for( int i=1; i < TAILLE_IMAGE-1; i++ ){

res[i] = m[0]*img[i-1]+m[1]*img[i]+m[2]*img[i+1];}

FIG. 1.11 – Filtre 1x3 en C ANSI classique

Pour paralléliser ce code pour l’extension AltiVec, il fautdonc repenser l’algorithmedu filtre de manière "vectorielle", c’est à dire en termes d’opérations opérant sur des vec-teurs de pixels et non plus pixel à pixel. Considérons le voisinage vectoriel d’un pixelPi

de l’image(cf fig.1.12). A partir de ce point, on voit que l’onpeut accéder aux pixels pré-cédent (Pi−1) et suivant (Pi+1) en effectuant des décalages d’éléments au sein du vecteur.

M0M0M0M0M0M0M0M0

M1M1 M1M1 M1M1 M1M1

M2M2M2 M2 M2M2M2 M2

X

X

X

+

+

= Ri

P P Pi-1 i+1i

P P Pi-1 i+1i

P P Pi-1 i+1i

FIG. 1.12 – Principe du filtre 1x3 en AltiVec

18


Une fois ces opération effectuées, une simple multiplication/somme des trois vecteurs(original,décalé à droite, décalé à gauche) nous permet de retrouver la valeur de l’imagefiltrée sur ce pixel ainsi que pour l’ensemble des pixels du vecteur. L’algorithme de filtrage"vectorisé" pour une image de 16 pixels (donc contenue dans un seul vecteur) est donnésur la figure 1.13. Comme nous le voyons, l’utilisation d’entiers 16 bits pour effectuer descalculs sans perte de dynamiques nous oblige à utiliser des opérations de conversions detypes vectoriels. Pour une image de plus de 16 pixels, on procède en itérant cet algorithmesur des blocs de 16 pixels.

C0= [ M0 ... M0]C1= [ M1 ... M1]C2= [ M2 ... M2]R1= [ P0 ... ... P15]

// Decalage de R1 à droite et à gaucheR0= R1 » 1R2= R1 « 1

TranstyperR0=> R01etR02.TranstyperR1=> R11etR12.TranstyperR2=> R21etR22.

// Ici nous utilisons des séries de multiplication additionpour tirer partie// de l’instruction AltiVecvec_madd qui effectue cette opérations en un cycle.R01= R01*C0+ R11*C1 + R21*C2 + 0R02= R02*C0+ R12*C1 + R22*C2 + 0

TranstyperR01etR02=> R13.EcrireR13dans l’image résultat.

FIG. 1.13 – Algorithme du filtre 1x3 en C AltiVec

Le tableau 1.14 donne pour différentes tailles d’images lesaccélérations obtenuesavec un code vectorisé selon la technique précédente par rapport à un code séquentiel"classique" (cf fig. 1.11). On remarquera que l’accélération mesurée excède la valeur"théorique" maximale - qui est de 8 pour un algorithme opérant sur des entiers 16 bits.Cette surlinéarité s’explique par les effets combinés du pipeline de l’Unité AltiVec, duchargement efficace des données dans le cache et de la réorganisation du code effectuépar le compilateur [17].

19


Taille de l’image C séquentiel C AltiVec Accélération16x16 3.89µs 2.03µs 1.9232x32 12.09µs 2.87µs 4.2164x64 48.80µs 6.27µs 7.78128x128 209.59µs 20.05µs 10.45256x256 854.37µs 75.99µs 11.24512x512 3737.92µs 322.85µs 11.581024x1024 16253.54µs 1440.39µs 11.28

FIG. 1.14 – Performances du Filtre 1x3

Ces tests ont permis de mettre en oeuvre un certain nombre de techniques de vectori-sation. Ces techniques sont largement approfondies dans les travaux de Lionel DAMEZ[16].

20

Chapitre 2

Position du Problème

La technologie AltiVec s’avère être un moyen efficace d’utiliser le parallélisme dedonnées au sein d’applications coûteuses en termes de tempsde calcul comme le traite-ment du signal en général et le traitement d’image en particulier. Son utilisation ne vatoutefois pas se faire sans quelques difficultés. Ce chapitre va présenter les principalesdifficultés et va montrer qu’elles ne peuvent être résolu facilement. Ce constat constituerale fondement des travaux présentés au Chapitre 3.

2.1 Difficulté du développement utilisant AltiVec

2.1.1 Gestion des types

Le code C AltiVec reste lisible pour des problèmes simples. Mais, pour des algo-rithmes plus complexes, les optimisations et les expressions dues aux pré-traitement desdonnées initiales rendent le code difficilement extensible. En outre, peu d’algorithmesconservent une écriture naturelle une fois vectorisé. Reprenons le filtre 1x3 du chapitreprécédent. Si l’on décide d’utiliser un masque de filtrage flottant, nous nous retrouvonsface à un des problèmes d’AltiVec : la conversion de type. Si en C cette conversion esttransparente, ce n’est pas le cas en AltiVec. En effet, le transtypage classique du C neproduit aucun changement du contenu d’unvector Altivec. Ce transtypage laisse in-tact les bits du vecteur et ne gère pas les problèmes dus au changement de la taille deséléments du vecteur. Ainsi, l’écriture d’un code comme celui de la figure 2.1 ne génèrepas du tout un vecteur de flottants correct. Il ne faut pas en effet oublier que si la tailledes vecteurs reste fixe (128 bits soit 16 octets), celle des éléments du vecteur varie. Letranstypage d’un vecteur de 16 entiers 8 bits produit ainsi 4vecteurs de flottants 32 bits.Il est donc nécessaire d’écrire explicitement la transformation du vecteur d’entiers 8 bitsen 4 vecteurs de flottants 32 bits.

21

2.1. DIFFICULTÉ DU DÉVELOPPEMENT UTILISANT ALTIVEC

vector unsigned char source;vector float f1;

f1 = (vector float)source;

FIG. 2.1 – Transtypage erroné de vecteur AltiVec.

Le principe de cette transformation est de créer à partir du vecteur de 16 entiers 8bits deux vecteurs de 8 entiers 16 bits contenant les mêmes valeurs. Puis, à partir de cesdeux vecteurs, on génère quatre vecteurs d’entiers 32 bits qui sont ensuite transformés envecteur de flottants (cf fig. 2.2). Appliqué au code du filtre 1x3, cette technique accroîtsignificativement la complexité du code. En effet, une fois les calculs effectués, il faut ànouveau transformer les vecteurs de flottants en vecteurs d’entiers 8 bits1.

vector unsigned char c;vector unsigned short s1,s2;vector float f1,f2,f3,f4;

// Conversion des 8 premiers éléments de cs1 = vec_unpackh( c );// Conversion des 8 derniers éléments de cs2 = vec_unpackl( c );

// Conversion des 4 premiers éléments de s1vec_st( vec_ctf( vec_unpackh(s1),0 ), 0, f1 );// Conversion des 4 derniers éléments de s1vec_st( vec_ctf( vec_unpackl(s1),0 ), 0, f2 );

// Conversion des 4 premiers éléments de s2vec_st( vec_ctf( vec_unpackh(s2),0 ), 0, f3 );// Conversion des 4 derniers éléments de s2vec_st( vec_ctf( vec_unpackl(s2),0 ), 0, f4 );

FIG. 2.2 – Transtypage de vecteur AltiVec.

Ce probléme de transtypage se retrouve pour toutes les combinaisons de types de don-nées AltiVec.

1On pourra trouver dans le manuel de référence d’AltiVec[17]les détails des fonctions utilisées ici

22

2.1. DIFFICULTÉ DU DÉVELOPPEMENT UTILISANT ALTIVEC

2.1.2 Autres difficultés

On liste ici, sans les détailler plus avant, un certain nombre de point technique quirendent moins trivial qu’il n’y parait l’écriture de code AltiVec. Pour plus de détails onpourra se reporter à [17] et [16].

1. Asymétrie du jeu d’instructions : un certain nombre d’instructions AltiVec n’existentque pour un sous-ensemble des types de données gérés par l’extension. Par exemple,les opérations de multiplications sont inexistantes pour les entiers 8 bits et 32 bits. Ilest donc nécessaire d’utiliser des constructions plus complexes, basées sur les opé-rations de transtypage, pour permettre de telles opérations.

2. Hétérogénéité du niveau de précision: certaines instructions AltiVec opèrent avecune faible précision. Ainsi des opérations comme le logarithme, l’exponentielle,l’inverse ou la racine carré fournissent un résultat 32 bitsavec 24 bits de précision.Il est donc nécessaire de pallier ces imprécisions en utilisant des techniques commele raffinement de Newton-Raphson[17] pour obtenir un résultat à la précision vou-lue. Le calcul de l’inverse d’un vecteur s’effectue par exemple comme ceci (cf fig.2.3) :

vector float inverse( vector float v ){

// rec = valeur approché de 1/v = ~(1/v)vector float rec = vec_re(v);

// one = [1.0 1.0 1.0 1.0 ]vector float one = vec_ctf(vec_splat_u32(1),0));

// Ce calcul utilise le raffinement de Newton-Raphson// à l’ordre un pour évaluer une valeur exacte de 1/v.// Avec :// vec_madd(a,b,c) = a*b+c// vec_nmsub(a,b,c) = c-a*b// On obtient :// r = ~(1/v)*( 1 - v*(1/v) ) + ~(1/v)

return vec_madd( rec,vec_nmsub( rec, v, one ),rec);}

FIG. 2.3 – Calcul de l’inverse en AltiVec

3. Gestion du cache et du pipeline: dans le cas d’un programme écrit en C, le com-pilateur décharge le développeur des subtilités de la gestion du pipeline et du cache

23

2.2. SOLUTION ENVISAGÉE

de données. Dans le cas d’un code C AltiVec, il est important que le développeurprenne en charge cette gestion. En effet, une application utilisant AltiVec peut voirses performances doubler ou tripler lors d’un simple réarrangement d’un grouped’instructions AltiVec de par la grande sensibilité du cache et du pipeline. Des tech-niques comme le dépliage de boucle ou le réorganisation des instructions au seind’une boucle[16] doivent être utilisées pour garantir un certain niveau de perfor-mance. mais le bon usage de ces techniques rend le code plus long et plus difficile àentretenir.

2.2 Solution envisagée

2.2.1 Principes

Face au difficultés soulevées plus haut, une approche possible consiste à créer uneclasse C++ encapsulant un concept de vecteur parallèle similaire à celui duvectorfournie par AltiVec. Cette classe nous permettrait d’utiliser AltiVec tout en augmentant leniveau d’abstraction du code et donc de produire du code lisible et facilement modifiable.L’interface de cette classe peut par exemple se fonder sur celle de la classevalarray dela bibliothèqueSTL[18] qui fournit un ensemble méthodes visant à manipuler destableauxde valeurs numériques de grande taille. La classevalarray est par ailleurs compatibleavec les nombreuses fonctions de la bibliothèquealgorithm , ce qui en fait un outil pré-cieux pour de nombreux développeurs. Nous avons donc développé dans cette premièreétape de travail une classe similaire àvalarray mais utilisant AltiVec pour effectuerles calculs nécessaires. Cette classeAVector fournit un ensemble de méthode de calculsainsi qu’un certain nombre d’opérateurs surchargés permettant d’écrire naturellement desopérations de manipulations de vecteurs. De part sa nature générique, la classeAVectorpermet de retrouver en C++ la diversité des types de données supportés par AltiVec. Voicipar exemple le filtre 1x3 réécrit en utilisant la classeAVector .

AVector<unsigned char, TAILLE> image;AVector<signed short, TAILLE> result;float mask[3];

/* On charge l’image eton remplit le masque. */

result = mask[0]*image.shift(-1) +mask[1]*image +mask[2]*image.shift(1);

}

FIG. 2.4 – Filtre 1x3 utilisant la classe AVector

24


Comme nous le voyons les opérateurs arithmétiques surchargés fournissent un moyenélégant de formaliser l’algorithme du filtrage. Il est clairque le gain en lisibilité est no-table. Reste à évaluer l’efficacité de cette approche, c’està dire le surcoût qu’elle induitpar rapport à une implantation directe en C AltiVec. Le tableau 2.5 donne pour cela lestemps de calculs pour une implantation utilisantAVector et les accélérations correspon-dantes par rapport à une implantation en C séquentiel du filtre décrit au chapitre précédent.

Taille de l’image Temps de calcul Gain16x16 11.69µs 0.33

32x32 16.18µs 0.74

64x64 46.29µs 1.05

128x128 2605.43µs 0.08

256x256 3428.13µs 0.25

512x512 17349.30µs 0.21

1024x1024 75811.47µs 0.21

FIG. 2.5 – Performances du Filtre 1x3 en C++ AltiVec

Comme on peut le constater, l’efficacité de cette approche est extrêmement faible.L’accélération par rapport à du C séquentiel reste inférieure à 2 (alors qu’elle atteint 11dans la version C AltiVec). Dans la plupart des cas, cette accélération est même inférieureà 1, le code vectorisé étant alorsmoins rapide que le code séquentiel !

2.2.2 Analyse de la situation

Les faibles performances obtenues en utilisant la classe AVector sont principalementdues au mécanisme d’évaluation utilisé par le compilateur C++. En examinant le stan-dard du langage C++, on s’aperçoit que lors de l’évaluation d’une expression incluant destypes pourvus d’opérateurs surchargés, ces derniers sont évalués par paires2 et provoquentla génération de variables temporaires au fur et à mesure de l’évaluation de l’expression.

Ainsi le code source suivant (fig. 2.6) :

AVector<float,TAILLE> w,x,y,z;z = x + y + w;

FIG. 2.6 – Expression simple utilisant une classe définie par l’utilisateur.

va se révéler équivalent à celui-ci (fig. 2.7) :

2On parle de réductiondyadique.

25


AVector<float,TAILLE> w,x,y,z;AVector<float,TAILLE> tmp1;for(i=0;i<TAILLE;i++{

tmp1[i] = y[i]+w[i];}

AVector<float,TAILLE> tmp2;for(i=0;i<TAILLE;i++{

tmp2[i] = x[i]+tmp1[i];}

for(i=0;i<TAILLE;i++{

z[i] = tmp2[i];}

FIG. 2.7 – Code "précompilé" du filtre 1x3 utilisant AVector.

Le nombre de variables intermédiaires augmente proportionnellement à la complexitéde l’expression. Chaque création et destruction d’une telle variable s’accompagne d’unemanipulation de l’espace mémoire3 (allocation ou libération). Le temps passé dans cesopérations devient de fait rapidement prépondérant. Le temps perdu dans les contrôleursde boucles et lors des recopies d’objets intermédiaires estaussi un facteur limitant, surtoutdans le cas d’objets de grande taille.Le gain apporté par l’extension AltiVec parvientà peine à compenser les pertes dues à ces mécanisme d’évaluations. L’approche basésur la simple encapsulation des fonctionnalités offertes par AltiVec apparaît donc, aprèsexpérimentation, comme une impasse. Cet état de fait a donc motivé la recherche d’uneautre solution. La description de cette solution fait l’objet du chapitre suivant.

3Ce qui est souvent le cas pour des classes de types tableaux numériques

26

Chapitre 3

lesExpressions Templates

Comme nous l’avons vu au chapitre précédent, l’approche fondée sur la simple encap-sulation des fonctionnalités de l’AltiVec dans une classe produit un code peu performantà cause de la multiplication des variables intermédiaires et des boucles de traitement. Lasolution passe donc par l’élimination (ou la réduction au strict minimum) de ces boucleset de ces variables. Ainsi le code suivant :

AVector<float,TAILLE> r,a,b,c;r = a + b + c;

devrait se compiler idéalement sous une forme équivalente à:

AVector<float,TAILLE> r,a,b,c;for( int i=0;i<TAILLE;i++)

r[i] = a[i] + b[i] + c[i];

Cette formulation se traduirait alors immédiatement et sans surcoût (par rapport à uneimplémentation manuelle) en un code C AltiVec équivalent à :

AVector<float,TAILLE> r,a,b,c;vector float tmp;for(int i=0;i<TAILLE/4;i++){

tmp = vec_add( vec_ld ( &a[4*i],0),vec_add( vec_ld( &b[4*i],0),

vec_ld( &c[4*i],0)));

vec_st( &r[4*i], 0, tmp);}

27

Dans ce code, les fonctionsvec_ld et vec_st sont respectivement des fonctionsde lecture et d’écriture de vecteur AltiVec etvec_add la fonction AltiVec d’additionvectorielle.

L’idée est donc de mettre en place un mécanisme qui permettrait au compilateur degénérer automatiquement ce code optimal à partir de l’expression de départ.

La technique desExpressions Templatesfournit la base d’un tel mécanisme. Cettetechnique a été développée par Todd Veldhuizen[19] et avaitpour but original de fournirune alternative élégante et performante au passage d’expression sous forme de pointeurde fonction en argument d’autres fonctions. Par exemple, labibliothèque standard du lan-gage C fournit des routines commeqsort() ou bsearch() dont un des argumentsest un pointeur vers une fonction définie par l’utilisateur.De nombreuses bibliothèquesfournissent des mécanismes semblables pour manipuler les fonctions comme un élémentatomique du langage. Par exemple, on peut considérer la fonction integrate qui effec-tue le calcul de l’intégrale d’une fonction numérique sur unintervalle donné (fig. 3.1) :

double f( double x){

return (x/(1.0+x));}double integrate( double (*f)(double), double inf, double sup){

static const double dx = 0.01;double r = 0.0;for( double x=inf;x<sup;x+= dx )

r += dx*f(x);return r;

}

int main (){

double i = integrate(f,0,10);}

FIG. 3.1 – Fonction integrate utilisant un pointeur de foncton

Le problème de cette approche par pointeur est son inefficacité, surtout si les opéra-tions effectuées au sein de la fonction sont simples. En effet, il est nécessaire d’effectuerun déréférencement de pointeur et un appel de fonction à chaque itération de l’algorithmeutilisé par la fonctionintegrate . Le principe desExpressions Templatesest de per-mettre l’utilisation d’expressions comme argument de fonction et de dérouler automati-quement le code nécessaire à l’évaluation de ces expressions au sein de la fonction appe-

28

lante au moment de la compilation. Avec cette approche, le code de la figure 3.1 se réécritainsi :

int main (){

Var<double> x;double i = integrate(x/(1.0+x),0,10);

}

FIG. 3.2 – Exemple simple d’Expressions Templates.

Le compilation de la fonctionintegrate produit alors un code dans lequel le codecorrespondant à la fonction à intégrer est déroulé ("inliné") en place (fig. 3.3) :

//Intégrale d’une fonction entre 0 et 100double r=0.0;

for(int x=0;x<100;x+=0.1)r += 0.1*(x/(1.0+x));

FIG. 3.3 – la fonction integrate "déroulée"

Pour réaliser cela, la technique desExpressions Templatesconsiste à examiner à lacompilation le contenu syntaxique d’une expression et à utiliser ces informations pourgénérer un code qui est l’exacte traduction de cette syntaxe. Ce principe repose sur celuide l’évaluation partielle du code à la compilation [20] qui consiste à déporter les calculset les opérations sur les structures de données et les données statiques à la compilationpour n’effectuer que les calculs et opérations sur les données dynamiques à l’exécution.Pour mieux comprendre cette technique, nous allons reprendre l’exemple de la fonctionintegrate vue ci-dessus (cf fig. 3.2).

Dans cet exemple, l’expression à intégrer est la suivante :

x/(1.0+x)

Au niveau du compilateur, une telle expression se représente par un arbre de syntaxeabstraite (Abstract Syntax Tree ou AST) :

29

x

_

+

x 1

..

FIG. 3.4 – Arbre syntaxique de x/(1+x)

Dans cette représentation lesnoeudsreprésentent les opérations à effectuer sur lesnoeuds fils, lesfeuillesreprésentent les données et les constantes sur lesquelles portent cesopérateurs. Pour une expression donné, les noeuds et leur agencement sont fixes et connusà la compilation alors que les valeurs portées par les feuilles sont en général connues àl’exécution. On peut ainsi dire que la forme de l’arbre syntaxique correspondent à la par-tie statiquede l’expression et que les feuilles correspondent à la partiedynamiquede cetteexpression comme illustrée sur la figure 3.5 :

x

_

+

x 1

..

FIG. 3.5 – Vue éclatée de l’arbre syntaxique de x/(1+x)

Sur ce schéma, nous avons représenté en rouge les partiesstatiquesde l’expressionx/(1+x) et en bleu, les parties dynamiques de cette expression. La technique d’opti-misation présentée dans ce chapitre s’appuie sur cette dualité statique/dynamique. Elledécompose l’évaluation d’une expression en deux phases :

1. une évaluation statique (à la compilation) pendant laquelle la structure de l’AST estanalysé et où l’on génère un codeoptimisé permettant l’évaluation de l’expressionpour un jeu de données dont les valeurs sont inconnues.

30

3.1. TECHNIQUE D’ÉVALUATION PARTIELLE

2. une évaluation dynamique (à l’exécution) au cours de laquelle lesvaleurs des don-nées de l’expression sont fournies au code produit précédemment.

L’interêt d’une telle approche -appelée évaluation partielle hors-line [20]- provient dufait que le travail d’analyse et d’optimisation effectuer àla compilation n’a plus à êtreeffectué à l’exécution, d’où un gain de temps d’exécution qui peut être significatif lorsquel’expression évaluée comporte de large parties statiques.

3.1 Technique d’évaluation partielle

La mise en oeuvre de la technique d’évaluation partielle ébauchée au paragraphe pré-cédent suppose que l’on soit capable de récupérer et de manipuler l’ AST d’une expressionau niveau du langage source. En C++, cette manipulation n’est possible qu’en représen-tant l’AST sous la forme d’untype et en utilisant le mécanisme destemplates.

3.1.1 Rappel sur les templates

Les templatesfurent créés dans le but de permettre l’écriture de code générique et fa-cilement réutilisable. Par exemple, une fonction calculant le minimum de deux variablesde types quelconques peut s’écrire :

template<class T> T min( T& a, T& b){

return ( a<b ? a : b );}

FIG. 3.6 – Une fonction template simple : min

Dans cette écritureT représente un argument de type alors quea et b sont des argu-ments de fonction classiques. Cette fonctionmin sera utilisable sur les types de donnéesatomiques et sur les types de données définis par l’utilisateur dés lors que ce type fournitune surcharge de l’opérateur "<". Il est alors possibled’instancier cette fonction géné-rique en lui fournissant des données de types diverses :

Il faut aussi noter que dans la majorité des cas, l’instanciation d’une fonction tem-plate génère non pas un appel vers une fonction mais un codeinline directement réécritau point d’appel de la fonction template. Ce mécanisme allège considérablement le coûtdue à la généricité et permet, à l’instar des macros, de produire du code à partir de diversparamètres au moment de la compilation. A partir de cette utilisation de base, diversestechniques ont vu le jour et ont permis de mettre au point des fonctions et des classes

31


double r1;int r2;char r3;

r1 = min( 3.57, 2.55 );r2 = min( 4512, 9433 );r3 = min( ’c’, ’f’ );

FIG. 3.7 – Utilisation d’une fonction template

templates permettant de générer du code "inline" très performant [21] ou de mettre enplace des équivalents statiques des structures de contrôles classiques. On parle alors demeta-programmation par templates[22].

3.1.2 Application à l’évaluation partielle

Dans notre cas, les techniques de meta-programmation par templates permettent demettre en place un système simple de construction d’AST. Si l’on revient à une définitionpurement grammaticale1 des expressions arithmétiques, on peut ainsi définir un ensembleréduits de règles pouvant décrire une expression arithmétique quelconque :

val := ID | CONSTOP := + | - | * | /expr := val | expr OP expr

FIG. 3.8 – Grammaire simplifiée des expressions arithmétiques

A partir de ces règles de grammaire, il est possible de définirun certain nombre detypes permettant de représenterau sein du langagela structure même d’un AST. Pourcela, on code la structure de l’arbre au sein d’untype de donnée. On définit alors troistypes de classes :

1. Les classes décrivant la topologie de l’AST.

L’unité de base de l’AST est le noeud. Dans notre exemple simplifié, chaque noeudpossède un fils droit, un fils gauche et un opérateur décrivantl’opération associée aunoeud. Cette topologie est reprise telle quelle dans la classeBinaryNode (fig. 3.9).Les paramètres templates deBinaryNode reflètent sa nature de noeud binaire.En effet, les paramètres de typeL et R représentent le contenu respectivement des

1Au sens grammaire des langages de programmation

32


fils gauche et droit du noeud de l’arbre binaire et le typeOPreprésente le type del’opération effectuée au sein du noeud.

template<class T, class L, class R, class OP>class BinaryNode{public :

BinaryNode( L& l, R& r ) : _l(l),_r(r) {}T eval( T x ) const{ return OP::apply(_l.eval(x),_r.eval(x)); }

private :L _l;R _r;

};

FIG. 3.9 – Classe template BinaryNode

Par exemple, le noeud représentant la sous-expression "1+x" a pour type :

BinaryNode<T,Const<T>,Var<T>,OpAdd>

Pour faciliter la gestion de tel noeud, on utilise ici une technique dite de templateanonyme. Cette technique permet d’encapsuler au sein d’un template un type d’unecomplexité arbitraire. Ainsi les typesL et Rpeuvent en fait être eux même des typeinsatncié à partir deBinaryNode .

En se basant sur la règle de grammaireexpr := val | expr OP expr, il estalors possible d’introduire une classe permettant de manipuler une sous-expressionquelconque. Ainsi, la classeExpr (fig. 3.10) sert de modèle pour l’ensemble des ex-pressions et sous-expressions d’un AST. Ses deux paramètres templates permettentde spécifier le type de données manipulé (paramètre T) et le type de l’expression enelle même (paramètre E).

template<class T, class E> class Expr{public :

Expr( E& xpr) : _xpr(xpr) {}T eval( T x ) const {return _xpr.eval(x); }

private :E _xpr;

};

FIG. 3.10 – Classe template Expr

33


La construction des types correspondants à une expression quelconque peut alorsêtre effectuée. Ainsi, l’expression donnée en exemple ci dessus (x/(1+x)) s’encodede la manière suivante (fig. 3.11) :

_..+

Expr<BinaryNode<Var,Expr< >,OpDiv> >

Expr<BinaryNode<Const,Var,OpAdd> >

x/(1+x) => Expr<BinaryNode<Var,Expr<BinaryNode<Const,Var,OpAdd>>,OpDiv>>

Var

VarConst

FIG. 3.11 – Reconstruction du type associé à x/(1+x)

Il est évident que la génération de tel type de donnée ne doit pas être laissé à lacharge de l’utilisateur final. Nous verrons plus loin comment gérer ces construc-tions.

Autre point important, la présence de la méthodeeval dans les interfaces des deuxclasses. Cette méthode est le point d’entrée qui sera utilisé par le compilateur pourproduire le code inline idéal et évaluer les aspects dynamique de l’expression. Lesdétails de cette méthode seront donnée plus loin.

34


2. Les classes décrivant les opérations au noeuds de l’AST.

Ces classes definissent un type pour chaque opérateur arithmétique utilisable dansl’AST. Par exemple la classeOpAddreprésente l’utilisation de l’opérateur + au seind’une expression (cf fig. 3.12) :

template<class T> struct OpAdd{

static inline T apply( T l, T r ) { return l+r; }};

FIG. 3.12 – Classe template OpAdd

On définit de même les classesOpSub,OpDiv , etc ... pour chaque type d’opéra-teur arithmétique. Il est aussi possible d’étendre ces classes pour leur permettre dereprésenter n’importe quelle fonction numérique comme le logarithme ou la racinecarré. Grâce aux propriétés d’inlining implicite des templates, le code de la mé-thodeapply se retrouve réinjecté au point même de son appel.

3. Les classes décrivant les données à évaluer à l’exécution.

Ces classes servent demarqueur(ou placeholder) au sein de notre représentationde l’arbre et se positionnent à l’emplacement d’une donnée de type dynamique quidevra être évaluée à l’exécution. Dans un premier temps, il est suffisant de considé-rer deux classes : la classeVar qui va représenter les données variables (fig. 3.13) :

template<class T> struct Var{

Var() {}T eval( T x ) const { return x; }

};

FIG. 3.13 – Classe template Data

et la classeConst qui va représenter une donnée de type constante (fig. 3.14) :

35


template<class T> class Const{public:

Const ( T& val) : _v(val){}T eval( T x ) const { return val; }

private:T _v;

};

FIG. 3.14 – Classe template Const

Ces deux classes exposent dans leur interface la méthodeeval décrite plus haut.

A partir de l’ensemble de ces classes et de leurs différentesspécialisations, il est re-lativement simple de fournir un mécanisme de construction de type pour des expressionsarithmétiques. Une simple surcharge des opérateurs arithmétiques du C++ permet à l’uti-lisateur d’écrire simplement des expressions et de générerle code statique correspondant.Grâce à ces opérateurs, il est possible de décrire de façon simple et lisible des expressionstout en permettant leur encodage automatique sous la forme d’un type C++. Bien sur, ilest nécessaire de fournir une version de chaque opérateur (+,-,*,/) pour chaque configura-tion possible des noeuds de l’arbre correspondant aux règles explicitées sur la figure 3.8.Ainsi, l’opérateur + appliqué à des variables de types Var<T> s’exprime ainsi (fig. 3.15) :

template<class T>Expr< BinaryNode<Var<T>,Var<T>,OpAdd<T>>>operator+( const Var<T>& l, const Var<T>& r ){

typedef BinaryNode<Var<T>,Var<T>,OpAdd<T>> expr_t;return Expr<T,expr_t>( expr_t(l,r) );

}

FIG. 3.15 – Opérateur + générateur de donnée statique

Si l’on se dote de l’ensemble des opérateurs classiques, l’écriture

Data<double> x;integrate( x/(1+x), 0,10);

se résout alors ainsi :

Data<double> x;integrate( operator/( x, operator+( 1, x ) ), 0,10);

36


3.1.3 Evaluation des données dynamiques

A partir de ces mécanismes de reconstruction, on obtient donc à la compilation uneinstance de la classeExpr qui contient l’ensemble des informations de structures néces-saires à l’évaluation de l’expression associée. L’évaluation proprement dite de cette ex-pression utilise la méthodeeval fournie par chacune des classes utilisées précédemmentpour décrire les données statiques de l’expression. Cette méthode à pour but de calculerune valeur de chaque variable de l’expression. La fonctionintegrate devient donc :

template<class E>double integrate( Expr<E>& expr, double s, double e ){

static const double dx = 0.01;double r = 0.0;for(int x=s;x<e;x+=dx) r += dx*expr.eval(x);return r;

}

FIG. 3.16 – Code de la fonction integrate

Lors de la compilation, l’appelle de la méthodeeval de l’objetExpr<E> va déclen-cher une série de résolution d’appel de fonction template etdonc produire un code inlinede manière récursive (fig. 3.17).

expr._xpr.eval(x)=> BinaryNode<T,Data<T>,Expr<E>,OpDiv>.eval(x)=> OpDiv::apply( _l.eval(x),_r.eval(x) )

<= _l.eval(x)=> x;

<=_r.eval(x)=> BinaryNode<T,Data<T>,Const<T>,OpAdd>.eval(x)=> OpAdd:apply( _l.eval(x),_r.eval(x) );

<= _l.eval(x)=> x;

<= _r.eval(x)=> 1;

=> 1+x=> x/(1+x);

FIG. 3.17 – Chaîne d’évaluation d’une expression

Dans ce schéma les symboles=> et <= représentent respectivement l’appel et la ré-duction d’un niveau de la récursion.

37

3.2. APPLICATION

Une fois cette réduction effectuéeà la compilation, le code permettant de calculerexpr(x) est déroulé automatiquement à l’emplacement précis où cette évaluation est de-mandée. Le code final ne contient donc aucun appel de fonction. Sur cette exemple, cecode final est donnée sur la figure 3.3.

3.2 Application

la technique de méta-programmation par templates présentée au paragraphe précédentpeut s’appliquer à la manipulation et au calcul sur des vecteurs numériques [19, 22] eten particulier à des vecteurs basés sur les types AltiVec. Elle permet alors de pallier à lamajeure partie des inconvénients mis en évidence au paragraphe 2.2.2.

Afin de permettre une utilisation simple desExpressions Templatesau sein d’uneclasse de vecteur numérique, il faut modifier à la fois l’interface classique d’une cetteclasse vecteur et les différents composants du mécanisme d’expressions. En fournissantune version spécialisé de l’opérateur d’affectation pour la classe vecteur, on reconstruitun mécanisme similaire à celui de la méthodeeval . Plus précisément, on peut concevoirun squelette de classe qui encapsule ces principes (fig. 3.18) :

template<class T> class Vecteur{public:

template<class E> Vecteur<T>& operator=( const Expr<T,E> & xpr ){

for( int i=0;i<_t;i++) _data[i] = xpr.eval(i);return *this;

}

T* begin() { return _data; }private:

int _t;T* _data;

};

FIG. 3.18 – Squelette d’une classe mêlant vecteur numérique et E.T

Dans cette classe minimale, l’opérateur d’affectation joue alors un rôle équivalent à ce-lui de la méthodeeval . Il prend comme argument une instance de la classeExpr<T,E>qui contient l’expression que l’on désire évaluer et affecter au vecteur. Le code de cet opé-rateur se déroule de la même manière que le code de la fonctionintegrate vu plus hautet génére en particulier un code inline. La principale différence avec la présentation faiteprécédemment consiste à remplacer les classesplaceholderpar des itérateurs pointant

38

3.2. APPLICATION

vers les données contenus dans un tableau numérique. On reformule la méthodeeval , laclassevar et les opérateurs arithmétique de la manière suivante :

1. La méthodeeval utilise un paramètre supplémentaire qui définit l’indice del’élé-ment à évaluer. Par exemple, la classeBinOp devient :

template<class T, class L, class R, class OP>class BinaryNode{public :

BinaryNode( L& l, R& r ) : _l(l),_r(r) {}T eval( int i ) const{ return OP::apply(_l.eval(i),_r.eval(i)); }

private :L _l;R _r;

};

FIG. 3.19 – Classe template BinaryNode modifiée

2. La classeVar sert désormais de conteneur pour les itérateurs sur les données nu-mériques (fig. 3.20) :

template<class T> class Var{

public:Var( T* val) : _data(val) {}T eval( int i ) const { return _data[i]; }

private:T* _data;

};

FIG. 3.20 – Classe template Var modifiée

De même, la classeConst subit le même type dez modification :

39

3.2. APPLICATION

template<class T> class Const{

public:Const( T val) : _data(val) {}T eval( int ) const { return _data; }

private:T _data;

};

FIG. 3.21 – Classe template Const modifiée

3. Les opérateurs arithmétiques utilisent désormais directement des instances de laclasseVecteur pour construire les expressions (fig. 3.22 :

template<class T>Expr< BinaryNode<Data<T>,Data<T>,OpAdd<T>>>operator+( const Vecteur<T>& l, const Vecteur <T>& r ){

typedef BinaryNode<Data<T>,Data<T>,OpAdd<T>> expr_t;return Expr<T,expr_t>( expr_t(Data(l.begin()),Data(r. begin())) );

}

FIG. 3.22 – Opérateur + modifié

Nous disposons désormais de l’ensemble des techniques nécessaires pour développerune classe de vecteur numérique utilisant l’extension AltiVec de manière performante.Nous allons donc aborder dans le chapitre suivant les détails de conception et de fonc-tionnement d’une telle classe.

40

Chapitre 4

La bibliothèque E.V.E

L’ensemble des travaux issus des techniques présentées au chapitre 3 a permis la réa-lisation d’un bibliothèque de gestion des tableaux numériques utilisant les fonctionnalitésd’AltiVec de manière efficace. Cette bibliothèque nommée E.V.E 1 est décrite dans sesgrandes lignes dans ce chapitre.

4.1 Présentation de l’interface

L’interface de E.V.E a été conçue pour permettre une utilisation intuitive et naturelledes fonctionnalités offertes par AltiVec. Pour ce faire, cette interface reprend le schémades classes et fonctions de la STL2 afin de permettre un portage simple d’applicationsexistantes et de fournir un cadre familier aux développeurs. Le but de ce chapitre estde présenter comment E.V.E peut s’utiliser au sein d’une application et quels sont lesdifférents niveaux de fonctionnalités que la bibliothèquepropose.

4.1.1 Mise en place de E.V.E

La bibliothèque E.V.E est utilisable via un nombre restreint de fichiers en-têtes. Pourutiliser E.V.E au sein d’un programme, il suffit donc d’inclure ces fichiers dans les sourcesde l’application. Par la suite, l’ensemble des classes et fonctions de E.V.E sont accessiblesvia lenamespaceeve . Un programme minimaliste utilisant E.V.E se présente alors ainsi(fig. 4.1) :

1acronyme deExpressive Velocity Engine.2Standard Template Library

4.1. PRÉSENTATION DE L’INTERFACE

// En-têtes strictement nécessaires.#include <EVE/eve.h>#include <EVE/array.h>

// utilisation du namespace eveusing namespace eve;

// Le reste de l’application

FIG. 4.1 – Initialisation de E.V.E

E.V.E supporte toutes les directives de compilations de la STL et se comporte de ma-nière standard vis à vis de ces directives. Pour plus de details, on peut se reporter à [18].

Au niveau de la compilation, un certain nombre d’options sont à utiliser. Pour lescompilateurs de la famille GCC 3.x, les options suivantes doivent être ajoutées au optionsclassiques de compilations :

-faltivec -ftemplate-depth-512 -finline-functions -fin line-limit=1000

FIG. 4.2 – Option de compilation de E.V.E

Sur certaines machines, l’option-finline-limit=1000 peut conduire à des tempsde compilations extrêmement long. Il est possible de diminuer ce temps de compilationen utilisant des valeurs de 500 à 2003.

4.1.2 Fonctionnalités de base

E.V.E repose principalement sur la classearray , pendant de la classevalarraydela STL, qui encapsule le concept de tableaux numériques. La classearray permet lacréation et la manipulation de tableaux de dimension 1 ou 2 etde taille fixe, connue à lacompilation et supporte un nombre restreint de type de données :

bool , float , (un)signed int , (un)signed short , (un)signed char .

Les schémas suivants sont alors possibles (fig. 4.3) :

3On peut noter ici que le manuel de GCC 3.1 nous encourage à utiliser des valeurs proches de 50000 dans le cas d’unutilisation poussée des templates. Des tests effectués avec une telle valeur en paramètres conduits à une compilation deplusieurs minutes pour une simple différence entre deux tableaux et plus devingt-cinq minutes pour une convolutionpar un masque 7x7. Il est donc nécessaire de bien considérer le rapport temps de compilation/gain final.

42


#include <vector>#include <EVE/eve.h>#include <EVE/array.h>using std::vector;using namespace eve;

float tab_classic[64];vector<signed short> stl_vector(128);

// Déclaration d’un tableau de 15 flottantsarray<float,15> tab1;

// Déclaration d’un tableau de 256*256 entiers 8 bits.array<signed char,256,256> tab2;

// Déclaration d’un tableau de 1000 bool initialisé à falsearray<bool,1000> tab3(false);

// Déclaration d’un tableau de 7*7 256*256 entiers 8 bits.// initialisé à partir de tab3array<signed char,256,256> tab4(tab3);

// Déclaration d’un tableau de 256*256 entiers 8 bits// initialisé à partir d’une expression de arrayarray<signed char,256,256> tab5(2*tab2-tab4);

// Déclaration d’un tableau de 8*8 flottants// initialisé à partir d’un tableau C classiquearray<float,8,8> tab6(tab_classic);

// Déclaration d’un tableau de 128 entiers 16 bits// initialisé à partir d’un vector de la STLarray<signed short,128> tab7(stl_vector.begin());

FIG. 4.3 – Utilisation dearray

La classearray fournit aussi une surcharge pour les opérateurs arithmétiques et lo-giques classiques. Les opérateurs=, +, - , / , * , <<, >>, ! , &, | , ~, ^ , +=, -= , *= , /= , &=,|= , ^= , <<=, >>= sont présents et surchargés de façon à générer un code utilisant de ma-nière efficace les fonctionnalités AltiVec. Tous ces opérateurs prennent en charge les opé-rations entrearray et des types scalaires. Sont aussi surchargés certaines fonctions del’en-têtemath.h , à savoirabs , ln , log , exp , trunc , round , ceil , floor , sqrt ,min , max, average . Toutes ces fonctions opèrent élément par élément et conserventleur caractère binaire ou unaire. Par exemple :

43


#include <EVE/eve.h>#include <EVE/array.h>using namespace eve;array<unsigned char,512,512> x,y,z,a,b,c;

// Pour tout i,j de 0 à 511 :

// z(i,j) = a(i,j) = b(i,j) = c(i,j) = 4;z = a = b = c = 4;

// x(i,j) = (2*a(i,j)+b(i,j))*ln(c(i,j))+2x = (2*a+b)*ln(c)+2;

// y(i,j) = (a(i,j)-2*b(i,j))/sqrt(c(i,j))y = (a-2*b)/sqrt(c);

// z(i,j) = z(i,j) + 3*min((a(i,j),b(i,j)])z += 3*min(a,b);

FIG. 4.4 – Fonctions et opérateurs dearray

array propose aussi un ensemble d’opérateurs et de fonctions dédiées aux tests boo-léens. Les opérateurs&&,|| ,==,!= ,<=,>=,> et < permettent d’effectuer des testsélé-ment par élémententre deuxarray et renvoient unarray<bool> comme résultat.Pour effectuer des test booléens utilisables dans des structures de controles classiques, ilest nécessaire d’utiliser les fonctions suivantes :

for_all exists

Ces fonctions permettent donc d’effecteur des tests entre vecteur et/ou entre expres-sion :

if(exists(v1 > v3)) puts("condition 1 remplie") ;

if(for_all(v1 == v2)) puts("condition 2 remplie") ;

Dans cette exemple, la phrase "Condition 1 remplie" s’affiche si et seulement si aumoins un élément du vecteurv1 est supérieur à son correspondant dans le vecteurv3 .C’est à dire si∃ i, v1[i] > v3[i]. La phrase "Condition 2 remplie" s’affiche si tous leséléments dev1 sont égaux à ceux dev2 .

44


La classearray fournit aussi des méthodes de calcul inter-éléments. Ces méthodespermettent de déterminer respectivement la somme des éléments du tableau, leur mini-mum, leur maximum.

array<float,16,16> v;float r,m;

// Somme des éléments de vr = v.sum()

// Minimum & maximum de vm = v.min()m = v.max()

// Moyenne des éléments de vr = v.average()

FIG. 4.5 – Fonctions inter-éléments

Grâce à l’ensemble de ces opérateurs et fonctions, il est possible d’implanter un cer-tain nombre d’algorithme simple. La figure 4.6 donnent l’exemple de deux algorithmesde traitement d’image écrits grâce à E.V.E :

array<unsigned char,512,512> res,img1,img2;

// Inversion d’une imageres = ~img1;

// Différence d’imageres = img2 - img1;

FIG. 4.6 – Exemple d’utilisation de E.V.E

Enfin, la classearray fournit un ensemble de mécanisme permettant d’initialisersimplement un vecteur ou une matrice. Tout d’abord, il est possible d’utiliser deslistesd’initialisation explicite :

Si la taille de la liste est inférieure à celle du tableau, leséléments non initialisées sontlaissés en l’état. Si la liste est plus grande que le tableau,une erreur de compilation seproduit.

la classearray supporte aussi l’initialisation par équation d’indice. L’en-têteEVE/util.h

45

4.2. ALGORITHMES ET PRIMITIVES DE PLUS HAUT-NIVEAU

array<float,7> mask;array<unsigned char,3,3> img;

mask = 0.25, 1, 0.25;

img = 1, 5, 1,9, 7, 9,1, 5, 1;

FIG. 4.7 – Liste d’initialisation dearray

fournit deux type :first_index etsecond_index qui représentent respectivementles indices verticaux et horizontaux dearray . Ces deux types peuvent être manipuléescomme des éléments arithmétiques au sein d’une expression.Les écritures suivantes sontalors possibles :

array<unsigned float,3,3> A;array<unsigned char,16> B;util::first_index i;util::second_index j;

// A(i,j) = 1/(i+j) pour i,j=0..2A = 1/i+j;

// B(i,j) = 3*exp(i)+1 pour i=0..15B = 3*exp(i)+1;

FIG. 4.8 –array et la notation indicielle

L’utilisation d’un second_index dans une expression affectée à un tableau mono-dimensionel provoque un erreur de compilation.

4.2 Algorithmes et primitives de plus haut-niveau

L’ensemble des algorithmes exprimables grâce à E.V.E ne se limitent pas aux quelquesexemples données au paragraphe précédent. E.V.E propose toute une série de fonctionsplus évoluées qui permet d’exprimer plus facilement certains types d’algorithmes. Cesfonctions et classes sont regroupées dans l’en-têteEVE/algorithm.h et sont optimi-sées pour gérer certains cas particuliers de manipulationsde tableaux numériques :

1. La fonctionwhere permet d’effectuer une mise à jour sélective d’un tableau à par-tir de l’évaluation d’unprédicat P, c’est à dire une expression dont l’évaluation

46


retourne un tableau de booléen. Son prototype est le suivant:

template <class T,class E1,class E2,int W,int H>inline boolean_evaluator<T,E1,E2,W,H>where( array<bool,W,H>& pred, expr<T,E1>& xpr1, expr<T,E 2>& xpr2 );

FIG. 4.9 – Prototype de la fonctionwhere

Lorsque la création d’un vecteur peut s’exprimer de la manière suivante :

v[i] =

{

e1[i] si P[i]e2[i] sinon

Cet algorithme est transcrit en une version AltiVec optimisée et s’utilise de la ma-nière suivante :

array<signed char,512,512> img,res;signed char seuil = 140;

// Binarisation d’une imageres = where( img > seuil, 0, 255);

// Selection par expressionres = where( abs(img) >= 1, 1, 2-abs(img) );

FIG. 4.10 – Exemple d’utilisation de la fonctionwhere

2. La fonctionfold implante la primitive dereductionprésenté au chapitre 1. Ellepermet d’effecteur des réductions d’opérations sur le contenu d’unarray . Sonprototype est le suivant :

template <class O, class T, int W, int H>T fold( array<T,W,H>& source, const T& zero );

FIG. 4.11 – Prototype de la fonctionfold

fold prend donc en argument le tableau à réduire et la valeur initiale de la ré-duction. L’opérateur à utiliser lors de la réduction est passé en paramètre template.Les opérateurs utilisables comme argument defold sont accessibles par l’en-têteEVE/util.h . Il est possible de créer ces propres opérateurs utilisablepar folden suivant le modèle fournit par la classeutil::op_exemple .

47


La fonctionfold s’utilise alors comme ceci :

array<signed char,512,512> img1;signed char m,s;

// Produit des élément d’un tableaum = fold<util::multiplies>( img1, img1[0] );

// Somme des éléments d’un tableauxs = fold<util::plus>( img1, 0 );

FIG. 4.12 – Exemple d’utilisation de la fonctionfold

3. Les fonctions de filtragesE.V.E fournit un ensemble de fonctions destinées au filtragede signaux 1D ou 2D.Deux manières de procédés sont fournies :

– Une fonction de filtrage générique :filter.cette fonction prend en argument un tableau quelconque et untableau monodi-mensionel servant de masque de convolution.filter effectue alors un produitde convolution entre le tableau de données et le masque et produit un tableau ré-sultat contenant le produit de convolution souhaitée.

array<unsigned char,256,256> tab;array<unsigned char,1,3> mask;

mask = 1,2,1;tab = filter(tab,mask);

FIG. 4.13 – Exemple d’utilisation de filter

– Des fonctions de filtrage spécialisés :filter_h_x et filter_v_x.E.V.E fournit une famille de classes permettant de générer de sproduite de convo-lutions à coefficients constants. Leur utilisation doit être préférée à celle de lafonctionfilter dans les cas ou les composants du masque de convolution sontconstants. Les classes fournit sont :

// Filtres horizontauxfilter_h_3 à filter_h_15

// Filtres verticauxfilter_v_3 à filter_v_15

48

4.3. UTILISATION CONJOINTE DE E.V.E ET DE LA STL

Leur utilisation est très simple :

array<unsigned char,256,256> tab;filter_h_3<1,2,1> gauss_x;filter_v_3<-1,0,1> grad_y;

tab = gauss_x(tab);tab = grad_y(tab);

FIG. 4.14 – Exemple d’utilisation des filtres constants

Les versions ultérieures de E.V.E permettront de générer uncode optimisées pour lacomposition des filtres ainsi qu’un support pour les filtresNxM.

4.3 Utilisation conjointe de E.V.E et de la STL

E.V.E n’a pas pour but de se substituer entièrement à la STL mais de fournir uneimplantation optimisée pour certaines de ses fonctionnalités. Plusieurs fonctionnalités deE.V.E sont en fait prévues pour permettre une inter-opérabilité entre ces deux biblio-thèques.

4.3.1 Gestions des itérateurs

La classearray fournit un ensemble de méthodes qui permet d’utiliser des itérateurscompatibles avec les itérateurs fournis et attendus par la STL. Les méthodesbegin ,end etposition permettent d’obtenir un itérateur utilisable dans d’autres fonctions dela STL non surchargées par E.V.E. Un exemple d’utilisation est par exemple le tri d’unarray :

array<unsigned char,256,256> tab;array<unsigned char,256,256>::iterator it;//tab est rempli de valeur aléatoire.std::fill( res.begin(), res.end(), rand() );

// tab est trié par std::sort via ces itérateursstd::sort( res.begin(), res.end() );

// Récupération de l’itérateur sur le 25e élément de tabit = tab.position(25);

FIG. 4.15 – Exemple d’utilisation des itérateurs de E.V.E.

49


4.3.2 Fonctions classiques de la STL

E.V.E surcharge les fonctions classiques de la STL, à savoir:

partial_sum inner_productcount_if countadjacent_difference

Ces fonctions prennent directement unarray en paramètre et effectuent leur calculsur l’ensemble des données contenues dans ce dernier. Ces opérations sont optimiséesde manière à tirer partie d’AltiVec (fig. 4.16). Leurs versions utilisant des itérateurs sontaussi utilisable mais ces dernières ne peuvent pour des raisons techniques être totalementoptimisées. Il en est de même avec les fonctions de la STL non présentées ici [18] : ellesne peuvent être utilisées directement sur un paramètre de typearray mais sont utilisablepar l’intermédiaire des itérateurs fournis par les méthodes vus au paragraphe précédent.

util::first_index i;util::second_index j;array<unsigned char,4,4> res,x,y,z;res = i+j;

// Version optimisée AltiVecx = adjacent_difference(res);

// Versions non-optimiséesy = adjacent_difference(res.begin(),res.end());copy( z.begin(), z.end(), y.begin(), y.end() );

FIG. 4.16 – Utilisation conjointe de EVE et des fonctions de la STL.

4.3.3 E.V.E et les flux standards

E.V.E se comporte de manière standard vis à vis des classes deflux de la STL. Lesopérateurs<< et >> sont surchargées pour toutes les classes de l’en-têteiostream etfstream . Le code suivant est donc parfaitement valide :

50


std::ifstream file_in("in.txt");std::ofstream file_out("out.txt");

util::first_index i;util::second_index j;array<unsigned char,4,4> res;

// res(i,j) = i+j pour i,j=0..3res = i+j;

std::cout << res << std::endl;

file_in >> res;where( res >127, 0, 255 );file_out << res;

FIG. 4.17 – Utilisation conjointe de EVE et des flux standards.

Lors de l’utilisation directe de<< et >>, les données contenues dans unarray sontécrites ou lues sur le flux de manière brute. Pour lire ou écrire ces valeurs de manière pluslisibles, on peut utiliser les méthodesprint_on et read_from .

#include <iostream>#include <EVE/eve.h>#include <EVE/array.h>

using namespace eve;

// Sortie sur le flux standard.res.print_on(std::cout);

// Lecture sur le flux standard.res.read_from(std::in);

FIG. 4.18 – Méthodesprint_on et read_from .

Les sorties respectives des exemples des figures 4.17 et 4.18sont données ici :

51


Sortie figure 4.170 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6

Sortie figure 4.18array :

size = 4x4content =

[ 0 1 2 31 2 3 42 3 4 53 4 5 6 ]

FIG. 4.19 – Comparaisonprint_on et cout .

52

Chapitre 5

Performances de E.V.E

5.1 Opérations élémentaires

Ces algorithmes sont des exemples simples de calculs appliqués au traitement d’images.L’accélération est mesurée entre le code C séquentiel et le code utilisant la bibliothèqueE.V.E. Le protocole utilisé consiste à exécuter le programme test sur une image de réfé-rence pour un grand nombre d’itérations (généralement 10000) et d’effectuer une moyennedes accélérations mesurées. L’ensemble des exécutables furent compilés sur une machinePPC G4 2x1.2GHz pourvue de 768 Mo de mémoire vive grâce à gcc 3.3. les codes utili-sant E.V.E furent compilés avec les options présentés au chapitre 4 et les codes séquentielsont étét compilés avec l’option -O3.

5.1.1 Principes

Inverseur d’image

L’inversion d’une image consiste à remplacer chaque pixel de l’image original parson complément à 2 dans l’image de sortie. Pour des images en 256 niveau de gris, cetteopération revient à calculer la différence entre 255 et la valeur du pixel courant.

Soustraction de deux images

Cette opération effectue la soustraction des valeurs des pixels de deux images.

5.2. ALGORITHMES DE LA STL

5.1.2 Code E.V.E

array<unsigned char,256,256> original,resultat;resultat = 255 - original;

FIG. 5.1 – Inverseur d’image

array<unsigned char,256,256> img1,img2;array<unsigned char,256,256> resultat;resultat = img1 - img2;

FIG. 5.2 – Soustracteur d’image

5.1.3 Performance :

Le tableau 5.3 liste les accélérations mesurées pour les deux algorithmes précédentspour des tailles d’image croissantes. La référence prise pour le calcul d’accélération est letemps d’exécution du dit algorithme écrit en C séquentiel. On observe ainsi que pour unelarge fourchette de taille d’image1, l’accélération fournit par E.V.E varie entre 7 et 12.Par contre, pour des échantillons de très grande tailles, l’accélération s’effondre. Cetteeffet est du à un mauvais remplissage du cache de donnée de l’unité AltiVec et peut êtrecontrebalancée via l’utilisation de primitives spécifiques2.

Taille Inverseur Soustracteur64x64 6.84 8.22

128x128 7.92 11.56

256x256 9.97 11.43

512x512 4.87 1.78

1024x1024 2.54 1.52

FIG. 5.3 – Performances des algorithmes simples.

5.2 Algorithmes de la STL

Ces tests mettent en évidence les performances de E.V.E sur des algorithmes repro-duisant des fonctions classiques de la bibliothèquealgorithm de la STL. Ces tests sonteffectués selon les mêmes modalités que les précedents maissont réalisés sur l’ensemble

1entre 64x64 et 1024x1024 typiquement2comme l’instructionvec_dst

54

5.2. ALGORITHMES DE LA STL

des types de données fournies par E.V.E. Pour référence lorsdu calcul de l’accélération ,nous utilisons les temps de calcul des algorithmes fournient par la STL.

5.2.1 Produit-somme interne

Ce test concerne la fonctioninner_product . Cette fonction est une fonction deréduction scalaire qui calcule la quantité suivante :

R =∑

a[i] ∗ b[i]

Performance :

Taille char short long float16x16 1.38 1.29 0.90 2.32

32x32 1.75 2.03 0.95 9.94

64x64 3.28 2.86 1.11 16.71

128x128 4.23 3.66 1.24 13.83

256x256 4.68 2.94 1.36 6.50

512x512 3.25 1.90 1.16 3.52

1024x1024 2.01 1.49 1.07 3.24

FIG. 5.4 – Performances du produit-somme interne.

5.2.2 Analyse :

Il faut noter l’asymétrie certaine des résultats entre les types entiers et flottants. Eneffet, l’accélération théorique des types entiers atteint16,8 ou 4 et celle du type flottantatteint 4. Or ici, nous obtenons des accélérations très inférieures à ces maxima théoriquespour les types entiers et supérieures à ces maxima pour les flottants. Deux phénoménessont ici en cause :

– une faiblesse relative de l’unité flottante scalaire.Cette unité possède en effetmoins d’étages de pipeline que son homologue vectorielle etest légèrement moinsrapide lors des accès au cache de donnée. L’unité AltiVec bénéficie donc d’unemeilleur architecture globale en plus de son caractère vectoriel ce qui augmentegrandement les accélérations sur ce type de données.

– le manque d’utilisation des instructions de manipulation du cache.Aucune desinstructions permettant de précharger des données n’a été utilisée dans toutes les

55

5.3. UN DÉTECTEUR DE POINT D’INTÉRÊT

fonctions de E.V.E. Cette lacune se justifie par un temps de développement restreintet produit donc ces résultats sous-linéaires. Une prochaine version de E.V.E permet-tra de manipuler ces instructions et donc de limiter ces pertes.

– les transtypages implicites.Il n’existe pas pour les types entiers 8 bits et 32 bitsde fonctions de multiplication-addition. Pour parvenir à effectuer le calcul correcte-ment, les types entiers doivent être transtypés en flottantsou en entiers 16 bits. Cestranstypages sont coûteux et ralentissent d’autant les calculs.

5.3 Un Détecteur de point d’intérêt

5.3.1 Principe

Cet exemple à pour but de montrer comment un algorithme complexe peut être ex-primé via l’interface de E.V.E. Pour cela, nous avons choisis de reprendre un detecteur depoint d’interêt, le detecteur de Harris [23]. Ce détecteur repose sur l’algorithme suivant :

Pour une image donnéeI(x, y), on effectue un lissage par un filtre gaussien horizontalet vertical. Ensuite, pour chaque pixel(x, y) on calcule :

M(x, y) =

(

( ∂I∂x

)2 ∂I∂x

∂I∂y

∂I∂x

∂I∂y

(∂I∂y

)2

)

Dans le cas d’une image numérique, ces gradients sont calculés via un filtrage par desfiltres adéquats. On lisse ensuiteM(x, y) par une filtre gaussien vertical puis horizontal.On évalue enfin la quantité :

H(x, y) = Det(M) − k.trace(M)2, k ∈ [0.04; 0.06]

On retient ensuite les maxima locaux deH supérieur à0.0001||H||∞

.

Ces principaux avantages sont d’être invariant aux rotations de l’images sources, d’êtremoins sensible au bruit que d’autres détecteurs du même types (Détecteur de Moravec parexemple) et de finalement retenir un nombre de points limités.

On présente ici le résultat de l’application du détecteur à une image tiré d’une sé-quence video :

56


FIG. 5.5 – Application du détecteur de Harris

5.3.2 Mise en oeuvre

Notre implémentation se concentre sur l’optimisation les phases de filtrages et de dé-tection de points d’intérêt. Avec E.V.E, les deux parties optimisées sont donc le filtragede l’image initiale et le calcul de la matriceM . Ces deux parties peuvent se coder ainsi :

array<signed short,320,240> img,a,b,c,t1,t2;array<float,320,240> H;filter_h_3<1,2,1> smooth_x;filter_v_3<1,2,1> smooth_y;filter_h_3<-1,0,1> grad_x;filter_v_3<-1,0,1> grad_y;

// Filtraget1 = smooth_x(img);t2 = smooth_y(img);t1 = grad_y(t1);t2 = grad_x(t2);

a = t1*t1;a = smooth_x(a);a = smooth_y(a);b = t2*t2;b = smooth_x(b);b = smooth_y(b);c = t1*t2;c = smooth_x(c);c = smooth_y(c);

// EvaluationH = (a*b-c*c)-0.06*(a+b)*(a+b);

FIG. 5.6 – Filtrage et Evaluation du détecteur de Harris

57


5.3.3 Performances

Les performances de ce détecteur furent mesurées par rapport à une implantation sé-quentiel en C. Les mesures ont été réalisé sur des images 320*240 en utilisant une versionnon définitive de l’API de E.V.E. Les résultats concernants les filtrages sont donc poten-tiellement biaisés. On donne pour comparaison les performances du même algorithmeimplanter sur un Pentium IV 2.4GhZ utilisant MMX et SSE2.

Temps d’execution Accélération Accélération Théorique1.83ms 5.38 8

FIG. 5.7 – Performances du détecteur de Harris - Filtrage.

Temps d’execution Accélération Accélération Théorique1.06ms 1.22 4

FIG. 5.8 – Performances du détecteur de Harris - Evaluation de H.

Plate-forme TempsPPC G4 + E.V.E 2.9ms

Pentium 4 + MMX-SSE2 5.5ms

FIG. 5.9 – Comparaison de performances PPC G4/Pentium IV.

5.3.4 Commentaires

Les résultats obtenus confirment que E.V.E génère un code relativement efficace.Néanmoins, les performances obtenues restent assez loin des performances théoriquesmaximales. Plusieurs cause à cela :

– Au niveau du filtrage : les filtres sont appliqués les uns après les autres. Chaqueappel de filtre génère une boucle de traitement et de chargements. Or pour un codeAltiVec écrit à la main, ce genre d’appel serait réduit par lefait que le program-meur aurait auparavant effectuée la composition des filtrespour se retrouver avecune seule boucle de traitement.

– Au niveau de l’évaluation : l’implantation actuelle des opérateurs arithmétiquesde E.V.E ne permet pas de différencier les instances des tableaux utilisés. Ainsi, lecode correspondant àa*a va charger deux fois le vecteur a en mémoire à chaqueitération. Il n’existe pas de moyen simple d’eviter ce problême.

58


– Globalement : c’est l’absence de préchargement du cache qui grève encore lesperformances. La résolution simple du problème de spécifierles stratégies de pré-chargement expression par expression est un problème ouvert qui sera intéressantde régler par la suite.

L’ensemble de ces points seront certainement étudiés plus avant et intégré à une futureversion de E.V.E, ce qui permettrait de se rapprocher encoredes performances obtenuespar un code écrit spécialement pour ce genre d’applications.

59

Conclusion

La bibliothèque E.V.E est encore incomplète. De nombreusesfonctionnalités sont àce jour encore à développer ou à corriger. Néanmoins, les premiers essais nous montrentque l’utilisation des techniques avancées de la programmation orientée objet telle que laMeta-Programmation Template s’avère une stratégie payante. De nombreuses fonction-nalités supplémentaires sont envisageables grâce a cette technique (composition de filtre,élimination d’invariant de boucles, etc.). Elle permettradonc de compléter rapidementl’API de E.V.E. parmi ces fonctionnalités, la résolution duproblème des stratégies de pré-chargement sera certainement un facteur important pour la suite du projet.

En outre, la volonté de Apple et de IBM de continuer à exploiter la technologie Alti-Vec comme par exemple au sein du processeur PPC 970 (G5) disponible depuis peu nousconforte dans l’intérêt que nous portons à cette technologie. Il est par ailleurs possibled’envisager un portage de E.V.E sur d’autres plates-formesutilisant des extensions SIMD(comme le Pentium avec MMX et SSE2). Ce portage permettrait la aussi de simplifier letravail de nombreux développeurs rebutés par la complexitéd’utilisation de ces unités.

Mais c’est dans un projet de plus grande ampleur que va venir s’insérer E.V.E. Ellesera en effet une brique de base d’environnement logiciel d’une machine parallèle hybride.Ce projet qui débutera en octobre 2003 vise à obtenir, en s’appuyant sur une utilisationconjointe de trois niveaux de parallélisme , des facteurs d’accélération supérieur à 50 pourdes algorithmes de reconnaissance et suivi d’objets.

60

Références bibliographiques

[1] L. Bougé. Le Modèle de Programmation à Parrallélisme de Données : une Perspec-tive Semantique. Technical Report 94-06, Laboratoire de l’Informatique du Parallé-lisme, ENS Lyon, 1994.

[2] C.A.R Hoare.Communicating Sequential Processes. Prentice Hall, 1985.

[3] Geraint Jones.Programming in occam. Prentice-Hall international, 87.

[4] Lyndon Clarke, Ian Glendinning, and Rolf Hempel. The mpimessage passing inter-face standard, March 94.

[5] R.H. Perrot. A Langage for Array and Vector Processors.ACM Trans. on Prog.Lang. and Syst., 1(2) :177–195, 1979.

[6] I. Foster, B. Avalani, A. Choudhary, and M. Xu. A Compilation System That Inte-grates HPF and Fortran M. In IEEE Computer Society Press, editor, Scalable HighPerformance Computing Conference, 1994.

[7] High Performance Fortran Forum.High Performance Fortran Language Specifica-tion V1.1, 1994.

[8] P. Marquet. Languages and Expressions of Data Parallelism. Technique et ScienceInformatiques, 12(6) :685–714, 1993.

[9] R. Backhouse. An Exploration of the Bird-Meertens Formalism. Technical ReportCS8810, Department of Mathematics and Computing Science, University of Gro-ningen, 1988.

[10] D.B Skillicorn. The Bird-Meertens Formalism as a Parallel Model. In J.S. Kowa-lik and L. Grandinetti, editors,NATO ARW "Software for Parallel Computation”,volume 106. Springer-Verlag NATO ASI, 1993.

[11] Fouliras and Hamlen. The Connection Machine. Technical Report QMW-DCS-1989-568, Queen Mary College, Department of Computer Science, 1989.

[12] Nathan Slingerman and Allan Jay Smith. Performance Analysis of Instruction SetArchitecture Extensions for Multimedia. Technical report, Apple Computer Inc. andUniversity of California at Berkeley, 2001.

[13] Alex Peleg and Uri Weiser. MMX Technology Extension to the Intel Architecture.IEEE Micro, 16(4) :42–50, Ao˚t 1996.

[14] Apple Velocity Engine Frequently Asked Questions. http ://developer.apple.com.

[15] Keith Diefendorf. AltiVec Extension to Power PC Accelerates Media Processing.Technical report, IEEE Micro, 2001.

[16] L. Damez. Evaluation de la Technologie AltiVec pour lesAlgorithles de VisionBas Niveau. Mémoire de DEA, Ecole Doctorale des Sciences pour l’Ingénieur,Université Blaise Pascal, Clermont Ferrand, Septembre 2002.

[17] Ian Ollman. AltiVec. http ://www.idevgames.com/fileshow.php3?showid=134, mars2001.

[18] Silicon Graphics, Inc.Standard Template Library Programmer’s Guide, 1993-2003.http ://www.sgi.com/tech/stl/.

[19] T Veldhuizen. Expression Templates.C++ Report, 7 :26–31, 1995.

[20] T Veldhuizen. C++ Templates as Partial Evaluation.C++ Report, 1995.

[21] S Karmesin and al. Arrays Design and Epression Evaluation in POOMA II. ISCO-PE’98, 1505 :38–44, 1998.

[22] T Veldhuizen. Using C++ Template Meta-Programms.C++ Report, 7 :36–43,1995.

[23] C Harris and M Stephens. A Combined Corner and Edge Detector. 4th Alvey VisionConference, 1988.

[24] M. Herbordt, J. Burrill, and C. Weems. Making a Dataparallel Language Portablefor Massively Parallel Array Computers. In IEEE Computer Society Press, editor,Int’l Workshop on Computer Architecture for Machine Perception, pages 160–169,October 1997.

[25] G. E. Blelloch. Programming Parallel Algorithms. Communications of the ACM,Mars 1996. http ://www.cs.cmu/.

[26] S. J. Gilbert. A MasPar Implementation of Data Parallelc++, Septembre 1992.

[27] Craig Lund. Altivec Introduction. Publication commerciale de Motorola, mai 2001.

[28] S Chiba. A Metaobject Protocol for C++.OOP SLA’95, pages 285–299, 1995.

[29] Y Ishikawa and al. Design and Implementation of Metalevel Architecture in C++ -MPC++ Approach.Reflection’96, 1996.

[30] D R Engler. Incorporating Application Semantic and Control into Compilation.USENIX Conference on DSL, 1997.

[31] T Veldhuizen. Arrays in Blitz++. Dr Dobb’s Journal of Software Tools, pages38–44, 1996.

[32] The C++ BOOST Library. http ://www.boost.org/.

[33] The SPIRIT Parser Framework. http ://www.boost.org/libs/spirit/index.html.

Documents

Développement d'un bibliothèque de calcul SIMD - Application au traitement d'images