Raulet mickaël 18 mai 2005

Optimisations Mémoire dans la Méthodologie AAA pour Code Embarqué sur Architectures Parallèles

• RAULET Mickaël

• 18 mai 2005

• Mitsubishi ITE - Equipe Software Radio

• IETR/INSA - Groupe Image

• INRIA – Groupe AOSTE

Plan

• Introduction

• Objectifs
• Problématique

• SynDEx

• Minimisation mémoire

• Applications

• Conclusions perspectives

Introduction : Objectifs

• Développement d’une méthodologie de prototypage rapide pour architectures complexes

• Diminution du temps de développement pour le portage sur une cible multi-composants (PC, DSP et/ou FPGA)

• Développement d’applications dans le domaine de l’embarqué (téléphonie mobile, décodeurs de salons)

• Réalisation de démonstrateurs

Introduction : Problématique

• Prototypage rapide d’applications de traitement du signal et images pour systèmes embarqués temps réel sur architectures distribuées hétérogènes

• Méthodologies pour passer rapidement (automatiquement) d’une description de haut niveau de l’application à une implantation exécutable
• Méthodologie AAA (Adéquation Algorithme Architecture)

Introduction : Problématique

• Prototypage rapide d’applications de traitement du signal et images pour systèmes embarqués temps réel sur architectures distribuées hétérogènes

• Applications fortement orientées données

Introduction : Problématique

• Prototypage rapide d’applications de traitement du signal et images pour systèmes embarqués temps réel sur architectures distribuées hétérogènes

• Minimisation des ressources et exécution “suffisamment” rapide

Introduction : Problématique

• Prototypage rapide d’applications de traitement du signal et images pour systèmes embarqués temps réel sur architectures distribuées hétérogènes

• Distribution/ordonnancement des traitements

Introduction : Problématique

• Prototypage rapide d’applications de traitement du signal et images pour systèmes embarqués temps réel sur architectures distribuées hétérogènes

• Mise en oeuvre conjointe de composants cible variés
• Travaux essentiellement sur cibles multi-composants

Introduction : Problématique

• Systèmes multi-composants

• Systèmes embarqués

• Limitation mémoire

• Traitement du signal, télécommunications et vidéo

• Consommation mémoire importante

• Nécessité d’une optimisation mémoire

• Nécessité d’une méthodologie adaptée

SynDEx : Présentation

• SynDEx : Synchronized Distributed Executives

• Logiciel de CAO niveau système pour applications distribuées temps réel et embarquées
• INRIA Rocquencourt projet AOSTE (Y. Sorel)

• Fonctionnalités

• Partitionnement/ordonnancement automatiques d’une application sur une architecture cible
• Algorithme glouton basée sur une minimisation de la latence (optimisation orientée vitesse)
• Génération d’un exécutif distribué indépendant de la cible

SynDEx : Caractéristiques

• Approche globale

• Modèle unifié de graphes

• Algorithme : parallélisme potentiel
• Architecture : parallélisme disponible
• Implantations : transformations de graphes

• Adéquation

• Choix d’une implantation optimisée

• But

• Génération automatique d’exécutifs
• taillés sur mesure aux applications,
• basés sur un ordonnancement hors-ligne des calculs et des communications

SynDEx : Caractéristiques

SynDEx : Caractéristiques

• Exécutif supporte :

• l’exécution de l’algorithme sur l’architecture
• l’ordonnancement, les communications et les synchronisations

• Taillé sur mesure :

• Minimisation du surcoût spatial et temporel
• Implantation optimisée (latence)
• Sans inter-blocage, garantie ordre total du graphe d’algorithme

• Basé sur macro-code

• Indépendant du processeur
• Supportant des architectures hétérogènes, portabilité

• Basé sur des bibliothèques génériques dépendantes

• des processeurs (DSP, PC, FPGA…)
• des communicateurs (SAM=FIFO, RAM)

Plan

• Introduction

• SynDEx

• Présentation
• Caractéristiques
• Chaîne de développement

• Minimisation mémoire

• Applications

• Conclusions perspectives

SynDEx : Chaîne de développement

SynDEx : Chaîne de développement

SynDEx : Chaîne de développement

SynDEx : Chaîne de développement

• Développements de nombreuses bibliothèques

• Vérification fonctionnelle

• Ajout de fonction d’affichage de l’image directement sous SynDEx
• Display générique
• Webcam

• Vérification et exploration architecturale  TCP

• facilitant la vérification fonctionnelle de l’application
• séparation de codeur-décodeur
• possibilité de décrire des architectures complexes (multi-PC)
• plateformes de test et de vérification

Plan

• Introduction

• SynDEx

• Minimisation mémoire

• Objectifs
• Principes d’allocation
• Mono-composant
• Multi-composants

• Applications

• Conclusions perspectives

Minimisation mémoire : Objectifs

Minimisation mémoire : Principes d’allocation

Minimisation mémoire : Mono-composant

Minimisation mémoire : Mono-composant

• Coloriage de graphe

• Approche classique
• minimisation des buffers (« registre »)

Minimisation mémoire : Mono-composant

• Autre Méthode mono-composant

• Minimisation « tétris »
• Basée également sur la durée de vie des buffers
• Basée uniquement sur des buffers de même type

Plan

• Introduction

• SynDEx

• Minimisation mémoire

• Objectifs
• Principes d’allocation
• Mono-composant
• Multi-composants

• Applications

• Conclusions perspectives

Minimisation mémoire : Multi-composants

• Considération des buffers communiqués inter-processeurs

• Diminution accrue de l’espace mémoire

