Cours et TD du 28/09/2023

Notation : q \xrightarrow[\qquad\Delta]{a} q\prime \text{ pour } (q, a, q\prime) \in \Delta

Année 80-90 : On fait des majeures avancées dans la partie hardware, jusqu’à atteindre une certaine limite
Ensuite, on veut mieux optimiser les logiciels, c’est pour ça qu’ont créé des processus multicœurs afin de pouvoir paralléliser les logiciels.

Dans l’ordre : Matériel > Langage de programmation > Logiciels programmés > Exécuté de manière centralisée ou distribuée ?

On ne peut pas, pour paralléliser des programmes, pour une structure donnée, dire qu’un morceau de code utilise une structure en bloquant les autres, ça, ce serait mauvais niveau performance.

Le but du cours est de comprendre comment de tels logiciels sont écrits pour faire de la concurrence.

Configuration d’un programme : sa mémoire, permet de savoir ce que peut faire un programme à un instant T.

Actions du programme (par ex. une affectation) → changer de configuration (a.k.a. changer la mémoire).

Avec ça on peut définir un graphe d’état avec les sommets, les configurations du programme et les arcs, les actions passant d’un état à un autre (transition).

Système de transition :

S = (Q, \Delta, \Sigma)
avec :

• Q : ensemble d’états
• \Sigma : alphabet d’actions
• \Delta Q \times \Sigma \times Q
  Ceci représente un graphe étiqueté.
  Un compteur :

graph LR;
    id1(( ))--put-->id2(((1)));
    id2--get-->id3(( ));

graph TD;
    0--put-->1;
    1--get-->0;

Un compteur qui va jusqu’à 2 : (buffer de taille 2)

graph LR;
    id1(( ))--put-->id2(((2)));
    id2--get-->id3(( ));

graph LR;
    0--put-->1;
    1--get-->0;
    1--put-->2;
    2--get-->1;

⇾ Avec 2 buffers de taille 1, on peut faire un buffer de taille 2 en les connectant entre eux.

graph LR;
  subgraph " "
    direction TB
    0'--put-->1';
    1'--get-->0';
  end
  subgraph "  "
    direction TB
    0--put-->1;
    1--get-->0;
  end
  1-->0'

Mais ce serait une composition séquentielle, alors, on peut faire ça :

Abstraction :
\begin{aligned} S_{1} =& (Q_{1}, \Delta_{1}, \Sigma) \\\\ S_{2} =& (Q_{2}, \Delta_{2}, \Sigma) \\\\ S_{1} || S_{2} =& (Q_{1} \times Q_{2}, \Delta_{12}, \Sigma) \\\\ \frac{q_{1} \xrightarrow[\qquad\Delta_{1}]{a} q_{1}\prime}{(q_{1}, q_{2}) \xrightarrow[\qquad\Delta_{12}]{a} (q_{1}\prime, q_{2})} & \frac{q_{2} \xrightarrow[\qquad\Delta_{2}]{a} q_{2}\prime}{(q_{1}, q_{2}) \xrightarrow[\qquad\Delta_{12}]{a} (q_{1}, q_{2}\prime)} \end{aligned}

Implémentation :

graph TD;
  a["(0, 0')"]
  b["(0, 1')"]
  c["(1, 1')"]
  d["(1, 0')"]
  a--put-->b
  a--put-->d
  b--put-->c
  d--put-->c

  c--get-->b
  c--get-->d
  d--get-->a
  b--get-->a

Pour un buffer FIFO :

graph LR;
  puta(( ))
  putb(( ))
  geta(( ))
  getb(( ))
  id[ ]
  puta--"put(a)"-->id
  putb--"put(b)"-->id
  id--"get(a)"-->geta
  id--"get(b)"-->getb

graph TB;
  a(a)
  b(b)
  id("-")
  a--"get(a)"-->id
  b--"get(b)"-->id
  id--"put(a)"-->a
  id--"put(b)"-->b

graph TB;
  vide( )
  a(a)
  b(b)
  aa(aa)
  bb(bb)
  ab(ab)
  ba(ba)
  vide--"put(a)"-->a
  vide--"put(b)"-->b
  a--"get(a)"-->vide
  b--"get(b)"-->vide
  a--"put(a)"-->aa
  a--"put(a)"-->ba
  aa--"get(a)"-->a
  ab--"get(b)"-->a
  b--"put(b)"-->ab
  b--"put(b)"-->bb
  ba--"get(a)"-->b
  bb--"get(b)"-->b

