UNE NOUVELLE APPROCHE DE PLACEMENT DE DONNEES EN MEMOIRE : APPLICATION A LA CONCEPTION D ARCHITECTURES D ENTRELACEURS PARALLELES

Description
UNE NOUVELLE APPROCHE DE PLACEMENT DE DONNEES EN MEMOIRE : APPLICATION A LA CONCEPTION D ARCHITECTURES D ENTRELACEURS PARALLELES Aroua Briki To cite this version: Aroua Briki. UNE NOUVELLE APPROCHE DE

Please download to get full document.

View again

of 112
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Small Business & Entrepreneurship

Publish on:

Views: 12 | Pages: 112

Extension: PDF | Download: 0

Share
Transcript
UNE NOUVELLE APPROCHE DE PLACEMENT DE DONNEES EN MEMOIRE : APPLICATION A LA CONCEPTION D ARCHITECTURES D ENTRELACEURS PARALLELES Aroua Briki To cite this version: Aroua Briki. UNE NOUVELLE APPROCHE DE PLACEMENT DE DONNEES EN MEMOIRE : APPLICATION A LA CONCEPTION D ARCHITECTURES D ENTRELACEURS PARALLELES. Traitement du signal et de l image. Université de Bretagne Sud, Français. tel HAL Id: tel https://tel.archives-ouvertes.fr/tel Submitted on 14 Jan 2014 HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. THESE / UNIVERSITE DE BRETAGNE-SUD sous le sceau de l Université européenne de Bretagne pour obtenir le titre de DOCTEUR DE L UNIVERSITE DE BRETAGNE-SUD Mention : présentée par Aroua Briki Préparée au Laboratoire Lab-STICC (UMR n 6285) Université de Bretagne Sud Ecole doctorale SICMA Thèse soutenue le 01 juillet 2013 devant le jury composé de : UNE NOUVELLE APPROCHE DE PLACEMENT DE DONNEES EN MEMOIRE : APPLICATION A LA CONCEPTION D ARCHITECTURES D ENTRELACEURS PARALLELES Amer Baghdadi (Telecom Bretagne / Lab-STICC) Christophe Jego (ENSEIRB / IMS) Smail Niar (Université de Valenciennes / LAMIH) Adel Ghazel (Sup Com Tunis) Eric Martin (Université de Bretagne Sud / Lab-STICC) Philippe Coussy (Université de Bretagne Sud / Lab-STICC) Cyrille Chavet (Université de Bretagne Sud / Lab-STICC) 3 4 Résumé Les applications du traitement du signal (TDSI) sont maintenant largement utilisées dans des domaines variés allant de l automobile aux communications sans fils, en passant par les applications multimédias et les télécommunications. La complexité croissante des algorithmes implémentés et l augmentation continue des volumes de données et des débits applicatifs requièrent souvent la conception de circuits intégrés dédiés (ASIC). Typiquement l architecture d un composant complexe du TDSI utilise (1) des éléments de calculs de plus en plus complexes, (2) des mémoires et des modules de brassage de données (entrelaceur/désentrelaceur pour les TurboCodes, blocs de redondance spatio-temporelle dans les systèmes OFDM 1 /MIMO, ). Aujourd hui, la complexité et le coût de ces systèmes sont très élevés; les concepteurs doivent pourtant parvenir à minimiser la consommation et la surface total du circuit, tout en garantissant les performances temporelles requises. Sur cette problématique globale, nous nous intéressons à l optimisation des architectures des modules de brassage de données (réseau d interconnexion, contrôleur ) devant réaliser une règle d entrelacement définie par l application et ayant pour objectif d utiliser un réseau d interconnexion défini par le concepteur. L'architecture que nous ciblons se compose d éléments de calculs (PE 0, PE n ), de mémoires de données utilisées pour stocker les opérandes et les résultats produits par les éléments de calculs (Mem 0, Mem m ), d un réseau d interconnexion reliant les éléments de calculs aux mémoires et d une unité de contrôle. Le réseau d interconnexion est défini par l utilisateur et peut être basé sur différent modèles : cross-bar, réseaux de Benes, réseau de Bruinj, barrière de multiplexeurs, barrel-shifters (barillets), papillons... L unité de contrôle est composée de deux parties : un contrôleur de réseau et un contrôleur de mémoires. Ces contrôleurs sont basés sur un ensemble de mémoires de contrôle (une ROM de contrôle par banc mémoire Mem dans l architecture cible) contenant les mots de commande relatifs au fonctionnement du système. L approche que nous proposons est à même d optimiser cette partie de contrôle de l architecture. Nous proposons plusieurs méthodologies d exploration et de conception permettant de générer automatiquement une architecture d entrelacement optimisée réalisant une règle de brassage de données, ou entrelacement, tel que définie par exemple dans un standard de communication. Les approches que nous proposons prennent en entrée (1) des diagrammes temporels (générés à partir de la règle d entrelacement et de contraintes spécifiant les séquences d accès parallèles aux données) et (2) une contrainte utilisateur sur le réseau d interconnexion que doit utiliser l architecture. Ce flot formalise ensuite ces contraintes de brassage des données sous la forme (1) d un modèle matriciel des séquences de données qui devront être traitées par chaque processeur et (2) d un Graphe de Conflit d Adressage (ACG), dont les propriétés permettent une exploration efficace de l'espace des solutions architecturales. L objectif est ensuite de générer une architecture cible, en garantissant un fonctionnement sans conflit d accès mémoire (lorsque plusieurs processeurs veulent accéder en même temps à un même banc mémoire mais pour traiter des données différentes), en respectant la contrainte de réseau et en optimisant l architecture obtenue (notamment concernant l architecture de son contrôleur). Cette approche a été mise en œuvre au sein d un d outil et appliquée sur plusieurs cas d étude : High Speed Packet Access (HSPA), Ultra-WideBand (UWB) et une application Wimax. Ces expériences montrent qu en comparaison aux approches de l état de l art nos approches permettent d atteindre des gains en surface significatifs. Notamment, pour des applications Turbo Codes pour lesquels les gains sont très importants. 1 OFDM : technique de modulation se basant sur le multiplexage fréquentiel de signaux. 5 6 Abstract Error correcting codes i.e. LDPC (Low Density Parity Check) and Turbo-codes are the foundation of communication. Standards like digital video broadcasting (DVB), high-speed wired links (ADSL ), wireless accesses (WiMAX, Wifi ), and telecommunications systems (HSPA, LTE ) all rely on it. LDPC and Turbo Codes are well-known, near Shannon limit, coding/decoding approaches that are able to achieve very low bit error rates for low Signal-to-Noise Ratio (SNR) applications. Decoding principle is based on message passing algorithm in which different processing elements iteratively exchange information in order to improve the error correction performance of these codes. In order to design high data rate applications, parallel architecture are needed. To increase memory bandwidth, main memory is divided into different memory banks to provide concurrent parallel access to all the processing elements. This allows to reduce the latency and thus to increase the throughput of decoders. Typical parallel decoder architecture includes processing elements connected through a dedicated Interconnection Network to memory banks and a dedicated Control Unit that drives the architecture. The network interleaves the data exchanged by the processing elements according to a rule named interleaving law or permutation law defined by the standard or the application to design. Unfortunately, depending on both interleaving law and memory mapping (i.e. data placement in memory banks), different processing elements may try to simultaneously access the same memory bank which results in memory conflicts. Three kinds of solution exist to avoid or minimize memory access conflicts: (1) Define an interleaving law that automatically maps data in different memory banks so that all processing elements can access them without any conflict at each time instance, but only when the designer is free to choose the permutation law; (2) Simply store data elements in different memory banks without considering conflicting accesses and then use different complex topologies and additional buffers to mange conflicts on runtime. This increases the cost and latency of the system. (3) Use memory mapping algorithms to map data in different memory banks so that each processing elements can access them without any conflict. This kind of approach results in a non-optimized architectures. In addition, ROM resources are needed in the controller to store the memory mapping (i.e. control words to address memory banks and to drive interconnection networks). Unfortunately, cost of the controller is not considered for optimization in any state of the art approaches. Our proposed approach is based on two main steps: first, starting from the set of constraints (i.e. the interleaving law, the parallelism and the targeted interconnection network), it generates a conflict free memory mapping (through a mapping algorithm based on memory constraint relaxation) and an Address Conflict Graph ACG. At this step, the data are assigned to memory banks (i.e. Bank Mapping), but their addresses in banks are still unknown (i.e. Address Mapping is not yet defined). In ACG, vertices represent data accesses in their respective memory banks, and edges represent conflicts between these accesses (e.g. write a new data at a currently used address). The memory mapping is performed thanks to a dedicated heuristic that aims to both generate a conflict free memory mapping and minimize the number of conflict in the generated ACGs. Indeed, when two data are stored in the same memory bank, and if their respective lifetimes in this memory bank are overlapping, two different memory locations (i.e. addresses) are required. Hence the bank mapping step strongly impacts the final ACGs, by generating more or less address conflicts. Then, memory mapping information and ACG are used during the Address Mapping step to explore the memory addressing in order to optimize the final cost of the memory controller. Finally, our design flow generates the final VHDL architecture with a conflict free memory mapping and the associated optimized control units. 7 Our approach has been applied to explore the design space of several test cases. The resulting architectures respect the designer architectural constraints in any case and the controllers are strongly optimized. 8 Table des matières Chapitre 1 Introduction 21 I. Introduction A. Codes Convolutifs a) Les codeurs convolutifs b) Code convolutif et diagramme de treillis c) Décodage des codes convolutifs B. Turbo-Codes a) Turbo-Codeur b) Entrelaceur c) Turbo Décodeur C. Parallélisme en Turbo Décodage a) Parallélisme des unités récursives b) Parallélisme au niveau du treillis c) Parallélisme au niveau du décodeur SISO d) Conclusion II. Les codes en bloc A. Codage des codes en blocs linéaires B. Codes LDPC Low Density Parity Check Codes C. Représentation du Graphe de Tanner D. Décodage E. Implémentation du décodeur LDPC a) Implémentation avec un parallélisme total b) Implémentation en série c) Implémentation avec un parallélisme partiel III. Les problèmes de conflits mémoires A. Les problèmes de conflits mémoire dans les Turbo-Codes B. Les problèmes de conflits mémoire dans les codes LDPC IV. Problématique et contributions V. Conclusion Chapitre 2 Etat de l'art 45 I. Introduction II. Approches de résolution des conflits mémoires pour Turbo-Codes et codes LDPC A. Définition de règles d entrelacement sans conflits a) Turbo-Codes à roulettes b) Entrelaceurs déterministes c) Les codes LDPC structurés B. Résolution des conflits à l exécution a) Cas des Turbo-codes b) Cas des codes LDPC C. Résolution des conflits à la conception a) Graphes de conflits et Turbo-Codes b) Graphes de conflits et codes LDPC c) Approches de placement mémoire pour les Turbo-codes d) Approches de placement mémoire pour les codes LDPC III. Bilan Chapitre 3 Placement mémoire sous contrainte de réseau 69 I. Introduction II. Formulation du problème d allocation mémoire pour les Turbo-codes et les codes LDPC.. 74 III. Allocation mémoire sans conflit sous contrainte de réseau d interconnexion A. Première approche d allocation mémoire a) Assignation initiale b) Résolution des conflits c) Analyse de complexité B. Exemple pédagogique IV. Allocation mémoire avec sélection de la donnée la plus contrainte A. Nouvelle approche B. Exemple visée pédagogique V. Conclusion Chapitre 4 Placement mémoire et optimisation du contrôle 93 I. Introduction II. Placement des données en mémoire sans conflit pour la génération d un contrôleur mémoire optimisé A. Graphe de Conflit d Adresse B. Exploitation d un ACG pour l optimisation de l architecture de contrôle a) Génération d un Graphe de Conflits d Adresses b) Assignation Initiale c) Phase de Résolution de Conflits d) Adressage des données au sein des bancs mémoire e) Analyse de complexité C. Exemple à visée pédagogique III. Compaction des ROMs d adressages optimisées A. Transformation des adresses mémoires en matrice de banc et placement des adresses mémoires dans des ROMs dédiées B. Compaction et Fusion des ROMs a) Tri des ROMs b) Compaction des ROMs c) Fusion des ROMs C. Architecture RTL schématique IV. Bilan Chapitre 5 Expérimentations 125 I. Introduction II. Conception des architectures d entrelaceurs parallèles pour les Turbo-codes A. Entrelaceur utilisé dans HSPA Evolution B. Résultat expérimentaux de l approche d assignation mémoire C. Intérêt notre approche (placement mémoire et adressage) III. Entrelaceur pour l Ultra-Wide Band A. Présentation B. Résultats expérimentaux IV. Conception d architectures de décodeurs LDPC A. Les codes LDPC aléatoires B. Les codes LDPC structurés C. Résultats expérimentaux a) LDPC aléatoires b) LDPC structurés V. Premières expérimentation un flot d exploration généralisé VI. Bilan Conclusion et perspectives Bibliographies... VI Table des figues Figure 1.1 Système de communication Figure 1.2 Codeur Convolutif Figure 1.3 Diagramme d états Figure 1.4 Diagramme de treillis Figure 1.5 Turbo-Codeur Figure 1.6 Fonction d entrelacement Figure 1.7 Turbo-Décodeur Figure 1.8 Implémentation en série d un Turbo décodeur Figure 1.9 Parallélisme de l unité de calcul récursive Figure 1.10 Parallélisme au niveau du treillis Figure 1.11 Parallélisme au niveau décodeur SISO Figure 1.12 Format systématique d un mot de code Figure 1.13 Circuit du codage pour un code systématique(7,4) Figure 1.14 Graphe de Tanner Figure 1.15 Architecture partiellement parallèle Figure 1.16 Traitement parallèle pour les Turbo Codes Figure 1.17 Les problèmes de conflits mémoire dans les turbo-décodeurs parallèles Figure 1.18 Les problèmes de conflits mémoires dans les décodeurs LDPC partiellement parallèles Figure 1.19 Architecture typique d un entrelaceur parallèle Figure 2.1. Permutation spatiale et temporelle pour la construction d un entrelaceur Figure 2.2 Représentation de la matrice H Figure 2. 3 La matrice H Base pour le standard WiMax avec un mot de code = 576, Z = 24 et r = 1/ Figure 2. 4 Architecture du distributeur LLR Figure 2. 5 Réseau multi étage hétérogène Figure 2. 6 Graphe de Bruijn binaire avec 16 nœuds Figure 2. 7 Réseau de Bruijn avec 8 processeurs, des routeurs et des interfaces réseau Figure 2. 8 Graphe de conflit pour les turbo-décodeurs Figure 2. 9 Architecture résultante Figure Graphe de conflit pour le décodeur LDPC Figure Architecture résultante Figure Principe de Tuilage Figure Matrices utilisées dans SAGE Figure Matrice d accès aux données pour les turbo-codes Figure Représentation du graphe biparti pour la Figure Figure Matrice d assignation de l approche basée sur la lecture multiple et l écriture multiple...64 Figure Modélisation biparti du problème d allocation de la mémoire pour les codes LDPC.. 65 Figure Représentation des arcs d un nœud d une donnée du graphe biparti Figure Graphe tripartie pour d accès aux données illustrées dans Figure Figure Tableau comparatif des approches de l état de l art Figure Rappel de l architecture cible Figure 3. 1 Architecture typique d un entrelaceur mémoire Figure 3. 2 Matrice d accès aux données Figure 3. 3 Matrice d affectation pour la mémoire d accès aux données Figure 3. 5 Assignation initiale Figure 3. 6 Algorithme de l assignation initiale Figure 3. 7 Algorithme de résolution de conflits Figure 3. 8 Report de l assignation de la première colonne Figure 3. 9 Deuxième et troisième assignation Figure Echec de contrainte architecturale dans la colonne de lecture à l instant Figure Matrice partiellement assignée résultat de l étape initiale de l algorithme Figure Solution valide d assignation mémoire Figure Architecture finale générée au niveau RTL Figure Sélection «donnée par donnée»dans l assignation initiale Figure Algorithme d assignation initiale traitant en priorité la donnée la plus contrainte Figure Résolution des conflits «donnée par donnée» Figure Matrices relatives à l exemple pédagogique Figure Réseau d interconnexion papillon avec un parallélisme de 4 à base de papillon élémentaire de parallélisme Figure Affectation de la première colonne d écriture Figure Assignation de la deuxième colonne Figure Violation des contraintes de réseaux Figure Annulation de l assignation des données conflictuelles Figure Résultat de l assignation initiale Figure Résultat final d allocation mémoire sans conflits Figure Architecture RTL générée Figure4. 1 Architecture cible d un entrelaceur mémoire parallèle 98 Figure 4. 2 Durée de vie d une donnée 99 Figure4. 3 Chevauchement de durée de vie de deux données 99 Figure4. 4 Durées de vie de l ensemble des données (d1, d2, d3, d4) 100 Figure4. 5 Graphe de conflit d adresse associés aux données (d1, d2, d3, d4) 100 Figure4. 6 Flot de conception pour la génération de l entrelaceur mémoire parallèle 101 Figure4. 8 Algorithme d assignation initiale tenant compte de la génération de ACG 104 Figure4. 9 Résolution des conflits dans un cycle particulier 104 Figure4. 10 Algorithme d adressage 105 Figure4. 11 Exemple d une matrice d adressage mémoire 107 Figure4. 12 Matrice d accès aux données 108 Figure4. 13 Résultat d affectation après quelques itérations 108 Figure4. 15 Graphe biparti associée à l exemple pédagogique 109 Figure4. 14 Graphe de conflit d adresse obtenu après quelques itérations 109 Figure4. 16 Durées de vie des données assignées au banc mémoire B 110 Figure4. 18 Ensemble d arêtes pondérées 110 Figure4. 19 Résultat final de l assignation mémoire 111 Figure4. 20 Graphe de conflit d adresse généré 111 Figure4. 21 Premier adressage mémoire 112 Figure4. 22 Matrice d adressage partiellement assignées Figure4. 23 Matrice d adressage finale 113 Figure4. 24 Séquences d adressage aux bancs mémoires 114 Figure4. 25 ROM d adressage pour le contrôle du banc mémoire A 115 Figure4. 26 Flot de conception de la Compaction&Fusion des ROMs 116 Figure4. 27 Compatibilité des adresses mémoires envoyées par deux ROMs dans un cycle de traitement particulier 117 Figure4. 28 Tri des ROMs 118 Figure4. 29 Algorithme de compaction des ROMs 119 Figure4. 30 Application de la compactions des ROMs sur l exemple pédagogique 120 Figure4. 30 Application de la compactions des ROMs sur l exemple pédagogique 121 Figure4. 31 Algorithme de fusion ROMs 122 Figure4. 32 Application de l algorithme de fusion des ROMs sur l exemple pédagogique 123 Figure4. 33 Architecture RTL générée 124 Figure4. 34 Flot de conception générale 125 Figure 5. 1 Surface en portes logiques d un turbo-décodeur utilisé dans le standard LTE Figure 5. 2 Flot de conception générique Figure 5. 3 Exemple d un fichier de contraintes tiré du standard WIMAX Figure 5. 4 Arrangement de K=44 données en une matrice 5* Figure 5. 5 Matrice après la permutation intra-ligne Figure 5. 6 Matrice après la permutation interligne Figure 5. 7 Comparaison en nombre de slices des architectures générées pour l entrelaceur HSPA Figure 5. 8 Les différents systèmes WLAN /PLAN existant Figure 5. 9 Schéma bloc d une architecture OFDM pour un émetteur Figure Comparaisons des résultats obtenus pour un entrelaceur UWB Figure Comparaisons des résultats pour un entrelaceur UWB en ciblant un barrel shifter Figure Exemple d une Architecture typique des codes LDPC
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks