Décomposition hiérarchique d’une séquence vidéo

LE MULTIFIL SUR LES SYSTÈMES MULTICŒURS

LE MULTIFIL SUR LES SYSTÈMES MULTICŒURS

Dans ce chapitre, nous introduirons brièvement quelques notions fondamentales du traitement parallèle et concurrent. Plus spécifiquement, nous mettrons l’accent sur le traitement parallèle appliqué à des systèmes multicœurs grâce au traitement multifil. Le lecteur désirant approfondir ces sujets pourra se référer aux ouvrages de (Akhter et Roberts, 2006; Butenhof, 1997; Reinders, 2007). Nous commencerons par une introduction générale sur le traitement multifil et son utilisation dans un contexte parallèle. Puis, nous présenterons trois types de système (les systèmes multiprocesseurs, les systèmes multicœurs et les systèmes dotés de la technologie HyperThreading (HT)) supportant l’exploitation parallèle du multifil. Par la suite, nous discuterons de mesures d’évaluation et de prédiction des performances d’une application parallèle. Nous invitons le lecteur à porter une attention particulière sur ces mesures de performances puisqu’elles seront appliquées à plusieurs reprises dans ce mémoire. Enfin, nous expliquerons brièvement le développement d’applications multifils. Plus spécifiquement, nous traiterons du cycle de développement d’une application parallèle, de la conception d’un algorithme parallèle et des interfaces de programmation parallèle.

Autres types de parallélismes

Il existe deux autres types de parallélisme sur les processeurs d’aujourd’hui : le parallélisme effectué au niveau des instructions et le parallélisme effectué au niveau des données (Hennessy, Patterson et Goldberg, 2003). Le premier type de parallélisme exploite l’indépendance qui existent entre certaines instructions rapprochées, afin d’exécuter plusieurs instructions en parallèle. Le traitement d’instructions en pipeline et le traitement superscalaire, qui peuvent être combinés dans une même architecture, permettent d’exploiter ce type de parallélisme. Le traitement d’instructions en pipeline divise les instructions en nombre fixe d’étapes simples qu’il exécute à la manière d’une chaîne de montage, tel qu’illustré à la figure 1.1.a. Le traitement superscalaire en pipeline est une technique améliorée du pipeline et peut être vue comme plusieurs chaînes de montage, tel qu’illustré à la figure 1.1.b. Le second type de parallélisme, plus connu sous le nom Single Instruction Multiple Data (SIMD) dans la taxonomie de Flynn (Flynn, 1966), permet de traiter plusieurs données en une seule instruction. Il est typiquement utilisé par des applications effectuant du traitement intensif sur les données, telles que les applications de traitement de signal numérique, les applications de traitement d’images et les applications multimédias traitant de l’audio et/ou du vidéo. D’abord utilisé par certains super ordinateurs et processeurs DSP (Hennessy, Patterson et Goldberg, 2003), ce type de parallélisme est maintenant offert par la majorité des ordinateurs récents sous la forme de différents jeux d’instructions étendus : MMX, SSE, SSE2, SSE3 et tout récemment SSE4 pour les processeurs Intel et AMD (Intel, 1999; Peleg et Weiser, 1996; Ramanathan et al., 2006); Altivec (Diefendorff et al., 2000) pour les processeurs PowerPC; et NEON (ARM, 2010) pour les processeurs ARM. Contrairement au parallélisme au niveau des instructions, le parallélisme au niveau des tâches nécessite généralement une participation active de l’équipe de développement, et cela, dès le départ, car il implique une conception architecturale globale pensée en terme de parallélisme. Comme nous le verrons plus loin, les concepteurs doivent choisir une architecture parallèle correspondant à leurs besoins et doivent décomposer les tâches en fonction de l’architecture choisie et du type d’application développée. Les programmeurs 10 doivent apprendre le fonctionnement des outils de développement parallèle utilisés et, dans certains cas, les fondations de l’architecture parallèle choisie.

Systèmes parallèles adaptées au traitement multifil

Les systèmes multiprocesseurs symétriques, les systèmes multicœur et les systèmes implémentant une forme de multifil simultané, par exemple, les systèmes dotés de la technologie HT d’Intel, sont, de nos jours, les trois types de technologies parallèles les plus adaptés à l’implémentation d’algorithmes parallèles basés sur le modèle multifil, puisqu’ils sont basés sur une mémoire partagée. Ces trois technologies, qui peuvent être combinés ensemble sur un même système, partagent plusieurs points communs aux niveaux système et usager, dont : • Une architecture basée sur un modèle de mémoire partagée. Ce type de modèle mémoire permet aux données de circuler rapidement d’une unité d’exécution à une autre, cependant, ce modèle nécessite l’emploi de mécanismes de cohérences entre les caches des unités. 11 • Des unités d’exécutions qui sont perçues comme des processeurs logiques par les systèmes d’exploitation communs (tels que Linux et Windows, par exemple). Comme nous le verrons plus en détail dans les trois prochaines sous-sections, ces trois types de technologie se distinguent essentiellement par leur microarchitecture. Notons qu’un système multiprocesseur (figure 1.2.b) est composé d’au moins deux processeurs intégrés sur le même support et reliés à la même mémoire par un bus, qu’un processeur HT (figure 1.2.c) est constitué de deux fils physiques qui se partagent un même ensemble d’unités d’exécution et une même cache et qu’un système multicœur (figure 1.2.d) contient au moins deux cœurs gravés sur une même puce. De plus, notons que ces technologies peuvent être intégrées dans un même système. Par exemple, la figure 1.2.e illustre un système multi-cœurs où chaque cœur est doté de la technologie HT.

