Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/06929.jsonl.gz/148

Peloton d'exécution
Dans cette expérience, le BioWall résoud le problème de
synchronisation de n'importe quelle colonne de cellules
définie par le visiteur. La solution implémentée sur le BioWall
réalise cette synchronisation dans un temps minimal.
Peloton d'exécution
L'implémentation du problème de synchronisation du peloton d'exécution s'opère dans un automate cellulaire à une dimension.
Les cellules de l'automate représentent une colonne de soldats, avec un général à une des extrémités. Le problème consiste à
spécifier les états et les transitions des soldats de manière que le général puisse les amener tous dans un état final particulier
(faire feu avec leurs fusils) au même instant. Au début, tous les soldats sont dans un seul état, l'état de repos. Quand le
général passe à l'état "feu lorsque prêt", il demeure dans cet état et la suite des opérations est laissée aux soldats. Le
signal se propage alors le long de la colonne à raison d'un soldat par pas de temps et leur problème consiste à se coordonner selon
un certain rythme. Pour ce faire, les soldats n'ont pas le droit de compter jusqu'à un nombre égal à celui des soldats du
peloton d'exécution.
Figure 1: Le processus de synchronisation d'une colonne de 10 soldats sur le BioWall.
Mode d'emploi
Dans l'implémentation du peloton d'éxécution sur le BioWall, le visiteur peut d'abord définir une rangée verticale de soldats
au repos, en pressant simplement sur les membranes tactiles d'unités adjacentes dans une colonne donnée (figure 1). Quand on
touche à nouveau n'importe quel soldat au repos, ils deviennent tous actifs (en jaune) simultanément et le dernier vers le bas
se change en général (en rouge). Les états successifs du peloton d'exécution apparaissent alors, un par pas de temps, dans les
colonnes successives vers la droite. Le processus se poursuit jusqu'à ce que tous les soldats atteignent simultanément l'état
feu (en vert).
Il existe plusieurs solutions au problème de synchronisation du peloton d'exécution. La solution à 6 états implémentée sur
le BioWall s'opère en un temps minimal de 2n-1 pas, dans lequel n représente le nombre de soldats de la rangée.
Pour en savoir plus
- J.Mazoyer. "A 6-State Minimal Time Solution to the Firing
Squad Synchronization Problem". Theoretical Computer Science
50, 1987, pp. 183-238.
Ressources

|End of task (final state reached).

© E.
Petraglio
1,308KB JPEG