• Durée de vie des buffers communiqués liée au modèle de synchronisation de SynDEx

Minimisation mémoire : Multi-composants

• Distribution/ordonnancement

Minimisation mémoire : Multi-composants

Minimisation mémoire : Multi-composants

• Schéma de principe dans SynDEx

Minimisation mémoire : Multi-composants

Minimisation mémoire : Multi-composants

Minimisation mémoire : Multi-composants

• Solution :

• Modifications du modèle SynDEx
• Sans changement de l’ordre total
• Avec prise en compte des temps de communications
• Sans changement de la latence
• Optimisations de la mémoire avec un gain important

Minimisation mémoire : Multi-composants

Minimisation mémoire : Conclusion

• Minimisation mémoire mono-composant efficace

• Minimisation « registre »
• Minimisation « tétris »

• Minimisation mémoire multi-composants

• Prise en compte des buffers communiqués inter-processeurs

• Optimisation supplémentaire de la génération de code

• Opérations implicites générant des « recopies » de buffers à buffers :
• Explode – implode
• Conditionnement
• Retard ou mémoire

Plan

• Introduction

• SynDEx

• Minimisation mémoire

• Applications

• UMTS
• MPEG-4
• LAR

• Conclusions perspectives

Applications : UMTS FDD

• Troisième génération de téléphone portable

• Caractéristiques

• Débits maximum 2 Mbits/sec
• Temps réel 10ms par trame
• 1 trame = 15 slots

Applications : UMTS (Tx)

Applications : UMTS

• Minimisation UMTS

• Portage sur un C6203 à 512 ko de RAM

• Automatique  Mieux que manuellement

• Gain de 7  Très proche d’un gain attendu de 7.5

• Minimisation de toutes les recopies  Diminution du temps

Applications : MPEG-4

• Successeur de MPEG-2

• Norme composée de sous-parties

• Partie 2 = Vidéo

• Norme complexe (boîte à outils)

• Scène composée d’objets
• Images de synthèse
• Images naturelles
• …

Application : Décodeur MPEG-4

• Décodeur images I (Intra) existant :

• Description bas niveau  Granularité fine

• 3 niveaux d’abstraction de description

• Niveau image  haut niveau
• Image I, P et B
• Niveau macrobloc  niveau intermédiaire
• 16 * 16 pixels
• Niveau bloc  bas niveau
• 6 blocs dans un macrobloc
• 4 blocs de luminance
• 2 blocs de chrominance

Application : Décodeur MPEG-4 Description gros grain

• Description niveau Image

• Images I
• Images P
• Images B

• Base des descriptions plus détaillées

• Description niveau intermédiaire
• Description bas niveau

Application : Décodeur MPEG-4 Description gros grain

Application : Décodeur MPEG-4 Description gros grain

• Description de haut niveau

• Gros grain
• Résultats sur DSP (C6416 à 400 MHz)

Application : Décodeur MPEG-4 Description grain fin

• Décodeur bas niveau  grain fin

• Granularité du décodeur :
• VLC inverse (VLC = codage à longueur variable)
• Scan inverse (scan = balayage)
• DCT inverse (DCT = transformée discrète en cosinus)
• …
• Possibilité de parallélisme

• Basée sur

• Description haut niveau
• Description images I bas niveau

Application : Décodeur MPEG-4 Description grain fin

• Schéma hiérachiques :

Application : Décodeur MPEG-4 Description grain fin

• Complexité SynDEx du décodeur bas niveau

• Nombre d’opérations proportionnel au nombre de macroblocs

Application : Décodeur MPEG-4 Description gros grain

• Décodeur MPEG-4 sur 2 processeurs :

• description de haut niveau (352*288)

• Gain de 54 recopies

• Minimisation mémoire :

• Gain de 1,6 (Granularité de l’application trop forte)

Application : Décodeur MPEG-4 Description gros grain

• Haut niveau

Applications : LAR

• Méthode développé au sein du laboratoire Image

• Méthode basée contenu

• Méthode hiérarchique

• Images fixes
• Fort taux de compression

Application : CODEC LAR

• Codec LAR sur 2 Processeurs

• Div_pic = 1
• 117 opérations
• 352*288

Plan

• Introduction

• SynDEx

• Minimisation mémoire

• Applications

• Conclusions perspectives

Conclusions perspectives : Optimisation mémoire

• Conclusion

• Génération de code automatique embarquée
• Post-traitement mémoire efficace
• Codage dans l’outil SynDEx
• Temps de minimisation efficace pour trouver la solution

• Perspectives

• Mise en place de la cache
• Travaux de F. Urban
• Mise en place des algorithmes génétiques
• Minimisation multi-critères

Conclusions perspectives : Optimisation mémoire

Conclusions perspectives : Applications

• Conclusion

• Diversité des applications
• Complexité des applications
• Niveau de granularité différent

• Perspectives

• Intégration d’un décodeur MPEG4-AVC dans un terminal (projet Mobim@ge)
• Extension du LAR (LAR vidéo)
• Extension de la méthodologie AAA pour des systèmes multi-couches (G. Roquier)
• Alliant vidéo et télécommunications

Application : Décodeur MPEG-4 Minimisation mémoire

• Utiliser intelligemment les mémoires suivant l’application

• Traitement sur des données en mémoire interne :
•  Plus rapide qu’avec des données en mémoire externe

Application : Décodeur MPEG-4 Minimisation mémoire

• Utilisation du QDMA pour le décodeur :

• Transferts mémoires externe-interne et externe-externe
• Mémorisation de l’image, recopie dans les buffers de sortie de l’image