# Notes sur la conception structurée des interfaces

Michel Depeyrot

► To cite this version:

Michel Depeyrot. Notes sur la conception structurée des interfaces. [Rapport de recherche] IRIA-RR-131 et IRIA-RR-132, IRIA. 1975, pp.124. hal-04716075

HAL Id: hal-04716075

https://inria.hal.science/hal-04716075v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA

laboria

<figure><img src="image_2.png" /></figure>

laboratoire de recherche
en informatique
et automatique

# Notes sur la conception structurée des interfaces

(Première partie)

<figure><img src="image_3.png" /></figure>

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n°131
Septembre 1975
<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /></figure>

# NOTES SUR LA CONCEPTION STRUCTURÉE DES INTERFACES

## (Première partie)

M. Depeyrot

## SOMMAIRE

Le langage PMS est un ensemble de primitives de description de calculateurs qui tend à être utilisé aussi pour les spécifications de leur conception.

Une faiblesse apparente du langage PMS, son manque de dynamique, est compensée ici par le biais de la formalisation des liaisons L. La motivation est que les liaisons jouent en fait un rôle essentiel pour procurer la réinformation ("feedback") dans un circuit logique, ce qui au niveau le plus fin permet de transformer les circuits combinatoires en séquentiels, puis permet au niveau des transferts de registres d'introduire le contrôle des sous-programmes, et enfin au plus haut niveau permet de réaliser la modularisation des structures. Les liens L dans PMS devraient donc être traités comme des processeurs d'interface tout en restant différents des processeurs de traitement P par des propriétés syntaxiques remarquables. L'analyse des relations entre les propriétés de dualité et les problèmes de synchronisation permet d'introduire adéquatement les primaires de base des interfaces.

Les propriétés syntaxiques et sémantiques hiérarchisées des liaisons permettent la décomposition en cascade de la commande d'interface $K_L$ en sous-modules de commande K, un progrès essentiel vers la "Conception Structurée", fournissant ainsi une technique de minimisation et de détection d'erreur, tout en facilitant l'implémentation et le test assistés par ordinateur.

Enfin l'étude exhaustive d'un exemple de liaison à 14 signaux amène à étendre le modèle d'automate et à définir une technique d'implémentation appelée microdiagramme.
Ce texte est la version française, mise à jour depuis la première présentation, du *Cours Avancé sur l'Architecture des calculateurs* de l'Alpe d'Huez ([3] : "Link dynamics and interface decomposition in PMS"). Le titre initial "Dynamique des liaisons et décomposition des interfaces en PMS" révélait plus l'outil que l'objet : l'outil, c'est un exemple d'interface d'entrée-sortie de système doté de mécanismes aptes à améliorer sa fiabilité ; mais l'objet, c'est la Conception Structurée des Systèmes, tant logiciels que matériels à l'aide du langage descriptif PMS rehaussé de l'appareillage dynamique issu de la théorie des automates.

Ce document-ci peut être lu indépendamment mais il s'insère dans une série donnée en référence : [1], [2], [4] dont les premiers sont déjà parus. Sa deuxième partie, à paraître prochainement, est la version française, mise à jour depuis sa première présentation, d'un exposé du *Colloque International sur l'Architecture des Calculateurs* de Grenoble ([4] : "Design of interfaces as stochastic channels with memory"). Elle inclut aussi un certain nombre d'extensions et un exemple d'application à un problème de microprocesseur.

**Mots clés** : Conception Assistée par Ordinateur, Décomposition, Interface, Liaison d'entrées-sorties, Canaux de Communication, Microdiagrammation, Modularisation, Test et Diagnostic, Dualité, Hiérarchie, Synchronisation, Polymate Paramétré, Microprocesseur.
La tendance des circuits électroniques composant les systèmes va vers une intégration à plus grande échelle qui conduit à remplacer finalement la conception des calculateurs par la conception des interfaces et liaisons L.

ABSTRACT

PMS is a set of computer description primitives that tends to be used as well for computer design specifications.

An apparent weakness of the PMS language, namely its lack of dynamics, is tackled here through the formalization of links L. The motivation is that links actually play an essential role to provide feedback in a logic circuit, which at the lowest level helps transform combinatorial circuits into sequential ones, then helps at the level of register transfers to introduce subprogram control, and finally helps at the highest level to realize modularization in structures. Links L in PMS should hence be considered as interface processors, while remarkable syntactic properties keep them distinct from computing processors P. It is shown how duality properties and synchronization problems interfere so as to introduce adequately the basic interface primitives.

Hierarchical syntactic and semantic properties of links make feasible the cascade-decomposition of their interface control $K_L$ into control submodules K, an essential improvement toward "structured design", hence providing us with a minimization and error-detection technique, while helping computer-aided design and test.

Finally, the thorough study of a 14-signal link example leads to extending the model of automata and to defining an implementation technique called microdiagramming.

Tendency for electronic circuits building up systems tends toward a larger scale integration that leads to replacing ultimately computer design with the design of interfaces and links L.
TABLE DES MATIERES

I. LIENS LOGICIELS ET MATERIELS DANS LES SYSTEMES INFORMATIQUES.

I.1. Rappel des définitions des primitives de PMS.

I.2. Précisions sur les liaisons et liens.

I.3. Rappel sur les modes de synchronisation.

II. HIERARCHIE, DUALITE ET SYNCHRONISATION DANS LES INTERFACES.

II.1. Langage de liaison, hiérarchie et compromis dans la dualité.

II.2. L'interface de synchronisation au niveau physique.

II.3. L'interface d'information au niveau physique.

II.4. De la dualité à la synchronisation.

III. ASPECTS SEMIOTIQUES DES INTERFACES SUR LIAISONS.

III.1. Fonctions de processus et de flux.

III.2. Les sept degrés sémiotiques.

IV. DEVELOPPEMENT DU PARADIGME DE DECOMPOSITION DE LIENS.

IV.1. Spécification algorithmique du dialogue.

IV.2. Spécification des transferts de registres et interconnexions.

IV.3. Elaboration des diagrammes de commande.

IV.4. L'implémentation des chemins de flux.

IV.5. Minimisation du graphe d'états.

IV.6. Assignation du codage des états sur un polymate paramétré.

V. APPLICATION ET ANALYSE DE LA CONCEPTION DESCENDANTE.

V.1. La microdiagrammation.

V.2. Notation en Chevrons pour le processus de conception descendante.

REFERENCES BIBLIOGRAPHIQUES.
# I. LIENS LOGICIELS ET MATERIELS DANS LES SYSTEMES INFORMATIQUES.

Selon qu'un système dynamique complexe est présenté en mettant l'emphase sur ses modules composants ou sur leur interconnexions, on peut utiliser un **graphe de fluence** (modules/sommets) ou un **diagramme de blocs** (interface/sommets). En ce sens le module (support de réalisation d'une fonction) et l'interface (support de passage d'un contexte) apparaissent comme duaux.

<figure><img src="image_6.png" /><figcaption>Figure 1. Graphe de fluence et diagramme de blocs.</figcaption></figure>

L'organisation de cette étude est fondée sur l'idée suivante : les concepts récents dans l'architecture des Systèmes -compatibilité, portabilité, adaptabilité, sécurité, protection, transparence- sont des propriétés d'interfaces entre les modules composant ces systèmes selon une organisation très structurée. Et en conséquence des trois principes dégagés (dualité, hiérarchie, synchronisation) trois classes d'interfaces doivent être distinguées :

**VERTICALES**: celles entre modules duaux (commandes et opérations) posant le problème de la factorisation duale rigoureuse, [2].

**HORIZONTALES**: celles entre modules à niveaux sémantiques différents, supérieur et subalterne immédiat (dans une hiérarchie), posant le problème d'une hiérarchisation claire,

**TRANSVERSES**: celles d'un même type à un même niveau, posant le problème d'une interconnexion appropriée.
<figure><img src="image_7.png" /><figcaption>Figure 2. Les trois classes d'interfaces.</figcaption></figure>

L'importance de cette approche de l'analyse des systèmes par le biais de leurs interfaces et des dialogues d'interconnexion est accrue par l'évolution technologique actuelle conduisant à un degré supérieur de modularisation tant pour les machines que pour leurs programmes. [21].

Au lieu d'essayer d'employer les modèles d'automates à des niveaux toujours plus fins des composants des machines [à cause de l'accroissement constant de la densité des circuits logiques qui a vu passer le niveau de validité de ces modèles du panier de DTL* (Années 50) à la plaquette d'ECL* (Années 60) puis au boitier de LSI* (Années 70)], la tendance de cette étude consiste à utiliser les modèles [24,25] d'automates pour la spécification des interfaces entre composants **fonctionnels** qui peuvent être exprimés en PMS† (et non seulement **topologiques** qui ne peuvent être eux exprimés que dans un contexte technologique précis).

De la sorte les problèmes de liens logiques (contexte) et de liaisons physiques (connexions) entre processeurs sont traités respectivement comme des problèmes d'**assignation de valeur** et d'**entrée-sortie**.

(*) DTL : Diode-Transistor logic.

ECL : Emitter-Compled logic.

LSI : Large-Scale integration.

(†) PMS étant utilisable tant pour le matériel que pour le logiciel [7].
Ce rapport présente le troisième volet d'une étude sur les Interfaces : celui concernant les interfaces transverses liant les modules au même niveau sémantique et qui sont dualement complets, c'est-à-dire liant des processeurs P avec leur unité de commande propre K et leur unité de transfert de registres propre D.

# I.1. Rappel des définitions des primitives de PMS [7].

1) **L** (liaisons ou liens) transfère des données d'un emplacement à un autre sans modification. La procédure de transmission a la forme d'un algorithme dont les étapes sont obtenues par entrelacement des actions initialisées alternativement par chacun des deux modules terminaux de la liaison. Cette procédure et les conventions de représentation des données forment l'interface.

2) **S** (sélecteur, commutateur ou décodeur) change la liaison qui connecte des composants à accès multiplexé afin de réorienter les transferts de données. Il permet l'adressage d'autres primitives.

3) **K** (commande, contrôle, séquencement) actionne l'exécution des opérations d'un composant dans le système en réponse aux diverses conditions d'entrée et en fonction de son propre état interne.

4) **D** (Opérateurs sur les Données, unité d'exécution) est le composant qui produit une nouvelle information dans une certaine représentation codée à partir d'un ensemble de données d'entrée.

<figure><img src="image_8.png" /><figcaption>Figure 3. Synoptique d'un système actuel en PMS.</figcaption></figure>
5) **M** (mémoire) enregistre les données sans modification au cours du temps. La mission essentielle de cette primitive "passive" est d'offrir une grande capacité d'enregistrement (elle est dite *passive* en ce sens qu'elle est incapable d'exécuter un algorithme).

6) **T** (transducteur, transcodeur ou modulateur) change le format des données, à partir d'une représentation non-numérique (analogique, externe au système numérique) ou à partir d'une représentation numérique (codage en bits, octets,...) vers une autre (internes au système numérique), mais il ne modifie pas la quantité d'information associée.

7) **P** (processeur) est un sous-système consistant en un ensemble d'autres composants avec un K qui détermine interprétativement la prochaine opération à requérir afin de pouvoir progrésser de manière autonome. Ainsi $P = \langle K, D \rangle$ où le symbole ", " représente l'interface vertical entre l'automate de commande ordonnant des actions et l'automate d'exécution signifiant dualement des conditions. De ce point de vue la différence entre D et T en quantité d'information consiste en ce que D ajoute aux données d'entrée (V*) les informations de commande (Z) émises par K.

<figure><img src="image_9.png" /><figcaption>Figure 4. Le tourbillon d'un processeur $\langle K, D \rangle$.</figcaption></figure>

La mission essentielle de cette primitive "active" est d'offrir une grande vitesse d'exécution (elle est dite *active* en ce sens qu'elle seule est capable d'exécuter un algorithme).

Un calculateur **C** est un système incluant au moins un processeur **P** et une mémoire **M** contenant le programme des opérations destinées à **P**. La connexion de plusieurs **C** forme un réseau **N** ("network").

C peut être vu comme une boîte noire dont l'environnement **E** intervient en entrée $E_I : \emptyset \to V^*$ et en sortie $E_O : W^* \to \emptyset$, où $V$ est l'alphabet fini d'entrée codant toutes les données (instructions et opérandes), où $W$ est l'alphabet intermédiaire incluant Y celui des résultats (sorties de $D$) et où $\emptyset$ est l'ensemble vide.
L'environnement $E = \{E_I, E_O\}$ mémorise les données, avec modifications éventuellement, afin d'être une source et un puits pour le flot au travers ("throughput") du système C. Celui-ci apparaît comme un quadruplet où chaque tiret (-) représente une interface transverse (de connexion) :

C ::= P-M-L-T (-E) où P = <$K_P, D_P$> et L = <$K_L, D_L$> effectuent des assignations de valeurs, mais $D_P$ représente des opérations *transformationnelles* comme $A ::= B + \bar{R}$ (opérations booléennes) tandis que $D_L$ représente des opérations *translationnelles* comme $d_M ::= \delta_T$ où $d_M$ est une variable en M et $\delta_T$ est une valeur en T. Ceci revient à distinguer entre calcul et accès-mémoire ou entrée/sortie.

Le rôle des liens L dans cette recherche de conception structurée (tant pour les programmes que pour les machines) mérite d'être souligné : parce que $D_L$ est seulement translationnel, l'étude de L est plus simple que celle de P. L'analyse des interfaces et liaisons facilite donc la mise en évidence des principes fondamentaux comme c'est le cas en référence [3]. De plus chaque fois qu'un L apparaît explicitement dans une équation architecturale en PMS, une interface est spécifiée, mais plus souvent une interface doit être définie alors qu'une liaison L n'apparaît pas explicitement, comme dans le cas d'une connexion P-M entre un processeur et sa mémoire.

## I.2. Précisions sur les liaisons et liens.

Du point de vue de l'architecture, L est la primitive essentielle, le ciment d'un système. La théorie des automates permet d'introduire par ce biais les concepts de méthodes d'accès et de machines séquentielles qui manquent à l'approche descriptive de PMS [26].

**Définition.** Une *liaison* ou *lien* est un triplet $(V,Y,\delta)$ où $\delta$ est une fonction de transfert $\delta: V* \to Y^*$ (où $V^*$ est l'ensemble des séquences finies obtenues par concaténation d'éléments d'un ensemble $V$). Dans les cas simples, où il n'y a pas de transduction séquentielle pour supporter une procédure du dialogue, $\delta: V \to Y: v \to y$ introduisant simplement un délai.
La définition logique des procédures de transfert sur un lien est une spécification d'interface séquentielle.

Un lien **multipoint** est tel que $V = \sum_{i=1}^{a} V_i$ ou $Y = \prod_{j=1}^{b} Y_j$, où × est le symbole du produit cartésien. (40)

Si $a = 1 = b$, le lien est **bipoint** entre deux primitives P et P': $P - L - P'$.

Un lien **simplex** $\vec{L} = (V, Y, \vec{\delta})$ permet exclusivement des transferts d'une primitive terminale vers l'autre : $P \to L \to P'$.

Un lien **demi-duplex** permet la transmission dans les deux sens, mais dans un seul à la fois. Il doit être représenté comme un lien à une seule voie physique : $P - L - P'$.

Un lien **vrai-duplex** permet la transmission simultanée dans les deux sens. Il peut être représenté par une paire de liens $(\vec{L}, \vec{L}')$ de sorte que $P \to L \to D'$. En fait il peut s'agir d'un dédoublement physique ou d'un multiplexage temporel de la même voie.

La **largeur logique** d'un lien est le nombre de bits d'information pouvant circuler simultanément. La **largeur physique** est le nombre de fils pouvant transmettre des signaux utiles.

Un seul module terminal doit avoir le contrôle des transferts sur un lien à un instant donné afin de permettre un ordonnancement cohérent des transferts et des traitements d'erreur [28].

Le contrôle d'un lien est **centralisé** si c'est toujours le même module terminal P qui peut et doit initialiser les transferts. La fonction de synchronisation est représentée en pointillé :

$P \text{ = = = = = = } L \text{ = = = = = = } P'$

La fonction de transfert d'informations (données et instructions) est en trait plein double. Occasionnellement on notera aussi $P \text{ = = = = = } L$.

Le contrôle d'un lien est **symétrique** si les deux terminaux sont capables d'initialiser les transferts :

$P \text{ = = = = = = } L \text{ = = = = = = } P'$
### I.3. Rappel sur les modes de synchronisation.

La préemption du lien requiert un mécanisme d'interblocage avec une certaine priorité. Le mode fondamental (F) consiste à refuser les entrées tant que l'état interne est instable et le mode hiérarchisé (H) consiste à découper l'échel-le du temps en demi-périodes où les entrées sont acceptées et demi-périodes où les états sont instables.

- mode F (réinformation des états) :

en cas de conflit dû à des accès simultanés, les deux terminaux peu- vent réitérer leurs requêtes d'accès avec des périodes différentes.

- mode H (hiérarchisé par une horloge) :

le contrôle du lien est hiérarchisé si un module superviseur peut initialiser les transferts (Horloge par exemple).

<figure><img src="image_10.png" /></figure>

Le mode H facilite la rapidité de coopération de composants physiquement éloignés, mais il ralentit le traitement à la vitesse du processeur le plus lent. Le mode F facilite la rapidité de coopération de composants rapprochés ainsi que le traitement des erreurs quand les signaux de réinformation (cf. retour impli-cite au §. II.4) sont utilisés pour informer l'émetteur des incidents de trans-mission sur les liens L correspondants ; mais il introduit des problèmes de courses (critiques éventuellement) dès que des accès simultanés sur des res-sources communes (sections critiques) sont possibles.

### Exemples.

1) Les entrées-sorties directes d'un calculateur sont effectuées en mode H par *scrutation* ; en mode F, elles sont gérées par *interruptions* prioritaires.

2) La composition des automates par produit pseudo-direct [9] requérant l'en-trelacement des transitions des composants est en mode F, tandis que la composition par produit direct ou semi-direct [25], requérant la simultanéité des transitions des composants, est en mode H : l'absence de signal de retour est requise par les théories algébriques actuelles.

3) Dans un polymate, l'aduction [26] en mode F est un forçage et en mode H une permutation sur l'espace d'état.
4) Les télétransmissions sur réseau en mode H sont dites périodiques et font usage de compteurs et horloges de garde locales, tandis qu'en mode F elles sont dites apériodiques et font usage de signaux de retour ("handshaking feedback") N.B. Le degré de finesse des définitions introduites correspond spécifiquement aux besoins de ces "Notes", mais le principe du langage PMS est de permettre un effet de "zoom" pour détailler au besoin.

## II. HIERARCHIE, DUALITE ET SYNCHRONISATION DANS LES INTERFACES.

Tout problème de synchronisation entre modules J (Unité de logiciel [6,15,23] ou de matériel [17,18,21]) est un problème de lien L (ou liaison), car c'est la gestion du dialogue sur leur interface qui établit la synchronisation de deux modules. J peut tenir lieu d'un processeur P ou d'une unité de mémoire M, ou encore d'un transducteur T... Dans ce paragraphe-ci les liens L sont formalisés plus finement qu'auparavant pour montrer comment leur rôle est essentiel dès le niveau élémentaire des circuits logiques pour porter la réinformation assurant le passage du combinatoire au séquentiel, puis au niveau des transferts de registres pour introduire le contrôle par sous-programme et aux niveaux supérieurs pour permettre une structuration modulaire de schéma de traitement.

### II.1. Langage de liaison, hiérarchie et compromis dans la dualité.

**Définition.** Soit L la connexion entre deux modules J et J'; deux terminaux [15] ("port") P<sub>L</sub> et P'<sub>L</sub> lui sont associés pour gérer la liaison dans chacun des modules. Leur notation résulte de leur interprétation : <u>processeurs de liens</u>.

L est l'emplacement d'un dialogue et peut donc être fictivement décomposé en une paire de liens simplexes L' et L" tels que :

$$J \to L' \to J'; \quad J \leftarrow L'' \leftarrow J'$$

Chaque lien simplexe est le lieu de génération et de réception d'un langage. Pour clarifier les idées, il est utile de comparer les quatre phases de la traduction d'un langage aux quatre phases de la communication sur une liaison.
Figure 5. Représentation synoptique d'une liaison.

G signifie Générateur et R signifie Récepteur. J est un module logiciel ou matériel.

