Simulation de décalageseffectifs 1D par des décalages de type fini 2D

Simulation de décalages effectifs 1D par des décalages de type fini 2D

Communication entre machines Canaux de communication Les machines de Turing MForbid et MSearch vont avoir besoin de communiquer entre elles. Entre deux zones de calcul adjacentes de même niveau, la communi cation est aisée puisqu’on ne trouve que des tuiles de communication entre ces zones. Ainsi un bit d’information peut être échangé entre deux zones de calcul adjacentes de niveau n à chaque étape de calcul (voir la Partie 2.3.2).

Mais entre deux bandes de calcul de niveaux différents le problème est plus difficile. Nous construisons dans cette partie des canaux de communication pour permettre à des machines évoluant dans des bandes de calcul de différents niveaux de communiquer entre elles. Pour construire ces canaux de communication, nous utilisons une substitution s2 sur l’alphabet G2.

Cet alphabet et les règles de la substitution s2 sont décrites dans la Figure 18. Nous modifions donc le décalage THorloge défini dans la Partie 2.3.4 pour y ajouter ces canaux de communication. Le nouveau décalage est donc : THorloge = TFCount Consist Synchro ProdTs1 s2 CZ2 où la substitution s1 s2 est définie sur l’alphabet produit G1 G2 et dont les règles sont formées d’une règle de s1 et d’une règle de s2.

En conséquence de quoi le décalage TM est lui aussi modifié pour intégrer ces canaux de com munication : TM=TFTransfert Init CompBord ProdTHorlogeAZ2 où le décalage THorloge est celui que l’on vient de redéfinir. Les segments rouges obtenus après itération de la substitution s2 sont appe lées lignes de communication. Elles sont utilisées pour permettre la communi cation entre des bandes de calcul de différents niveaux.

Les lignes de commu nication sont agencées de manière à former des rectangles. Les deux rectangles obtenus après n itérations de la substitution s2 sur un élément de l’alphabet G2 sont appelés rectangles de communication de niveau n. Chaque rectangle de niveau n croise deux rectangles de niveau n 1 et est intersecté par un rectangle de niveau n+1.

Si l’on considère une tuile de calcul de bord (resp. )dans une zone de calcul de niveau n, elle est toujours située à l’intérieur d’un rectangle de communication de niveau n. Ainsi en partant de la tuile de calcul 66 (resp. ) et en se déplaçant vers la gauche (resp. la droite),

on rencontre nécessairement le côté gauche (resp. le côté droit) d’un de ces rectangles. Et sur les côtés supérieur et inférieur de ce rectangle se trouvent deux tuiles de calcul et ,situées dans deux zones de calcul adjacentes de niveau n 1.