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

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. 8 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.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 OFDM1/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 (PE0,...PEn), de mémoires de données utilisées pour stocker les opérandes et les résultats produits par les éléments de calculs (Mem0,...Memm), 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 oeuvre 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