<figure><img src="image_11.png" /></figure>

G et R' appartiennent à la liaison L' de J à J' tandis que G' et R appartiennent à la liaison L'' de J' à J. Une coordination interne à P_L et P'_L est requise pour l'emploi simultané des deux liaisons simplexes L' et L'' de L.

Une liaison duplex $L = (L',L'')$ est donc un quadruple $(G,R,G',R')$ tandis que chaque contrôleur de terminal en inclut une moitié :

$P_L = (Gin,Rin,G,R)$ et $P'_L = (G',R',Gin',Rin')$, où les autrès moitiés (à suffixe in) sont les parties des contrôleurs de terminal internes à J et J'.

On note $K_L = (G,R)$, $K_{in} = (Rin,Gin)$

et $K'_L = (G',R')$, $K'_{in} = (Rin',Gin')$.

D'où l'équation du lien en PMS :

$$L := J - K_{in} - K_L - L - K'_L - K_{in}' - J'$$

Chacun des contrôleurs de terminal $P_L$ et $P'_L$ effectue une traduction de requêtes en messages et de messages en fonctions.
Les quatre phases de la traduction :

Par exemple $P_L$ peut être vu comme un transducteur :
Requêtes → Rin - G → messages L'.

Support lexical : décodage des mnémoniques
Organisation syntaxique : décomposition des requêtes.

Activité sémantique : interprétation des requêtes
Expression pragmatique : génération des messages sous forme de paquets (signaux de synchronisation et code)

Activité des accepteurs de requêtes ou messages : Rin', R, Rin ou R'.

Activité des émetteurs de messages ou fonctions : G', Gin, G ou Gin'.

Ainsi chaque contrôleur de terminal $P_L$ et $P_L'$ effectue deux traductions dont une seule concerne la communication-même sur l'interface L (G,R ou G',R'). D'où le deuxième point de vue exprimé comme suit.

Les quatre phases de la communication :

Seuls les modules directement liés à l'interface L sont concernés :

$K_L$ ______ L ______ $K'_L$ ≡ $[_{R \leftarrow L' \leftarrow G'}^{G \rightarrow L' \rightarrow R'}]$

Construction sémantique : élaboration des messages
Activité pragmatique : gestion de la synchronisation

Activité des émetteurs de messages : G et G'.

Support lexical : (dés-)assemblage des messages
Structure syntaxique : analyse des requêtes

Activité des accepteurs de messages : R' et R.

Sur une chaîne comme G'-L''-R, le générateur G' est présenté comme un émetteur de messages dans un langage-source tandis que R est présenté comme un récepteur de langage-objet opérant de manière interprétative.
Une version non-modulaire de l'interconnexion J-J' est ce qui reste du système J-L-J' quand Kin est directement connecté à Kin'. La différence est précisément L et donne la mesure du coût d'une conception modulaire. En l'absence d'un lien L, l'interface entre J et J' est le quadruple :

$$I_L = (R_{in}, G_{in'}, R_{in'}, G_{in}).$$

Notons [voir 8] l'interface L'' par un triplet de lignes pointillées (——=——), où la ligne isolée transmet les signaux de contrôle et synchronisation tandis que la ligne double porte l'information, c'est-à-dire d'une part instructions et paramètres, d'autre part pointeurs et valeurs de variables.

<figure><img src="image_12.png" /><figcaption>Figure 6. Equation de Liaison en PMS.</figcaption></figure>

La connexion $L^+$ entre $K_{G'}$ et $K_R$ représente la dynamique de la liaison au niveau "hardware" où le temps est une échelle continue, tandis que $L^\ddagger$ entre $D_{G'}$ et $D_R$ représente l'ensemble des registres supportant le flux d'interface pour le niveau de langage synchrone où le temps est une échelle discrète (échantillonnée). En d'autres termes, deux types de contrôle doivent être distingués : l'un physique ($L^+$) et l'autre logique ($L^\ddagger$) ; ils correspondent respectivement à la coordination et à la communication.
La dualité entre les classes d'information transitant sur $L^+$, de commande et de texte, présentée au niveau logique dans la référence [2], peut maintenant être étendue à une dualité de niveau physique entre **signaux de synchronisation** et **bits d'information**. Intuitivement à ce niveau $L^+$ les premiers signaux peuvent être associés au temps (séquencement) et les seconds (bits) à l'espace (codage). Il y a possibilité de compromis entre eux aussi ("trade-off") pour un certain débit d'information (ou vitesse du flux en bits) du fait que la cadence entre impulsions peut être échangée contre la largeur de la liaison (nombre de fils). Nous avions rencontré un tel compromis pour le niveau logique $L^+$ et nous le retrouvons au paragraphe IV.2. pour la mémorisation des paramètres d'itération (DO UNTIL), soit dans K soit dans D [cf. 8]. Ce compromis dans la dualité est une des difficultés essentielles en CONCEPTION STRUCTUREE de machines informa-tiques.

## II.2. L'interface de synchronisation au niveau physique (échange de signaux "hardware").

Nous avons vu que la synchronisation des bases de temps de modules ayant des horloges différentes est l'affaire du **noyau cablé** des machines qui n'est jamais réductible à de la programmation dans quelque échange d'implan-tation que ce soit entre le programmé et le cablé. De plus (§.1.3) l'importance des modes de synchronisation F et H dans l'étude des liens tient à ce qu'une interface est généralement introduite dans un système pour permettre l'accès partagé en bon ordre à un module donné J à partir de plusieurs modules asyn-chrones $J'$ :

<figure><img src="image_13.png" /><figcaption>Figure 7. Schéma de liaison multiaccès entre modules.</figcaption></figure>

Un mode **hybride** de synchronisation est le cas le plus fréquent : il consiste en une combinaison booléenne des modes F et H : le mode F $\cup$ H les emploie alternativement ; le mode F $\cap$ H les emploie de manière redondante.
Un paradigme de l'insolvabilité logique du problème de la réjection de requêtes asynchrones en dialogue de mode F consiste en un mécanisme d'allocation du module J au premier des modules J' qui y accède et de réjection des autres modules J' jusqu'à ce que J soit libéré par le premier preneur. Ce problème est au niveau physique ce qu'est au niveau logique le problème du producteur (RO par exemple ici) et du consommateur (RI par exemple ici) présenté en [2].

<figure><img src="image_14.png" /><figcaption>Figure 8. Un circuit de réjection d'accès.</figcaption></figure>

L'intersection logique ($\cap$) des signaux RO et RI en provenance des modules J' asynchrones résulte en un signal non-logique au point $\alpha$ puisque l'impulsion de sortie n'a aucune largeur-limite garantie. Le principe d'incertitude de HEISENBERG s'applique à la bascule de décision DI dès que RI n'arrive pas le premier, de sorte que le temps pris par DI pour décider de basculer ou non est indéterminé.
Si RO et RI arrivent au même instant un circuit de priorité rejette
RI en β, mais l'incertitude demeure, avec une probabilité fonction de la techno-
logie et des délais de liaison, quand RI arrive légèrement plus tôt que RO et
dès que la zone d'incertitude touche le point β, même si RI arrive en second.
A cause de la dispersion des délais des circuits, un mécanisme de réjection de
longueur finie est sans faille seulement en probabilité. La solution ultime
consiste en la détection des conflits par un circuit ET appliqué sur les bas-
cules DO,DI ou MO,MI, pour déclencher l'inhibition de RI.

II.3. L'interface d'information au niveau physique (transfert de bits
cablés).

L'information proprement dite est transportée sur des lignes spécifiques connectant des registres traités comme autant de rangées d'éléments de mémorisation de bits ; le nombre de ces éléments par rangée correspond à la largeur en bits de la liaison.

L'Art de la Conception requiert la prise en compte harmonieuse à la
fois des exigences "descendantes" (depuis le niveau logique ou synchrone jusqu'à
ce niveau-ci de registres du flux) et des exigences "ascendantes" (depuis le
niveau physique ou asynchrone jusqu'à ce même niveau de transfert de registres).
Cet Art ne doit pas être confondu avec une absence de rigueur, car il permet
l'application à ce niveau de diverses techniques de développement systématique
éventuellement composables par des méthodes heuristiques.

Une fois que le mode de synchronisation est réalisé, ce qui revient
pour la commande $K_G$ du générateur à un moyen d'activer une horloge relative
à l'intérieur de la commande du récepteur $K_R$, il reste à établir une certaine
interaction entre cette horloge esclave relative et les registres IER de bordure
de la liaison ("latches" ou loquets), ainsi qu'à choisir les propriétés des
éléments de mémorisation par bits (bistables) [26].
<table><caption>Figure 9. Tableau synoptique de l'effet oblique.</caption><thead><tr><th></th><th>Transition du Contrôle</th><th>Transfert d'information</th></tr></thead><tbody><tr><td>Logique<br>(synchrone)</td><td>I<sub>k</sub> (activations)</td><td>I<sub>D</sub> (données)</td></tr><tr><td>HIERARCHIE</td><td></td><td></td></tr><tr><td>Physique<br>(asynchronne)</td><td>Synchronisation I<sub>k</sub></td><td>Texte I<sub>T</sub> = I<sub>D</sub> + I<sub>K</sub></td></tr><tr><td></td><td>Coordination</td><td>DUALITE</td></tr><tr><td></td><td></td><td>Communication</td></tr></tbody></table>

La différence essentielle entre le matériel et le logiciel réside en ceci que le premier créé une infrastructure temporelle discrétisée pour le second, de sorte que les programmes se déroulent sur une échelle de temps sans continuité et donc sans incertitude fondamentale. Ainsi, tandis que les problèmes d'asynchronisme sont solubles de manière déterministe au niveau logique (PROGRAMMES), ils ne le sont que de manière stochastique au niveau physique (MACHINES).

Tout découpage d'un module en sous-ensembles ne définit pas une interface transverse (§.I) : une interface de lien assume un mode de communication spécifique et donc un langage, mais tout langage ne définit pas une interface transverse à moins qu'il ne possède [6] une certaine transparence vis à vis des mécanismes de réalisation de son générateur et de son récepteur, c'est-à-dire une certaine possibilité d'ignorance du niveau physique par le niveau logique (interface horizontale entre sémantique et pragmatique).

Nous avons vu au §.I.2 qu'une interface verticale correspond à la virgule entre K et D dans P = <K,D> ou encore entre (P-M) et (L-T) dans C::= P-M-L-T ou encore entre K<sub>R</sub> et D<sub>R</sub> dans un processeur de lien P<sub>L</sub>.
De manière générale [2] toute instruction au travers d'une interface verticale commande un transfert de données qui peut être monadique $R ::= \bar{R}$, diadique $S ::= A+B$, etc. et qui génère une assignation de valeur fournissant un résultat S et/ou un code de condition en retour sur l'interface verticale.

### Assertion 1.

Une interface verticale entre deux modules est telle que la séquence des instructions exécutées peut seulement être spécifiée interprétativement (à cause des prédicats).

Ceci est le cas pour tout langage de nature universelle [12] dont le contrôle est basé sur les trois primitives suivantes de programmation verticale :

- séquencement avec THEN (transmission d'activation),

- itération avec DOUNTIL (gestion d'un compteur),

- condition avec IFTHENELSE (gestion d'un prédicat).

De telles interfaces sont aussi appelées transformationnelles. Elles sont étudiées algébriquement en [2].

### Assertion 2.

1) Une interface est transverse si la séquence des instructions échangées est indépendante de l'exécution. Ce peut donc être une interface verticale restreinte avec un langage inconditionnel (sans IFTHENELSE) ou une interface translationnelle comme L dans M-L-T.

2) Une interface transverse est une interface de lien quand les seuls transferts de données sont des transferts-identités (translation dans $D_L$) basés sur les deux primitives suivantes :

- rangement avec TAKE (écriture),

- chargement avec GIVE (lecture).
## II.4. De la Dualité à la Synchronisation.

Le but de ce paragraphe est de regrouper les concepts logiciels et matériels de liage et de multi-accès.

Une section de programme est complètement spécifiée à l'instant où il n'a plus de nom de variable libre. Son évaluation peut alors être effectuée en commençant par l'étape de compilation [2,23] et en terminant par l'étape d'exécution au fur et à mesure du liage par substitutions.

### II.4.1. Schéma de traitement complexe.

Le choix de l'instant de certaines opérations de liage affecte la validité de l'évaluation, surtout dans le cas d'expressions liées au contexte quand plusieurs programmes emploient un contexte partagé. L'accès aux cellules de mémoire partagées (sections critiques) doit alors être protégé par un mécanisme d'interblocage (LOCK) ou verrou.

Le graphe de contrôle $G_K$ des phases d'un traitement d'information[2,22] pouvait jusqu'ici en monotraitement être décrit avec des primitives de contrôle [12] combinatoires comme IFTHENELSE, DOUNTIL, THEN, (FORK, JOIN, QUIT, ...). Pour le séquencement de processus parallèles à partage de ressources (D ici) permettant le multitraitement, des primitives séquentielles deviennent nécessaires (P,V,...).

On peut citer comme exemple la primitive SEQ (séquence) qui implique que les activations qu'elle désigne ($\rightarrow$) ne peuvent être simultanées mais doivent se succéder dans un ordre prescrit. Chaque processus activé doit renvoyer un signal (<-----) de retour au terme de son activité.

Le parallélisme géré par des primitives combinatoires [1,2] n'est pas de même nature que celui considéré ici. En effet la synchronisation là est gérée directement entre polymates de commande K sans l'intermédiaire de sections critiques en D. La synchronisation ici se fait au niveau des ressources partagées car les divers K sont logiquement indépendants. Ce parallélisme-ci est dit asynchrone.

Le graphe de contrôle $G(K_i)$ d'un processus parallèle peut maintenant faire apparaître pour chaque branche $z_m$ des connexions d'activation (START) d'un autre processus $K_j$ et non seulement des connexions de transfert de registres (ACTION) en $R(D_i)$, comme indiqué sur la figure 10.
La transition de $z_m$ vers son successeur $z_n$ peut requérir maintenant des con-
nexions de retour (DONÉ) signalant la fin de l'exécution du processus-fils
par $K_j$ (et non seulement une connexion de condition en provenance de $D_i$). Le
START et le DONÉ jouent les rôles similaires aux primitives FORK et JOIN [2],
mais $K_j$ peut maintenant être le mécanisme d'interblocage LOCK, ce qui permet
que le partage de ressources soit possible, c'est-à-dire que :

$$
D_i \cap D_j \neq \emptyset.
$$

Nous appelons _schéma de traitement complexe_ un ensemble de graphes de contrôle
ainsi connectés (et un module est une implémentation spécifique d'une primitive).

<figure><img src="image_15.png" /><figcaption>Figure 10. Interconnexions dans un schéma de traitement complexe.</figcaption></figure>

Pour exprimer qu'un processus ou son graphe est _inactif_, il suffit de
définir un _état zéro_ dans l'espace d'état de leur polymate, et son activation est
alors effectuée par une entrée additive $u_0$ forçant un état initial. Cette possibi-
lité est offerte par l'implémentation $R(K)$ en forme canonique duale [1].

Dans le cas des polymates [26], les interconnexions d'activation se font
par le moyen du vocabulaire additif U, tandis qu'ici les mêmes polymates K sont
interconnectés par le moyen du vocabulaire multiplicatif V et se voient les uns
les autres comme des D car ils sont actifs simultanément et indépendamment.
A chaque connexion entre graphes de contrôle d'un schéma de traitement
correspond un bit d'état de liage η :

$\eta(\alpha) = \begin{cases} 1 & \text{si et seulement si l'exécution est initialisée (START),} \\ 0 & \text{si et seulement si l'exécution est achevée (DONE).} \end{cases}$

Un sommet est **inactif** si ses connexions d'entrée et de sortie sont à l'état 0. Il en est de même pour un graphe liant une sortie (<—>) à toute entrée (→).

Un sommet d'un graphe $G(K)$ est dit **initialisé** lorsque son expression booléenne d'entrée vaut 1 et toutes ses connexions de sortie ont la valeur 0. Sa fonction peut elle-même être représentée par un graphe $G(z)$ lorsque elle est séquentielle comme SEQ. Une configuration de référence d'un graphe $G(K)$ est un ensemble d'états de connexions d'entrée commandant un changement d'état de connexion de sortie.

L'état d'un module ou processus K est défini par l'ensemble des sommets actifs. Le module K est **applicable** quand une configuration d'évènements sur ses connexions d'entrée primaires est une configuration de référence : il entre alors en activité. Un module est **primitif** s'il est fait seulement d'un $K_i$ non connecté à un $D_i$ mais seulement à d'autres $K_j$. Un module d'exécution ne contient que des connexions d'entrée α. Un module est **en attente** tant qu'il n'a pas reçu le signal de retour après avoir émis une activation.

<figure><img src="image_16.png" /><figcaption>**Figure 11.** Module et graphe de la primitive de diffusion homogène PARALLEL FOR.</figcaption></figure>
Un schéma de traitement est _valide_ si le renvoi d'un DONE ($\eta_i(\omega_i)=1$) a lieu au bout d'un temps fini après réception du START correspondant ($\eta_i(\alpha_i)=1$). Il est dit _sans pertes_ si ses sections critiques sont bien protégées, c'est-à-dire si aucun module applicable ne peut affecter les transferts de registres effectués par un autre module simultanément applicable [KAR.69].

Un schéma est sans __ ("Deadlock") s'il lui est impossible, ayant au départ tous ses modules inactifs, d'atteindre l'état où tous ses modules sont en attente, tous ses connexions d'entrée sont activées, toutes celles de sortie inhibées. C'est un problème de hasard dans le séquencement qui doit apparaître sur le graphe de contrôle $G_K$.

Un schéma est _sans course_ si pour toute paire de modules qui peuvent devenir simultanément applicables, tout flux en D contrôlé par les deux modules peut être altéré par l'un d'entre eux au plus.

La validité et l'absence de courses se vérifient localement puisqu'elles introduisent des restrictions seulement entre paires de modules directement connectés. Ce sont des propriétés statiques, c'est-à-dire vérifiables à la conception avant [2], toute exécution (compilatives). Mais l'absence d'étreinte est une propriété globale et dynamique (interprétative) d'un schéma de traitement, puisque l'introduction d'un processus parallèle supplémentaire dans un schéma perturbe cette propriété pour les modules préexistants.

### II.4.2. Exemples de connexion et d'étreintes fatales.

#### THEOREME DE CONNEXION. 3.

Tout schéma de traitement complexe peut être transformé par interconnexion en un seul processeur, c'est-à-dire sans retour interne implicite $\omega$ et donc peut être décrit par un seul graphe de contrôle $G_K$.

Nous allons effectuer la démonstration sur un exemple [11] dû à DIJKSTRA [5] et qui est le paradigme des liens L entre programmes.

Ce théorème est l'inverse de celui des appels imbriqués [26] qui permet de définir une réalisation de la primitive REQUEST séquentielle.
Exemple : Processus parallèles PRODUCTEUR et CONSOMMATEUR.

Deux processus parallèles PROD et CONS opèrent concurement sur un
tampon.

<figure><img src="image_17.png" /><figcaption>Figure 12. Processus à lier dans le schéma.</figcaption></figure>

PROD introduit des données dans un tampon non borné tandis que CONS
extrait ces données pour les traiter. Il y a deux ressources :

-N, le nombre de portions de données déjà produites ($O_N N < \infty$),

-B, la variable logique de droit d'accès au tampon (B=0 ou 1).

A l'initialisation N = 0 et B=1.
<figure><img src="image_18.png" /></figure>

Réseau de Transfert.

<figure><img src="image_19.png" /><figcaption>Figure 13. Liage des processus en un schéma de traitement complexe (avec retours implicites).</figcaption></figure>
<figure><img src="image_20.png" /><figcaption>Figure 14. Liage des graphes de contrôle avec retour interne implicite (<---).</figcaption></figure>

$\begin{array}{l} \{ B = \text{REQUEST} (B) \text{ par PROD } \{ B' = \text{id. par CONS } \{ N, N' = \text{id. pour } (N). \\ \bar{B}' = \text{RELEASE} (B) \text{ par PROD } \bar{B} = \text{id. par CONS } \bar{N}', \bar{N} = \text{id. pour } (N). \end{array}$
<figure><img src="image_21.png" /><figcaption>Figure 15. Liage en un graphe de contrôle sans retour implicite</figcaption></figure>

(<---).

Cette opération de liage correspond à la création des "modules étendus à transfert de registres" de [8].
<figure><img src="image_22.png" /><figcaption>Figure 16. Alternative : mise en parallèle des deux REQUEST de CONS.
(polymate à transition d'états complexes).</figcaption></figure>

Pour une implémentation cablée, cette mise en parallèle permet une accélération de la logique ; elle est exploitable grâce à l'implémentation $R(K)$ du Corollaire de la coassignation en [26].

Comme dernière illustration des applications du principe de dualité pour la synchronisation de processus asynchrones, nous présentons le cas d'une étreinte fatale ("Deadlock") dans un système d'exploitation exprimé par trajectoires de flux et de processus respectivement.
Exemple. L'étreinte fatale sur flux.

Le traitement des transactions sur des bases de données peut donner lieu à des étreintes qui par dualité peuvent être ramenées au cas précédent.

Soit un processus $p^A$ dont la phase $p_1^A$ réserve (LOCK) l'argument $m_1^A$ (RECORD) ce qui amène la phase $p_2^A$ à réserver $m_2^A$, puis $p_3^A$ à réserver $m_3^A$, ainsi qu'un processus $p^B$ dont la phase $p_1^B$ réserve $m_1^B$, ce qui amène la phase $p_2^B$ à demander (REQUEST) $m_2^A$; alors $m_3^A$ amène la phase $p_4^A$ à requérir $m_1^B$. Seul l'achèvement de $p^A$ (phase $p_\infty^A$) ou de $p^B$ (phase $p_\infty^B$) pourrait desserrer l'étreinte.

<figure><img src="image_23.png" /><figcaption>Figure 17. Dualisation du réseau de transfert R en graphe de contrôle G pour une étreinte fatale.</figcaption></figure>
### III. ASPECTS SEMIOTIQUES DES INTERFACES SUR LIAISONS.

Nous concentrons maintenant l'étude sur les interfaces TRANSVERSES connectant les divers modules composant un schéma de traitement à un certain niveau, par exemple l'interface entre unités centrales Pc et canaux Pio, l'interface entre canal Pio et contrôleur de périphérique Pt [17], le lien d'un terminal d'accès à processus [15] dans une système d'exploitation [16], les procédures de transmission dans un réseau de calculateurs [20, 18].

#### III.1. Fonctions de processus et de flux.

Les liens L sont présentés ici comme des **processeurs d'interface** se distinguant des processeurs de traitement P par des propriétés sémiotiques remarquables. Ces propriétés permettront dans le paragraphe suivant la décomposition en cascade [1, 9] des contrôleurs de liens $K_L$, améliorant notablement la "conception structurée" d'un système et facilitant ainsi la minimisation, la détection des erreurs, le test et l'implémentation automatiques.

Puisque le rôle d'un lien [1, 2] est d'effectuer une assignation de valeur translationnelle, le but des fonctions d'interface est d'associer des enregistrements de données à des noms d'entités ou des contenus de registres à des emplacements de cellules de mémoire (par exemple : entrée-sortie directe d'un C, accès à une chaîne d'octet en Mp,...). Ces assignations élémentaires peuvent être combinées en transferts de blocs par quelque algorithme d'optimisation destiné à minimiser le pourcentage de gestion ("overhead") du dialogue sur L.

On appelle NOM ("NAME") tout pointeur d'un élément dans un ensemble qui peut ne pas être ordonné linéairement, à l'opposé d'une étiquette ou d'une adresse. Au niveau d'un sélecteur S, une adresse ("PORT") est destinée à la désignation du module terminal visé au travers de L. Les terminaux sont donc considérés comme ordonnés linéairement.

Les principes de dialogue et actions de base sur un interface sont :

1) START et DONE pour l'activation et l'aperçu,

2) GIVE et TAKE pour les commandes de transfert,

3) les échanges de texte dans un sens et dans l'autre,

4) la notification des incidents à l'émetteur du texte.
### III.2. Les sept degrés sémiotiques.

Les actions les plus simples sur un interface sont le chargement (GIVE) et le rangement (TAKE) d'un enregistrement de donnée élémentaire (par exemple un octet ou un mot à lire ou écrire en un seul transfert sur L). La structure syntaxique élémentaire pour une fonction d'interface est donc l'émission en une instruction à une seule adresse : DEGRE ZERO.

```
ES ::= TAKE,PORT,NAME,RECORD
```

où ES est le signal d'activation exprimant au niveau physique $L^\dagger$ la primitive START,

ou bien
```
ES ::= GIVE,PORT,NAME
```

```
DS ::= RECORD
```

où DS est le signal des données exprimant la primitive DONE pour le GIVE.

Dans ces cas, un module maître J' commande le transfert vers ou à partir d'un PORT du module J d'un enregistrement RECORD dont le pointeur est NAME en J mais dont l'emplacement est implicite dans J'. Par exemple, si J est un cylindre d'appareil de mémorisation à accès direct $M_d$ (disque), alors PORT et NAME initialisent les actions SEEK et SEARCH respectivement.

L'emplacement effectif de RECORD dans J est connu de Gin mais n'a pas à être échangé sur L. Si cependant un vrai nom logique doit être associé à un enregistrement, ce dernier est défini pour porter son nom (TITLE) en lui-même comme suit :

```
RECORD ::= (RECORD TITLE, DATA CONTENTS).
```

$P'_L$ convertit TITLE en NAME pour la transmission et $P_L$ convertit NAME en une adresse d'emplacement dans J à la réception.

Il en est de même pour le module esclave J où un mécanisme de conversion dynamique d'adresse ($NAME \rightarrow LOCATION$) pourrait procurer la transparence d'emplacement si R interprétait NAME mais ignorait RECORD TITLE tandis que Gin seul accèderait aux emplacements effectifs (LOCATION) de RECORD dans J.
<figure><img src="image_24.png" /><figcaption>Figure 18. Communication d'adresse sur l'interface de lien L.</figcaption></figure>

Un exemple d'émission de degré zéro est une instruction de processeur central Pc telle que (CODE,CELL,WORD) où CODE peut être soit LOAD, soit STORE. La syntaxe la plus élémentaire correspond à une liaison Mp - Pc synchrone demi-duplex avec commande centralisée en Kp et bipoint.

### DEGRE UN (itération).
[mécanisme syntaxique au niveau physique].

Le pourcentage de gestion ("overhead") du dialogue d'interface peut être réduit en transmettant les enregistrements non pas par entités mais par blocs dans une émission itérée selon un paramètre de comptage :

```
DOUNTIL { FUNCTION,PORT,NAME,COUNT,RECORD (i) } qui est exécuté successivement pour i = 0, ..., COUNT-1.
```

Ici NAME est le pointeur de RECORD (0) (par exemple le premier octet du premier secteur sur disque Md), et COUNT est le nombre d'entités élémentaires de données à transférer. Le point d'entrée PORT du module esclave J effectue une incrémentation automatique d'adresse commençant à LOCATION et finissant à LOCATION + COUNT - 1.

### DEGRE DEUX (paquets).
[mécanisme pragmatique au niveau physique].

L'emploi d'un signal de retour RS est essentiel pour la notification d'erreurs de transfert à l'émetteur afin de permettre la récupération des erreurs. Un paquet est défini par la concatenation d'un signal d'émission et de son signal de retour : PAC ::= ESo RS. Le champ fonction associé à ES fait place pour RS à un champ de notification, de sorte que RS supporte à la fois la synchronisation logique (primitive DONE) et la transmission des notifications de J vers J' :

```
RS ::= NOTIFICATION, DIAGNOSIS
      (éventuellement)
```
Le champ DIAGNOSIS porte les paramètres d'occurrence de l'erreur et occupe un champ de données similaire au champ d'information RECORD de ES.

En sens inverse, le paquet de DATA peut être défini comme

ACK ::= DS o QS (ACKNOWLEDGEMENT).

Le signal d'aperçu QS de J' vers J devrait être émis à toute inversion de sens des émissions comme dans le transfert de GIVE suivant :

ES o RS o DS o QS = PAC o ACK.

DEGRE TROIS (fragmentation). [mécanisme sémantique au niveau physique].

A partir du moment où NAME est acquis par le module adressé J (ainsi que PORT, FUNCTION et COUNT), il est inutile de répéter ces informations à chaque itération dans un transfert de bloc. Un paquet de tête peut donc être séparé du paquet de texte, même pour une primitive TAKE. Par exemple :

ES1 ::= TAKE,PORT,NAME dans PAC.1::= ES1 o RS1,
et
ES2 ::= RECORD dans PAC.2::= ES2 o RS2.

DEGRE QUATRE (Assemblage). [mécanisme syntaxique au niveau logique].

La structure physique d'une liaison L restreint la largeur des émissions (nombre de bits par transfert). Les composants sont les constructions syntaxiques nécessaires pour adapter les paquets de tête et de texte aux champs de fonctions $I_K$ et de données $I_D$.

Dans le cas du paradigme de lien que nous définissons, la liaison est faite de 14 lignes et le fonctionnement est demi-duplex.

Figure 19. Spécification physique du paradigme de lien L.

<figure><img src="image_25.png" /></figure>
N.B. Par souci d'homogénéité avec les publications de référence [3, 4] sur ce même thème et avec la pratique actuelle des langages informatiques, les primitives sont baptisées en langue anglaise ; les figures sont annotées de même à partir d'ici.

Dans cet exemple avec des enregistrements de 24 bits, les champs d'information IF et de données DF ne peuvent en porter qu'un tiers par paquet, de sorte qu'il est nécessaire d'effectuer un désassemblage à l'émission en fractions gauche (LF), médiane (MF) et droite (RF), soit de J' vers J :

```
INFORM COMPONENT ::= ES1(LF) o ES2(MF) o ES3(RF) o RS3, pour un texte de TAKE
où ESN (.) signifie que ES est utilisé pour échantillonner l'émission du Nième
octet, et de J vers J' :
```

```
DATA COMPONENT ::= DS1(LF,NF1) o DS2(MF,NF2) o DS3(RF,NF3) o QS0 pour un texte de GIVE.
```

Considérons un fragment de tête sans sélection de PORT (liaison bipoint) et large de deux octets pour porter les codes de fonction (GIVE,TAKE,...) :

```
HEADING COMPONENT ::= ES1(LF) o RS1(NF) o ES2(RF) o RS2(NF).
```

Un composant apparaît donc comme un fragment vidé de sa sémantique. L'assemblage introduit une macro-structure avec des porteurs d'émissions organisés hiérarchiquement en composants et paquets.

### DEGRE CINQ (séquencement). [mécanisme pragmatique au niveau logique].

Même les actions élémentaires comme GIVE et TAKE doivent être maintenant élaborées comme des séquences de fragments concatenés selon une loi. En outre le module J' dispose d'une primitive WARN pour alerter J de l'occurrence d'un incident de transfert.

La détection des erreurs de séquencement peut être améliorée au niveau des paquets en adoptant la structure suivante pour un désassemblage sur IF :

```
INFORM COMPONENT ::= ES1 (INFO,LF) o ES2 (WARN, MF) o ES3 (INFO,RF) o RS3
quoique MF soit le second octet du champ d'information et non un paramètre de
diagnostic.
```
<figure><img src="image_26.png" /><figcaption>Figure 20. Diagramme $S_h$ de la Syntaxe des séquences sur L.
(h : "high level").</figcaption></figure>
<figure><img src="image_27.png" /><figcaption>Figure 21. Diagramme S<sub>l</sub> de la syntaxe des composants sur L.

(l : "low level").</figcaption></figure>
DEGRE SIX (comptage). [mécanisme sémantique au niveau logique].

Il y a deux façons pour le module maître J' de spécifier la valeur de COUNT au module esclave J ; la façon explicite consisterait à envoyer effectivement cette valeur avant la transmission du texte. La façon implicite consiste en l'utilisation d'un code-virgule ("comma-code") marquant le composant d'ordre COUNT-1 de RECORD à l'intention du module esclave.

Le générateur G' d'une séquence GIVE ou TAKE émet d'abord une paire d'octets dans un paquet de tête portant le champ adresse et un bit d'aiguillage FLB ("flagfield"). Ce dernier sert à différencier le type d'accès à effectuer dans le module esclave J comme suit.

<table><thead><tr><th>(TAKE,FLB)</th><th>Exemples :</th></tr></thead><tbody><tr><td>0 1 : à l'endroit</td><td>accès usuel avec rangement du texte en J par adresses croissantes.</td></tr><tr><td>0 0 : à l'envers :</td><td>cas de lecture arrière sur périphérique M<sub>s</sub> (bande magnétique) d'un bloc que J' range à l'endroit dans J.</td></tr><tr><td>(GIVE,FLB)</td><td></td></tr><tr><td>1 0 : non destructif :</td><td>accès usuel dans une cellule de mémoire à semi-conducteurs.</td></tr><tr><td>1 1 : destructif</td><td>cas d'une instruction TEST-AND-SET (Système 360) ou d'une lecture dans une cellule de mémoire à tores de ferrite.</td></tr></tbody></table>

Nous traitons au paragraphe IV.3 la conception du récepteur R (jusqu'à G in) dans le cas où les fonctions d'accès-mémoire possibles sur J sont :

0 1 ) WRITE,

1 0 ) READ,

1 1 ) READ-AND-RESET.
Tandis que les séquences peuvent seulement exprimer la transmission de fichiers physiques, il peut être utile d'exécuter des *phrases* sur des fichiers logiques (impliquant des enveloppes de procédures de communication) au moyen de concatenations syntaxiquement admissibles de séquences.

Dans notre paradigme, pour garantir l'indépendance complète des phrases entre elles, il est utile que la dernière séquence de toute phrase soit une fonction WARN qui achève la notification des incidents et remette au repos tous les contrôleurs $K'_{in}, K'_{L}, K_{L}, Kin$.

<figure><img src="image_28.png" /><figcaption>Figure 22. Diagramme de la syntaxe d'une phrase.</figcaption></figure>

L'accepteur syntaxique à ce niveau des phrases ne peut être un K cablé car il lui faut en général prendre en considération la sémantique des fichiers transférés ; il est remplacé par des standards d'exploitation de haut niveau [BAL.71].

Nous pouvons résumer ce paragraphe III.2 par le LEMME 4. suivant :
Lorsque des modules d'un système de calcul sont interconnectés par une interface transverse, la syntaxe du langage de transfert est **régulière**, c'est-à-dire que les ordres de transfert peuvent être générés, acceptés et exécutés par des automates finis $G', R, C_{in}$.

En d'autres termes les ordres récursifs ou imbriqués sont exclus.

De plus, comme les itérations portent sur un compte boursé a priori pour des raisons de simplicité, ces automates sont d'ordre fini k (c'est-à-dire fonctions au plus des k dernières paires d'entrée-sortie).
IV. DEVELOPPEMENT DU PARADIGME DE DECOMPOSITION DE LIENS.

Le processus de conception "descendante" [13, 14] ne doit pas être con-
fondu avec la structuration hiérarchisée[2, 5, 27] de l'objet de cette conception
structurée. Ce processus se compose ici de sept étapes.

L'étude détaillée du paradigme L nous conduit à la définition d'une
nouvelle forme canonique de machine séquentielle, l'automate (ou polymate) paramétré,
qui permet de traiter de manière systématique les variables locales d'un P en K ou
en D.

IV. 1.Spécification algorithmique du dialogue.

Résumons la spécification de ce paradigme de liaison L de manière ascen-
dante, d'abord au niveau des composants, puis des séquences.

Les transferts sont échantillonnés par des signaux d'émission ES et de
données DS. La structure physique requiert la concaténation de paquets de synchronisa-
tion en mode F (signal o retour) : PAC ::= ES o RS et ACK ::= DS o QS pour former
des composants :

1) Le champ-adresse est <0,14> et le champ d'aiguillage FLB est <15>, en employant
la notation <i,j> pour les bits compris entre le ième et le jième [7] . La
fonction est répétée dans le champ FF de chaque paquet de tête.