La technologie Hyper-Threading

L’HT est le nom donné par Intel à son adaptation du multifil simultané (Tullsen, Eggers et Levy, 1995). Cette adaptation, apparue en 2002, consiste à intégrer deux processeurs logiques sur une même puce pour remplir plus efficacement le flot d’instructions du processeur physique. Selon (Marr et al., 2002), cette technologie permet d’augmenter la quantité d’instructions du processeur de 15 % à 30 % pour une augmentation de seulement 5 % de son nombre de transistors. En pratique, selon les mêmes auteurs, le gain de vitesse varie en fonction de l’application et peut, dans certains cas exceptionnels, être négatif. En matière d’architecture, les deux fils physiques se partagent le cœur du processeur, le bus système et une partie de la cache. Chaque fil a ses propres registres, ses états sur le système et son contrôleur d’interruptions. Un algorithme, exécuté automatiquement par le processeur, permet de sélectionner les instructions qui seront utilisées pour remplir le flot d’instructions. Quand les deux fils sont actifs, la sélection s’effectue en alternance. Si l’un des deux fils est inactif, seules les instructions du fil actif seront chargées. La cache est séparée statiquement en attribuant la moitié de la mémoire à chaque fil. Cette approche simple nécessite peu de transistors, mais a pour désavantage d’augmenter le nombre d’absences d’informations dans la cache (cache miss en anglais), lorsqu’un fil physique n’utilise pas entièrement la cache qui lui 13 est allouée et l’autre, au contraire, manque de cache pour conserver l’ensemble de ses données (Tuck et Tullsen, 2003). L’HT a d’abord été implémenté sur des serveurs Xeon, car ce type de technologie se prêtait bien aux applications multiclients, qui sont pour la plupart des applications multifils. Ensuite, cette technologie a été intégrée à d’autres processeurs Intel pour être remplacée progressivement par la suite par des architectures multicœurs. Aujourd’hui, Intel intègre de nouveau cette technologie dans certains processeurs multicœurs haute-performance, tel que les processeurs Nehalem (Singhal, 2008).

Table des matières