Il y a une synchronisation, la boite doit attendre la boite précédente.
\text{Sync} \subseteq \Sigma
\frac{q_{1} \xrightarrow[\qquad\Delta_{1}]{a} q_{1}' \quad q_{2} \xrightarrow[\qquad\Delta_{2}]{a} q_{2}' \quad a \leftarrow \text{Sync}}{(q_{1}, q_{2}) \xrightarrow[\qquad\Delta_{12}]{a} (q_{1}, q_{2}')}

\begin{aligned} & \tau_{a}, \tau_{b} \in \text{Sync} \\\\ S_{1}\prime =& S_{1}\left[\frac{\text{get(a)}}{\tau_{a}}, \frac{\text{get(b)}}{\tau_{b}}\right] \\\\ S_{2}\prime =& S_{2}\left[\frac{\text{put(a)}}{\tau_{a}}, \frac{\text{put(b)}}{\tau_{b}}\right] \\\\ & S_{1}\prime ||\scriptstyle{\{\tau_{a}, \tau_{b}\}}S_{2}\prime \end{aligned}

graph TB;
  subgraph S2
    puta(( ))
    putb(( ))
    geta(( ))
    getb(( ))
    id[ ]
    puta--"τ_a"-->id
    putb--"τ_b"-->id
    id--"get(a)"-->geta
    id--"get(b)"-->getb
  end
  subgraph S1
    2puta(( ))
    2putb(( ))
    2geta(( ))
    2getb(( ))
    2id[ ]
    2puta--"put(a)"-->2id
    2putb--"put(b)"-->2id
    2id--"τ_a"-->2geta
    2id--"τ_b"-->2getb
  end

graph TB;
  vide("(-, -)")
  a_("(a, -)")
  b_("(b, -)")
  _a("(-, a)")
  _b("(-, b)")
  aa("(a, a)")
  bb("(b, b)")
  ab("(a, b)")
  ba("(b, a)")
  
  a_--"τ_a"-->_a
  b_--"τ_b"-->_b
  
  vide--"put(a)"-->a_
  vide--"put(b)"-->b_
  _a--"put(a)"-->aa
  _a--"put(b)"-->ba
  _b--"put(a)"-->ab
  _b--"put(b)"-->bb
  
  _a--"get(a)"-->vide
  _b--"get(b)"-->vide
  aa--"get(a)"-->a_
  ab--"get(b)"-->a_
  ba--"get(a)"-->b_
  bb--"get(b)"-->b_

Pour LIFO maintenant :

graph TB;
  vide("(-, -)")
  
  vide--"put(a)"-->a
  vide--"put(b)"-->b
  a--"put(a)"-->aa
  a--"put(b)"-->ba
  b--"put(a)"-->ab
  b--"put(b)"-->bb
  
  a--"get(a)"-->vide
  b--"get(b)"-->vide
  aa--"get(a)"-->a
  ab--"get(a)"-->b
  ba--"get(b)"-->a
  bb--"get(b)"-->b

Avec des boîtes là (la S2 est la même qu’avant) :

graph TB;
subgraph S2
  a(a)
  b(b)
  id("-")
  a--"get(a)"-->id
  b--"get(b)"-->id
  id--"put(a)"-->a
  id--"put(b)"-->b
end
subgraph S1
  vide["-"]
  x[x]
  vide--"put_g(x)<br>put_d(x)"-->x
  x--"get_g(x)<br>get_d(x)"-->vide
end

Autrement dit :

On a donc :
\tau_{a} = \text{put(x) = get\_d(x) et }\tau_{b} = \text{get(x) et put\_d(x)}

graph LR;
  vide("(-, -)")
  x_("(x, -)")
  _x("(-, x)")
  xx("(x, x)")

  vide--"put_g(x)"--> x_
  x_ --"get_g(x)"--> vide
  x_ --"Tau_a"--> _x
  _x --"Tau_b"--> x_
  _x --"put_g(x)"--> xx
  xx --"get_g(x)"--> _x