2) Le champ-INFO est <0,23> : l'octet gauche <0,7> est envoyé d'abord avec INFO dans FF, puis l'octet médian <8,15> avec WARN dans FF, enfin l'octet droit <16,23> avec INFO dans FF. Ce dernier est le seul à recevoir un signal de retour RS3.

3) Le champ-DATA est <0,23> aussi, mais le signal d'aperçu QSØ est envoyé seulement pour indiquer que l'envoi du bloc en cours de transfert dans une séquence GIVE n'est pas terminé.

Les *phrases* sont faites de *séquences* construites avec des *fragments*
portés par des *composants*, qui a leur tour sont faits de fonctions primitives portées
par des *paquets*.
## IV. 1.1.Dispositifs de détection d'erreurs.

Comme la fonction du récepteur est d'identifier les transferts corrects, une fonction de réinformation basique d'un lien est de transmettre sa perception de la qualité de la transmission en retour au générateur. Il s'ensuit que les classes duals d'erreurs détectables sont :

-les erreurs de synchronisation, détectées par des restrictions sur les possibilités du séquencement (dans le temps) placées sur les procédures de dialogue légales,

-les erreurs d'information, détectées par des règles de redondance (dans l'espace) placées dans le texte transféré.

Les premières sont généralement signalées par retour ou aperçu (RS, QS), tandis que les secondes reçoivent généralement la forme d'un code spécial (parité, cyclique,...). Toutes deux doivent être prises en compte de manière appropriée tôt dans la phase de conception d'une liaison.

<table><thead><tr><th>FF</th><th></th><th>Champ fonction envoyé par le module maître J' à J.</th></tr></thead><tbody><tr><td>00</td><td>WARN</td><td>Un octet de détection et correction d'erreur en parallèle.</td></tr><tr><td>01</td><td>TAKE</td><td>R doit mémoriser un bloc de mots envoyé par G' à J.</td></tr><tr><td>10</td><td>GIVE</td><td>G doit envoyer à R' un bloc de mots pour J'.</td></tr><tr><td>11</td><td>INFO</td><td>Un octet de texte est porté par ce transfert (jamais dans un composant de tête) de J' à J.</td></tr></tbody></table>

<table><thead><tr><th>NF</th><th></th><th>Champ notification envoyé par le module esclave J à J'</th></tr></thead><tbody><tr><td>00</td><td>NO ERROR DETECTED</td><td rowspan="4">Par exemple un composant d'information (INFO) suivait directement un composant de donnée (DATA).</td></tr><tr><td>01</td><td>PARITY ERROR</td></tr><tr><td>10</td><td>SEQUENCING ERROR</td></tr><tr><td>11</td><td>ERROR OF BOTH KINDS</td></tr></tbody></table>

## IV. 1.2.Syntaxe d'interface globale et unilatérale.

La composition des diagrammes de syntaxe $S_ℓ$ et $S_h$ permet d'élaborer le diagramme de syntaxe $S_C$ de la procédure d'interface.
Comme les deux terminaux participent de manière entrelacée au dialogue de niveau-composant, deux graphes _similaires_ $S_G$ et $S'_G$ (au sens que leurs sommets peuvent être mis en bijection) de génération de syntaxe unilatérale peuvent être extraits de $S_\ell$.

<figure><img src="image_29.png" /><figcaption>Figure 23. Graphe global de procédure $S_C$ des composants d'interface. (élaboré comme le chronogramme pour les phases d'échantillonnage ("strobes") sur le cable de la liaison).</figcaption></figure>
<figure><img src="image_30.png" /><figcaption>Figure 25. Graphe S<sub>G</sub> de génération de la syntaxe d'interface du module J' au niveau composant.</figcaption></figure>

<figure><img src="image_31.png" /></figure>
IV. 2.Spezification des transferts de registres et interconnexions.

Les registres de transfert doivent permettre les flux de translation de données (pour L) aussi bien que de transformation de données (pour P), ainsi que le passage des paramètres requis par la chaîne Rin' - G' - R - Gin. De plus la définition descendante de la procédure de dialogue sur la liaison L invite à structurer $K_G$, et $K_R$ au moyen d'appels de sous-programmes ouverts, c'est-à-dire communa une cascade de sous-modules $K_i$ [1, 26].

<figure><img src="image_32.png" /><figcaption>Figure 26. Décomposition en cascade du Récepteur.</figcaption></figure>

a. Représentation linéarisée.

