# Segmentation automatique des programmes indépendamment des langages de programmation

Marie-Sylvie Achard, Jean-Yves Babonneau, Gérard Morisset

► To cite this version:

Marie-Sylvie Achard, Jean-Yves Babonneau, Gérard Morisset. Segmentation automatique des programmes indépendamment des langages de programmation. [Rapport de recherche] IRIA-RR-125, IRIA. 1975, pp.36. hal-04716109

HAL Id: hal-04716109

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

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
RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

Segmentation automatique
des programmes indépendamment
des langages de programmation

M.S. Achard, J.Y. Babonneau,
G. Morisset.

Rapport de Recherche n° 125

Mai 1975
# SEGMENTATION AUTOMATIQUE DES PROGRAMMES / INDEPENDAMMENT / DES LANGAGES DE PROGRAMMATION

M.S. Achard, J.Y. Babonneau, G. Morisset

## Abstract :

A knowledge of the way in which programs are structured seems fundamental to us in facilitating the interpretation of their behaviour. The work presented in this report is concerned with the display of a program's structure and forms part of the overall project "OPALE", based on the link-editor : "RELIEUR". The advantages of situating this research at the level of the "RELIEUR" are :

- independence of programming languages used,

- the results can be communicated to programmers,

- the automatic segmentation obtained after this structure analysis can be used by the "RELIEUR"

The salient point of this work is therefore to be formed in the realization of a link-matrix between "sections" (program elements manipulated by the link-editor). A dynamic clusters algorithm analyses this matrix.

## Résumé :

Il nous est apparu fondamental d'approfondir la connaissance de la manière dont se structurent les programmes afin de faciliter l'interprétation de leur comportement. Les travaux présentés dans ce rapport concernent cette mise en évidence d'une structure d'un programme. Cette étude s'inscrit dans le cadre du projet "OPALE" centré sur le RELIEUR. Située ainsi au niveau de la reliure, elle présente plusieurs avantages :

- indépendance vis à vis du langage de programmation utilisé,

- les résultats peuvent être communiqués au programmeur,

- une segmentation automatique obtenue après cette analyse peut être utilisée par le RELIEUR.

Le point essentiel de ce travail se trouve donc dans la réalisation de la matrice des liens entre "sections" (éléments de programme manipulés par le RELIEUR). Un algorithme de reconnaissance des formes analyse cette matrice.
# PLAN

## INTRODUCTION

### I - INTRODUCTION DU PROBLEME

I.1 Problèmes d'implantation des programmes en mémoire.

I.2 Principaux algorithmes de pagination.

I.3 Analyse du comportement des programmes.

I.3.1 Essais réalisés.

I.3.2 Position du problème.

I.3.3 Objectifs poursuivis.

### II - ETUDE DES OBJETS DU RELIEUR - DESCRIPTION DU RELIEUR

II.1 Objets du RELIEUR.

II.2 Description des différentes phases du RELIEUR.

### III - OBTENTION DE LA MATRICE DES LIENS ENTRE SECTIONS

III.1 Définition mathématique.

III.2 Matrice intermédaire.

III.3 Matrice statique.

III.4 Représentation interne de la matrice.

### IV - MISE EN EVIDENCE D'UNE STRUCTURE D'UN PROGRAMME

IV.1 Motivation du choix de l'algorithme.

IV.2 Méthode des nuées dynamiques.

IV.3 Adaptation de cet algorithme à notre problème.

IV.4 Fonctionnement de l'algorithme et résultats obtenus.

## CONCLUSION
Les systèmes d'exploitation sont constitués d'un ensemble complexe de programmes souvent mal connu du programmeur. Dans un tel environnement, l'étude du comportement des programmes peut être abordée de deux manières :

- soit convaincre le programmeur de la nécessité d'avoir une meilleure connaissance du milieu dans lequel sera traité son programme. Cette solution paraît assez irréaliste : d'une part cela supposerait être capable d'assujettir tous les programmeurs ; d'autre part, il faudrait tenir compte de la complexité des systèmes, en constante évolution.

- soit réaliser une adaptation automatique du programme au milieu. Mener à bien une solution aussi ambitieuse, nécessite, en premier lieu, une connaissance approfondie de la façon dont est structuré un programme. Les travaux présentés ici concernent cette première étape : mise en évidence d'une structure des programmes. C'est un problème fondamental qui s'intégre aux recherches actuelles sur la programmation structurée. Cette étude s'inscrit dans le cadre du projet "OPALE" mené au LABORIA et centré sur le RELIEUR. Cet outil de recherche concentre en effet les informations venant des différents traducteurs. Sa place privilégiée dans la chaîne de traduction lui confère une vue d'ensemble tout en conservant une vision assez fine des éléments de programme constitué à son niveau par les sections.

L'intérêt de cette approche réside dans le fait que le RELIEUR est responsable de l'implantation des sections. L'étude d'une structure des programmes au niveau de la reliure présente ainsi plusieurs avantages :

- Indépendance du langage de programmation utilisée.

- Les résultats de cette analyse peuvent être communiqués au programmeur qui aura ainsi une meilleure compréhension de ses programmes. Il pourra aussi, lors de modifications localisées, en connaître la portée.