INTRODUCTION
CHAPITRE 1 LE MULTIFIL SUR LES SYSTÈMES MULTICŒURS
1.1 Introduction
1.2 Autres types de parallélismes
1.3 Systèmes parallèles adaptées au traitement multifil
1.3.1 Systèmes multiprocesseurs symétriques
1.3.2 La technologie Hyper-Threading
1.3.3 Systèmes multicœurs homogènes
1.4 Autres architectures parallèles
1.5 Les mesures de performance d’une application parallèle
1.5.1 L’accélération et l’efficience d’une application parallèle
1.5.2 La Loi d’Amdahl
1.5.3 La loi de Gustafson
1.6 Développement d’applications multifils
1.6.1 Décomposition fonctionnelle et décomposition du domaine
1.6.2 Cycle de développement
1.6.3 Conception d’un algorithme parallèle
1.6.4 Interfaces de programmation
1.7 Conclusion
CHAPITRE 2 LE STANDARD DE CODAGE VIDEO H.264
2.1 Introduction
2.2 Séquence d’encodage
2.2.1 Estimation et compensation de mouvement par bloc
2.2.2 Transformées et quantification
2.2.3 Codage entropique
2.3 Décomposition hiérarchique d’une séquence vidéo
2.3.1 Groupes d’images
2.3.2 Trames
2.3.3 Tranches
2.3.4 Macroblocs
2.4 Mécanismes de prédiction
2.4.1 Prédiction intra
2.4.2 Prédiction Inter
2.4.2.1 Prédiction de vecteurs de mouvement
2.5 Résumé sur les dépendances
2.6 Mesures de qualité vidéo
2.7 Conclusion
CHAPITRE 3 ÉTAT DE L’ART – PARALLÉLISATION D’UN ENCODEUR
VIDÉO
3.1 Introduction
3.2 Exigences d’un encodeur vidéo
3.3 Décomposition d’un encodeur vidéo H.264
3.3.1 Décomposition fonctionnelle
3.3.2 Décomposition du domaine
3.3.2.1 Décomposition au niveau des groupes d’images
3.3.2.2 Décomposition au niveau des trames
3.3.2.3 Décomposition au niveau des tranches
3.3.2.4 Décomposition au niveau des macroblocs
3.4 Approches d’encodage parallèle sur systèmes à mémoire partagée
3.4.1 Approche parallèle au niveau des trames et des tranches
3.4.2 Approche parallèle au niveau des macroblocs et des trames
3.4.3 Approche adaptative au niveau des tranches
3.5 Approches systèmes à mémoire distribuée pour l’encodage parallèle
3.5.1 Approches parallèles pour les processeurs massivement parallèles
3.5.2 Approches parallèles pour les grappes d’ordinateurs
3.6 Conclusion
CHAPITRE 4 APPROCHE MULTI-TRANCHES D’INTEL
4.1 Introduction
4.2 Description des tests d’encodage
4.3 Analyse des performances de l’approche d’Intel
4.3.1 Impacts du nombre de tranches sur les performances
4.3.2 Proportion du code séquentiel de l’approche d’Intel
4.3.3 Distribution de la charge de travail de l’approche d’Intel
4.3.4 Modèle de prédiction de l’accélération de l’approche d’Intel
4.4 Parallélisation du filtre de déblocage de H.264
4.4.1 Description du filtre de déblocage de H.264
4.4.2 Parallélisation du filtre de déblocage de H.264
4.4.3 Impacts de la désactivation du filtrage des bordures des tranches
sur la qualité
4.5 Résultats
4.6 Conclusion
CHAPITRE 5 NOUVELLE APPROCHE MULTI-TRANCHES ET MULTI-TRAMES
5.1 Introduction
5.2 Description de notre approche de type multi-trames et multi-tranches
5.2.1 Vue sommaire
5.2.2 Division d’une trame
5.2.3 Points de synchronisation
5.2.4 Mécanismes de synchronisation
5.2.5 Contrôle du débit avec délai
5.2.6 Estimation de mouvement et interpolation
5.2.7 Utilisation de tranches supplémentaires
5.3 Modes d’estimation de mouvement
5.3.1 Le mode restreint aux frontières de la tranche courante
5.3.2 Le mode ouvert aux tranches disponibles
5.3.3 Le mode complet avec blocage
5.4 Analyse des résultats
5.4.1 Comparaison entre les trois modes proposés
5.4.2 Comparaison avec l’approche d’Intel
5.5 Discussion
5.6 Conclusion
CONCLUSION
ANNEXE I COMPARAISON ENTRE LA QUALITÉ VISUELLE DES SÉQUENCES VIDÉO EN FONCTION DES DÉBITS UTILISÉS
ANNEXE II PARAMÈTRES D’ENCODAGE
ANNEXE III PERTE DE QUALITÉ, EN FONCTION DU NOMBRE DE TRANCHE, POUR CHACUNE DES SÉQUENCES TESTÉES
ANNEXE IV DISTRIBUTION DES TYPES DE MACROBLOC EN FONCTION DU NOMBRE DE TRANCHES ET DU DÉBIT
ANNEXE V TEMPS D’ENCODAGE SÉQUENTIEL DE L’APPROCHE
D’INTEL POUR DIFFÉRENTES SÉQUENCES EN
FONCTION DU NOMBRE DE TRANCHES
ANNEXE VI AUGMENTATION DU TEMPS D’ENCODAGE SÉQUENTIEL DE L’APPROCHE D’INTEL POUR DIFFÉRENTS DÉBITS EN
FONCTION DU NOMBRE DE TRANCHES
ANNEXE VII TEMPS D’ENCODAGE EN FONCTION DU NOMBRE DE TRANCHES POUR DIFFÉRENTS DÉBITS EN FONCTION DU NOMBRE DE TRANCHES
ANNEXE VIII PARALLÉLISATION DU FILTRE DE DÉBLOCAGE
ANNEXE IX DIVISION D’UNE TRAME EN TRANCHES POUR UNE RÉSOLUTION DE 1280 × 720
ANNEXE X FONCTIONS DE SYNCHRONISATION
ANNEXE XI PERFORMANCE DU PREMIER MODE EN FONCTION DU NOMBRE DE CŒURS ET DU NOMBRE DE TRANCHES SUPPLÉMENTAIRES
ANNEXE XII PERFORMANCES DU SECOND MODE EN FONCTION
DU NOMBRE DE CŒURS ET DU NOMBRE DE
TRANCHES SUPPLÉMENTAIRES
ANNEXE XIII PERFORMANCES DU TROISIÈME MODE EN FONCTION DU NOMBRE DE CŒURS ET DU NOMBRE DEANNEXE XIV COMPARAISON DE PERFORMANCE LES TROIS MODES MTMT PROPOSÉS
LISTE DE RÉFÉRENCES BIBLIOGRAPHIQUES

Télécharger le rapport complet