b. Représentation hiérarchisée.
Chaque fois que la structure du flux en D révèle une possibilité de décomposition hiérarchisée, des sous-modules $K_i$ peuvent être conçus indépendamment, de manière analogue à des processus parallèles dans un système d'exploitation (à la réentrance près). Mais, comme pour la programmation *pure*, une séparation stricte doit être maintenue entre les échanges duaux de synchronisation et de communication. Cette séparation est encore plus cruciale pour la machinerie où le parallélisme de bas niveau est inhérent à la conception ("hardware"). L'activité est ici passée séquentiellement au sein d'un sous-module $K_i$, tandis que le chemin des données $D_L$ permet de passer l'information avec une largeur fixe. Il y a cependant moyen d'utiliser le contrôle $K_L$ pour garder des paramètres : l'effet du remplacement du contrôle DOUNTIL d'une instruction itérée par une séquence répétitive linéaire de cette instruction est un artifice de programmation bien connu qui relève de ce compromis dans la dualité temps-espace mentionnée [1, 2]. Ceci rend la distinction structurale entre K et D quelque peu floue. Nous présentons une solution à cette difficulté au §.V, sous forme d'un "polymate paramétré".

#### IV. 3. Elaboration des diagrammes de commande (programmation par processus parallèles).

Les bits d'état QF, QI <0,1>, QD <0,1> sont introduits pour paramétrer les itérations de RLF, RLI et RLD respectivement. Par souci de brévité, seul le cas de RhF sera traité entièrement. Nous présentons cependant les activations respectives des six sous-modules $K_i$ pour garantir que leur décomposition modulaire est cohérente.

Noter que les règles ACTIVATE du §.II.4.1 correspondent ici à une séquence de symboles (contrôle, assignations):

<figure><img src="image_33.png" /><figcaption>Figure 27. Interprétation d'un graphe de commande [2] en organigramme.</figcaption></figure>
<figure><img src="image_34.png" /><figcaption>Figure 28. La partie D de P<sub>L</sub> dans le terminal esclave J. Noter que les symboles --- 0 correspondent aux sommets des règles OPERATE de [2].</figcaption></figure>

L
<figure><img src="image_35.png" /><figcaption>Figure 29. Récepteurs de bas niveau.</figcaption></figure>
Dans RℓF, cet exemple illustre que si le dernier IFTHENELSE marqué par un astérique (*) était conditionné par ((FH) = LFR) AND (QF = 0), les deux itérations RS1 et RS2 pourraient être fusionnées en une seule paramétrée par (QF).

<figure><img src="image_36.png" /></figure>
c.Cas de R&D.

<figure><img src="image_37.png" /></figure>
<figure><img src="image_38.png" /><figcaption>Figure 30. Récepteurs de haut-niveau.</figcaption></figure>
b. Cas de RhI.

<figure><img src="image_39.png" /></figure>
<figure><img src="image_40.png" /></figure>
IV. 4.L'implémentation des chemins de flux. (méthodes d'accès).

Nous voulons insister sur le fait que l'essentiel du processus de la conception structurée descendante est achevé maintenant que toute optimisation valable a été pratiquée au niveau de transfert de registre sur le diagramme de commande.
L'implémentation des chemins de transfert est un processus immédiat car il y a peu de différence entre la sémantique (description des flux) et la pragmatique (cablages), à l'opposé de l'implémentation des chemins de transition où demeure une bonne part d'optimisation intuitive.

Par souci de brévité nous poursuivons les détails d'implémentation seulement pour le cas des bits du registre d'assemblage ASR <16,23> ; les registres de transfert doivent naturellement être faits de bascules de type DATA (§. IV.3) itérative-ment.

<figure><img src="image_41.png" /><figcaption>Figure 31. Exemple de chemin de transfert.</figcaption></figure>
Soit $e_1$ le signal ACTIVATE (§.III.8.1) de $RhI$ pour : $ASR<16,23>\rightarrow LER$,
$e_2$ de $RhD$ pour : $LER\leftarrow ASR<16,23>\rightarrow$ et $e_3$ de $R\ell I$ pour : $MER\leftarrow ASR$.

En pratique, il reste à accomplir la tâche de distribution des divers éléments booléens et des bascules parmi les boitiers technologiques disponibles, puis d'adaptation électrique de ces boitiers avec des résistances (et capacités), enfin de leur implantation sur des cartes imprimées.

#### IV. 5. Minimisation du graphe d'états.

Il est fructueux de rappeler ici que la conception du cablé se distingue de celle de l'enregistré [5, 12] sous trois aspects essentiels :

1. L'échelle du temps est continue et sa discrétisation doit être contrôlée au plus bas niveau (du bit).

2. L'implantation n'est pas effectuée sur un tableau homogène linéaire M de cellules de mémoire, mais sur un ensemble hétérogène, structuré hiérarchiquement, de cartes et de boitiers (dans des armoires et des paniers).

3. Le langage-machine est celui des primitives logiques combinatoires et des bascules au lieu d'un code d'instruction, de sorte que l'optimisation de code ("software") en longueur ou en temps d'exécution est remplacée par la minimisation des éléments ("hardware") en nombre ou en nombre de types.

Le choix essentiel à ce point est entre les schémas de réalisation de forme transition-sortie (§. IV.3) ou état-sortie. Nous présentons ici le paradigme avec des bascules synchrones basculant sur front (MEALY) qui fournissent un résultat plus compact et plus rapide. Il s'agit alors de remplacer le diagramme de commande $RhF$ par le graphe d'état de la machine séquentielle $\Sigma hF$.

Nous avons montré [voir 9] comment le *paradoxe de GUINSBURG* sur la minimisation de telles machines séquentielles "très incomplètement spécifiées" peut être résolu par une décomposition. Cet algorithme n'est pas nécessaire dans le cas présent où la minimisation s'opère aisément de manière intuitive. Dans les cas plus complexes des algorithmes sont disponibles [10].
Figure 32. Exemple de graphe d'états (ΣhF).

Comparer à la figure 21 des diagrammes de la syntaxe des composants sur L.

<figure><img src="image_42.png" /></figure>

INPUT SPACE
START
QF = 1
QF = 0
FH = 00,11 (⊕ => 0)
FH = 01, 10(⊕ => 1)

<table><thead><tr><th>τ</th><th>DONE<br>START</th><th>QF=1</th><th>QF=0</th><th>FH=11<sup>00</sup></th><th>FH=10</th></tr></thead><tbody><tr><td>OhF</td><td>!</td><td>PAC.1</td><td>*</td><td>*</td><td>*</td></tr><tr><td>PAC.1</td><td>*</td><td>*</td><td>PAC.2</td><td>*</td><td>*</td></tr><tr><td>PAC.2</td><td>*</td><td>*</td><td>*</td><td>OhF</td><td>PAUSE</td></tr><tr><td>PAUSE</td><td>OhF</td><td>*</td><td>*</td><td>*</td><td>*</td></tr></tbody></table>
IV. 6.Assignation du codage des états sur un polymate paramétré.

Il faut maintenant assigner des bascules pour représenter les micro-
algorithmes comme ΣhF. A la suite de notre analyse des structures des interfaces de
lien, nous introduisons pour cela une nouvelle forme canonique de machine séquentielle :
<u>le polymate paramétré</u>. Il consiste en une machine (éventuellement synchrone) où des
bascules DATA servent à coder les microinstructions (<u>phases</u>) tandis que des bascules
TRIGGER servent à coder les microitérations (<u>étapes</u>). Il permet l'implémentation
de tout sous-module de commande Kᵢ avec une séparation claire des paramètres des
chemins de transition (processus) et des variables des chemins de transfert (flux).
Chaque sous-module Kᵢ apparaît alors comme la plus petite entité capable d'activité
autonome <u>en parallèle</u> avec le reste de la machinerie (cf.§IV. 2).

<figure><img src="image_43.png" /><figcaption>Figure 33. Polymate paramétré en forme canonique.</figcaption></figure>

Si l'on compare cette forme de modularisation "à sémantique" aux décomposi-
tions algébriques [25] en machines à permutations et à forçages, on voit que la
séparation des types d'entrée sur un polymate remplace un coûteux accroissement du
nombre d'éléments de mémoire Mp et Ms (cf. [1, 26] et II.3).
Si des bascules JK (polymates du §. IV.3) remplacent à la fois les bascules TRIGGER et les bascules DATA, une séparation pareille entre phases et étapes tend à être obscurcie dans la pratique, mais en ceci réside une source d'erreurs conceptuelles (cf.corollaire de l'assignation primitive en [1]).

Le K de tout processeur P peut maintenant être interprété fonctionnellement comme un système d'exploitation gérant les ressources de son D. Quand il y a parallélisme entre des sous-modules $K_i$, des sections critiques comme au §. II.4.1, doivent être protégées par des verrous (LOCK).

Dans $\Sigma hF$, quatre bascules DATA sont utilisées pour un codage primitif des Etats : DØ pour $OhF$, D1 pour PAC.1, D2 pour PAC.2 et D3 pour PAUSE. Aucune bascule TRIGGER n'est employée. Une porte OU-EXCLUSIF à partir de ces bascules fournit un dispositif de détection d'erreur simple grâce au codage primitif.

Nous supposerons maintenant que les phases sont codées primitivement (ce qui accroît le nombre de bascules, mais réduit à la fois le temps de cycle et la complexité des fonctions combinatoires) mais que les étapes sont codées dans un compteur (paramètre d'itération) avec une assignation compacte (code pondéré en $2^i$).
# V. APPLICATION ET ANALYSE DE LA CONCEPTION DESCENDANTE.

Cette étude logique du paradigme de lien L est destinée à procurer plus généralement une certaine vision de la conception structurée des systèmes informatiques. Elle nous mène donc naturellement à repenser les outils mathématiques existants de formalisation des algorithmes matériels comme logiciels.

## V.1. La microdiagrammation : implémentation des chemins de transition en forme canonique et comparaison avec la coassignation.

L'approche suivie jusqu'ici amène à combiner les avantages du cablage, ceux de la microprogrammation et ceux de la diagrammation [8] grâce au composant technologique IFTHENELSE comprenant une paire de portes ET complémentaires conditionnées par les paramètres internes (Ms) et par les conditions externes (V) en forme normale disjonctive. Ce composant est présenté sur la figure 34.

Le degré d'intégration en portes logiques sur un tel boitier correspond à celui des gammes TTL et ECL actuelles courantes. Nous sommes conscient que la mode actuelle concentre les études sur la microprogrammation. Mais dans un processeur P rapide la plupart des microinstructions ne peuvent contrôler directement le flux en D ; il leur faut activer des sous-modules rapides $K_i$ dont la réalisation doit être non-microprogrammée pour démultiplier le temps de cycle de la mémoire de commande du microprocesseur principal K. C'est bien à cela qu'est due l'émergence des PLA ("Programmable Logic Arrays") et leur tendance à remplacer les microprogrammes ; c'est bien cela aussi qui motive la recherche de modules universels programmables nouveaux [1].

De toutes manières, les fonctions primitives identifiées au niveau des composants technologiques actuels peuvent se retrouver plongées dans une fresque plus vaste d'une technologie plus intégrée : la recherche de telles primitives n'est donc pas vraiment limitée à des applications à court terme.
<figure><img src="image_44.png" /><figcaption>Figure 34. Composant technologique IFTHENELSE.</figcaption></figure>

Un branchement inconditionnel (THEN) est fait d'une simple porte ET. Chaque sommet ACTIVATE d'un diagramme de commande K est alors implémenté par une bascule DATA du registre de phase $Q_p$. Les modules IFTHENELSE peuvent ainsi remplacer (comme indiqué au §.IV. 3) les modules ACTIVATE de l'assignation duale lorsque l'on cherche à réduire le nombre de basculs qu'elle requiert [1, 26]. Mais la logique obtenue y perd cependant en régularité, comme le montrent les figures 27 et 33 de sorte que l'avènement du LSI devrait donner toute sa rentabilité pratique à la forme canonique duale.
<caption>Figure 35. Polymate microdiagrammé paramétré.</caption>

Il reste une possibilité de minimisation, au moment de l'implantation des boitiers sur une carte de circuit imprimé, par le biais de la fusion des implicants communs — semblable à l'optimisation de code réalisée dans la phase pragmatique d'un traducteur.

<figure><img src="image_45.png" /></figure>

Ma est la **matrice d'action** avec des interconnexions de type-diode fournissant la sortance requise par les divers codes de sortie primaire de chaque phase.

Md est la **matrice de dynamique** fournissant les interconnexions secondaires pour transition d'état : elle est très "creuse" grâce à l'assignation primitive des états.
<figure><img src="image_46.png" /><figcaption>Figure 36. Paradigme pour chemin de transition.</figcaption></figure>

**Exemple.** La mesure de complexité d'une telle conception étant le nombre de boitiers ECL, l'emploi de boitiers IFTHENELSE fait passer cette mesure de 6 à 4 pour ce module SiF qui est assez représentatif.
Il faut d'abord effectuer une conversion en forme état-sortie complètement spécifiée (cf. Figure 32 ) avec sept états et cinq entrées.

<figure><img src="image_47.png" /><figcaption>Figure 37. Forme état-sortie de l'exemple ΣhF.</figcaption></figure>

$$
v_3 = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \quad ; \quad v_4 = \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}
$$

Un choix judicieux de spécification complète de la fonction de transition permet de minimiser l'implémentation.

$$
v_0 = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \quad ; \quad v_5 = \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} \quad ; \quad v_6 = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}
$$
<table><thead><tr><th>Assignation D<sub>S</sub></th><th>w<sub>0</sub></th><th>w<sub>1</sub></th><th>w<sub>2</sub></th><th>w<sub>3</sub></th><th>w<sub>4</sub></th><th>w<sub>5</sub></th><th>w<sub>6</sub></th><th>w<sub>7</sub></th><th>w<sub>8</sub></th><th>Sorties</th></tr></thead><tbody><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>PAC.1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>f<sub>1</sub></td></tr><tr><td>PAC.2</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>f<sub>2</sub></td></tr><tr><td>WARN</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>f<sub>3</sub></td></tr><tr><td>TAKE</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td><td>f<sub>4</sub></td></tr><tr><td>INFO</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>f<sub>5</sub></td></tr><tr><td>GIVE</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>f<sub>6</sub></td></tr></tbody></table>

Table de coassignation.

<table><thead><tr><th>λ</th><th>v<sub>0</sub></th><th>v<sub>3</sub></th><th>v<sub>4</sub></th><th>v<sub>5</sub></th><th>v<sub>6</sub></th></tr></thead><tbody><tr><td>M<sub>0</sub></td><td>M<sub>8</sub></td><td>M<sub>7</sub></td><td>M<sub>7</sub></td><td>M<sub>7</sub></td><td>M<sub>7</sub></td></tr><tr><td>M<sub>1</sub></td><td>M<sub>2</sub></td><td>M<sub>1</sub></td><td>M<sub>1</sub></td><td>M<sub>1</sub></td><td>M<sub>1</sub></td></tr><tr><td>M<sub>2</sub></td><td>M<sub>1</sub></td><td>M<sub>7</sub></td><td>M<sub>7</sub></td><td>M<sub>7</sub></td><td>M<sub>7</sub></td></tr><tr><td>M<sub>3</sub></td><td>M<sub>3</sub></td><td>M<sub>2</sub></td><td>M<sub>8</sub></td><td>M<sub>8</sub></td><td>M<sub>8</sub></td></tr><tr><td>M<sub>4</sub></td><td>M<sub>4</sub></td><td>M<sub>8</sub></td><td>M<sub>2</sub></td><td>M<sub>8</sub></td><td>M<sub>8</sub></td></tr><tr><td>M<sub>5</sub></td><td>M<sub>5</sub></td><td>M<sub>8</sub></td><td>M<sub>8</sub></td><td>M<sub>2</sub></td><td>M<sub>8</sub></td></tr><tr><td>M<sub>6</sub></td><td>M<sub>6</sub></td><td>M<sub>8</sub></td><td>M<sub>8</sub></td><td>M<sub>8</sub></td><td>M<sub>2</sub></td></tr><tr><td>M<sub>7</sub></td><td>M<sub>7</sub></td><td>M<sub>2</sub></td><td>M<sub>2</sub></td><td>M<sub>2</sub></td><td>M<sub>2</sub></td></tr></tbody></table>

Table de liaison.
Ici la fonction de rythme effectue la sélection du mode ($\mu$) de fonctionnement, soit en parallèle, soit en décalage, des bascules $M_i$ formant un registre d'état à couplage sériel tel que:

$$M_0 \leftrightarrow u_s, M_i \leftrightarrow M_{i-1}, \forall i \in \{1,...,8\}, y_s \leftrightarrow M_8$$

<figure><img src="image_48.png" /><figcaption>Figure 38. ΣhF en forme de polymate coassigné.</figcaption></figure>
Il est remarquable qu'une matrice d'action $M_a$ est très "creuse" et que les bascules $M_0, M_5$ et $M_6$ ne servent qu'en sortie primaire et ne sont pas réinjectées en entrée secondaire (Registres de Condition exclusive en [2]). Ici, le polymate est rendu complètement contrôlable (mais non instantanément) par la connexion sérielle de toutes les bascules à une seule liaison d'entrée U permettant de coder les états sériellement.

d. Forme canonique à coassignation transition-sortie $\Sigma h F_T$.

Il faut d'abord compléter la spécification de la fonction de transition $\tau$ en fusionnant les états PAC et PAUSE en un seul état :

$$ (f_1|v_0) = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad (f_2|v_0) = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix}, \quad (f_3|v_3) = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix}, $$

$$ (f_4|v_4) = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix}, \quad (f_5|v_5) = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix}, \quad (f_6|v_6) = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix} $$

<table><caption>Table de coassignation.</caption><thead><tr><th>D<sub>T</sub></th><th>e<sub>0</sub></th><th>e<sub>1</sub></th><th>e<sub>2</sub></th><th>e<sub>3</sub></th></tr></thead><tbody><tr><th>z<sub>0</sub></th><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><th>z<sub>1</sub></th><td>1</td><td>0</td><td>1</td><td>0</td></tr></tbody></table>

<table><caption>Table de liaison.</caption><thead><tr><th>λ</th><th>(f<sub>1</sub>|v<sub>0</sub>)</th><th>(f<sub>2</sub>|v<sub>0</sub>)</th><th>(v<sub>0</sub>)</th><th>(f<sub>3</sub>|v<sub>3</sub>)</th><th>(f<sub>4</sub>|v<sub>4</sub>)</th><th>(f<sub>5</sub>|v<sub>5</sub>)</th><th>(f<sub>6</sub>|v<sub>6</sub>)</th></tr></thead><tbody><tr><th>e<sub>1</sub></th><td>e<sub>3</sub></td><td>e<sub>3</sub></td><td>e<sub>3</sub></td><td>e<sub>2</sub></td><td>e<sub>2</sub></td><td>e<sub>2</sub></td><td>e<sub>2</sub></td></tr><tr><th>e<sub>2</sub></th><td>e<sub>1</sub></td><td>e<sub>2</sub></td><td>e<sub>0</sub></td><td>e<sub>1</sub></td><td>e<sub>1</sub></td><td>e<sub>1</sub></td><td>e<sub>1</sub></td></tr></tbody></table>
La forme de coassignation (S ouT) doit être la même que celle de l'automate à implémenter et du graphe qui le représente.

<figure><img src="image_49.png" /><figcaption>Figure 39. Forme transition-sortie de ΣhF et coassignation.</figcaption></figure>

<figure><img src="image_50.png" /></figure>

Alors que le polymate microdiagrammé paramétré correspond à un degré d'intégration pré-LSI comme les "modules de transfert de registres éten-dus" [8], le polymate coassigné est bien adapté à une intégration à grande échelle (LSI) avec tableaux à logique programmable (PLA) pour une grande variété de modules $K_i$ à condition que les paramètres q,d et p soient suffisamment grands.

Contrairement aux théories algébriques [25, 9], cette approche sé-mantique de la modularisation ne conduit pas à une recherche de décomposition sans tourbillons ("loop-free").

## V.2. Notation en chevrons pour le processus de conception descendante.

Nous avons présenté la conception (structurée) comme un processus de traduction pouvant générer une parmi six formes d'objet : programmation ("vertical Software") ou microprogrammation ("Horizontal Software"), diagram-mation ("Chartware"), cablage ("Hardware"), microdiagrammation ou coassignation.
La modularité dans chacune de ces formes de réalisation implique la spécification d'interfaces de liaison précises.
<figure><img src="image_51.png" /><figcaption>Figure 40. Les chevrons des sept étapes de la conception [2].</figcaption></figure>