- Une segmentation automatique, obtenue après cette analyse, peut être utilisée par le RELIEUR lui-même. L'implantation des sections ne se fera pas dans un ordre aléatoire mais dans un ordre tenant compte de la façon dont est structuré un programme.

Le point essentiel de ce travail se trouve donc dans la réalisation de la matrice des liens existant entre les sections. Cette matrice nous permettra de mettre en évidence une structure du programme.
Plusieurs algorithmes implantés de façon modulaire peuvent être responsables de cette analyse. Nous décrivons principalement un algorithme de reconnaissance des formes et nous examinerons les résultats ainsi obtenus.

L'étude réalisée sur une matrice dynamique a été envisagée comme un prolongement de ce travail. Cette étude, concernant le comportement des programmes et leur adaptation au milieu paginé, fait l'objet de la thèse de M. MORISSET.
# I - INTRODUCTION DU PROBLEME

Ce paragraphe permet de situer l'étude présentée, non par rapport au milieu paginé mais plutôt par rapport au cadre du projet "OPALE" dans laquelle elle a été réalisée.

## I.1 PROBLEME D'IMPLANTATION DES PROGRAMMES EN MEMOIRE.

Il incombe au système d'exploitation de gérer le déroulement des programmes, de prévoir les ressources nécessaires. Pour cela, on donne à chaque utilisateur un calculateur virtuel dont il dispose entièrement. Il possède en particulier une mémoire virtuelle. Les objets structurés de façon linéaire ou segmentée, qui composent le programme, sont implantés dans l'espace adressable que constitue la mémoire virtuelle. La segmentation accroit la complexité du mécanisme d'adressage permettant de passer de la mémoire virtuelle à la mémoire physique. Mais elle permet de refléter la structure logique du programme et de ses données.

Cette segmentation peut être laissée à la charge de l'utilisateur, mais nous nous proposons de la rendre automatique afin de soulager l'utilisateur de cette tâche fastidieuse dans le cas particulier de très gros programmes.

La correspondance adresse-virtuelle, adresse réelle nécessite l'emploi d'une table. Pour établir cette correspondance, on procède à un regroupement des informations en blocs dans l'espace virtuel afin de réduire les informations nécessaires.

- Une première méthode dite de "Segmentation" consiste à utiliser des "segments" : ensemble de mots portant un nom et de taille quelconque.

- Une seconde méthode dite de " pagination " consiste à découper l'espace virtuel et la mémoire centrale en blocs de taille fixe appelés "pages".

- Une troisième méthode combine segmentation et pagination.
Cette dernière méthode permet grâce à la segmentation _de mieux respecter la structure logique des programmes_ tout en conservant les avantages du milieu paginé, milieu adopté par un nombre croissant de systèmes actuels.

C'est dans ce milieu que nous nous situerons désormais et nous n'étudierons que les problèmes de gestion qui lui sont propres.

## I.2 PRINCIPAUX ALGORITHMES DE PAGINATION

Les deux problèmes de gestion de mémoire à résoudre concernent :

- les méthodes de chargement d'une page en mémoire centrale,

- les algorithmes de remplacement.

Il est difficile de trouver un critère permettant de choisir l'algorithme pour la gestion de la mémoire d'un programme donné. _Tous ces algorithmes ignorent la structure du programme._ Or cette structure constitue une donnée non modifiable par le système. Et il est primordial d'en tenir compte.

Le choix de l'un ou l'autre de ces algorithmes est orienté par l'étude des courbes de fréquence d'utilisation des pages.

Or, pour étudier le comportement des programmes en milieu paginé et l'évolution de ce comportement en fonction du temps, il faut en premier lieu avoir une connaissance précise de la structure des programmes.

Ce sont les composants logiques du programme (procédures, sous-programmes, modules) et leur enchaînement qui déterminent le comportement des programmes.

Ainsi le problème posé par l'implantation des programmes en mémoire vient de la _superposition d'un milieu logique sur un milieu physique_, ce dernier étant imposé par des contraintes de gestion de mémoire sans aucun rapport avec la structure logique du programme.

## I.3 ANALYSE DU COMPORTEMENT DES PROGRAMMES.

### I.3.1 Essais réalisés.

Que peut-on attendre d'un programme qui n'est plus une donnée mais un objet structuré ? Plusieurs expériences permettent de répondre à cette question.

Celle de Comeau [ 2 ] en particulier permet une réorganisation de la mémoire virtuelle. Mais Comeau pense que la responsabilité "d'ajuster" les programmes à la taille des pages incombe au programmeur lui-même.
Contrairement à Comeau, nous pensons qu'il est difficile pour le programmeur de réaliser cette adaptation, aussi les recherches actuelles visent à rendre cette restructuration automatique.

Hatfield et Gérald [13] ont obtenu des résultats très satisfaisants après restructuration des programmes.

Des essais plus récents par Masuda, Shiota, Nogushi et Ohki [14] montrent que ces résultats peuvent être améliorés.

