Data flow modelling and optimization of loops for multi-core architectures
Modélisation flux de données et optimisation pour architecture multi-cœurs de motifs répétitifs
Résumé
Since applications such as video coding/decoding or digital communications with advanced features are becoming more complex, the need for computational power is rapidly increasing. In order to satisfy software requirements, the use of parallel architecture is a common answer. To reduce the software development effort for such architectures, it is necessary to provide the programmer with efficient tools capable of automatically solving communications and software partitioning/scheduling concerns. The Algorithm Architecture Matching methodology helps the programmer by providing automatic transformation, partitioning and scheduling of an application for a given architecture This methodology relies on an application model that allows to extract the available parallelism. The contributions of this thesis tackle both the problem of the model and the associated optimization for parallelism extraction. The Data flow model is indeed a natural representation for data-oriented applications since it represents data dependencies between the operations allowing to extract parallelism. In this model, the application is described as a graph in which nodes represent computations and edges carry the stream of data-tokens between operations. A restricted version of data-flow, termed synchronous data-flow (SDF), offers strong compile-time predictability properties, but has limited expressive power. In this thesis we propose a new type of hierarchy based on interfaces (Interface-based SDF) allowing more expressiveness while maintaining its predictability. This interface-based hierarchy gives the application designer more flexibility to apply iterative design approaches, and to make optimizing choices at the design level. This type of hierarchy is also closer to the host language semantics such as C because hierarchy levels can be interpreted as code closures (i.e., semantic boundaries), and allow one to design iterative patterns. One of the main problems with this hierarchical SDF model is the lack of trade-off between parallelism and network clustering. In this thesis we present a systematic method for applying an important class of loop transformation techniques in the context of interface-based SDF semantics. The resulting approach provides novel capabilities for integrating parallelism extraction properties of the targeted loop transformations with the useful modeling, analysis, and code reuse properties provided by SDF.
Face au défi que représente la programmation des architectures multi-cœurs/processeurs, il est devenu nécessaire de proposer aux développeurs des outils adaptés permettant d'abstraire les notions inhérentes au parallélisme et facilitant le portage d'une application sur différentes architectures. La méthodologie AAA (Adéquation Algorithme Architecture) propose au développeur d'automatiser les étapes de partitionnement, ordonnancement à partir d'une description haut niveau de l'application et de l'architecture. Cette méthodologie permet donc le prototypage rapide d'une application sur différentes architectures avec un minimum d'effort et un résultat approchant l'optimal. Les apports de cette thèse se situent à la fois au niveau du modèle de spécification et de ses optimisations relatives au contexte des architectures parallèles. Le modèle flux de données répond aux problèmes de modélisation des applications fortement synchronisées par les données. Le sous-ensemble SDF (Synchronous Data Flow), limite l'expressivité du modèle mais apporte un complément d'information permettant une optimisation efficace et garantissant l'intégrité du calcul dans tous les contextes. Les travaux développés dans ce mémoire introduisent un nouveau modèle de hiérarchie dans SDF afin d'améliorer l'expressivité tout en préservant les propriétés du modèle initial. Ce modèle basé sur des interfaces, permet une approche plus naturelle pour le développeur accoutumé au langage C. Ce nouveau modèle apportant un complément d'information, nous proposons également un ensemble de traitement améliorant la prise en charge des motifs de répétition imbriqués. En effet le modèle de hiérarchie introduit en première partie permet la spécification de motifs dit de " nids de boucles " pouvant masquer le parallélisme potentiel. Il est donc nécessaire d'associer au modèle des traitements permettant de révéler ce parallélisme tout en préservant l'aspect factorisé du calcul. Les méthodes présentées sont adaptées du contexte des compilateurs pour supercalculateurs et de l'univers des réseaux systoliques.