Le rôle des L dans cet effort vers la conception structurée méritait une attention spéciale parce que leurs opérations sur les données sont translationnelles (§.I.1) et donc plus simples que celles des P, transformationnelles. L'analyse des L facilite ainsi la mise en évidence des principes du traitement des données (synchronisation, dualité et hiérarchie), mais le schéma ci-dessus (figure 40) demeure valable quand la procédure de communication est remplacée par un algorithme de calcul.

Ainsi, de même que la programmation structurée [5, 13] se traduit opérationnellement par des "normes de programmation" et des mécanismes de vérification de la fonctionnalité, de même la conception structurée se traduit par des "standards de réalisation" et des facilités de test.
[1] M. DEPEYROT. "Les automates programmables par coassignation". Rapport de Recherche LABORIA n° 86. (Novembre 1974).

[2] M. DEPEYROT. "Duality and Hierarchy in Data Processors". Rapport de Recherche LABORIA n° 90. (Novembre 1974).

[3] M. DEPEYROT. "Link Dynamics and Interface Decomposition in PMS". (Notes on Structured Design). Proceedings of the "Advanced EEC Course in Computing System Architecture". Alpe d'Huez. (A paraître chez HERMANN). (December 1972).

[4] M. DEPEYROT. "Design of Interfaces as stochastic Channels with memory". GRENOBLE International Workshop on Computer Architecture. (June 1973).

[5] E.W. DIJKSTRA. "Notes on structured programming". EWD.249 and Report 70. Wsk 03. Technical University. EINDHOVEN. (April 1970).

[6] D.L. PARNAS. "A technique for software module specification with examples". Cód. ACM. Vol. 15, nr. 5, pp. 330-336. (May 1972).

[7] C.G. BELL, A. NEWELL. "Computer structures : Readings and examples". Mc Graw Hill. (1971).

[8] C.G. BELL, J. GRASON, A. NEWELL. "Designing computers and digital Systems". Digital Press. (1972).

[9] M. DEPEYROT. "Un algorithme rapide de décomposition". Symposium International "Systèmes Logiques – Conception et Application". BRUXELLES. (Septembre 1969).

[10] G. MICHEL. "Minimisation des machines séquentielles incomplètement spécifiées". Rapport de Recherche LABORIA n° 70. (Mai 1974).
[11] J.P. ROSSIENSKY, V.T. TIXIER. "LP-70 : A System Programming Language with parallel processes". Symposium Européen de l'ACM. BONN. (Mai 1970).

[12] H.D. MILLS. "Mathematical foundations for structured programming". IBM Corp. FSC 72 - 6012. (1972).

[13] N. WIRTH. "Program Development by stepwise refinement". Com. ACM, Vol. 14, nr. 4, pp. 221-227. (April 1971).

[14] F.W. ZURCHER, B. RANDELL. "Iterative multi-level modelling - A methodology for computer system design". IFIP Congress Proceedings. Hardware I; "Analysis of Computer Systems". EDINBURGH. (August 1968).

[15] R.M. BALZER. "PORTS-A method for dynamic interprogram communication and job control". AFIPS.SJCC, pp. 485-489. (1971).

[16] A.G. FRASER. "On the meaning of names in programming systems". Com. ACM, Vol. 14, nr. 6, pp. 409-416. (June 1971).

[17] A.G. FRASER. "On the interface between computers and Data Communications Systems". Com. ACM, Vol. 15, nr. 7, pp. 566-573. (July 1972).

[18] D.T. BROWN, R.L. ELBSEN, C.A. THORN. "Channel and Direct Access Device Architecture". IBM System Journal, Vol. 11, nr. 3, pp. 186-199. (1972).

[19] D. BJORNER. "Finite state Automaton-Definition of Data communication line control procedure". AFIPS.FJCC, pp. 477-491. (1970).

[20] B.W. STUTZMAN. "Data Communication Control Procedures". Computing Surveys, Vol. 4, nr. 4, pp. 197-220. (December 1972).

[21] S.H. FULLER, R.C. CHEN. "The I/O Port Architecture for computer modules". Carnegie-Mellon University. Dept. of Computer Science Report. (March 1973).
[22] R.M. KARP, R.E. MILLER. "Parallel Program Schemata". Journal of Comp. and System Sc., Vol. 3, pp. 147-195. (1969).

[23] G. RADIN. " A note on the concept of Binding". IBM Research Report, RC 3287, (nr.15045). (March 17, 1971).

[24] C.E. SHANNON, W. WEAVER. "The Mathematical Theory of Communication". The University of Illinois Press. URBANA. Illinois. (1949).

[25] J. HARTMANIS, R.E. STEARNS. "Algebraic Structure Theory of sequential machines". Prentice Hall. (1966).

[26] M. DEPEYROT. "Une généralisation de la notion d'automate et applications". Thèse de l'Université de Grenoble (Juin 1975).

[27] K.A. DUKE, H.D. SCHNURMANN, T.I. WILSON. "System Validation by Three-level modeling Synthesis". IBM J. of R. and D. Vol. 15, nr.3, pp. 166-174. (March 1971).

[28] R.C-H. CHEN. "Bus Communications Systems". Ph D Dissertation. Carnegie-Mellon University. (January 1974).
<figure><img src="image_52.png" /></figure>
RIA
laboria

<figure><img src="image_53.png" /></figure>

laboratoire de recherche
en informatique
et automatique

Notes sur
la conception structurée
des interfaces

(Deuxième partie)

Michel
M. Depeyrot

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n°132
Septembre 1975
<figure><img src="image_54.png" /></figure>
NOTES SUR LA CONCEPTION STRUCTURÉE DES INTERFACES

(Deuxième partie)

M. Depeyrot

Sommaire

Les interfaces des systèmes de traitement de l'information sont analysées et un modèle est présenté pour les interfaces dites "verticales", qui assurent la liaison entre deux modules d'un système au même niveau sémantique. Le modèle est apparenté au canal stochastique à mémoire de Shannon, cette mémoire étant celle de l'automate de la procédure de dialogue commandant l'interface.
Un schéma d'optimisation de la vitesse de transfert d'une structure en infoduc ("pipeline") est présenté. Le modèle englobe la communication entre processus dans le logiciel aussi bien que la coopération de microprocesseurs dans le matériel ou que les entrées-sorties de machines. La détection des erreurs, leur notification et leur récupération sont considérées dans le cadre du canal stochastique et avec des transferts en infoduc, l'objectif étant d'optimiser le rapport performance/coût.

Le paradigme de la première partie [1] est traité complètement pour en extraire les aspects essentiels de la conception structurée des interfaces.
Enfin une application concrète de cette étude théorique pour la résistance d'une conception vis à vis des pannes est illustrée sur l'exemple d'un microprocesseur à douze bits récemment apparu sur le marché.

Mots clés : Liaison, interface, canal, stochastique, infoduc, conception structurée, traitement des erreurs, test et diagnostic, microprocesseur, dualité.
Computer System Interfaces are analyzed and a model is presented for
the so-called "vertical interfaces" that link two system modules at the same
semantic level. The model is related to Shannon's stochastic channel with me-
mory, this memory being that of the dialogue procedure automaton controlling
the interface. A pipelined transfer rate optimization scheme is presented. The
model encompasses process communication in software as well as microprocessor
cooperation in hardware or machine input-output. Error-detection, notification
and recovery are considered in the stochastic channel framework and with pipe-
lined transfers, aiming at cost-effectiveness.

The paradigm from the first part [1] is thoroughly treated to exhibit
all crucial features of interface design. Finally one concrete application of
this theoretical study for failure-resilient design is illustrated on the exam-
ple of a recently marketed twelve-bit microprocessor.

Key-words and phrases : link, interface, channel, stochastic, pipeline,
structured design, error-handling, test and diagnostic,
microprocessor, duality.
I. Modèle de canal stochastique et récupération sur erreurs.

I.1. Générateur unilatéral et automate récepteur.

I.2. Automate d'interface global.

I.3. Canaux stochastiques à mémoire.

I.4. Prédiction et filtrage.

I.5. Synthèse pour la fiabilité des interfaces.

I.6. Conclusion sur la conception structurée des liens.

II. Application à la résistance aux pannes dans un microprocesseur.

II.1. Description sommaire du microprocesseur TLCS-12.

II.2. Description du dialogue sur le bus d'entrée-sortie.

II.3. Automates unilatéraux et global du bus.

II.4. Comportement en cas d'erreurs.

III. Transparence et cohérence en conception structurée.

III.1. L'ingénierie des systèmes face aux Mathématiques Appliquées.

III.2. Aspects logistiques de la décomposition modulaire.

III.3. Aspects fonctionnels de la transparence entre modules.

III.4. Interfaces et stationarité.

III.5. Interfaces et cohérence.

Références Bibliographiques.
L'exemple d'interface de liaison exposé dans la première partie de ces notes peut être considéré comme un paradigme pour deux raisons fondamentales :

- il a servi au paragraphe 4[1] pour mettre en exergue les implications résultant de la structure hiérarchisée de sa procédure de dialogue (essentiellement le niveau des séquences au dessus du niveau des composants).

- il va servir ici de contre-exemple par rapport au cas dégénéré [29] (où les automates globaux et unilatéraux sont similaires au même sens que $S_G$ et $S'_G$) et va permettre d'élaborer une méthodologie pour garantir la fonctionnalité ("correctness") du dialogue.

Nous voulons ensuite comparer le modèle d'un interface bruité au modèle de SHANNON pour canaux de communication à mémoire, cette mémoire étant ici celle de l'automate de la procédure de dialogue contrôlant l'interface.

Un schéma d'optimisation de la vitesse de transfert est présenté et la détection, la notification puis la récupération sur erreur sont analysées dans ce cadre. Ainsi, l'efficacité de la conception structurée au moyen des principes et modèles de ces notes est démontrée pragmatiquement.

## I.1. Générateur unilatéral et Automate récepteur.

Le récepteur $R$ (ou "reconnaisseur") dans le terminal esclave $J$ est décomposé en $R_\ell$ avec 5 états et $R_h$ avec 3 états. ($\ell$ pour "low-level" et $h$ pour "high level"). Ces automates détectent les émissions non correctes sur la liaison en analysant d'abord la fonctionnalité des composants émis par le terminal maître, puis la fonctionnalité des séquences.

L'entrelacement [30] qui consiste en l'alternance des émissions de $R_\ell$ et $R_h$, résulte en un récepteur global $\tilde{R}$ qui est un automate à 15 états ($3 \times 5$), quoique en fait l'automate $R$ n'ait que 9 états (<15). Cette inégalité de décomposition

$$|R_\ell| \times |R_h| = |\tilde{R}| \ge |R|$$
est vraiment générale et due au fait que par nature les automates de dialogue (comme les graphes d'algorithmes) sont très incomplètement spécifiés du moment que la plupart des paires état-entrée ne peuvent se présenter en l'absence d'incidents de transmission [15].

Ces considérations étant faites indépendamment de toute assignation d'états [1, 13] pour le récepteur, elles ne conduisent généralement pas à des économies de matériel significatives [§.III.2], mais nous allons voir comment elles facilitent le traitement des erreurs du moment que toute paire inspécifiée état-entrée est atteignable en cas d'incident lorsqu'une procédure de renvoi à l'état approprié doit être développée pour chaque cas de récupération d'incident.

## I.2 Automate d'interface global.

De même que nous avons dû distinguer entre syntaxe globale et syntaxes unilatérales, il nous faut considérer l'interface de liaison comme un automate abstrait $A_L$ composé par entrelacement [1] d'automates générateurs et récepteurs $G, G', R$ et $R'$. Algébriquement, il s'agit de produit pseudo-direct [1, 19, 22]. L'étude algébrique de ce genre de composition de systèmes dynamiques est demeurée très em- bryonnaire alors qu'il est à la base de la plupart des interconnexions "en tourbillon" rencontrées dans la pratique, fondées sur un dialogue de mode F (dit avec "handshaking")

### Définition.

Deux automates sont **similaires** si leurs graphes le sont et donc si leurs états peuvent être mis en bijection.

Remarque. La détection en temps réel des erreurs de fonctionnement amène à adjoindre à chaque automate un état d'erreur où le fonctionnement est bloqué en attente d'une procédure spéciale de récupération, c'est-à-dire d'une action d'un type spécial. Le modèle de polymate est bien adapté pour cela et, en particulier, l'assignation duale les états permet de réserver le code $w_j \equiv 0, \forall i \in \{1,...,d\}$, pour l'état de repos et d'erreur [voir 1, 33] et de réserver une entrée additive pour la récupération après incident.
<figure><img src="image_55.png" /><figcaption>Figure 1. Automate $R_ℓ$ reconnaisseur des composants.</figcaption></figure>

Toutes les transitions de $R_ℓ$ n'entraînent pas une sortie pour $R_h$ (voir WAIT). WDG signifie horloge de garde ("Watchdog").

<figure><img src="image_56.png" /><figcaption>Figure 2. Automate $R_h$ reconnaisseur des séquences.</figcaption></figure>
<caption>Figure 3. Automate R récepteur non décomposé dans le terminal-esclave J.</caption>

WDG est le déclenchement de l'horloge de garde.

<figure><img src="image_57.png" /></figure>
<figure><img src="image_58.png" /><figcaption>Figure 5. Automate $G_ℓ$ générateur de composants dans le terminal-maître J'.</figcaption></figure>

<figure><img src="image_59.png" /></figure>
<figure><img src="image_60.png" /><figcaption>Figure 6. Automate $G_ℓ$ générateur de composants dans le terminal-esclave J.</figcaption></figure>

Puisque J est esclave par rapport à J', il n'y a pas d'automate générateur $G_h$ de séquences, de sorte que $G \equiv G_ℓ$.

<figure><img src="image_61.png" /><figcaption>Figure 7. Automate $R'_ℓ$ récepteur de composants dans le terminal-maître J'.</figcaption></figure>
<figure><img src="image_62.png" /><figcaption>Figure 8. Automate R'h récepteur de séquences dans le terminal-maître J'.</figcaption></figure>

En tant que module-maître, J' ne peut tester lui-même les séquences dont il est générateur, de sorte que $R' \equiv R_\ell$.
Soient $X_G$ et $X_{G'}$ les états de la commande des générateurs de dialogue $G$ et $G'$ sur la liaison duplex $L$. Soient $X_R$ et $X_{R'}$ les états du terminal opposé tels qu'ils sont identifiés au moyen des signaux de détection d'erreur et de synchronisation par chaque récepteur. Nous pouvons alors distinguer quatre espaces d'état et automates d'interface de liaison :

$X_G \times X_R$ : L'espace d'état de la commande $K$ du terminal esclave $P_L$,

$X_{G'} \times X_{R'}$ : L'espace d'état de la commande $K'$ du terminal maître $P'_L$,

$X_R \times X_{R'}$ : L'espace d'état du dialogue reçu dans $A_L$,

$X_G \times X_{G'}$ : L'espace d'état du dialogue émis dans $A'_L$,

où ce dernier automate $A'_L$ est la version déterministe de l'interface prévue à la conception. L'automate précédent $A_L$ est la version la plus réaliste mais aussi la plus précise. C'est le fait que les automates maître et esclave respectivement ne sont pas similaires qui garantit à l'interface (à son automate global) une existence en soi et une mémoire propre. Quant aux erreurs de synchronisation et de communication, elles introduisent en son sein des transitions aléatoires. C'est le but des procédures de dialogue et des mécanismes récepteurs de rendre les automates de dialogue reçu $A_L$ et de dialogue émis $A'_L$ similaires (ce qui revient à rendre $P_L$ et $P'_L$ respectivement observables par $P'_L$ et $P_L$).

## THEOREME 1.

$A'_L$ peut être défini également par l'échange des sommets et des flèches du diagramme global $S_C$ de la procédure d'interface (avec des précautions appropriées pour l'activation et l'arrêt), et par l'entrelacement des fonctions de transition de $G$ et $G'$.
<figure><img src="image_63.png" /><figcaption>Figure 9. Diagramme de l'espace d'état d'interface dans A*<sub>L</sub>. (tel que déduit de S<sub>C</sub> par l'échange des sommets et des flèches).</figcaption></figure>
## Démonstration.

Composants et séquences sont définis de telle sorte que $S_C$ peut être déduit de $S_G$ et $S'_G$ par composition entrelacée (demi-duplex) dénotée par $\mathcal{L}$ ("interlacing") : $S_G \times S'_G = S_C$. Soit $J$ le symbole pour l'échange ("interchange") des sommets et des flèches. Comme les transformations $J$ et $\mathcal{L}$ sont commutatives, le diagramme suivant est commutatif :

<figure><img src="image_64.png" /></figure>

C.Q.F.D.

Remarquons que le nombre des états d'émission est 13 dans $A_L^*$ alors qu'il est $g = 7$ pour $G_\ell$ et $g' = 7$ dans $G'_\ell$. Nous retrouvons l'inégalité de décomposition puisque $13 < g \times g' = 49$.

Comme $A_L^*$ à 13 états et que son alphabet d'entrée est $V_L = \{DS,ES,QS,RS\}$ avec $|V_L| = 4$, la procédure de dialogue définit seulement 15 paires état-entrée possibles fonctionnellement parmi les $13 \times 4 = 52$ possibles en présence d'incidents. Ce vocabulaire $V_L$ est espace d'entrée pour $R$ et $R'$ et espace de sortie pour $G$ et $G'$. Il est l'unique espace d'entrée-sortie pour $K,K'$ et $A_L^*$. Comme dans [12, 30] il est toujours possible de lui donner une représentation matricielle incomplètement spécifiée. Supposons qu'aux transitions dues aux paires état-entrée $(x_i,v_k)$ non définies par la procédure de dialogue, il soit possible d'affecter des probabilités $p_{ij}$ que l'état suivant soit $x_j$. Comme $\sum_j p_{ij} = 1$ $\forall i$, à chaque $v_k$ correspond une matrice de Markov.

## Exemple.

Soit $v(ES)$ la matrice de représentation de $ES \in V_L$. Le symbole de Kronecker $\delta_i^j$ permet de représenter le vecteur-ligne de l'état $x_i$ déterministe. Les probabilités des états 2,4,10,11 et 12 (figure 9) sont laissées inspecifiées (symbole $*$). Nous les étudions seulement pour l'état 9.
$$
v(\text{ES}) =
\begin{bmatrix}
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
* & * & * & * & * & * & * & * & * & * & * & * \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
* & * & * & * & * & * & * & * & * & * & * & * \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
* & * & * & * & * & * & * & * & * & * & * & * \\
0 & \overline{i} & 0 & 0 & 0 & i & 0 & 0 & 0 & 0 & 0 & 0 \\
* & * & * & * & * & * & * & * & * & * & * & * \\
* & * & * & * & * & * & * & * & * & * & * & * \\
* & * & * & * & * & * & * & * & * & * & * & * \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}
$$

Soit $\alpha$ la probabilité d'WRN, $\lambda$ celle d'un GIVE, $\mu$ celle d'un TAKE. Alors i est la probabilité de INFO et

$i = (1 - \bar{i}) \text{ avec } \bar{i} = \alpha + \lambda + \mu.$

L'ensemble des matrices de Markov de l'alphabet $V_L$ forme un automate stochastique représentant un canal de communication à mémoire. Il faut lui garantir un comportement déterministe par des stratégies de détection et correction d'erreurs de sorte que, au terme de séquences de récupération, $A_L$ "simule" le comportement de $A_L^*$. Ces automates étant des _accepteurs_ de séquences dans l'itéré $V_L^*$, leur application de sortie binaire (OK/KO) est la fonction caractéristique des signaux concaténés correctement.
I.3. Canaux stochastiques à mémoire.

Cette approche de la modélisation des interfaces de liaison comme des canaux de communication est duale de celle de SHANNON et WEAVER [1949], où la mémoire joue un rôle par rapport aux données comparable à celui d'un transducteur séquentiel D. La mémoire ici joue en fait un rôle par rapport à la commande comparable à celui d'une machine séquentielle K. D'où l'intérêt pratique des propriétés de dualité entre données et commandes, qui s'exprime aussi comme une dualité entre communication et synchronisation. En effet, il y a une différence profonde entre la nature du bruit dans un cas et dans l'autre : celui du modèle de SHANNON concerne les erreurs de communication, tandis que celui du présent modèle concerne les erreurs de synchronisation.

Définitions.

1) Une *source de bruit* B pour l'interface de liaison L est une paire de signaux parasites/pertes (+/-) fonctionnant en parallèle avec la paire de générateurs-récepteurs du lien de manière stochastique.

<figure><img src="image_65.png" /><figcaption>Figure 10. Schéma de la source de bruit B sur L.</figcaption></figure>

Les signaux reçus par R' sont ceux de G entrelacés avec ceux de $B'_+$
moins ceux détruits par $B'_-$.

2) Les contrôleurs $P_L$ et $P'_L$ sont dits _en-phase_ si l'état d'émission $\epsilon$ de $A_L^*$ est en bijection avec l'état de réception $\rho$ de $A_L$. Plus précisément $K$ et $K'$ sont en phase.

Un signal parasite de $B_+$ ou une perte par $B_-$ met $P_L$ et $P'_L$ _en déphasage_ :
$\epsilon \neq \rho$. Plus précisément $x_K \neq x_{K'}$.
Un contrôle de parité sur les champs de fonction et de texte de la liaison peut procurer une notification d'erreur immédiate dans le cas d'émissions parasites par $B_+$.

## LEMME 2.

Les probabilités d'état suivant $p_{ij}$ du canal de communication L peuvent être déduites des probabilités d'activité de la source de bruit B (+ et -) et des probabilités de génération du vocabulaire $V_L$, conditionnelles (en fonction du dernier élément de $V_L$ transmis sur l'interface).

### Démonstration.

Soit $\tau$ la fonction de transition pour une paire état-entrée : $\tau(x_i, v_k) = x_t$ (état suivant). Soit $p_{q|k}$ la probabilité d'occurrence simultanée d'un parasite $v_q$ superposé à $v_k$ (écho ou diaphonie par exemple). Alors :

$$p_{ij} = \sum_q p_{q|k} \mid \tau(x_i, v_k \oplus v_q) = x_j.$$

En cas de perte d'un signal d'échantillonnage de $V_L$ (par suite d'un niveau de tension insuffisant par exemple), $x_t$ est l'état d'émission dans $A_L^*$. Soit $p_{h|k}$ la probabilité que $v_h$ soit émis alors que $A_L$ est dans l'état de réception $x_i$, c'est-à-dire que B a détruit $v_k$. Alors :

$$p_{ij} = \sum_h p_{h|k} \mid \tau(x_i, v_h) = x_j.$$

C.Q.F.D.

Il est clair que le traitement des erreurs vise à obtenir $p_{ij} = 1$ pour $j = t$ en cas d'émission parasitée et $\tau(v_h, x_t) = x_j$ en cas de perte d'émission, de sorte que les terminaux soient remis en phase.

### Notes :

1) Deux cas d'étreinte fatale [voir 1] peuvent être rencontrés dans le cas d'une erreur non détectable sur le champ fonction lorsque un parasite et une perte surviennent simultanément ($B_+ \cap B_-$). Dans le cas où J essaie d'exécuter un GIVE tandis que J' exécute un TAKE, il y a essai d'emploi simultané de la liaison qui devient une section critique. Inversement, il y a **répulsion fatale** dans le cas où J attend l'exécution d'un TAKE alors que J' a commandé un GIVE.
Dans tous ces cas il est nécessaire qu'un des automates détecte l'étreinte (blocage plus long qu'une horloge de garde par exemple) et signale la présence de parasites ou de pertes.

2) Le modèle de bruits simultanés $(B_+ \cap B_-)$ permet d'ajouter aux incidents fugitifs sur L les pannes permanentes dans $P_L$ et $P'_L$ (un signal remplacant un autre).

Un usage potentiellement fructueux de ce modèle de canal stochastique pour un interface doit être considéré lorsque les séquences ont une certaine distribution de probabilité et une certaine longueur moyenne par texte de transmission ; les probabilités de chaque composant peuvent être déduites et la fonction de transition moyenne peut être représentée comme une matrice de Markov qui est la moyenne pondérée des matrices $m(v_k)$ des signaux de l'alphabet $V_L$ :

$M_L = \sum_{k=1}^{n} \pi_k m(v_k)$ où $n = |V_L|$ et le poids $\pi_k$ est la probabilité d'occurrence de $v_k$ parmi les éléments de $V_L$.

Si $\tilde{m}(v_k)$ est la matrice sous-markovienne $(\sum_j \tilde{m}_{ij} \le 1)$ obtenue par sous-traction de $m(v_k)$ des probabilités de transition $\pi_{it}$ sans erreur, la matrice $\tilde{M}_L = \sum_{k=1}^{n} \pi_k \tilde{m}(v_k)$ joue le rôle d'une "carte de chaleur" ("heat-chart") fonctionnell dont les points chauds sont les lignes à sommes $\sum_j \tilde{m}_{ij}$ les plus élevées, et les incide dangereux sont les paires état-bruit les plus fréquentes (c'est-à-dire ayant les plus hautes probabilités $\tilde{m}_{ij}$).

Le schéma le plus efficace de récupération des incidents par une stratégie $\Sigma$ est celui qui minimise le coût moyen de détection des erreurs (pondéré avec les probabilités de la carte de chaleur) et le coût moyen de resynchronisation, une fois qu'un choix a été effectué pour chaque paire état-entrée erronée d'un mécanisme $\varphi$ de requête de récupération implémenté soit dans la machinerie soit dans un programme en J ou en J'.

Le problème est apparenté à celui de [18], mais ici nous avons un degré de complexité supérieur puisque deux automates connectés en tourbillon ($P_L$ et $P'_L$) sont impliqués, de sorte que les séquences d'entrée de chacun ne sont pas quelconques.
Soient $\sigma$ et $\sigma'$ les fonctions de sortie des terminaux $P_L$ et $P'_L$.

α) Soit $\eta_0$ l'état initial inconnu de K = (G,R) dans $P_L$. Il existe une séquence préétablie de rentrée ("homing") $\tilde{v}_\alpha = v_1 \cdots v_\ell \stackrel{\Delta}{=} \Pi_{i=1}^\ell v_i$, si pour une requête $\varphi_\alpha$ émise par J' [cf. 1] et générée par G' indépendamment des émissions de G, la connaissance par R' des séquences de sortie de $P_L$ :

$$ \tilde{y} = \Pi_{j=1}^{\ell} \sigma(\tau(\eta_0, \Pi_{i=1}^{j} v_i)) $$

suffit à $P'_L$ pour connaître l'état final de K en temps fini :

$$ \eta_\ell = \tau(\eta_0, \tilde{v}_\alpha) \text{ avec } \ell < \infty. $$

β) Il existe une séquence adaptative de rentrée lorsque la requête $\varphi_\beta$ de J' est interprétée par K' en une séquence $\tilde{v}_\beta$ en tenant compte des sorties de G telles que R' les reconnaît.

γ) Il existe une séquence préétablie de synchronisation $\tilde{v}_\gamma$ si pour une requête $\varphi_\gamma$ de J' interprétée par G' indépendamment des émissions de G, quel que soit l'état initial $\eta_0$ de K, son état final est l'état final visé $\eta_\ell$, pour une séquence de sortie quelconque $\tilde{y}$ de R, et tel que:

$$ \eta_\ell = \tau(\eta_0, \tilde{v}_\gamma) \text{ avec } \ell < \infty. $$

δ) Il existe une séquence adaptative de phasage lorsque la requête $\varphi_\delta$ de J' est interprétée par K' en une séquence $\tilde{v}_\delta$ en tenant compte des sorties de G telles que R' les reconnaît, et l'état final visé $\eta_\ell$ de K est n'importe quel état non déphasé par rapport à $\eta'_\ell$ de K', c'est à dire tels que $\rho_\ell$ de $A_L$ soit en bijection avec $\varepsilon_\ell$ de $A^*_L$.

