Complexité en temps du calcul du produit matriciel sur la classe des réseaux rectangulaires. Algorithmes systoliques pour la multiplication de deux matrices. Détection en temps linéaire des carres d'un mot par des réseaux systoliques.

.

Le traitement itératif est actuellement largement répandu dans les récepteurs sans fil modernes pour le décodage des codes de canal avancés. L'extension de ce principe avec l'ajout d'une boucle de rétroaction vers l'égaliseur et le demappeur a montré d'excellentes performances dans des conditions sévères de canaux de transmission (effacement, multi-trajets, modèles réels de canaux à évanouissements). Toutefois, l'adoption du traitement itératif avec du turbo décodage est fortement limitée par la complexité d'implémentation engendrée, qui impacte fortement sur le débit, la latence et la consommation. Pour faire face à ces problèmes et permettre l'adoption généralisée du traitement itératif, de nouvelles techniques d'optimisation au niveau système doivent être exploitées. Dans ce travail, nous avons étudié la vitesse de convergence et la complexité au niveau système des récepteurs avancés combinant plusieurs processus itératifs. La première partie de cette thèse a été axée sur l'étude de la combinaison de la démodulation itérative avec du turbo décodage, tandis que la deuxième partie a étendu cette étude vers les récepteurs itératifs MIMO en appliquant de la turbo égalisation, de la turbo démodulation et du turbo décodage. Plusieurs techniques de communication et paramètres système, tels que spécifiés dans les applications émergentes de communication sans fil, ont été pris en compte. De nouveaux ordonnancements des itérations pour les boucles de rétroaction internes et externes ont été proposés pour améliorer la convergence et réduire la complexité globale en termes d'opérations arithmétiques et d'accès mémoire. En outre, l'analyse effectuée et les ordonnancements proposés démontrent l'efficacité des boucles de rétroaction externes, même en termes de complexité, par rapport aux récepteurs classiques non itératifs. Ces résultats ont permis la proposition de nouveaux récepteurs itératifs à complexité adaptative appliquant du turbo décodage, de la turbo démodulation et de la turbo égalisation.

L'auteur n'a pas fourni de résumé en français / The end of chip frequency scaling capacity, due heat dissipation limitations, made manufacturers search for an alternative to sustain the processing capacity growth. The chosen solution was to increase the hardware parallelism, by packing multiple independent processors in a single chip, in a Multiple-Instruction Multiple-Data (MIMD) fashion, each with special instructions to operate over a vector of data, in a Single-Instruction Multiple-Data (SIMD) manner. Such paradigm change, brought to software developer the convoluted task of producing efficient and scalable applications. Programming languages and associated tools evolved to aid such task for new developed applications. But automated optimizations capable of coping with such a new complex hardware, from legacy, single threaded applications, is still lacking.To apply code transformations, either developers or compilers, require to assert that, by doing so, they are not changing the expected comportment of the application producing unexpected results. But syntactically poor codes, such as use of pointer parameters with multiple possible indirections, complex loop structures, or incomplete codes, make very hard to extract application behavior solely from the source code in what is called a static analyses. To cope with the lack of information extracted from the source code, many tools and research has been done in, how to use dynamic analyses, that does application profiling based on run-time information, to fill the missing information. The combination of static and dynamic information to characterize an application are called hybrid analyses. This works advocates for the use of hybrid analyses to be able to optimizations on loops, regions where most of computations are done. It proposes a framework capable of statically applying some complex loop transformations, that previously would be considered unsafe, by assuring their safe use during run-time with a lightweight test.The proposed framework uses application execution profiling to help the static loop optimizer to: 1) identify and classify program hot-spots, so as to focus only on regions vital for the execution time; 2) guide the optimizer in understanding the overall loop behavior, so as to reduce the valid loop transformations search space; 3) using instruction's memory access functions, it statically builds a lightweight run-time test that determine, based on the program parameters values, if a given optimization is safe to be used or not. It's applicability is shown by performing complex loop transformations into a variety of loops, obtained from applications of different fields, and demonstrating that the run-time overhead is insignificant compared to the loop execution time or gained performance, in the vast majority of cases.

Une des étapes les plus cruciales dans le processus d’analyse des performances d’une application est la détection des goulets d’étranglement. Un goulet étant tout évènement qui contribue à l’allongement temps d’exécution, la détection de ses causes est importante pour les développeurs d’applications afin de comprendre les défauts de conception et de génération de code. Cependant, la détection de goulets devient un art difficile. Dans le passé, des techniques qui reposaient sur le comptage du nombre d’évènements, arrivaient facilement à trouver les goulets. Maintenant, la complexité accrue des micro-architectures modernes et l’introduction de plusieurs niveaux de parallélisme ont rendu ces techniques beaucoup moins efficaces. Par conséquent, il y a un réel besoin de réflexion sur de nouvelles approches.Notre travail porte sur le développement d’outils d’évaluation de performance des boucles de calculs issues d’applications scientifiques. Nous travaillons sur Decan, un outil d’analyse de performance qui présente une approche intéressante et prometteuse appelée l’Analyse Décrémentale. Decan repose sur l’idée d’effectuer des changements contrôlés sur les boucles du programme et de comparer la version obtenue (appelée variante) avec la version originale, permettant ainsi de détecter la présence ou pas de goulets d’étranglement.Tout d’abord, nous avons enrichi Decan avec de nouvelles variantes, que nous avons conçues, testées et validées. Ces variantes sont, par la suite, intégrées dans une analyse de performance poussée appelée l’Analyse Différentielle. Nous avons intégré l’outil et l’analyse dans une méthodologie d’analyse de performance plus globale appelée Pamda.Nous décrirons aussi les différents apports à l’outil Decan. Sont particulièrement détaillées les techniques de préservation des structures de contrôle du programme,ainsi que l’ajout du support pour les programmes parallèles.Finalement, nous effectuons une étude statistique qui permet de vérifier la possibilité d’utiliser des compteurs d’évènements, autres que le temps d’exécution, comme métriques de comparaison entre les variantes Decan / A crucial step in the process of application performance analysis is the accurate detection of program bottlenecks. A bottleneck is any event which contributes to extend the execution time. Determining their cause is important for application developpers as it enable them to detect code design and generation flaws.Bottleneck detection is becoming a difficult art. Techniques such as event counts,which succeeded to find bottlenecks easily in the past, became less efficient because of the increasing complexity of modern micro-processors, and because of the introduction of parallelism at several levels. Consequently, a real need for new analysis approaches is present in order to face these challenges.Our work focuses on performance analysis and bottleneck detection of computeintensive loops in scientific applications. We work on Decan, a performance analysis and bottleneck detection tool, which offers an interesting and promising approach called Decremental Analysis. The tool, which operates at binary level, is based on the idea of performing controlled modifications on the instructions of a loop, and comparing the new version (called variant) to the original one. The goal is to assess the cost of specific events, and thus the existence or not of bottlenecks.Our first contribution, consists of extending Decan with new variants that we designed, tested and validated. Based on these variants, we developed analysis methods which we used to characterize hot loops and find their bottlenecks. Welater, integrated the tool into a performance analysis methodology (Pamda) which coordinates several analysis tools in order to achieve a more efficient application performance analysis.Second, we introduce several improvements on the Decan tool. Techniquesdeveloped to preserve the control flow of the modified programs, allowed to use thetool on real applications instead of extracted kernels. Support for parallel programs(thread and process based) was also added. Finally, our tool primarily relying on execution time as the main concern for its analysis process, we study the opportunity of also using other hardware generated events, through a study of their stability, precision and overhead