Pour un même nombre de défaut de page la taille moyenne du working-set est diminuée de 45%. C'est au niveau de la compilation que l'on construit la matrice des liens entre les différentes routines du programme dans le cadre d'un compilateur FORTRAN. Cette matrice sert ensuite de donnée à un algorithme cherchant à regrouper les routines fortement liées entre elles. Cet algorithme est basé sur des méthodes statistiques de regroupement en classes et non sur des méthodes graphiques. On définit la distance entre routines en fonction de la fréquence d'appel des routines entre elles et en fonction de leur taille, car on cherche à former des classes dont la taille ne dépasse pas une page.

Cette étude a lieu au niveau du compilateur :

Elle implique donc d'adjointre à chaque compilateur le module d'analyse permettant cette restructuration. De plus, pour un programme écrit en plusieurs langages, cette méthode ne permet pas de mettre en évidence une structure du programme dans son ensemble, car il n'y a aucun lien entre les compilateurs.

### 1.3.2 Position du Problème.

Nous venons de voir que le problème à résoudre consiste à mettre en évidence une structure propre à un programme, car nous n'avons pas la prétention d'exhiber la structure d'un programme mais une structure de ce programme. Tout ceci explique l'essor des recherches actuelles sur les langages structurés. Mais en se plaçant au niveau du langage, on se heurte à une multiplicité de langages déjà existants : par exemple pour certains types de problèmes un langage d'assemblage peut être plus approprié qu'un langage plus évolué. De façon plus générale on peut constituer un programme à l'aide de modules écrits en différents langages.
Il est nécessaire dès maintenant de bien définir ce qu'est un module : les modules sont des entités logiques conçues, réalisées et compilées indépendamment les unes des autres. Cette notion de modularité intervient même pour un programme écrit dans un seul langage car elle est nécessaire à la conception et à l'exploitation de ce programme.

Les liens entre ces modules, tout comme les liens internes (à l'intérieur d'un module), déterminent le comportement d'un programme. Il est donc impératif pour connaître une structure d'un programme, d'identifier ces liens : les dénombrer et en connaître l'orientation.

Du fait de ces problèmes de langage et compte tenu de la structure modulaire des programmes, il faut pouvoir en constituer un graphe : les sommets sont les modules, les arcs sont les liens orientés entre ces modules. La connaissance de ce graphe pourra permettre d'améliorer l'implantation du programme dans le milieu physique qui lui sera imposé.

Dans ce contexte, nous proposons de confier la mise en évidence de ce graphe à l'éditeur de liens. Le RELIEUR réalisé à l'IRIA concrétise ces travaux.

### I.3.3 Objectifs poursuivis.

Il ne s'agit pas de décrire le RELIEUR ; il est néanmoins nécessaire de connaître sa place dans la chaîne de traduction et d'évaluer les avantages et les inconvénients de cette place dans l'étude d'une structure des programmes.

Dans une première étape, le programme source est traduit en langage binaire objet (ou B.O., voir annexe) par les compilateurs : dans le cas le plus général, comme nous l'avons vu au paragraphe précédent, ce programme peut en effet être constitué de plusieurs modules écrits en différents langages. Le B.O. est le langage source du relieur qui joue ainsi un rôle centralisateur dans la chaîne de traduction. C'est le relieur qui constitue ensuite un programme exécutable.
Module $M_1$.
écrit en
FORTRAN

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

$M_2$ en $PL_1$

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

$M_3$ en 10070

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

Compileur
FORTRAN

Compileur
$PL_1$

Compileur
du
LP 10070

$M.O_1$ en $B.O.$

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

$M.O_2$ en $B.O.$

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

$M.O_3$ en $B.O.$

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

RELIEUR

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

Programme
chargeable

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

Chargeur

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

Schéma de la chaîne de traduction d'un programme constitué de trois
modules écrits en FORTRAN, $PL_1$, LP 10070.
Le but que nous poursuivons est en fait de soulager les taches des traducteurs et d'accroître les responsabilités du relieur. Une des premières fonctions adjointe au relieur consiste à constituer un graphe du programme.

La bonne compréhension de la méthode d'analyse de ce graphe nécessite une description sommaire des modules ou, plus précisément, des objets dont la gestion est confiée au relieur.
## II - ÉTUDE DES OBJETS DU RELIEUR - DESCRIPTION DU RELIEUR

### II.1 OBJETS DU RELIEUR

Un objet est identifié par :

- un type : - type 1 : références en avant,

- type 2 : sections et externes,

- un numéro attribué par le compilateur,

- un nom affecté par le programmeur en général.

D'où la représentation par le triplet : <TYPE,NUMERO,NOM>

Exemple :

Tous les exemples illustrant ce rapport sont écrits dans un langage issu
du LP 10070.

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

Exemple 1

La classe des références en avant peut être vide. Dans le cas d'un
compilateur à une passe, une référence à une étiquette non encore définie
engendre une déclaration de référence en avant dont la gestion est
confiée au RELIEUR. C'est le cas de l'exemple ci-dessus.
A l'exception des objets définis par une adresse absolue, tous les autres objets sont définis par les objets de type 2 : "Sections". D'un point de vue physique, une section est l'image de T mots contigus de la mémoire auxquels sont associés une protection et repérés par rapport à la base.