Noter que l'émission perturbée doit être avortée et reprise pour achever la récupération de l'incident après ces séquences de phasage.
## PROPOSITIONS. 3.

a) Pour un automate $K = (G,R)$ donné avec un nombre minimal $k$ d'états, il existe une séquence préétablie de rentrée $\tilde{v}_\alpha$ de longueur au plus égale à $(k-1)^2$.

b) La conception d'une stratégie $\Sigma$ de récupération sur incidents revient à compléter la spécification des automates $K$ et $K'$ de manière que pour toute occurrence d'erreur simple $\tilde{v} \in V_L$ une séquence de phasage $\tilde{v}_\delta$ soit générée automatiquement avec une longueur $|\tilde{v}_\delta| \ll l_\Sigma < \infty$.

c) Il existe une séquence préétablie de synchronisation $\tilde{v}_\delta$ pour un automate-esclave $K = (G,R)$ complètement observable et d'ordre $k$ :

$$|\tilde{v}_\delta| \ll (k-1)^{2k}/2.$$

## Démonstration.

a) Il suffit de vérifier la cohérence de nos définitions et de celles de la théorie des "Expériences d'identification d'état et de détection de fautes", puis d'appliquer le Theorème 13-1 dans [14].

b) Compléter la spécification des fonctions de transition des divers $K$ sur $L$ revient à spécifier tous les automates $K$ pour chaque paire état-entrée de sorte que, pour tout incident $\tilde{v} \in V_L$, une séquence $\tilde{v}_\delta$ de récupération soit exécutée sur une longueur $\tilde{l}$ : ainsi la transition inspécifiée de longueur $1$ : $\tau(\rho_{t-1}, \tilde{v}_t)$ est remplacée par une transition $\tilde{\tau}(\rho_{t-1}, \tilde{v}_t) = \rho_{t+\tilde{l}}$ avec $\eta_{\tilde{l}} \equiv \eta'_{\tilde{l}} \iff \rho_{t+\tilde{l}} \equiv \eta_{\tilde{l}} \text{ ET } \eta'_{\tilde{l}}$. Ainsi pour toute paire $(\eta_{t-1}, \eta'_{t-1})$ non déphasée à l'instant $t-1$, l'incident $\tilde{v}_t$ entraînant une transition vers $\eta_t \neq \eta'_t$ doit aussi entraîner l'émission par $K'$ et $K$ d'une séquence $\tilde{v}_\delta$ de longueur $\tilde{l}$ : quelle que soit la séquence des états intermédiaires entre les instants $t$ et $t + \tilde{l}$, si aucun autre incident n'est survenu, les états ne sont pas déphasés à l'instant $t + \tilde{l}$.

c) C'est à nouveau une application directe d'un théorème de la théorie de la commutation et des automates [Théorème 13-2 dans 14].

C.Q.F.D.

## Note.

Si la récursivité dans le traitement des erreurs doit être prise en compte pour le cas des incidents successifs, la proposition précédente doit être modifiée de manière complexe.
## I.4. Prédiction et filtrage.

Considérons maintenant les interfaces à tampons comme les boîtes à lettres ("mailbox") dans les terminaux de lien entre processus programmés [ 2, 3 ] ou comme les mémoires de travail sur canaux de liaison entre processeurs cablés.

L'accroissement de la "largeur de bande" d'un L requiert un certain recouvrement des transferts, soit dans le temps (vitesse), soit dans l'espace (capacité). Les paquets ont été définis comme des paires ordonnées de signaux d'échantillonnage ("handshaking pairs") :

$$ PAC (i) = ES(i) \circ RS(i), $$ 
 et $$ ACK (j) = DS(j) \circ QS(j), $$

mais ce concept peut être généralisé pour permettre à plusieurs signaux d'échantillonnage du générateur ou du récepteur d'être alternés. Il s'agit donc d'une méthode de recouvrement des transferts dans le temps. (Dans l'espace, il faudrait accroître le nombre de fils DATA-INFO du L).

Par souci de simplification nous supposons dans ce paragraphe le nombre de signaux d'échange (ES/DS) et d'acquittement (RS/QS) égaux respectivement dans une séquence (ce n'est pas le cas dans le paradigme du paragraphe précédent avec $RS1, RS2, RS3, QSØ$).

**Définitions.**

1) Soit DEPTH la profondeur de filtrage maximale de L, c'est-à-dire le nombre de générations ES ou DS qui ont été transférées et n'ont pas encore reçu de signal de synchronisation RS ou QS en retour.

Par exemple, un TAKE filtré avec DEPTH = 3 permettrait la situation suivante sur L :

ES(i-1,λ-2) o RS(i-1,λ-1) o ES(i,λ) o ES(i+1, λ+1) o ES(i+2,λ+2) o RS(i,λ+DEPTH)... où le premier indice est le numéro d'ordre logique i indiquant que RS(i,λ+3) est la réponse à ES(i,λ), tandis que le second indice est celui de l'instant de transfert λ indiquant que ES(i+1,λ+1) est le successeur temporel de ES(i,λ).

P.S. L'équivalent en mode H du mécanisme de filtrage par DEPTH (en mode F) est l'emploi d'une horloge de gerde tolérant un délai maximal entre ES(i) et RS(i).
2) Inversement soit DEGREE le degré de préiction maximal de L, c'est-à-dire le nombre de signaux de retour RS ou QS qui ont été émis en avance mais n'ont pas encore reçu de signal d'émission ES ou DS.

Par exemple, un GIVE prédit avec DEGREE = 2 permettrait la situation suivante sur L :

$$DS(j-1, \lambda-4) \circ QS(j-1, \lambda-3) \circ QS(j, \lambda-DEGREE) \circ QS(j+1, \lambda-1) \circ DS(j, \lambda)\dots$$

La règle de synchronisation la plus simple (celle du paradigme L précédent) est caractérisée par DEPTH = 1 et DEGREE = 0. Un paquet au plus peut être traité à tout instant et aucune génération n'est demandée à l'avance par le signal de retour.

Ces nouveaux mécanismes de découplage des paquets améliorent la flexibilité des flux de transferts dès que l'un des terminaux est soit surchargé, soit sous-occupé, ce qui permet d'accroître la bande passante d'une liaison multi-accès en vrai-duplex au niveau des paquets.

DEPTH et DEGREE peuvent être considérés comme des propriétés non pas de L mais des terminaux $P_L$ et $P'_L$, ce qui permet de distinguer SLAVE/MASTER -DEGREE/DEPTH au besoin.

## THEOREME DES SEMAPHORES D'ACCELERATION. 4.

Un interface de synchronisation au niveau logique [1] d'une liaison L* vrai-duplex multi-accès à tampons associe les modules dans un relation producteur-consommateur [3] de sorte que l'accélération des flux qu'il supporte peut être gérée par un sémaphore.

## Commentaire.

Il y a là un domaine nouveau d'application des sémaphores (contrôle de débit), ou peut-être un retour aux sources [cf. 4] de l'ELECTROLOGICA-8. En tout cas ce mécanisme de synchronisation fait partie du domaine (dont l'échelle de temps est discrétisée) où la distinction entre matériel et logiciel ("hard/Soft") est superflue.
<figure><img src="image_66.png" /><figcaption>Figure 11. Schémas multi-accès maître-esclave à divers niveaux de finesse.</figcaption></figure>

### Démonstration :

Soit $N^*$ un tampon de la liaison (appelé "boite à lettres" dans un terminal enregistré) et $S^*$ un commutateur-sélecteur : $S^* = (K^*, N^*)$. Soit $J'$ un module maître à un instant donné par rapport à la liaison asymétrique $L^* ;$ il doit pouvoir s'approprier le terminal du module esclave $J$ par le moyen de $S^*$ (partie de $P_L$). Cependant $S^*$ ne doit ni ralentir $J$ par des accès excessifs à $Rin = (Kin, Din)$, ni interférer avec les accès en provenance d'autres modules $J''$ au travers d'autres liaisons $L''$. Considérons alors que $S^*$ est doté d'un compteur $c$ d'occupation du tampon $N^*$ de longueur $n$ avec $0 \le c \le n$.

### a) Recouvrement dans l'espace.

Soit $J ::= Rin - S - K ;$ un tel schéma est vraiment général pour la partie d'interface avec $P_L$ $M...$ et peut être étendu comme suit :

$$ J ::= \begin{array}{l} \text{Rin} \\ \text{S} \\ \text{M} \end{array} \quad \text{avec } P = (K,D) \text{ par exemple.} $$
Si M peut être fait de plusieurs blocs-mémoire à fonctionnement parallèle
$\mathfrak{M}$ i, alors les adresses en J peuvent être entrelacées parmi les blocs pour faciliter
le parallélisme d'accès : $M:: = \mathfrak{M} 1//...// \mathfrak{M} p$.

Définitions.

1) L'ajournement d'un accès d'écriture en M pour une séquence TAKE consiste pour $P_L$ à attendre que tous les enregistrements soient assemblés en Din et prêts pour un transfert simultané dans chacun des $\mathfrak{M}$ i afin de réduire la durée d'allocation de S à $P_L$ (c'est-à-dire à S*) aux dépends de J.

2) Inversement, pour une séquence GIVE, la simultanéité des accès à chaque $\mathfrak{M}$ i pour une lecture implique une anticipation qui est possible lors de transferts de blocs grâce à l'incrémentation automatique d'adresse [voir 1 : Degré UN].

L'ajournement et l'anticipation sont limités par la largeur-mémoire $p$ du module-esclave J et par la longueur $n$ du tampon $N*$ ; le filtrage dans une GIVE permet de mettre à profit l'anticipation, et inversement l'ajournement permet de mettre à profit la prédiction dans un TAKE.

b. Recouvrement dans le temps.

Si le module-esclave J est connecté à plusieurs liaisons L', L* par le terminal $P_L$, l'entrelacement des enregistrments échangés entre J' et S* permet de réduire les conflits de multi-accès en Kin.

Du côté du module-maître J', la profondeur DEPTH pour le filtrage dans une séquence TAKE limite l'anticipation des émissions de J', lorsque l'ajournement des accès-écriture de Rin vers M obstrue $N*$, tandis que le degré $\Upsilon$ de prédiction dans une séquence TAKE amène K' à exécuter cette séquence plus rapidement pour satisfaire le débit de Kin.

Inversement, du côté du module-esclave J, la profondeur $\phi$ de filtrage dans une séquence GIVE aide Kin à s'adapter au débit de K', tandis que le degré DEGREE pour la prédiction dans une séquence GIVE limite l'ajournement des accès-lecture de Rin et M lorsque J' anticipe des réceptions.
La supervision de ces coopérations de type producteur-consommateur peut être assurée par un sémaphore s dans P'$_L$ comme suit.

**Cas de TAKE :**

Module-maître J' producteur et module-esclave J consommateur.

c est le nombre d'enregistrements tamponnés en N*, acquis de J' et acquittés par RS,
à envoyer à J en AJOURNEMENT; s est le nombre d'enregistrements tamponnés en N*, acquis
de J' et non acquittés (FILTRAGE) : $\forall s < SLAVE DEPTH$ ou bien $s = 0$ si K' et S* sont
synchronisés en phase, ou bien $|s|$ est le nombre d'enregistrements requis de K' par S*
(PREDICTION) : MASTER DEGREE $<s<0$.

Exemple : $ES(i-1,\lambda-2) \circ RS(i-1,\lambda-1) \circ RS(i,\lambda) \circ RS(i+1,\lambda+1) \circ ES(i,\lambda+DEGREE)$

**Cas de GIVE :**

Module-esclave J producteur et module-maître J' consommateur.

c est le nombre d'enregistrements tamponnés en N*, acquis de J et à transmette à J'
à la demande (ANTICIPATION); s est le nombre d'enregistrements requis de S* par
K' (PREDICTION) : $\forall s < SLAVE DEGREE$
ou bien $s = 0$ si K' et S* sont synchronisés en phase,
ou bien $|s|$ est le nombre d'enregistrements reçus de S* par J' et non acquittés
par QS(FILTRAGE) : MASTER DEPTH $<s<0$.

Exemple :

$$DS(j-1,\lambda-5) \circ QS(j-1,\lambda-4) \circ DS(j,\lambda-DEPTH) \circ DS(j+1,\lambda-2) \circ DS(j+2,\lambda-1) \circ QS(j,\lambda)\dots$$

Toutes les situations sont ainsi contrôlées avec s et il faut interpréter les
signaux d'échantillonnage comme suit :

ES : réservation d'un registre en N* pour J' => $s ::= s+1$

RS : libération d'un registre en N* pour J' => $c ::= c-1$
$s ::= s-1$

