Réseaux de processus flots de données avec routage pour la modélisation de systèmes embarqués
Institution:
NiceDisciplines:
Directors:
Abstract EN:
This thesis defines a new model of computation and communication, called k-periodically routed graph (KRG). This model belongs to the family of dataflow process networks. Data routings are regular and explicit, in the form of k-periodic binary sequences. We study mathematical and behavioural properties of KRGs. Because of explicit routings and conflict-freeness, data dependencies can be expressed in algebraic terms, as well as behaviour preserving topological transformations. Then we show how KRG schedules can be expressed using k-periodic clocks. We position our model in the heart of a design flow, dedicated to data intensive processing applications. In particular we show KRG abilities of explicit modelling of instruction level and data parallelism, extracted from a polyhedral model. Low level optimizations, out of the scope of polyhedral models, can then be applied to the design. Finally, we present a methodology for implementing KRGs, based on latency insensitive design.
Abstract FR:
Cette thèse définit un nouveau modèle de calcul et de communication, dénommé graphe à routage k-périodique (KRG). Ce modèle, de la famille des réseaux de processus de flots de données, admet des aiguillages réguliers des données, explicités par des séquences binaires k-périodiques. Nous étudions les propriétés mathématiques intrinsèques au modèle. Le routage explicite et l’absence de conflit nous permettent d’exprimer algébriquement les dépendances de données, de même que des transformations topologiques préservant le comportement du graphe. Nous montrons ensuite comment ordonnancer le KRG, en associant aux nœuds des horloges k-périodiques. Nous positionnons ensuite notre modèle au sein d’un flot de conception dédié aux applications de traitement intensif de données. Nous montrons en particulier la capacité des KRG à représenter explicitement le parallélisme d’instruction et de données extrait du modèle polyédrique. Nous pouvons alors appliquer un ensemble d’optimisations de bas niveau, sortant du cadre affine du modèle polyédrique. Nous présentons enfin une méthodologie pour l’implantation des KRG, basée sur la conception insensible aux latences.