<figure><img src="image_12.png" /><figcaption>Figure 1</figcaption></figure>

Données externes
+
internes

MO₁

DEF WORD A;
WORD IA;
DEF ARRAY 3 WORD B;
WORD IB;

R1 := IA + B;

Code

R2 := 'TEXT';

Litteraux

MO₂

WORD IA;
WORD ID;
DEF WORD C;
REF WORD B;

R1 := IA + ID;

R2 := 'TEXT';

Exemple 2.
Le découpage en sections de ce programme, constitué de deux modules
objets, peut être représenté ainsi :

<figure><img src="image_13.png" /><figcaption>Figure 2.</figcaption></figure>

La responsabilité du découpage du programme en sections incombe au traducteur
ou au programmeur s'il travaille en langage d'assemblage ; en général :

- sections de code,

- sections de données,

- sections de littéraux (constantes).

En conclusion, nous constatons que du point de vue physique :

- les sections constituent des entités indivisibles

- tous les autres objets appartiennent à l'une ou l'autre de
ces sections.

D'autre part nous allons voir que la gestion de ces sections c'est-à-dire la
prise de décision de leur implantation dépend uniquement du RELIEUR.
Les sections sont les éléments fondamentaux de la structuration des
programmes. Cette étude se situera donc au niveau de l'étude des liens
entre ces sections.

## II.2 DESCRIPTION DES DIFFERENTES PHASES DU RELIEUR.

Une connaissance sommaire des différentes étapes de la reliure s'impose
afin de mieux comprendre comment le RELIEUR détecte les liens existant entre
les sections.
- **_Première phase_** :

Le RELIEUR réalise une première passe sur la B.O. pour :

a) constituer les tables des références en avant, des externes et
des sections,

b) dénombrer les objets des deux types.

- Deuxième phase :

C'est la phase pendant laquelle le RELIEUR :

a) prend la décision de l'ordre d'implantation des sections :

. soit de façon arbitraire,

. soit après étude d'une structure du programme,

b) traduit en terme d'adresse la définition des autres objets.

C'est lors de cette phase que l'on peut agir pour adapter le programme
au milieu physique.

- Troisième phase :

Pendant la deuxième passe sur la B.O. le RELIEUR :

a) constitue le module de chargement,

b) engendre le code exécutable,

c) imprime les MAPS : par fichier et par section,

par ordre alphabétique des externes.

III. OBTENTION DE LA MATRICE DES LIENS ENTRE
SECTIONS

III.1 DEFINITION MATHEMATIQUE.

Comme nous ne nous intéressons qu'aux objets dont le RELIEUR est uni-
quement responsable (cf paragraphe II.1) nous allons établir sous forme
matricielle les liens entre sections.
Cette matrice représente le graphe $G(X,\Gamma)$ défini par :

- $X$ : ensemble des sections.

- $\Gamma$ : application de $X$ dans $X$ : relation de liaison entre sections.

L'obtention de cette matrice nécessite de passer par une matrice intermédiaire représentant les liens entre sections et objets de type 2.

Soit $X'$ ensemble des objets de type 2.

$$X \subset X'$$

Et soit $\Gamma'$ l'application relation de liaison entre sections et objets de type 2 :

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

La matrice intermédiaire est représentée par le graphe $G'(X',\Gamma')$.

### III.2 MATRICE INTERMEDIAIRE

Lors des différentes phases du RELIEUR, nous avons vu que la première consiste, en particulier, à construire les tables des externes, des sections et des références en avant. Le RELIEUR possède alors une vue partielle, des liens existant entre les objets, représentée par le graphe $G'(X',\Gamma')$ défini ci-dessus.

- $X'$ étant l'ensemble des objets de type 2, quel est le rôle des références en avant ? Au fur et à mesure du déroulement de la phase 1, on connaît d'abord les sections $x_i$ utilisant une référence en avant.

Cette dernière est définie, par la suite, par un objet y de type 2 qui est donc, soit la section dans laquelle se trouve la définition de la référence en avant, soit un externe. On met ainsi en évidence par l'intermédiaire d'une référence en avant une liaison $x_i \Gamma' y$ du graphe $G'(X',\Gamma')$.

- D'autre part, le RELIEUR permet de construire les liaisons sections-objets de type 2 connues à l'aide des tables des externes et des sections.

### III.3 MATRICE STATIQUE

Dans la phase 2 du RELIEUR, on associe à chaque externe le numéro de section dans laquelle il est défini. Nous avons vu l'importance des sections en tant qu'entités indivisibles et en tant qu'éléments sur lesquels le RELIEUR peut agir lors de la décision d'implantation des programmes. C'est donc la matrice réduite à la représentation des liaisons de section à section qui présente le plus grand intérêt. De plus ces liaisons sont pondérées.
Le cas extrême d'un externe défini par plusieurs sections doit être étudié avec soin. Toute section faisant appel à cet externe est liée aux différentes sections le définissant. Ainsi à partir d'une simple liaison section → Externe peuvent être mises en évidence plusieurs liaisons section → section. Nous avons rencontré ce cas deux fois dans le programme du compilateur PLI conversationnel construit à l'IRIA, écrit en METASYMBOL.