DS : libération d'un registre en N* pour J' => $c ::= c-1$
$s ::= s-1$

QS : réservation d'un registre en N* pour J' => $s ::= s+1$

C.Q.F.D.
Soit $r$ le nombre d'enregistrements déjà reçus d'une séquence.

1. GIVE => |s| -r <COUNT et COUNT-r est le nombre d'enregistrements à acquitter.

2. TAKE => c <COUNT.

3. Soit un ensemble de modules maîtres {$J', J'', \dots, J^\mu, \dots$} connectés sur $S^*$ :

$$ \Sigma_{\mu} (s_{\mu} + c_{\mu}) = n \stackrel{\Delta}{=} |N^*|. $$

4. Filtrage => $\Sigma_{\mu} (c_{\mu} + \phi_{\mu}) = n$ avec $\phi_{\mu} = \Sigma_{\mu} \phi_{\mu} \stackrel{\Delta}{=} \text{SLAVE DEPTH.}$

5. Prédiction' => $\Sigma_{\mu} (c_{\mu} + \bar{\phi}_{\mu}) = n$ avec $\bar{\phi}_{\mu} = \Sigma_{\mu} \bar{\phi}_{\mu} \stackrel{\Delta}{=} \text{MASTER DEGREE.}$

Notes :

- Dans une séquence GIVE avec prédiction, la fin de la séquence doit être marquée par un compte explicite (par opposition au composant RETURN dans la partie 1) suffisamment en avance pour ne pas entrer en contradiction avec le degré de prédiction $\bar{\phi}$, donc avec une marge d'avance égale à DEGREE.

- Un module-maître $J'$ dans un réseau peut fonctionner selon deux modes : par sélection ("selecting") du coterminal $P_L^V$ (en mode F) parmi les comodules {$J^V$} chaque fois que $J'$ veut dialoguer, ou par interrogation ("polling") des co-terminaux (en mode H) de sorte que le dialogue ne soit établi que lorsque les comodules sont disponibles. Ainsi le mode F correspond ici à l'anticipation avec filtrage et le mode H à l'ajournement avec prédiction.

I.5. Synthèse pour la fiabilité d'une interface.

L'amélioration de la fiabilité d'un système peut être obtenue seulement si elle est traitée comme un problème de calcul variationnel autour d'un comportement correct du système : elle ne peut ainsi être séparée de la conception du système.
1. Le premier ordre de ce calcul variationnel requiert l'implémentation de mécanismes de détection d'erreurs :

1.a. par exploitation de la structure de base de la réalisation (détections de parités sur le champ-fonctions et le champ-données),

1.b. par exploitation des restrictions syntaxiques sur le langage d'interface entre modules (séquences illégales comme `INFO` o `DATA`).

2. Le second ordre requiert l'implémentation de procédures de notification d'incidents (par le module esclave au module maître dans le cas d'une liaison asymétrique). Les signaux de retour (RS) et de données (DS) dans notre paradigme L peuvent être judicieusement exploités pour cela (champ NF).

3. Le troisième ordre consiste en une logique efficace de récupération sur incident :

3.a. régénération des données affectées, par code correcteur ou relance (codage rafraîchissable ou/et fichiers de reprise), etc. [10].

3.b. resynchronisation des automates par séquences adaptatives ou préétablies remettant en phase les générateurs et récepteurs de syntaxe.

Il est important d' remarquer qu'une section critique, une fois allouée par verrou quelconque (sémaphore, TEST-AND-SET,...), empêche la relance du processus qui se l'est appropriée, à moins que le verrou n'inclue une *signature*, c'est-à-dire le nom de ce processus, pour permettre la réallocation lors d'une relance en cas d'incident.

4. Le quatrième ordre revient à garantir un comportement adéquat du système en cas de perte des signaux rapportant l'occurrence d'erreurs (par exemple : emploi de parités sur le champ de notification d'erreur NF ou blocage de l'automate esclave en cas de détection d'erreur).

5. Le cinquième ordre vise la limitation de l'impact possible des erreurs dont la détection peut ne pouvoir être effectuée (erreurs doubles de parité,...). Par exemple une erreur double sur le champ fonction peut transformer un GIVE en un `TAKE` : nous avons vu une solution au §.I.3 (Note 1).
6. Le sixième ordre consiste à garantir que le traitement des erreurs détectées ne facilite pas l'occurrence d'erreurs indétectables. Qu'advient-il dans un Système répétant sept fois une instruction rafraîchissable lorsque une erreur permanente induit une erreur de parité ? -Peut être ce système finira-t-il par déclarer permanente la panne, mais éventuellement une deuxième erreur de parité fugitive cachera-t-elle l'erreur initiale permanente.

7. Le septième ordre requiert la prise en compte simultanée des problèmes de notification d'incidents et de recouvrement (prédiction et filtrage). La notification automatique des incidents du module-esclave J au module-maître J' requiert l'emploi du champ NF sur la liaison L. Le contenu de ce champ doit être renvoyé à J' lorsque $P_L$ et $P'_L$ sont en phase, avec $s = 0$, ou bien il faut que les signaux émis par J soient caractérisés par 3 paramètres :

$RS(i, \lambda, \delta)$ où i et j représentent l'indice logique, $\lambda$ l'instant

$DS(j, \lambda, \delta)$ de transfert et $\delta$ le pointeur autorelatif vers l'objet de NF.

Concrètement, il faut alors réserver un champ-pointeur pour $\delta$ à la conception de la liaison L.

**Exemple :** Dans un TAKE filtré avec incident sur $ES(i+1,\lambda+1)$ dans la séquence $ES(i,\lambda) \circ ES(i+1, \lambda+1) \circ RS(i, \lambda+2, \delta)$, il faudrait $\delta = +1$ pour signifier l'indice logique $i(RS) + \delta = i+1$ de l'émission erronée.

## Définitions.

1. La notification des incidents est non-ambiguë si l'asynchronisme des émissions de signaux d'échange (ES/DS) et d'acquittement (RS/QS) n'introduit pas de dcute quant au composant (ou paquet) en erreur.

2. La notification est conjointe si elle est signalée dans le paquet-même où l'incident a eu lieu : -pour une séquence TAKE, dans $RS(i,\lambda+\ell,0)$ si l'incident a eu lieu dans $ES(i,\lambda)$ entre J' et R,

-pour une séquence GIVE, dans $DS(j,\lambda,0)$ -même si l'incident a eu lieu entre J et S*.
3. La notification est **disjointe** si le pointeur autorelatif δ est non nul. Elle peut être **tôt** (δ > 0) ou **tard** (δ < 0) afin de réduire l'ambiguïté ou d'empêcher la notification d'erreurs sur des enregistrements RECORD(k) acquis de J par $P_L$ en anticipation d'une demande QS à venir de J' (GIVE filtré) alors que $k > COUNT$, c'est-à-dire en cas de compte implicite sur transfert par blocs.

4. La notification est **immédiate** si elle est portée par le signal émis par J immédiatement après le transfert en erreur ; sinon elle est **retardée** :

$$ \Delta(\text{TAKE}) \stackrel{\Delta}{=} \lambda(\text{NF}) - \lambda(\text{ES}) > 1 \text{ et } \Delta(\text{GIVE}) \stackrel{\Delta}{=} \lambda(\text{NF}) - \lambda(\text{DS}) > 0. $$

**Exemple :**

ES(i,λ) o ES(i+1,λ+1) o ES(i+2, λ+2) o RS(i,λ+3,1), lorsque RS porte sur ES(i+1,λ+1) et donc NF est retardé d'un temps (et tôt).

DS(j,λ,0) o DS(j+1,λ+1, -1), lorsque le second DS porte un NF complémentaire concernant le premier DS si certains mécanismes de détection d'erreur sont plus lents que l'émission des données.

## PROPOSITIONS. 6.

a. Dans une séquence GIVE, les incidents peuvent être signalés sans ambiguïté par notification immédiate conjointe, seulement si les données ne sont émises par $P_L$ qu'après achèvement de toutes les vérifications d'erreur ($δ = 0$).

b. Dans une séquence TAKE, ceci n'est vrai que pour DEPTH = 1 et DEGREE = 0.

c. Une notification peut être retardée et conjointe :

$$ \text{ES}(i,\lambda) \circ \text{RS}(i-1,\lambda+1,0) \circ \text{RS}(i,\lambda+2,0). $$

d. Une notification peut être immédiate et disjointe :

$$ \text{ES}(i,\lambda) \circ \text{ES}(i+1,\lambda+1) \circ \text{RS}(i,\lambda+2,1). $$
e. Une notification peut être disjointe tôt dans une séquence TAKE avec prédiction seulement, et si des vérifications par J' sont effectuées après acquittement comme dans ES(i-1,λ-2) o RS(i-1,λ-1,0) o RS(i,λ,-1) où les deux RS portent sur le même ES.

f. Dans une séquence GIVE, une notification disjointe tôt ne présente pas d'intérêt comme dans DS(i,λ,+1) o DS(i+1,λ,0) où le champ NF du premier DS peut toujours être rapporté par le second DS équivalemment.

## I.6. Conclusion sur la conception structurée des liens.

Cet ensemble de propositions a seulement pour but de démontrer, et la complexité du problème, et l'adéquation du formalisme. Le but de cette étude qui était de donner aux liaisons L dans PMS une dynamique est donc atteint, ainsi que la démonstration que le traitement des incidents fait partie intégrante de la conception et interfère étroitement avec les mécanismes de synchronisation entre modules.

Par ailleurs la hiérarchisation des processeurs de liaison nous a amenés à mettre au point une méthodologie de conception structurée descendante, qui est valable pour tous processeurs P. Ces notes devraient ainsi ouvrir de nouveaux champs d'application à des théories (automates, canaux de communication, polymates) souvent accusées d'avoir un lien trop lâche avec les problèmes concrets de l'Informatique. De plus l'emploi systématique des primitives du langage PMS [24] favorise des rapprochements intuitifs qui devraient permettre peu à peu de regrouper des techniques trop éparses et de faire émerger une véritable discipline scientifique de la Conception des Systèmes.
## II. APPLICATION A LA RESISTANCE AUX PANNES DANS UN MICROPROCESSEUR.

Nous abordons ici l'application de cette étude théorique au cas concret d'un microprocesseur récemment apparu sur le marché.

### II.1. Description sommaire du microprocesseur TLCS-12.

Le microprocesseur TLCS-12 est la première unité centrale P manipulant des mots de douze bits en parallèle et entièrement contenue dans un boitier de circuit à haut degré d'intégration. Elle a été présentée dans l'article en référence [31].

Ce boitier TOSHIBA en LSI/MOS ("Large-Scale Integrated/Metal-Oxyde Semiconductor") est organisé autour d'un bus unique asynchrone capable de transférer douze bits d'information à la fois. Dans le cas du dialogue avec un périphérique, ces bits sont répartis en quatre pour les informations de contrôle $I_K$ (commandes et états) et huit pour les données $I_D$, en demi-duplex. C'est $I_K$ qui détermine si $I_D$ est une donnée d'adressage ou une donnée d'échange.

Suite à la première partie de ces notes, il est raisonnable de considérer comme un principe que toute liaison physique L dispose de deux niveaux de définition : le niveau précédent (logiciel) et le niveau inférieur de synchronisation (matériel) où le bus est vu comme un lien de douze bits de large. Ces douze bits sont tous traités comme des données $I_d$ tandis que d'autres signaux $I_K$ sont requis pour gérer la synchronisation des modules connectés par L.

<figure><img src="image_67.png" /><figcaption>Figure 12. Le principe de synchronisation.</figcaption></figure>

Dans le cas de dialogue entre $P_C$ et les autres contrôleurs ($K_M$ et $K_T$), adresses et données sont envoyées alternativement, les premières servant à sélectionner le destinataire qui s'approprie un instant la liaison L.
<figure><img src="image_68.png" /><figcaption>Figure 13. Synoptique d'un système bâti autour du bus du PLC-12.</figcaption></figure>
Le boitier du microprocesseur contient une unité de gestion $P_L$ du bus L qui le lie aux autres boitiers du système en générant et recevant les signaux de synchronisation $I_K$ ("Timing") qui coordonnent les phases l'horloges indépendantes des différents boitiers. Le boitier du microprocesseur a pour interface physique 42 connexions incluant les alimentations en +5 Volts et -5 Volts et la masse (0). Le temps d'accès du programme en mémoire vive $M_v$ est de 300 nanosecondes.

Les données sont transférées entre le microprocesseur central $P_C$ et les mémoires vive $M_v$ ou morte $M_m$ sous contrôle de l'unité $K_m$ qui répond aux signaux de synchronisation $I_K$ sur le bus émis par $P_C$. C'est $K_m$ qui génère ensuite adresses et ordres spéciaux pour $M_v$ et $M_m$. Une unité similaire $K_T$ effectue un travail similaire pour les périphériques. Ces deux unités de commande $K_m$ et $K_T$ diffèrent essentiellement par leurs domaines d'adresage et leurs échelles de synchronisation car les périphériques employés avec un microprocesseur sont très lents.

## II.2. Description du dialogue sur le bus d'entrée-sortie.

Le bus asynchrone L, tant à l'intérieur qu'à l'extérieur du microprocesseur $P_C$ est complètement sous le contrôle de celui-ci. Une requête d'échange sur le bus émise par une microinstruction dans $P_C$ éclenche son unité de gestion $P_L$ interne à $P_C$. D'abord $P_L$ arrête l'horloge interne de $P_C$ et gère le bus L avec les trois signaux de synchronisation $I_K$ : deux signaux de sortie $C_1$ et $C_2$ et un signal d'entrée ACK.
<figure><img src="image_69.png" /><figcaption>Figure 14. Cadence interne de $P_c$. (chronogramme).</figcaption></figure>

Le microprocesseur dispose d'une génération d'horloge à quatre phases par période. Pendant $t_1$, les résultats de la période précédente sont placés dans des registres internes. Les branchements conditionnels sont résolus pendant $t_2$, à la suite de quoi la microinstruction appropriée est extraite de la mémoire de commande interne à $P_c$. La microinstruction est exécutée pendant $t_4$, mais si la microinstruction requiert l'emploi du bus L externe à $P_c$, l'horloge est bloquée dans cette phase.

Les deux signaux de sortie $C_1$ et $C_2$ montent simultanément, indiquant qu'une adresse de boitier ou périphérique externe est postée sur le bus L. La réception de cette adresse par le destinataire est signalée par le signal d'aperçu ACK en retour ('Acknowledgement') à $P_L$. Le microprocesseur peut alors ne plus maintenir l'adresse sur le bus.

Si $C_2$ revient à zéro tandis que $C_1$ est maintenu, le destinataire est censé mettre sur le bus une donnée que le microprocesseur $P_c$ doit lire. Quand le destinataire répond à cette requête, il remet à zéro le signal ACK.
Enfin quand le microprocesseur a lu la donnée, l'unité de gestion du bus $P_L$ remet $C_1$ à zéro permettant au destinataire de se déconnecter du bus.

Si au contraire, le microprocesseur maintient $C_2$ comme $C_1$ à un et remplace l'adresse postée sur le bus L par une donnée, quand $C_1$ revient à zéro tandis que $C_2$ est maintenu le destinataire adressé précédemment est appelé à enregistrer la donnée écrite sur le bus par le microprocesseur. Le destinataire renvoit alors le signal d'aperçu ACK après réception, permettant à l'unité de gestion du bus $P_L$ de s'en déconnecter en ramenant $C_2$ à zéro et de générer une impulsion de relance pour l'horloge interne du microprocesseur $P_C$ qui reprend alors son fonctionnement interne.

<figure><img src="image_70.png" /><figcaption>Figure 15. Chronogramme des échanges sur le bus.</figcaption></figure>

La durée d'un cycle d'échange sur L peut varier de 200 ns en écriture à 5 µs en lecture : d'où l'importance de l'asynchronisme.

## II.3. Automates unilatéraux et global du bus.

Le chronogramme précédent ne permet pas un raisonnement clair sur la fonctionnalité du bus parce que la logique de l'interface mélange les signaux d'information alors que ceux-ci sont présentés individuellement.

En réalité, c'est l'entrelacement des émissions de deux automates qu'il s'agit de représenter : d'une part $P_L$, l'unité de gestion du bus dans
le microprocesseur, d'autre part K', l'unité de commande du destinataire (ici $K_M$ ou $K_T$).

Les automates unilatéraux sont les unités qui gèrent la synchro-nisation de L de part et d'autre.

<figure><img src="image_71.png" /><figcaption>Figure 16. Automates unilatéraux $P_L$ et $K'$.</figcaption></figure>

L'automate global de la liaison est $A_L$ qui représente l'état de la paire ($P_L$, $K'$). Ses variables d'état sont codées sur l'ensemble des signaux de commande :

<table><thead><tr><th>Z</th><th>C<sub>1</sub></th><th>C<sub>2</sub></th><th>ACK</th><th>Etat</th><th>Commentaire</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>Repos</td><td>Etat stable de P<sub>L</sub> et K'.</td></tr><tr><td>1</td><td>0</td><td>0</td><td>1</td><td>Interdit</td><td>Inutilisé mais atteignable par erreur.</td></tr><tr><td>2</td><td>0</td><td>1</td><td>0</td><td>Write</td><td>Transfert vers K'.</td></tr><tr><td>3</td><td>0</td><td>1</td><td>1</td><td>Take</td><td>Requête d'écriture par P<sub>L</sub>.</td></tr><tr><td>4</td><td>1</td><td>0</td><td>0</td><td>Read</td><td>Transfert vers P<sub>c</sub>.</td></tr><tr><td>5</td><td>1</td><td>0</td><td>1</td><td>Give</td><td>Requête de lecture par P<sub>L</sub>.</td></tr><tr><td>6</td><td>1</td><td>1</td><td>0</td><td>Start</td><td>Adresse postée par P<sub>L</sub>.</td></tr><tr><td>7</td><td>1</td><td>1</td><td>1</td><td>Aperçu</td><td>Adresse reçue par K'.</td></tr></tbody></table>

La combinaison 001 représente un état non spécifié.
<figure><img src="image_72.png" /><figcaption>Figure 17. Automate global $A_L$ du TLCS-12.</figcaption></figure>

Il est remarquable que cet être $A_L$ abstrait mais très naturel est caractéristique de l'interface du bus L et qu'il est révélateur de ses propriétés intimes : - sa fonctionnalité dans l'entrelacement des émissions des interlocuteurs $P_L$ et $K'$,

- ses risques de panne par la présence d'états interdits.
La liaison L apparaît ainsi comme un canal de communication à mémoire, mais cette mémoire concerne le séquencement du contrôle sur $I_K$ et non le délai de transfert des données $I_D$ comme c'est le cas dans la référence [23].

En ce sens, ce modèle $A_L$ que nous venons d'exhiber fait d'une liaison L un canal de communication à mémoire au sens dual de celui de Shannon.

## II.4. Comportement en cas d'erreurs.

Il est un cas d'erreur particulièrement délicat, celui où $A_L$ est envoyé par une émission parasite (bruit ou perte en ligne) dans l'état INTERDIT où $(C_1, C_2, ACK) = (0,0,1)$.

Un dispositif de détection d'erreur en temps réel pourrait être l'adjonction d'un bit de parité pour $C_1, C_2$ d'une part, pour ACK d'autre part, ce qui coûterait deux fils de plus sur trois soit 40 % du total sur $I_K$.

Un dispositif de détection d'erreur en temps différé devrait être dans $P_L$, une simple fonction combinatoire $(\bar{C}_1, \bar{C}_2, ACK)$. Dans ce cas, un dispositif de correction d'erreur devrait permettre le retour de K' à l'état ACK sans transferts de données perturbant encore plus l'état des données, suivi d'une reprise du programme d'échange antérieur (si possible) qui a été sans doute exécuté de façon erronée.

D'après la figure 16, le plus simple est que $P_L$ effectue une transition de lecture :

$$ \bar{C}_1 \bar{C}_2 \rightarrow C_1 C_2 \rightarrow C_1 \bar{C}_2 \rightarrow \bar{C}_1 \bar{C}_2 $$

sans prendre en compte l'information envoyée par K' pour une adresse quelconque. Mais K' ne sera alors resynchronisé que si son graphe de fonctionnement correspond à la figure 18 un peu plus complètement spécifiée que la figure 16.

**Figure 18.** Complément à l'automate K' pour récupération sur erreur.

<figure><img src="image_73.png" /></figure>
L'expérience montre que sur tout interface standard d'entrée-sortie actuel de tels problèmes sont omis lors de la conception chez les constructeurs et rencontrés ultérieurement sur les sites-clients à grands frais.

Pis encore, les dialogues incomplètement spécifiés de ce genre sont fréquemment la cause d'incompatibilités et de répulsions fatales entre unités d'un même système par suite d'interprétations différentes et contradictoires par des équipes distinctes chez un même constructeur ou chez les fabricants de périphériques compatibles.
### III. TRANSPARENCE ET COHERENCE EN CONCEPTION STRUCTUREE.

#### III.1. L'Ingénierie des Systèmes face aux Mathématiques Appliquées.

L'essence de ces notes est qu'une Théorie des Interfaces est l'outil nécessaire pour une méthodologie de conception des systèmes informatiques en un temps où les contraintes de compatibilité, extensibilité et fiabilité sont devenues les objectifs majeurs. Cette recherche montre comment quelques principes et des modèles appropriés peuvent fournir des résultats substantiels pour guider le concepteur au travers d'un réseau complexe de décisions techniques.

Il est bon à ce point d'insister sur la nature pragmatique des travaux présentés.

<figure><img src="image_74.png" /><figcaption>Figure 19. La démarche de l'Ingénierie des Systèmes.</figcaption></figure>

C'est seulement parce que nous avons élaboré un modèle – ou plutôt une gamme de modèles – adéquat pour un problème concret, puis développé un formalisme, une méthodologie et des résultats sur modèle, et que nous avons finalement appliqué cette méthodologie et ces résultats sur le problème initial, que nous pouvons dire que ce travail relève de l'Ingénierie des Systèmes. Il est alors tentant d'opposer cette démarche à celle des Mathématiques Appliquées qui est la recherche de domaines d'application pour des résultats abstraits ou des modèles connus initialement.
Il est bon de noter cependant que cette opposition ne doit pas devenir un
cloisonnement d'éccles de pensée pour deux raisons : d'abord la démarche des Mathéma-
tiques Appliquées est occasionnellement fertile en soi, comme dans l'expérience
en [19, 20, 21 et 22] ; ensuite, cette démarche est une partie intégrante de
l'Ingénierie des Systèmes : en effet, lorsque la phase (1) de "modelage du système
informatique" nous conduit à spécifier une interface en termes d'entrelacement d'auto-
mates unilatéraux, la phase (2) d'"analyse abstraite" consiste à ramener ce modèle
à une extension de la théorie mathématique existante des automates stochastiques et
incomplètement spécifiés.

### III.2. Aspects logistiques de la décomposition modulaire.

L'intérêt de la décomposition modulaire d'un système n'est pas seulement
de permettre la parallélisation et donc l'accélération du traitement, ni de permettre
la simplification de la conception et des tests, il est aussi et peut-être surtout
de permettre une planification fine rigoureuse. C'est un principe élémentaire d la
Théorie de la Décision en présence d'incertitude que de ramener les évaluations au
niveau de sous-tâches aussi élémentaires que possible pour deux raisons :

- l'évaluation de la charge et de la durée prévisionnelle de réalisation est plus facile pour une tâche petite,

- la composition des évaluations élémentaires entraîne une compensation entre erreurs d'évaluation et accroît la véracité de l'estimation globale.

Autant les recherches dans le logiciel que dans le matériel ont pendant
la dernière décennie placé une emphase excessive sur les aspects syntaxiques du
traitement et de la traduction de l'information par opposition à leurs aspects
sémantiques. Quant aux problèmes pragmatiques, détachés des précédents, ils ne pouvaient
avoir grand sens. C'est pourquoi les techniques algébriques de décomposition [13,
22, 30] n'ont jamais convaincu les praticiens qui exigent prudemment une démonstration
au préalable que l'apprentissage d'une nouvelle technique est un investissement
profitable. En l'occurrence les bases de notre technique (les théories des Automates)
ne font généralement pas partie du bagage des concepteurs d'interfaces, quoique elles
tendent à être considérées comme des outils fondamentaux pour l'Architecture des
Systèmes [11, 26, 29].
Surtout nous avons montré qu'une approche sémantique (c'est-à-dire inspirée par la structure du flux en D) de la décomposition de K en polymates paramétrés programmables est concevable ; il est alors intéressant de reconsidérer l'un des aspects les plus attirants qui était promis par les techniques algébriques de décomposition et qui demeure applicable :

soit $K$ doté de $k$ états et décomposable en $K_1$ et $K_2$ tels que $k <_{k_1, k_2}$ ; le nombre $d$-états de la réalisation décomposée est alors $K = k_1 + k_2$.

Si la réalisation est faite avec une assignation des états aussi compacte que possible (ce qui n'est faisable qu'en implémentation cablée), alors $K$ et $K'$ requièrent pratiquement le même nombre de bascules et les avantages de la décomposition sont de rendre la réalisation plus simple (moins de boucles de réinformation), plus adaptable et diagnosticable (par association du niveau de détection d'erreur $R_ℓ$ ou $R_h$ à un module de génération spécifique $G'_ℓ$ ou $G'_h$ par exemple sur notre paradigme L).

Mais si l'assignation des états (sur implémentation cablée, microprogrammée,...) est primitive dans chaque sous-module $K_i$ (une bascule DATA par phase), alors le nombre de bascules est réduit considérablement par la décomposition grâce à la relation suivante :

$$k_1 + k_2 < k_1 \cdot k_2 \quad \forall k_1, k_2 > 1 \text{ et } k \ge 5.$$

Tout ceci est encore plus vrai dans le cas de la coassignation.

### III.3. Aspects fonctionnels de la transparence entre modules.

La diagrammation peut être distinguée de la méthode avec polymates paramétrés par le fait que celle-ci ne mélange pas les registres de paramètres et les registres D, résolvant ainsi le problème du compromis associé à la dualité.

Grâce à cette séparation nette entre les composants $K$ et $D$ d'un processeur, il est concevable de définir un programme de test pour la partie $D$ indépendamment du mode d'implémentation de la partie $K$ et donc portable ; il suffit de le compléter par un microprogramme de test non portable de la partie $K$ dédié à ce que son implémentation a de spécifique [32].
Ces considérations révèlent qu'un progrès essentiel vers l'automatisation de la conception des calculateurs sera atteint lorsqu'un compilateur génèrera du code-objet optimisé ayant le format d'un microprogramme horizontal (par opposition à la programmation séquentielle), c'est-à-dire ayant la structure d'un polymate microdiagrammé (sans compteur ordinal), ou encore ayant le format de coassignation.

Nous savons par l'équivalence de Nérode [cf. 16, 17] que la spécification de relations entrée-sortie pour des séquences suffisamment longues sur une machine à nombre fini d'états fournit une représentation équivalente des fonctions internes de transition et de sortie. Ceci permet de définir rigoureusement la notion de portabilité d'un module ou de *transparence* d'une de ses interfaces de liaison : des modules compatibles horizontalement ont des automates terminaux $P_L$ équivalents au sens des relations d'entrée-sortie définies par la syntaxe de dialogue sur la liaison L ; des modules compatibles verticalement fournissent la même sémantique et la même pragmatique (traitement des erreurs en particulier) sur la liaison L.

Nous avons mis l'accent sur le concept de lien L de PMS tout en donnant à ce langage le rôle d'une axiomatique pour l'architecture des systèmes. Cela nous vaut de pouvoir maintenant "situer" nos résultats : il intéressant de souligner par exemple que la hiérarchisation de base logique/physique nous a permis d'exhiber une méthodologie de décomposition systématique des terminaux $P_L$ de liaisons cablées entre modules asynchrones. Cette décomposition, toujours applicable en pareil cas est duale de celle [24] des sous-processus d'opérations en D.

Nous avons tenu aussi à traiter comme un tout les processeurs cablés et programmés (la machinerie et les procédures), ce qui permet de comparer les primitives START et DONE en [1] entre sous-modules aux fonctions POP et TOP permettant [voir 6] la décomposition en tourbillon de sous-programmes. Tandis que les sous-programmes présentent la difficulté supplémentaire d'être réentrants, les sous-processeurs présentent celle de fonctionner en vraie simultanéité.

Il est juste d'ajouter ici que, à l'opposé des systèmes logiciels modernes exploitant les principes de vérification syntaxique, la plupart des machines sont cablées indépendamment de toute vérification de syntaxe régulière dans les unités K.
L'expérience montre que les interfaces de liaison (matériel) semblent plus fiables que les liens (logiciel) uniquement parce que les erreurs syntaxiques non comprises et cablées sont prises en compte à grands frais par des mécanismes de déroutement cablés et/ou programmés.

En outre la décomposition sémantique a un impact notoire sur la pragmatique du traitement des erreurs ; par suite d'une conception mal modularisée la vérification dynamique des erreurs de génération de séquences de commandes entre les modules d'un système d'exploitation est effectuée trop souvent, non pas au niveau du module en faute (sur l'interface), mais ailleurs, aux dépends bien sûr de la transparence mais avant tout de l'efficacité. Un superviseur d'entrée-sortie ne devrait pas avoir à vérifier la fonctionnalité ("Correctness") d'un programme...canal, puisque un tel programme est simplement un texte pour le canal et que ses erreurs révèlent essentiellement d'un mauvais séquencement des appels de macroinstructions d'entrée-sortie (c'est-à-dire au niveau du système de gestion de fichiers), ou encore que ses erreurs relèvent d'une cadence inadéquate des transferts au niveau du contrôleur cablé K du canal [25, 27].

