MODELES D'ALGORITHMES

L'algorithme peut être modélisé par :

• un graphe flot de contrôle
  • organigramme dont les sommets sont des opérations et les arcs une relation d'ordre d'exécution sur des opérations (contrôle : mise en séquence, branchements, conditionnel ou inconditionnel)
  • automate, plus compact, dont les sommets représentent les états et les arcs les transitions d'un état à un autre état. Une transition est effective (tirée) lors de l'arrivée d'un événement (apparition d'une donnée en entrée), elle induit l'exécution d'une opération.
  Dans les deux cas les opérations manipulent les données par l'intermédiaire de variables qui peuvent être partagées par plusieurs opérations, conduisant fréquemment à des erreurs. La mémoire détat est implicitement localisée dans les variables.
  
  Le flot de contrôle induit un ordre total sur l'exécution des opérations.
• un graphe flot de données éventuellement conditionné : graphe de dépendances de données infiniment répété. Pour chaque graphe de dépendance les sommets sont des opérations (atomiques) et les arcs des transferts de données entre opérations. Ils représentent une relation d'ordre d'exécution, pour les opérations se tranférant des données.
  Ce modèle évite les erreurs dues aux partage des variables, il fait apparaître explicitement la mémoire d'état de l'algorithme.
  Il met en évidence le parallélisme intrinsèque de l'algorithme appelé parallélisme potentiel. Les opérations ne se transférant pas de données pourront être exécutées en parallèle si les ressources nécessaires sont disponibles.
  La notion de flot de données correspond à la répétition infinie d'un transfert de donnée. Dans le cas des flots d'entrée et de sortie cela correspond à la notion de suite d'événements entrant et sortant du système.
  
  Le flot de données induit un ordre partiel sur l'exécution des opérations.

to 5cm

 
Figure: Graphe d'algorithme flot de données