Exemple 3 :

```
Section 1
    CSECT 0
    DEF DEBUT-RAZ
    ...
    DEBUT-RAZ EQU $
    ...

Section 2
    CSECT 0
    DEF FIN-RAZ
    ...
    FIN-RAZ EQU $
    ...

Section 3
    CSECT 0
    REF DEBUT-RAZ
    REF FIN-RAZ
    DEF LONG-RAZ
    ...
    LONG-RAZ EQU DEBUT-RAZ - FIN-RAZ
    ...
```

L'externe LONG-RAZ est défini par les deux sections 1 et 2 et tient compte de l'implantation relative de la section 1 par rapport à la section 2.

Lors d'une étude de la structure du programme en vue d'une restructuration de ce même programme, il est capital d'avoir détesté ces cas où le programmeur tient compte d'une certaine implantation de ses sections.
Exemple de constitution de la matrice intermédiaire puis de la matrice
finale pour un programme formé de deux modules objets :

M.O.₁

Numéro de l'externe
dans la matrice.

Section 0
[ REF WORD W ; (W,Externe,1) → 256 + 1
REF LABEL ETIQ ; (ETIQ, Externe,2) → 256 + 2
DEF ARRAY 3 WORD T ;
DEF PROCEDURE A ;

Section 1

BEGIN
W := R1 := T + 1; → La section 1 référence
l'externe W et la section 0 dans
laquelle est défini T (Poids égaux
à 1)
GOTO ETIQ ; → La section 1 utilise une référence
en avant (REFAV,1) (poids = 1)
GOTO ETIQ ; → Utilisation de la référence en avant
(REFAV,1) une deuxième fois
poids = 2
END.

→ Définition de la référence en avant
(REFAV,1) par l'externe ETIQ de
numéro 258 dans la matrice. Ainsi
la section 1 référence l'externe
258 avec un poids égal à 2.
La matrice statique finale est la suivante :

<table><tr><td></td><td>0</td><td>1</td><td>2</td><td>3</td></tr><tr><td>0</td><td></td><td></td><td></td><td></td></tr><tr><td>1</td><td>1</td><td></td><td>1</td><td>2</td></tr><tr><td>2</td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td></td><td>1</td><td>2</td><td></td></tr></table>

### III.4 REPRESENTATION INTERNE DE LA MATRICE

La structure de donnée choisie pour la matrice statique sera également celle de la matrice dynamique : le nombre de branchement d'une section à une autre représentant alors une fréquence et non un poids.

Cette matrice est essentiellement creuse ; donc pour occuper le moins de place possible en mémoire, nous avons opté pour une représentation en listes croisées. C'est-à-dire que nous pouvons accéder à un élément I, J de la matrice aussi bien à l'intérieur de sa ligne qu'à l'intérieur de sa colonne.

Ainsi, grâce à sa structure de liste, l'encombrement de la matrice est minime ce qui permet de l'implanter toute entière en mémoire lors de son exploitation statique par un module d'analyse. D'autre part cette exploitation est grandement facilitée par le double chaînage ordonné.

Nous donnons, ci-après quelques exemples de matrices statiques obtenues sous ESOPE et SIRIS 8.

Les sections sont numérotées en hexadécimal. La colonne "C" correspond aux références à des constantes.

La colonne "X" correspond aux références à des externes non définis.

Trois symboles permettent de distinguer les valeurs prises par le poids.

<table><thead><tr><td>symbole</td><td>poids</td></tr></thead><tbody><tr><td>1</td><td>0<p≤3</td></tr><tr><td>+</td><td>3<p≤10</td></tr><tr><td>*</td><td>p>10</td></tr></tbody></table>
<figure><img src="image_15.png" /></figure>
SOUS ESOPF

<figure><img src="image_16.png" /></figure>
# IV. MISE EN EVIDENCE D'UNE STRUCTURE D'UN PROGRAMME

## IV.1 MOTIVATION DU CHOIX DE L'ALGORITHME

Deux voies se présentaient pour mettre en évidence une structure d'un programme : utiliser une méthode basée sur la théorie des graphes ou une méthode statistique. Nous avons choisi cette dernière méthode car d'une part nous disposons d'une matrice qui n'est pas simplement booléenne ; d'autre part l'algorithme des "nuées dynamiques" de M. DIDAY [6,7] a déjà servi à résoudre des problèmes du même type : "optimisation de l'implantation de fichiers sur disques" FLORY [10]. L'utilisation d'algorithme basé sur la reconnaissance des formes, par les japonais, pour une étude analogue à la nôtre, nous a également confirmés dans ce choix.

L'algorithme des "nuées dynamiques" réalise une partition en classes d'éléments très fortement liés. Si lors de sa conception le programme a une structure modulaire, l'algorithme met en évidence ces modules. Cette recherche tient compte de la logique du programme si elle a lieu à partir d'une matrice statique. Elle pourra également s'appliquer à l'étude de son comportement à partir d'une matrice dynamique.

## IV.2 METHODE DES NUÉES DYNAMIQUES ET LA RECONNAISSANCE DES FORMES

Les problèmes de reconnaissance des formes consistent à chercher, selon un critère de ressemblance, une partition dans un ensemble d'objets caractérisés par un nombre fini de paramètres. Le but de l'algorithme des "nuées dynamiques" de M. DIDAY [6,7] qui est un algorithme répondant à cette préoccupation, est donc de donner une partition de l'ensemble des objets étudiés, ainsi qu'une mesure de la valeur de la partition obtenue.
La distance entre les éléments, ainsi que le nombre de classes K de la partition, sont fixés par l'utilisateur. Nous allons étudier les différentes étapes de l'algorithme.

1. On fait un tirage aléatoire d'éléments appelés "étalons" parmi les objets de la population donnée. Par souci de clarté choisissons un seul étalon par classe (on pourrait en prendre plusieurs selon le problème traité). Soit K étalons : ils jouent le rôle de centre d'agrégation des K classes.

2. Chaque élément de la population est affecté à la classe associée au centre d'agrégation le plus proche. On construit ainsi K classes.

3. On cherche alors quels sont les éléments les plus représentatifs de ces K classes : c'est-à-dire les K nouveaux étalons.

4. Si les étalons n'ont pas changé, on obtient un classement identique pour deux itérations successives. La convergence est atteinte.

- sinon on retourne en 2.

La population est ainsi classée plusieurs fois.

Le processus est arrêté soit lorsqu'il se stabilise de lui-même (convergence atteinte) soit lorsqu'un nombre d'itérations fixé à l'avance a été atteint (convergence non atteinte).

On mesure la validité de la partition obtenue à partir d'un critère α modifiable par l'utilisateur.

On peut par exemple le calculer à partir du critère caractérisant l'étalon $e_k$ d'une classe $C_k : \sum_{x \in C_k} d(x, e_k)$

$$ \alpha = \sum_{k=1}^{K} \sum_{x \in C_k} d(x, e_k) $$

Si on refait un tirage aléatoire d'étalons, on obtient à la convergence K autres classes avec un critère α'. La meilleure partition est celle dont le critère est le plus faible.
Dans le cas où l'on prend plusieurs étalons pour la représentation d'une classe, on appelle noyau d'une classe l'ensemble des étalons de cette classe.

Prenons l'exemple suivant constitué de six éléments représentés dans le plan ; on choisit ici la distance Euclidienne.

<figure><img src="image_17.png" /><figcaption>Figure 1.</figcaption></figure>

L'utilisateur a demandé 2 classes et 2 étalons par classe. Supposons que le premier tirage aléatoire ait donné pour noyaux d'étalon :

$$E_1 = \{y_1, y_4\}$$

$$E_2 = \{y_3, y_6\}$$

Les classes obtenues à la convergence seront :

$$C_1 = \{y_1, y_2, y_4\}$$

$$C_2 = \{y_3, y_5, y_6\}$$

<figure><img src="image_18.png" /><figcaption>Figure 2.</figcaption></figure>
Les nouveaux étalons calculés pour les classes C₁ et C₂ sont respectivement :

$$E_1 = \{y_1, y_2\}$$

$$E_2 = \{y_5, y_6\}$$

On obtient alors les nouvelles classes :

$$C_1 = \{y_1, y_2, y_3\}$$

$$C_2 = \{y_4, y_5, y_6\}$$

Si l'on recherche les nouveaux étalons de ces classes on retrouve $E_1$ et $E_2$. La convergence est atteinte.

<figure><img src="image_19.png" /><figcaption>Figure 3.</figcaption></figure>

La valeur du critère est :

$$\alpha = d(y_3, y_1) + d(y_3, y_2) + d(y_4, y_5) + d(y_4, y_6)$$

Par sa définition même, ce critère décroît quand le nombre de classes demandé augmente et sa limite inférieure est 0 (quand on obtient autant de classes que d'éléments à classer).
IV.3 ADAPTATION DE CET ALGORITHMÈ A NOTRE PROBLEME.

Le module réalisant la segmentation à l'aide de l'algorithme"des nuées
dynamiques" fait partie du programme d'analyse. Ce programme accède à la
matrice construite par le RELIEUR et crée dans une zone dynamique une
nouvelle matrice qui sera le tableau de données, utilisé par le programme
FORTRAN de reconnaissance des formes.

La matrice du RELIEUR donne le poids P(I,J) affecté aux différentes
liaisons entre les sections I et J. Plusieurs solutions sont possibles
pour définir la distance entre deux sections :

$$
D(I,J) = P_{\max} - P(I,J) \quad \text{ou} \quad D(I,J) = \frac{1}{P(I,J)} \cdots
$$

$P_{\max}$ est le poids maximum rencontré parmi les poids des liaisons de la
matrice.

On peut d'autre part, réaliser une homothétie sur les distances.
Pour plusieurs tests réalisés, un coefficient d'homothétie fixé à 60
a permis d'obtenir la convergence beaucoup plus rapidement et les résultats
obtenus sont identiques dans le cas du programme test qui était le RELIEUR.

On peut de façon optionnelle supprimer, de l'ensemble des sections,
les sections terminales c'est-à-dire celles qui n'appellent pas d'autres
sections. On peut alors étudier comment se structure le programme et obtenir
une segmentation. Il convient ensuite de rattacher ces sections terminales aux
sections les appelant. Si plusieurs sections qui ne sont pas dans le même
segment, font appel à une même section terminale, on crée un nouveau segment
appelé "racine" qui sera l'ensemble de ces sections terminales communes
à plusieurs segments.

Nous définissons le critère permettant de mesurer la validité d'une
partition en K classes, obtenue à la convergence, comme les K sommes des
sommes des distances des éléments entre eux, à l'intérieur des classes Ck
qu'ils constituent :

$$
\alpha = \sum_{k=1}^{K} \sum_{x_i, x_j \in C_k} d(x_i, x_j)
$$
IV.4 FONCTIONNEMENT DE L' ALGORITHME ET RESULTATS OBTENUS.

L'algorithme a été modifié afin d'obtenir un nombre de classes variables
Ce nombre variant de deux classes à un nombre $K_{max}$ calculé en fonction du
nombre total de sections dont est constitué le programme.

Dans une première étape, on recherche la valeur du critère pour les
différents tirages aléatoires, on garde celui qui donne la meilleure
partition pour deux classes puis pour trois classes et ainsi jusqu'à $K_{max}$.

A partir de ces classes ainsi sélectionnées, on cherche à suivre
l'évolution des éléments de ces classes.

Observons les résultats obtenus pour le RELIEUR (Figure 4). On suit
l'évolution des classes qui se décomposent en sous-classes et on essaie de
mettre en évidence une arborescence si elle existe.

On constate que la scission en trois classes est obtenue à partir
d'éléments des deux classes précédentes. La valeur du critère pour trois
classes est d'ailleurs supérieure à celle obtenue pour deux classes. Par
contre, lors de la décomposition en quatre classes, on retrouve les deux
classes obtenues à partir de la décomposition en deux classes à quelques
éléments près qui forment deux sous-classes. La valeur du critère est
plus faible que pour deux classes.

Pour une décomposition en cinq puis en six classes, on obtient encore
une décomposition en deux classes principales à peu près stables d'une
décomposition à l'autre et des sous-classes formées souvent d'un seul
élément ce qui explique la diminution du critère alors que les classes
principales évoluent peu. Une décomposition plus poussée n'est donc pas
nécessaire.

On a constaté d'autre part qu'en réalisant une homothétie dont le
coefficient est 60, on obtient la convergence beaucoup plus vite mais les
résultats obtenus sont identiques, c'est-à-dire que l'on constate la même
décomposition artificielle pour trois classes, ce qui se traduit sur la
courbe des valeurs du critère par une augmentation de la pente de la courbe
pour K = 3. (Figure 5).

En conclusion après avoir éliminé certains découpages artificiels,
l'examen de la courbe des critères permet de retenir les décompositions les
plus intéressantes.
<figure><img src="image_20.png" /></figure>

Décomposition obtenue pour le relieur (71 sections).

<caption>Figure 4.</caption>
<figure><img src="image_21.png" /><figcaption>Figure 5.</figcaption></figure>

nombre de classes

Courbe de la valeur du critère fonction du nombre de classes pour le RELIEUF.
Les recherches actuelles tendent à démontrer qu'il est nécessaire de
mieux comprendre les programmes avant de les exploiter. Dans le cadre de
l'adaptation des programmes au milieu paginé, nous étions convaincus de
l'intérêt de cette évolution.

Nous avons donc considéré le problème sous ses différentes formes et,
en particulier, tenté d'acquérir, à tous les niveaux, des informations sur la
structure des programmes. Les recherches concernant la matrice statique de
liens entre sections, répondent à cette préoccupation. L'objectif suivant,
relatif à l'étude d'une matrice dynamique obtenue après une ou plusieurs
exécutions, est poursuivi afin de compléter la connaissance du programme.

Le cadre dans lequel nous avons obtenu nos informations, c'est-à-dire
à partir du RELIEUR, confère à ces travaux une grande généralité en les
rendant indépendants du langage de programmation utilisé.

L'étude d'une structure des programmes a nécessité, comme nous l'avons
vu dans les précédents chapitres, une décomposition en deux étapes :

- Construction de la matrice des liens existant entre les sections.

- Analyse de cette matrice pour mettre en évidence une segmentation
du programme.

Cette seconde étape fait appel à un algorithme de reconnaissance des
formes qui a déjà trouvé des applications dans des domaines similaires, ce
qui a justifié notre choix. Mais notre désir de ne pas nous limiter ou de
ne pas limiter d'autres personnes susceptibles de s'intéresser à ce type
d'étude, nous a amené à faire un effort de modularité : son remplacement
par un autre algorithme a été rendu particulièrement aisé.

Afin de pouvoir démontrer l'apport d'une telle étude, au départ
théorique, sur un plan concret, il nous a paru important de réaliser un
outil fonctionnant de façon opérationnelle (cf Annexe 2).

En dehors des objectifs initialement recherchés, cette étude présente
d'importantes retombées. Les renseignements concernant la façon dont se
structurent les programmes peuvent non seulement être utilisés par le RELIEUR
mais ont déjà été exploités par le programmeur lui-même. Ainsi cette étude
répond également aux préoccupations de la programmation structurée.
En outre, l'exploitation de la matrice statique présente un intérêt fondamental dans le cadre de l'étude des "CONTEXTES", nouvel axe de recherche développé au sein du projet "OPALE". Elle doit permettre ainsi d'une part d'améliorer la gestion des librairies, d'autre part de faciliter la constitution de gros programmes.
Bibliographie

[1] CHRETIENNE P.

"Gestion de la mémoire des ordinateurs"

Thèse de troisième cycle. Institut de Programmation de Paris
N° IP. 74-8 (mai 1974)

[2] COMEAU L.W.

"A study of the effect of user program optimization in a paging
system", ACM Symp. on operating systems Principles Gatlinbourg,
Tennessee ; Oct 1-4 (1967).

[3] DENNING P.J.

"The working-set model for program behavior"

Comm. ACM ; 11, 5 (mai 1968) pages 323-333.

[4] DENNING P.J., CHEN Y.C., SHELDER G.S.

"A model for program behavior under demand paging"

Rep. R.C. 2301 IBM T.J. Watson Research Center,
Yorktown Heights N.Y. Septembre 1968.

[5] DENNING P.J., SCHWARTZ S.C.

"Properties of the working-set model".

Comm. ACM, 15, 3 (mars 1972) pages 191-198.

[6] DIDAY E.

"Une nouvelle méthode en classification automatique et reconnaissance
des formes": la méthode des nuées dynamiques".

Revue de statistique appliquée. Vol XIX n° 2 1971

[7] DIDAY E.

"Optimisation en classification automatique et reconnaissance des
formes". Bulletin de l'IRIA n° 12 (Mai-Juin 1972).
[8] FERRARI D.
"The method of critical working sets for the automatic improvement of program locality". Berkeley California.

[9] FERRARI D.
"A tool for automatic program restructuring".
Conférence de l'ACM Atlanta Georgia (Août 1973).

[10] FLORY A.
"Optimisation de l'implantation de fichiers situés sur disques par des méthodes de classification automatique". Thèse de troisième cycle. Université Claude Bernard - Lyon (Septembre 1973).

[11] GELENBE S.E., TIBERIO P.
"Page size in demand paging systems".
ACM - SIGME First Symp. on Measurement and Evaluation.
Palo Alto Février 1973.

[12] HATFIELD D.J.
"Experiments with page size, program access pattern and virtual memory performance".
IBM Journal of research and development ; 16, 1, pages 58-66 (1972)

[13] HATFIELD D.J., GERALD J.
"Program restructuring for virtual memory".
IBM Syst. J. n° 3 (1971).

[14] MASUDA T., SHIOTA H., NOGUCHI K., OHKI T.
"Optimization of program organisation by cluster analysis". (1974).

Bibliographie concernant plus particulièrement la programmation structurée.

[15] ARSAC J.
"Les langages sans étiquettes".
Institut de Programmation, n° IP 73-13. (Septembre 1973).
[16] ARSAC J.
"Un langage de programmation sans branchement".
RAIRO, 6ème année, B2, pages 3-24 (Juin 1972).

[17] DIJKSTRA E.W.
"Structured programming in software engineering techniques"
J.N. BUXTON and B. RANDELL (Eds) NATO scientific Affairs Division
Bruxelles, Belgique, 1970, pages 84-88.

[18] HANSEN P.D.
"Structured Multiprogramming".
CACM, 15, 7 (1972) pages 574-578.

[19] HOARE C.A.R.
"Hintz for programming language design".
Computer science Report STAN-CS-74-403 Stanford Univ., Stanford, Californie, Janvier 1974.

[20] KNUTH D.E.
"A review of structured programming".
Stanford Computer Science Department, Report STAN-CS-73-371 -
Juin 1973.

[21] KNUTH D.E.
"Structured Programming with "goto" Statements".
Stanford University. Computing Surveys 1974.

[22] MILLS H.D.
"How to write correct programs and know it".
Report FSC 73)5008 IBM Federal Systems Division, Gaithersburgh, Md.

[23] PARNAS D.L.
"A Technique for Software Module Specification with Examples".
CACM, 15, 5, (1972) pages 330-336.

[24] SNOWDON R.A., PEARL.
"An Interactive System for the Preparation and Validation of Structured Programs".
Report 28, Computing Center, Univ. of Newcastle Upon Tyne, (Nov. 1971).
[25] WIRTH N.
"On the composition of well Structured Programs".
Computing Surveys 1974.

[26] WULF.W.A.
"A programming without the "goto". "
Information Processing 71. IFIP, Vol 1. North Holland Publ. CO.
Amsterdam, The Netherlands, 1971, pages 408-413.

[27] ACHARD M.S.
"Segmentation automatique des programmes indépendamment des langages de programmation".
Thèse de 3ème cycle, Université de Paris VI, avril 1975.