### III.4. Interfaces et Stationarité.

Nous avons vu que la transparence est la propriété d'un module par rapport à un flux qui le traverse en provenance ou en direction d'un module de référence. La dose appropriée de transparence [cf. 7] dans la spécification des modules en question est le critère de rigueur à appliquer à l'introduction d'un interface : c'est un critère qualitatif pour l'instant et encore vague.

Les variables et paramètres gérés comme des données d'interface par un module P (vu comme un transmetteur) peuvent être analysées en quatre ensembles : celles qui sont reçues en entrée exclusivement, celles qui sont émises en sortie (ou éventuellement reçues puis émises après altération dans un flux traversant P), celles qui sont purement transmises mais non utilisées par P, et celles qui ne demeurent pas stationnaires (variables de travail ou codage d'états) qui ne devraient pas faire partie d'une interface. Ce dernier ensemble correspond à une pratique fréquente, malheureusement contradictoire avec une modularité vraie (au sens de la transparence) : il arrive que des zones d'interface servent dans un système d'exploitation de zone-mémoire pour variables intermédiaires, ou encore, dans un canal d'entrée-sortie, que le processeur central connaisse le détail de l'état du contrôleur d'un périphérique en temps réel, ou même que le fonctionnement interne d'un contrôleur fasse apparaître des impulsions parasites sur ses liaisons de sortie, ou enfin que le texte
d'un programme-canal soit partiellement fourni au superviseur d'entrée-sortie par le système de gestion de fichiers (cas de bandes magnétiques) et complété par son exécution même. Le résultat de telles pratiques est que une altération de l'un des modules coopérant au travers de cet interface, quoique le maintenant fonctionnellement compatible, introduise des situations d'asynchronisme hasardeuses. Voici l'une des raisons principales du dépérissement lent mais irréversible des grands systèmes subissant des modifications de détail au cours de leur mise au point et pour leurs extensions.

<figure><img src="image_75.png" /><figcaption>Figure 20. Partition des données d'interface au travers de P.</figcaption></figure>
### III.5. Interfaces et cohérence.

Le premier aspect de la cohérence peut être exprimé par les principes suivants :

P1. "L'information transmise ne devrait pas être soumise à un changement de représentation par le transmetteur".

P2. "L'information transmise devrait plutôt être transmise avec redondance au travers d'une seule interface (éventuellement dupliquée) plutôt que partiellement pontée autour du transmetteur, même si celui-ci ne s'en sert que partiellement".

Ce second principe facilite la simplicité des schémas d'interconnexion et peut suggérer une conception hiérarchisée [4, 9]. Le premier principe implique qu'une certaine représentation optimale pour les transferts doit être utilisée dès que possible uniformément plutôt que de subir des recodages qui introduisent ralentissement, complexité et sources d'erreurs. Par exemple, les flux entre $P'_L$ et $P'_L$ et entre $P'_L$ et $M$ dans J devraient être similaires (en d'autres termes, la liaison-canal d'entrée sortie et la liaison canal-mémoire d'un calculateur devraient avoir des procédures de dialogue et une syntaxe semblables, à la largeur de bande près).

Le deuxième aspect de la cohérence tient à l'existence de trois espèces d'interfaces : les interfaces **fonctionnelles** correspondent à un découpage comme $K_1 \times K_2$ dans K sans connexion par un lien implicite ou explicite (c'est-à-dire que K combine les fonctions de $K_1$ et $K_2$ sans décomposition modulaire) ; les interfaces **logiques** correspondent à une réalisation modulaire effective comme $K_1 \times K_2$ dans $K$ ou $J' - L - J$ dans le paradigme ; les interfaces **technologiques** apparaissent à la limite de deux technologies (dans un mélange de microcode et code-machine dans un programme, ou un mélange de boitiers TTL-ECL dans un circuit cablé). Ce deuxième aspect de la cohérence peut être exprimé par les principes suivants :

P3. "Les interfaces fonctionnelles et technologiques devraient coïncider avec des interfaces logiques autant que possible".

P4. "Les niveaux de fiabilité et les débits d'un flux à chaque interface devraient être homogénéisés pour l'ensemble d'un système".
De ces quatre principes de cohérence dans un système informatique aucun n'est appliqué avec constance dans une architecture opérationnelle, quoique le dernier devienne une des premières exigences des utilisateurs.

Qui plus est, l'évolution technologique [28] accentue le besoin d'une approche plus rationnelle de la modularisation : la structure d'interfaces des microprocesseurs est précisément ce qui les distingue des minicalculateurs actuels. Avec la venue de l'intégration à grande échelle (LSI) dans les grands systèmes, il faudra appliquer de plus en plus des techniques d'optimisation de la structure et des liaisons comme celles que nous avons présentées dans ces notes : dès qu'un boitier peut contenir un microprocesseur, l'interface technologique entre les boitiers doit être étendu au niveau logique ou les problèmes de synchronisation et des procédures de dialogue élaborées doivent être prises en compte. De même la programmation structurée [5, 8] est ce qui distingue les techniques du logiciel moderne, mais elle demeurera propos vague jusqu'à ce que des critères quantitatifs soient admis qui permettent de qualifier les interfaces correctement conçues.

Pour citer F.P.BROOKS,Jr.:

"Computer Architecture, like other architecture, is the ART of determining the needs of a user of a structure and then designing to meet those needs as effectively as possible within economic and technological constraints.

Architecture must include engineering considerations, so that the design will be economical and feasible ; but the emphasis in Architecture is upon the needs of the user, whereas in Engineering the emphasis is upon the needs of the fabricator".
[1] M. DEPEYROT. "Notes sur la conception structurée". [Première Partie]. Rapport de Recherche LABORIA (numéro précédent).

[2] R.M. BALZER. "PORTS-A method for dynamic interprogram communication and job control". AFIPS.SJCC, pp. 485-489. (1971).

[3] E.W. DIJKSTRA. "Copperating sequential processes". Report EWD 123. Technical University, EINDHOVEN. (September 1965).

[4] E.W. DIJKSTRA. "The structure of the T.H.E. multiprogramming system". Com. ACM, Vol. 11, nr. 5, pp. 341-346. (May 1968).

[5] O.J. DAHL, E.W. DIJKSTRA, C.A. HOARE. "Structured Programming". APIC Studies in Data Processing. nr. 8. Academic Press. (1972).

[6] H.D. MILLS. "Mathematical foundations for structured programming". IBM Corporation. FSC 72-6012. (1972).

[7] D.L. PARNAS. "A technique for software module specification with examples". Com. ACM, Vol. 15, nr. 5, pp. 330-336. (May 1972).

[8] N. WIRTH. "Program Development by stepwise refinement". Com. ACM, Vol. 14, nr. 4, pp. 221-227. (April 1971).

[9] F. BANCILHON et al. "Principes de Conception du Système SPECTRE". Revue Bleue de l'AFCET. R.A.I.R.O. 7ème Année, B-3, pp. 31-62. (Octobre 1973).

[10] A.N. HIGGINS. "Error recovery through programming". AFIPS. FJCC. pp. 39-43. (1968).

[11] H.B. BARNES. "A programmer's view of Automata". Computing Surveys, Vol. 4, nr. 1, pp. 221-240. (December 1972).
[12] F. BANCILHON, M. DEPEYROT. "Réalisation d'un modèle stochastique pour un automate non fiable à partir d'expériences d'entrée-sortie". Revue Bleue de l'AFCET. R.A.I.R.O. Sème Année, B-2, pp. 127-153. (Juin 1974).

[13] J. HARTMANIS, R.E. STEARNS. "Algebraic Structure Theory of Sequential machines". Prentice Hall, (1966).

[14] Z. KOHAVI. "Switching and finite Automata Theory". Mc Graw Hill. (1970).

[15] G. MICHEL. "Minimisation des machines séquentielles incomplètement spécifiées". Rapport de Recherche LABORIA. n° 70 (Mai 1974).

[16] A. NERODE. "Linear automaton Transformations". Proceedings of the American Mathematical Society, Vol IX, pp. 541-544. (August 1958).

[17] G.N. RENEY. "Sequential Functions". Journal ACM, Vol. 5, pp. 177-180. (1958).

[18] S. WINOGRAD. "Input-error limiting Automata". Journal ACM, Vol. 11, nr. 3, pp. 338-351. (July 1964).

[19] M. DEPEYROT. "Fondements Algébriques de la Transformation de Fourier Rapide". Cahier n° 3 de l'I.R.I.A. pp. 25-169. (Novembre 1970).

[20] M. DEPEYROT. "Linear system identification using real-time deconvolution". IEEE-C-19, nr. 12. pp. 1139-1145. (December 1970).

[21] M. DEPEYROT, J. MONDELLI. "Organisation hiérarchique de la Transformation de Fourier Rapide". Automatique. 16e Année, Tome XVI, n° 4, pp. 232-241. (Avril 1971).

[22] M. DEPEYROT, J.P. MARMORAT, J. MONDELLI. "An Automaton-Theoretic approach to the Fast Fourier Transform". Proceedings of the Symposium on Computers and Automata. Polytechnic Institute of Brooklyn. (13-15 Avril 1971).
[23] C.E. SHANNON, W. WEAVER. "The Mathematical Theory of Communication". The University of Illinois Press. URBANA, Illinois. (1949).

[24] C.G. BELL, J. GRASON, A. NEWELL. "Designing computers and digital Systems". Digital Press. (1972).

[25] D.T. BROWN, R.L. ELBSEN, C.A. THORN. "Channel and Direct Access Device Architecture". IBM System Journal, Vol.11, nr. 3, pp. 186-199. (1972).

[26] D. BJORNER. "Finite state Automaton-Definition of Data communication line control procedure". AFIPS.FJCC, pp. 477-491. (1970).

[27] A.G. FRASER. "On the interface between computers and Data Communications Systems". Com. ACM, Vol. 15, nr. 7, pp. 566-573. (July 1972).

[28] S.H. FULLER, R.C. CHEN. "The I/O Port Architecture for computer modules". Carnegie-Mellon University. Dept. of Computer Science Report. (March 1973).

[29] B.W. STUTZMAN. "Data Communication Control Procedures". Computing Surveys, Vol. 4, nr. 4, pp. 197-220. (December 1972).

[30] M. DEPEYROT. "Sur la synchronisation et la fiabilité des automates". RAIRO. Revue Bleue. 5ème Année. B-2. pp. 87-110. (Décembre 1971).

[31] T. TARUI, K. NAMIMOTO, Y. TAKAHASHI. "Twelve-bit microprocessor nears mini-computer's performance level". Electronics. Vol. 47, nr. 6, pp. 111-116. (March 21, 1974).

[32] M. DEPEYROT. "Computer component and system testing as a part of Computer-aided Production and Maintenance". Rapport de Recherche LABORIA. n° 83. (Octobre 1974).

[33] M. DEPEYROT. "Une généralisation de la Notion d'Automate et Applications", Thèse de l'Université de Grenoble. Spécialité Informatique (Juin 1975).