DISTRIBUTION ET ORDONNANCEMENT

 
Figure: Graphe algorithme après distribution

L'implantation d'un algorithme sur une architecture consiste à réduire le parallélisme potentiel de l'algorithme au parallélisme matériel disponible. Les modèles de graphes utilisés pour spécifier l'algorithme et l'architecture conduisent à formaliser l'implantation en terme de transformations de graphes.

La réduction est obtenue en transformant progressivement le graphe flot de donnée modélisant l'algorithme en étant guidé par le graphe architecture modélisant l'architecture.

L'Implantation est modélisée par la composition de quatre transformations de graphes

• Routage : connexion complète du graphe de l'architecture Allocation spatiale de ressources

• Distribution des opérations de l'algorithme sur chaque composant

• Distribution des opérations de transfert induites par la distribution précédente sur chaque composant

  Allocation temporelle de ressources

• Ordonnancement de toutes les opérations sur chaque composant

EXEMPLE : Le séquenceur d'un composant programmable
ordonnance des macro-instructions
opérations allouées par la distribution

Cette composition de transformations
conserve les propriétés temporelles montrées
lors de la vérification de l'algorithme hors contraintes matériel