Résolution de systèmes d’inéquations linéaires; mode d’emploi du logiciel PIP

Paul Feautrier et Nadia Tawbi^{∗}

Laboratoire MASI, Université P. et M. Curie 75252 PARIS CEDEX 05 FRANCE

e-mail : PAF at FRUNIP62.bitnet ou feautrier@masi.ibp.fr

2 Décembre 1989

Résumé

Ce papier présente un programme qui résoud les problèmes paramétriques en nombres entiers, c’est-à-dire qui trouve le minimum lexicographique de l’ensemble des points de coordonnées entières d’un polyèdre convexe, quand ce polyèdre dépend linéairement de paramètres entiers. L’algorithme PIP et son implémentation en C sont décrits brièvement. Les données, les résultats et le mode d’emploi sont spécifiés en détail. Enfin, un interface qui permet l’utilisation de PIP depuis Le Lisp est décrit.

Abstract

This paper documents a program which solves Parametric Integer Programming problems, i.e. which finds the lexicographic minimum of the set of integer points which lie inside a convex polyhedron, when that polyhedron depends linearly on one or more integral parameters. The PIP algorithm and an implementation in C are briefly described; the data, results and modus operandi are specified in details. Lastly, an interface for using PIP from Le Lisp is described.

∗Adresse actuelle : Centre de Recherche, Groupe BULL, 68, Route de Versailles, 78430 LOUVECIENNES

1 Présentation du problème

L’analyse sémantique de programmes contenant des accès à des tableaux conduit souvent à la résolution de problèmes de programmation mathématique en nombres entiers dépendants de paramètres. Il y a à cela deux raisons:

• Les fonctions d’indice sont très souvent des formes linéaires par rapport aux compte-tours des boucles.

• Les conditions de succession temporelle imposent un ordre sur l’espace des solutions.

Considérons par exemple le fragment de programme:

    for i:= 0 to m do
        for j := 0 to n do              {I}
            a[2*i+j] := i+j;

Après exécution de ces boucles, pour quelles valeur de k A[k] est-il défini et quelle en est la valeur? On voit facilement que les valeurs de i, j, k convenables sont solutions du système:

0 ≤ i ≤ m,  (1)
0 ≤ j ≤ n,  (2)
2i + j = k.  (3)

D’autre part, la solution qui nous intéresse est celle qui correspond à l’exécution la plus tardive, c’est-à-dire à la plus grande valeur possible du vecteur < i, j > dans l’ordre lexicographique. Nous sommes donc amenés à nous intéresser au problème suivant:

Soit F(k, m, n) le polyèdre :

F(k, m, n) = {< i, j > |0 ≤ i ≤ m, 0 ≤ j ≤ n, 2i + j = k}.  (4)

Quel est le maximum lexicographique de l’ensemble des points entiers contenus dans F(k, m, n)? Dans cet énoncé, les variables k, m et n sont des paramètres, ce qui signifie que l’on cherche une solution fonction de k, m, n. On se convainc d’ailleurs facilement que si

k > 2m + n,

l’ensemble F(k, m, n) est vide. La solution obtenue devra refléter ce phénomène.

Le problème peut se généraliser dans les termes suivants. Considérons un polyèdre^{1}:

1La notation x⃗ ≥ 0 est une abbréviation pour

x_{i} ≥ 0, i = 1, |x⃗|, où |x⃗| est la dimension du vecteur x⃗.

F(z⃗) = {x⃗|x⃗ ≥ 0, Ax⃗ + Bz⃗ + c⃗ ≥ 0}.  (5)

Dans cette formule, x⃗ est un vecteur à n composantes : le vecteur des inconnues. z⃗ est le vecteur des paramètres, à p composantes. Le polyèdre F(z⃗), qui est un sous ensemble de R^{n}, est défini par n + l inégalités : les n composantes de la condition

x⃗ ≥ 0

et les inégalités engendrées par les matrices A de dimension l×n, B de dimension l × p, et par le vecteur constant c⃗ de dimension l.

Le polyèdre F(z⃗) se déplace et se déforme en fonction de z⃗. On est toujours amené à restreindre les valeurs possibles des paramètres par la condition:

z⃗ ≥ 0.

Parfois, les paramètres sont contraints par un système supplémentaire d’inégalités:

Mz⃗ + h⃗ ≥ 0,

qui constituent le contexte du problème. M est une matrice de dimension m × p et h⃗ un vecteur de dimension m.

On supposera enfin que toutes les données du problème (A, B, M, c⃗, h⃗) sont entières ^{2}.

Le problème de la programmation entière paramétrique est de déterminer pour quelles valeurs entières du paramètre z⃗ le polyèdre F(z⃗) contient des points entiers. Si la réponse est positive, il est de plus demandé d’exhiber l’un de ces points. Le choix se porte en général sur le point lexicographiquement le plus petit, et ceci pour deux raisons:

• La condition x⃗ ≥ 0 garantit l’existence du minimum sous la seule condition de l’existence d’un point faisable entier.

• L’utilisation de l’ordre lexicographique (outre qu’il a un sens bien précis en informatique), évite les questions de dégénérescence (i.e. de minima multiples) qui se posent avec une fonction économique linéaire.

Une méthode de résolution des problèmes paramétriques en entiers a été donnée dans [Fea88a]. Elle part de l’algorithme classique de Dantzig-Gomory pour la résolution des problèmes non paramétriques. On commence par exécuter des échanges (changements linéaires de variables) aussi longtemps qu’il y a des inégalités qui ne sont pas visiblement satisfaites. Cette phase peut se terminer par un échec (aucun échange n’est plus possible, et donc le système n’a pas de solution), ou bien par la mise en évidence d’une solution rationnelle. Si cette solution est entière, le problème est résolu. Sinon, on construit une coupure, c’està-dire que l’on ajoute une nouvelle contrainte qui élimine le minimum rationnel mais aucune solution entière, et on reprend les échanges.

2Nous dirons qu’un vecteur ou une matrice sont entiers si toutes leurs coordonnées sont entières.

Une analyse serrée de cet algorithme montre que les échanges peuvent être effectués même lorsque les termes “constants” sont des expressions dépendant linéairement de paramètres et que ces opérations ne changent pas la forme du problème. Le choix des variables à échanger est guidé par l’analyse du signe des termes “constants”. En présence de paramètres, ce signe ne peut pas en général être défini, et il faut donc diviser le problème en deux branches. Chaque branche correspond à l’une des deux hypothèses possibles pour le signe d’une forme linéaire qui ne dépend que des paramètres. On obtient donc deux sousproblèmes en ajoutant l’une ou l’autre de ces hypothèses au contexte initial.

De la même façon, on peut construire une coupure en présence de paramètres. L’opération conduit à l’introduction d’un paramètre supplémentaire et de deux nouvelles conditions de contexte. Le nouveau paramètre s’interprète comme le quotient entier d’une forme linéaire par un nombre entier fixé.

La forme de la solution résulte de cette analyse.

• En cas de succès, on obtient une solution sous la forme:

x⃗ = Tz⃗′ + s⃗.

Le vecteur z⃗′ est composé des paramètres originaux et des paramètres supplémentaires introduits lors de la construction des coupures, lesquels s’expriment, comme nous l’avons dit, comme quotient entier d’une forme linéaire par une constante. Il en résulte que ces paramètres nouveaux peuvent être éliminés de proche en proche au profit des paramètres originaux. Nous appelerons forme quasi-affine une forme construite à partir de variables et de constantes entières par les trois opérations d’addition, de multiplication par une constante entière et de division euclidienne par une constante entière.

• En cas d’échec, nous utiliserons le signe <> pour marquer que le polyèdre F(z⃗) est vide de points entiers.

• Le dernier cas est celui où le problème se subdivise en deux. Il est facile de voir que le critère de division est le signe d’une forme quasi-affine. La solution peut alors s’écrire comme une conditionelle:

                     if foo >= 0 then x+ else x-.

On peut résumer ces observations à l’aide de la grammaire hors-contexte suivante (dans laquelle on suppose donnés les non-terminaux ^{3} Entier et Va-

riable.

3Les symboles des non-terminaux commencent tous par une majuscule.

Grammaire 1 :

Forme_quasi_affine ::= Entier | Variable
    | (Forme_quasi_affine * Entier)
    | (Forme_quasi_affine / Entier)
    | (Forme_quasi_affine + Forme_quasi_affine)
    | (Forme_quasi_affine - Forme_quasi_affine)
Liste_de_composantes ::= Forme_quasi_affine
    | Liste_de_composantes , Forme_quasi_affine
Solution ::= < Liste_de_composantes >
    | <>
Quast ::= Solution
    | if Forme_quasi_affine >= 0 then Quast else Quast

Les solutions du problème sont décrites par le non-terminal Quast, abbréviation de l’anglais quasi-affine selection tree. En présentant certains exemples, il nous arrivera de prendre des libertés avec cette grammaire et notamment de réduire le nombre de parenthèses.

La preuve de correction de l’algorithme ci-dessus se divise en deux parties. On remarque tout d’abord que l’algorithme n’est qu’une version algébrique d’un algorithme numérique. Si la transposition symbolique a été correctement faite, (et on se reportera pour les détails à l’article cité), il n’y a pas plus de doute sur la correction partielle de l’algorithme qu’il n’y en a pour une transformation algébrique banale. Tout autre est le problème de la convergence. L’algorithme paramètrique construit un arbre de solutions; donner des valeurs aux paramètres et exécuter l’algorithme numérique, revient à choisir et suivre une branche de l’arbre. Or on peut démontrer que l’algorithme numérique non seulement se termine toujours, mais que sa complexité peut être bornée uniformément par rapport aux paramètres. On en déduit facilement que l’arbre des solutions est fini et que l’algorithme paramétrique converge.

La complexité théorique de l’algorithme est évidemment formidable. Nous avons observé en pratique que, dans les cas d’intérêt informatique, elle reste acceptable.

Le processus de résolution n’est pas entièrement déterministe : un problème paramètrique en entiers a beaucoup de solutions formellement distinctes mais numériquement équivalentes. Le choix entre solutions est plus une question d’esthétique qu’une question mathématique. La règle essentielle que nous avons suivie est celle qui consiste à faire apparatre les signes <> le plus tôt possible. Cette politique a pour conséquence de regrouper au mieux les “cas pathologiques” et de simplifier dans une certaine mesure les expressions obtenues.

Le logiciel PIP est une implémentation de l’algorithme de [Fea88a]. Il existe tout d’abord un “noyau” écrit en C dans un souci de performances. Ce programme est difficile à utiliser seul et ses résultats ne sont pas très lisibles. Un outillage Lisp le rend plus ergonomique. On trouvera section 2 la présentation détaillée du noyau C, et section 3 celle de l’outillage auxilliaire. La conclusion discute des qualités et des défauts de la présente implémentation. Les indications nécessaires à la mise en œuvre de PIP sont données dans l’appendice.

2 Structure et utilisation du logiciel PIP

2.1 Présentation générale

Le logiciel PIP se présente comme un programme autonome écrit en C. Les données sont lues et les résultats sont écrits dans des fichiers de forme textuelle. Le programme PIP fonctionne aussi bien sous MS/DOS que sous Unix. Comme l’algorithme utilise des tableaux de taille variable (puisqu’il faut parfois ajouter une contrainte ou ajouter un paramètre), la mémoire doit être gérée dynamiquement. Pour des raisons de portabilité et d’efficacité, cette gestion n’utilise qu’un minimum de fonctions système (en fait les seules fonctions Unix malloc et free).

Le logiciel PIP est en général utilisé en conjonction avec d’autres logiciels écrits dans des langages différents (le plus souvent Le Lisp). Il est donc nécessaire de le lancer dynamiquement au moyen d’une instruction de type fork exec (lancement d’un nouveau processus) qui est comme on sait extrêmement coûteuse. Il y a intérêt à amortir cette opération sur le plus grand nombre possible de problèmes. PIP est donc prévu pour traiter plusieurs jeux de données qui se suivent dans le même fichier et pour accumuler de la même façon les résultats.

Le logiciel PIP peut manipuler aussi bien des entiers sur 16 que sur 32 bits. Son code source comporte un type Entier qui peut être défini aussi bien comme int que comme long int. Pour bien comprendre l’importance de ce facteur, il faut connaitre quelques détails du fonctionnement de PIP. La partie centrale de ce logiciel est un code d’échange de variables analogue à la phase centrale d’un algorithme de Gauss. Comme nous l’avons dit ci-dessus, les données de PIP sont des entiers, mais au cours des échanges, il peut être nécessaire de diviser par le pivot, ce qui fait en général apparaître des rationnels. De plus, lorsqu’une phase d’échange se termine, il est indispensable de pouvoir décider si la solution rationnelle est entière ou non; c’est dire que les calculs doivent être menés avec une précision infinie. L’utilisation d’un code général de calcul sur les rationnels aurait coûté trop cher en temps de calcul. Le logiciel PIP s’appuie sur la remarque suivante : tous les rationnels qui interviennent dans l’algorithme peuvent être pris comme ayant le même dénominateur, qui est le produit des pivots utilisés depuis le début de la phase d’échange. Cette technique a l’avantage de ne presque pas augmenter l’encombrement de la mémoire, et de simplifier dans une certaine mesure les calculs. L’opération élémentaire de la phase d’échange est alors la division d’un produit en croix :

(a.b − c.d)/D,

et on peut démontrer que la division doit toujours “tomber juste”. Il n’y a donc pas de possibilité d’erreur d’arrondi, et la seule difficulté peut provenir d’un dépassement de capacité. On a observé que si de tels dépassement se produisent lorsqu’on résoud de très gros problèmes (plusieurs dizaines de contraintes) à l’aide de versions à 16 bits, ils n’ont jamais été rencontrés dans l’utilisation des versions à 32 bits de PIP.

Dans cette version, nous n’avons pas utilisé les possibilités de surveillance des dépassements de capacité en entier des machines DOS ou Unix (utilisation de la primitive signal). Pour éviter de présenter des résultats erronés, le logiciel PIP vérifie systématiquement que la propriété de divisibilité indiquée ci-dessus est bien vérifiée (la probabilité qu’elle reste vraie après un dépassement non detecté est en effet infinitésimale). Si (a.b−c.d) mod D n’est pas nul, un message d’erreur est engendré et le programme se termine.

Le nombre de produits en croix calculés est une bonne mesure du travail effectué par PIP et donc de la complexité du problème soumis. Ces opérations sont comptées et le total est affiché quand un calcul se termine. Les valeurs usuelles sont de l’ordre de la dizaine pour les petits problèmes. Les plus gros problèmes jamais résolus par PIP ont conduit à quelques centaines de milliers de produits en croix.

2.2 Spécification du fichier des données

Elle est donnée par la grammaire hors-contexte suivante ^{4}:

Grammaire 2 :

Fichier  ::= Probleme ...
Probleme ::= ( Commentaire Nn Np Nl Nm Bg Nq Tableau Contexte )
Commentaire ::= Liste
Liste    ::= Atome | ( Liste ... )
Tableau  ::= ( Vecteur ... )
Contexte ::= ( Vecteur ... )
Vecteur  ::= #[ Entier ... ]
Nn ::= Entier
Np ::= Entier
Nl ::= Entier
Nm ::= Entier
Bg ::= Entier
Nq ::= 0 | 1

4Nous introduisons la notation classique ... pour indiquer la répétition arbitraire d’un élément grammatical. La notation X ... peut être remplacée par un nouveau non-terminal Xlist et par la règle:

Xlist ::= X | X Xlist

Nous avons également introduit le nouveau non-terminal Atome qui représente les atomes du système Lisp utilisé. PIP ne fait aucun contrôle de syntaxe pour les Atomes.

Pour bien comprendre la structure ainsi définie, il faut se souvenir qu’elle a été conçue pour pouvoir être facilement engendrée depuis un code Lisp. En particulier, chaque problème est une liste équilibrée du point de vue des parenthèses et des crochets.

Un commentaire est une liste arbitraire. Le commentaire de chaque problème est, comme nous le verrons plus loin, reproduit en tête de chaque solution. Cette information peut être utilisée par le logiciel qui exploite PIP pour “s’y retrouver” lorsque les résultats ont tous été obtenus.

On notera que deux problèmes successifs peuvent être séparés par un texte arbitraire à condition que celui-ci ne contienne pas de parenthèses. Ce texte est entièrement ignoré par PIP.

Les données qui suivent servent à fixer les dimensions du problème. Nn donne le nombre de variables (c’est le nombre n du premier paragraphe). De même, Np est le nombre de paramètres (p), et Nl est le nombre de contraintes à satisfaire (l). Nm donne le nombre de contraintes du contexte (m).

Le paramètre Bg joue un rôle spécial qui ne deviendra clair qu’au paragraphe suivant. Il donne le numéro d’ordre d’un paramètre que l’on peut supposer “infiniment grand” (i.e., si ce paramètre a un coefficient positif dans une forme ϕ, on peut immédiatement en déduire ϕ > 0, etc.). Si Bg < 0, il n’y a pas de paramètre infiniment grand dans le problème. Attention, le numéro d’ordre du grand paramètre s’entend comme l’indice de sa colonne du Tableau, la première colonne (qui correspond à la première variable) portant l’indice 0.

Le dernier entier, Nq, se comporte comme un booléen. Si sa valeur est true (donc non nulle en C), la résolution se poursuit jusqu’à obtention d’une solution entière. Si Nq est false (nul), la première solution rationnelle trouvée est acceptée.

Le Tableau est la spécification des contraintes à satisfaire. Chaque Vecteur représente une inégalité. On trouve dans l’ordre les coefficients des inconnues (c’est-à-dire une ligne de la matrice A), le coefficient constant (une composante du vecteur c⃗) et les coefficients des paramètres (une ligne de la matrice B). La notation est strictement positionelle : c’est la responsabilité de l’utilisateur que de veiller à ce que l’ordre des inconnues et des paramètres soit toujours le même de ligne en ligne et de marquer par des zéros les termes absents. Le nombre de vecteurs est l et chaque vecteur a exactement n + 1 + p éléments.

De la même façon, Contexte est une liste de Vecteurs, chacun contenant une ligne de la matrice M suivie de la composante correspondante du vecteur h⃗. Il y a donc m Vecteurs, chacun ayant p + 1 éléments.

2.2.1 Exemple

L’exemple qui suit est tiré de [Fea88b]. On considère le nid de boucles

for i:= 0 to m do
   for j := 0 to n do              {II}

      for k := 0 to i+j do ...

que l’on souhaite réécrire dans l’ordre k, j, i. La borne inférieure de la boucle sur j se déduit de la résolution du problème suivant:

D_{2}(k) = { <j, i> |i ≤ m, j ≤ n, k ≤ i + j}.

On remarquera au passage que les bornes inférieures nulles ont disparu de l’énoncé. Les inconnues d’un problème paramétrique en entiers sont en effet implicitement non négatives.

Le problème est à résoudre dans le contexte k ≤ m + n, lequel résulte de l’étude préalable de la boucle sur k. A ces spécifications correspond le fichier de données suivant:

( (Borne inferieure apres inversion de boucle
     (variables j i)
     (parametres k m n))
  2 3 3 1 -1 1
  ( #[0 -1 0 0 1 0]
    #[-1 0 0 0 0 1]
    #[1 1 0 -1 0 0]
   )
  ( #[-1 1 1 0])
)

2.3 Mode d’emploi

La commande de lancement de PIP s’écrit:

     pip [-s|-v] [entree [sortie]]

Normalement, PIP émet un message informatif à la fin de chaque problème. La présence de l’option -s inhibe cette émission. L’option -v, au contraire, provoque la recopie, dans un fichier disque, de toutes les données reçues et de tous les résultats engendrés par PIP. Le nom du fichier récepteur est la valeur affectée à la variable d’environnement DEBUG, ou, à défaut, un nom engendré

par mktemp.

entree et sortie sont les noms des fichiers contenant respectivement les spécifications des problèmes à résoudre et les solutions. Si la sortie est omise, les résultats sont émis sur la sortie standard. Si l’entrée est omise, les données sont lues sur l’entrée standard. Outre les résultats, PIP émet des messages informatifs et des messages d’erreur sur sa sortie standard (ces messages ne sont donc pas affectés par la spécification d’un fichier de sortie).

2.3.1 Messages informatifs • Version C.x. Actuellement, x = 3.

• cross : <n>, alloc : <m> Ce message est émis à la fin de la résolution de chaque problème. Il donne le nombre de “produits en croix” effectués (n), et le nombre d’appels à l’allocateur de mémoire (m). Ce message n’est émis que si l’option -s ne figure pas dans la ligne d’appel de PIP.

2.3.2 Messages d’erreur

• grosse solution!!! : sol La taille de la solution dépasse celle de la zone réservée pour son enregistrement. Contrôler les données et, si cela est justifié, recompiler le programme en modifiant la valeur de la constante

  SOL SIZE dans le fichier type.h

• salades de saison .... : sol Erreur dans le logiciel : la gestion dynamique de la zone des solutions est devenue incohérente. Notifier les auteurs.

• xxx/Catastrophe en li xx co xx : trt

Probable dépassement de capacité dans un calcul en entier.

• xxx/Explosion ! : trt
• pgcd negatif ! ddd : trt
• tab reset : cafouillage
• tab reset : panique
• tab init : la machine est trop petite

Erreur dans le logiciel. Notifier les auteurs.

• tab alloc : plus de place Les données du problème dépassent la taille de la mémoire.

2.4 Présentation des résultats

Le fichier des résultats peut être défini par la grammaire suivante: Grammaire 3 :

Fichier ::= Resultat ...
Resultat :: ( Commentaire Solution )
Solution ::= Quast_group
 | void

Quast_group ::= Quast
    | (newparm Entier Vecteur Entier) ... Quast
Quast ::= Forme
    | (if Vecteur Quast_group Quast_group)
Forme ::= (list Vecteur ...)
    | nil
Vecteur ::= #[ Coefficient ... ]
Coefficient ::= Entier | Entier / Entier

Pour chaque problème posé on retrouve le commentaire tel quel suivi de la solution. Celle-ci peut être le mot-clé void, ce qui indique que le contexte du problème original est vide. Sinon, c’est la représentation lispienne d’un quast, éventuellement précédé de la définition d’un ou plusieurs nouveaux paramètres.

Les coefficients d’un vecteur peuvent être soit des entiers, soit des rationnels représentés sous la forme num/denom. Cette dernière situation ne peut se présenter que si le calcul a été effectué avec la donnée Nq = 0.

Dans une solution, un vecteur est la représentation d’une forme affine; chaque composante du vecteur est le coefficient du paramètre de même rang. La dernière composante est le terme constant. Dans ce qui suit nous parlerons de la “valeur du vecteur” pour désigner la valeur de cette forme.

La définition d’un nouveau paramètre comporte le mot-clé newparm, un numéro d’ordre, un vecteur de coefficients et un dénominateur. Le nouveau paramètre est égal au quotient entier de la valeur du vecteur par le dénominateur. Le fait de créer un nouveau paramètre rallonge d’une position le vecteur des paramètres. Le nouveau paramètre ne peut être utilisé (n’est visible) que dans le Quast qui suit son introduction. Il résulte de cette disposition que la longueur des vecteurs qui se rencontrent dans une solution n’est pas fixe. Elle n’est cependant pas arbitraire et doit être égale à 1 plus le nombre de paramètres originaux plus le nombre de paramètres nouveaux dont la définition est localement visible.

La suite de la solution est une expression conditionnelle multiniveau. Si elle comporte un if, le booléen testé est le résultat de la comparaison à zéro de la valeur du vecteur figurant après le if.

La solution se termine soit par le mot-clé nil, si on est dans une situation où le problème n’a pas de solution, soit par une Forme. Une forme est une liste de vecteurs. Chaque vecteur correspond à une inconnue et en donne la valeur.

2.4.1 Exemple

Voici le fichier résultant de la résolution du problème (2.2.1).

( (Borne inferieure apres inversion de boucle
     (variables j i)
     (parametres k m n))
  (if #[ -1 1 0 0]
      (list #[ 0 0 0 0]

            #[ 1 0 0 0]
      )
      (list #[ 1 -1 0 0]
            #[ 0 1 0 0]
      )
   )
)

Il n’y a pas d’introduction de nouveaux paramètres. La forme associée au prédicat du premier if est :

−1 × k + 1 × n + 0 × n + 0 × 1 = m − k

et le test porte en conséquence sur m − k ≥ 0. La solution correspondante est < 0, k >. Sinon, la solution est < m − k, m >.

Au total, et en reprenant les notations du paragraphe (1), le minimum lexicographique de D_{2} est:

    if m-k >= 0 then <0, k> else <m-k, m>.

Quand à la borne inférieure cherchée, qui seule nous importe, c’est:

    if m-k then 0 else m-k

Pour information, voici une copie de la sortie standard de PIP lorsque l’on omet de stipuler un fichier de sortie.

Version C.2
( (Borne inferieure apres inversion de boucle
     (variables j i)
     (parametres k m n))(if #[ -1 1 0 0]
(list #[ 0 0 0 0]
#[ 1 0 0 0]
)
(list #[ 1 -1 0 0]
#[ 0 1 0 0]
)
)
)
cross : 54, alloc : 2

On notera que les résultats étant essentiellement destinés à d’autres logiciels, les efforts de mise en page ont été réduits au minimum.

3 Outils d’aide à l’utilisation de PIP

Comme on a pu s’en rendre compte, l’utilisation directe de PIP n’est pas très ergonomique, que l’utilisateur soit humain ou soit un autre logiciel. Cette section présente un ensemble de fonction écrites en Lisp qui facilitent l’emploi de PIP en fournissant deux types de facilités:

• une notation plus proche de l’usage mathématique pour représenter les contraintes d’un problème;

• des extensions de l’algorithme de base pour traiter le problème du maximum lexicographique et les contraintes par équations.

Avertissement : la lecture de cette section nécessite une bonne connaissance du langage Lisp et de préférence de la version Le Lisp ([INR87]).

3.1 Un outil de manipulation de polynômes

L’outil que nous présentons ici a été développé pour un usage plus étendu que celui qui est nécessaire pour PIP(voir [TF89]). Il permet de manipuler des polynômes de degré arbitraire à plusieurs inconnues, et donc en particulier les formes linéaires qui représentent les contraintes de PIP. L’outil se présente comme un fichier Lisp poly.ll contenant un certain nombre de fonctions qui seront présentées plus loin.

3.1.1 Représentation des polynomes

La syntaxe d’un polynome est la suivante ^{5}:

Grammaire 4 :

Monome ::= ( Base . Exposant )
Base ::= Symbole | 1 | (Symbole Polynome ... )
Exposant ::= Entier
Facteur ::= ( Monome ... )
Terme ::= ( Facteur . Coefficient)
Coefficient ::= Entier | Entier/Entier
Polynome ::= ( Terme ... )

Le non-terminal Symbole représente les symboles autorisés par le système Lisp utilisé. Tous les calculs arithmétiques sont faits à l’aide du sous-système ratio (voir [INR87] Chapitre 10). Les énumérations qui figurent dans la définition du non-terminal Polynome représentent une addition; c’est au contraire une multiplication dans le cas de Facteur.

5Le lecteur devra interpréter ci-dessous et dans toute cette section les écritures comme des images de listes Lisp. Par exemple, la notation ( X . Y ) indique qu’il faut prendre une instance de chacun des non-terminaux X et Y et leur appliquer l’opération Lisp CONS. Il n’y aura ni parenthèse ni point dans le résultat obtenu.

La définition ci-dessus ne donne rééllement un polynôme que si les bases sont limitées aux symboles et au nombre 1. Le troisième cas ((Symbole Polynome ...)), permet d’introduire des fonctions arbitraires. Nous en verrons l’utilisation plus loin.

Comme chacun sait, il y a de nombreuses façons de représenter le même polynôme, et beaucoup d’entre elles seront conforme à la grammaire ci-dessus. Pour simplifier la programmation, on impose un certain nombre de règles supplémentaires qui définissent les polynomes normalisés. A une exception près, le bon fonctionnement des fonctions de poly.ll n’est garanti que si les polynômes donnés en argument sont normalisés; les polynomes rendus en résultats sont alors normalisés.

Les termes dont le coefficient est nul ne doivent pas être conservés.

La base d’un monome peut être un symbole (c’est-à-dire une variable) ou l’entier 1; dans ce dernier cas, l’exposant doit être également 1, et le facteur qui contient un tel monome ne doit contenir que lui. On représente ainsi le terme constant d’un polynome.

Un nombre peut être considéré comme un polynome. La représentation normalisée du rationnel 7/2 s’écrit:

                 ( ( (( 1 . 1)) . 7/2 ) )

Puisque les termes dont le coefficient est nul ne doivent pas être représentés, il en résulte que la représentation du 0 est la liste vide : nil. Les programmes qui doivent éventuellement signaler un erreur doivent utiliser une autre valeur (par exemple l’atome t tout seul, qui ne peut en aucun cas être un polynome).

Dans un facteur, la même base ne peut apparaitre qu’une seule fois, et il ne peut y avoir simultanément une base numérique et des bases symboliques. Si les bases sont symboliques, elles doivent apparaitre dans l’ordre alphabétique.

Dans un polynome, les différents termes doivent avoir des facteurs distincts. Les facteurs doivent se suivre dans l’ordre alphabétique étendu (a^{2} précède b^{3}, mais a^{3} précède a^{2}).

Le célèbre polynome ax^{2} + bx + c se représente comme:

             ( ( ( (a . 1)(x . 2) ) . 1)
               ( ( (b . 1)(x . 1) ) . 1)
               ( ( (c . 1) ) . 1)
             )

3.1.2 Opérations sur les polynomes Opérations algébriques :

• (#:p:addpoly p1 p2) La somme des polynomes p1 et p2.

• (#:p:diffpoly p1 p2) La différence des polynomes p1 et p2.

• (#:p:moins p) L’opposé du polynome p.

• (#:p:multpoly p1 p2) Le produit des polynomes p1 et p2.

• (#:p:puispoly p n) Le polynome p élevé à la puissance entière n. Autres opérations :

• (#:p:factor p x) Cette fonction factorise le polynome p suivant la variable x. La syntaxe du résultat est: Grammaire 5 :

Polynome_factorise ::= ( Morceau ... )
Morceau ::= ( ( X . Entier) Polynome)

Dans cette grammaire, X désigne le symbole de la variable clé de la factorisation. Le Polynome est conforme à la syntaxe de la grammaire 4, mais ne contient aucune occurence de x.

• (#:p:exp p) Remet un polynôme factorisé conforme à la grammaire 5 sous forme normale.

• (#:p:subsp p x q) Substitue le polynôme q à la variable x dans le polynôme p et met le résultat sous forme normale.

• (#:p:redpoly p) Cette fonction met le polynôme p sous forme normale. Son utilisation doit être exceptionelle.

• (#:p:translate p) Imprime le polynôme p sous une forme agréable à lire.

• (#:p:polytolisp p) reconstitue une expression Lisp à partir du polynôme

p.

• (#:p:cap exp) forme le polynôme équivalent à l’expression exp en supposant que celle-ci est un nombre ou une variable ou un appel de fonction.

3.1.3 Exemple

La fonction que nous présentons ci-dessous lit une expression et construit, si possible, le polynôme associé sous forme normale. La syntaxe Lispienne des expressions est :

Grammaire 6 :

Primaire ::= Symbole | Entier
    | Entier/Entier
    | (Symbole Expression ... )
Expression ::= Primaire
    | (** Expression Entier)
    | (* Expression Expression)
    | (+ Expression Expression)
    | (- Expression)
    | (- Expression Expression)

La méthode suivie est une descente récursive dans l’expression Lisp suivant la grammaire ci-dessus. Après l’évaluation des descendants de chaque noeud, la valeur du noeud est obtenue par application de la fonction qui correspond à l’opérateur du noeud. Si la fonction est inconnue (quatrième cas de la définition d’un Primaire), on recopie simplement la fonction suivie de la conversion de ses arguments.

(defun convert (exp)
  (cond ((numberp exp)   (#:p:cap exp))
     ((variablep exp) (#:p:cap exp))
     ((consp exp)
        (let ( (n (length exp))
               (arglist (mapcar 'convert (cdr exp)))
                )
          (selectq n
            (1 (#:p:cap exp)) ;fonction sans arguments
            (2 (if (eq (car exp) '-)
                   (#:p:moins (car arglist))
                   (#:p:cap (cons (car exp) arglist))
                    ))
            (3 (selectq (car exp)
                 (+ (#:p:addpoly (car arglist)(cadr arglist)))
                 (- (#:p:diffpoly (car arglist)(cadr arglist)))
                 (* (#:p:multpoly (car arglist)(cadr arglist)))
                 (** (if (numberp (cadr exp))

                         (#:p:puispoly (car arglist) (cadr exp))
                         (#:p:cap (cons '** arglist))))
                 (t (#:p:cap (cons (car exp) arglist)))
                  ))
            (t (#:p:cap (cons (car exp) arglist)))
             ))
        ))
   )

3.2 Extensions de l’usage de PIP

De nombreux problèmes peuvent être résolus par PIP après avoir subi des transformations plus ou moins complexes. Deux d’entre eux sont suffisamment fréquents pour qu’un logiciel d’adaptation spécial soit intéressant. Le premier concerne le cas où certaines contraintes sont des équations. Le second est la recherche non plus d’un minimum mais d’un maximum lexicographique.

D’autres extensions du même genre (par exemple, le cas de la minimisation d’une fonction économique linéaire), sont laissées à la sagacité de l’utilisateur.

3.2.1 Environnement général

Les fonctions Lisp proposées ci-dessous font partie d’un environnement général d’utilisation de PIP contenu dans l’un des fichiers upip.ll ou dospip.ll. Cet environnement peut être utilisé de façon compatible sous Unix ou MS/DOS, à condition de respecter strictement le mode d’emploi ci-dessous (en particulier, ne pas omettre l’appel d’une fonction sous le fallacieux prétexte qu’elle ne fait rien). Le principe est le suivant:

• Sous Unix, au chargement de upip.ll, quelques fonctions d’interface écrites en C sont incorporées à l’interprète. Ces fonctions font partie du fichier oracle.c. Sous DOS, il ne se passe rien.

• Sous Unix, la fonction (pip start), sans argument, crée un processus fils qui exécute PIP. Ce programme est relié à l’interprète Lisp par deux tubes; il se met en attente de lecture sur le tube d’entrée. La valeur retournée par pip start, appelée dans ce qui suit le lien, doit être soigneusement enregistrée. Elle permet de retrouver les deux tubes utilisés pour la liaison avec PIP. Il est ainsi possible d’engendrer plusieurs instances de PIP, ce qui n’a d’ailleurs d’intérêt que sur un multiprocesseur. PIP est appelé avec l’option -s (silencieux), sauf si la variable d’environnement DEBUG est positionneée.

Sous MS/DOS, pip start n’a aucun effet.

• Sous MS/DOS, la fonction (pip open), sans argument, crée dans le répertoire courant un fichier temporaire vide appelé probleme. Sous Unix, pip open

vide le tampon d’entrée.

• Les fonctions d’énoncé de problèmes lex min et lex max, qui vont être décrites plus loin, accumulent dans le fichier probleme ou dans le tube d’entrée des jeux de données conformes à la grammaire 2.

• Il est également possible de construire soi-même les éléments d’un problème, et de les soumettre à PIP au moyen de la fonction

    (pip_problem lien comm nq tableau context
                    parmlist nvar bigparm)

– lien est la valeur retournée par pip start;

– comm est le commentaire;

– nq est le booléen à la C qui controle le caractère rationnel ou entier de la solution;

– tableau est la liste des vecteurs lignes de la matrice des inéquations à résoudre. L’ordre des termes est le même que celui qui a été spécifié en 2.2 pour le fichier des données de PIP.

– context est la liste des vecteurs lignes du contexte;

– parmlist est la liste des paramètres;

– nvar est un entier donnant le nombre des variables;

– bigparm indique la présence et donne le rang (s’il est positif), d’un paramètre “infiniment grand” qui est utile pour résoudre des problèmes de maximum (voir plus loin 3.2.3).

• Sous MS/DOS, un appel à la fonction (pip solve) sans argument, provoque l’exécution de PIP via la commande Lisp COMLINE. Sous Unix, pip solve n’a aucun effet. Le processus PIP étant actif en permanence, il a commencé à résoudre les problèmes soumis dès leur apparition dans le tube d’entrée. Les solutions sont rangées, dans le bon ordre, dans le fichier resultat du répertoire courant ou dans le tube de sortie. Le fichier exécutable de PIP est recherché dans le répertoire dont le nom est la valeur de la variable d’environnement PIP, qui doit avoir été positionnée convenablement (en général de l’extérieur du programme).

Sous MS/DOS, on écrira par exemple:

                 set PIP=\pip\

Par contre, en cas d’utilisation du Shell de Bourne sous Unix, on écrira:

                 PIP=Pip/ ; export PIP

Le choix entre la version 16 bits et la version 32 bits est “cablé” dans le texte de upip.ll ou dospip.ll. Pour agir sur lui, on modifiera l’instruction qui calcule le chemin d’accés à l’exécutable.

• La fonction (pip solution lien), retourne à chaque appel la solution d’un problème, et ceci jusqu’à épuisement du fichier resultat ou du tube de sortie.

• Sous MS/DOS, un appel à la fonction (pip close), sans argument, ferme tous les fichiers et permet de recommencer un nouveau cycle. Sous Unix, pip close n’a aucun effet.

• Sous Unix, un appel à la fonction (pip stop lien) ferme les tubes de communication, ce qui a pour effet de faire apparatre une fin de fichier à l’entrée de PIP, et provoque en conséquence sa terminaison. Sous MS/DOS, pip stop n’a aucun effet.

La grammaire des solutions est une version de la grammaire 4 étendue pour traiter les conditionelles et les divisions euclidiennes.

Grammaire 7 :

Monome ::= ( Base . Exposant )
Base ::= Symbole | 1 | (div Polynome Entier)
Exposant ::= Entier
Facteur ::= ( Monome ... )
Terme ::= ( Facteur . Coefficient)
Coefficient ::= Entier | Entier/Entier
Polynome ::= ( Terme ... )
Solution ::= nil | (list Polynome ...)
Quast ::= Solution
    | (if (plusp Polynome) Solution Solution)
Resultat ::= (Commentaire . Quast)

Naturellement, tous les polynômes qui apparaissent dans une solution sont des formes linéaires. Il doit être assez clair que pour fonctionner, pip solution a besoin de connaître la liste et l’ordre d’apparition des paramètres du problème. Ceci est fait grâce au commentaire. Le commentaire vu par PIP est en fait un composite.

        (parmlist "min" comm)

Ce n’est bien évidemment que la partie comm qui est retournée à l’utilisateur

par pip solution.

3.2.2 Equations

Nous étendons maintenant la definition (5) pour y inclure des contraintes équationelles:

F(z⃗) = {x⃗|x⃗ ≥ 0, Ax⃗ + Bz⃗ + c⃗ ≥ 0, Dx⃗ + Ez⃗ + f⃗ = 0}.  (6)

Soit r × n la dimension de D, et r × p celle de E. Nous introduisons les r inégalités:

Dx⃗ + Ez⃗ + f⃗ ≥ 0,  (7)

ainsi que l’inégalité supplémentaire ^{6}:

∑_{i=1}^{r} D_{i•}x⃗ + E_{i•}z⃗ + f⃗_{i} ≤ 0.  (8)

Il est clair que dire que r nombres sont non-négatifs, et que leur somme est non-positive est équivalent à dire que ces nombres sont nuls. Nous avons donc bien ramené le problème à l inégalités et r égalités à un problème à l + r + 1 inégalités.

Pour soumettre à PIP un problème contenant des égalités et des inégalités, on utilisera la fonction lex min, qui doit évidemment apparaître entre un pip open

et un pip solve.

La séquence d’appel de lex min est la suivante:

(lex_min lien comm equa ineqs context varlist parmlist nq)

où les arguments ont le sens suivant:

• lien est l’argument qui permet de retrouver les tubes d’accès à PIP.

• comm est le commentaire;

• equa est une liste de Polynomes représentant les équations;

• ineqs est la liste des inéquations;

• context est la liste des inéquations représentant le contexte;

• varlist est la liste des variables;

• parmlist est la liste des paramètres;

• nq est un entier jouant le même rôle que l’entier Nq de la grammaire 2 (contrôle de la résolution en entier ou en rationnel).

6X étant une matrice, nous noterons X_{i•} le i-ème vecteur ligne de X et X_{•j} son j-ième vecteur colonne

Il est important de comprendre qu’au retour de lex min, le problème posé n’est pas résolu, mais seulement enregistré. La solution ne sera disponible qu’au retour de la fonction pip solve. lex min vérifie la cohérence de ses arguments : les Polynomes qui figurent dans les équations, les inéquations et le contexte doivent être des formes linéaires n’utilisant pas d’autres symboles que les variables et les paramètres. En cas d’anomalie, l’un des messages:

Equation non lineaire ou variable omise ....
Inequation non lineaire ou variable omise ....
Contexte non lineaire ou variable omise ....

est émis et le problème n’est pas enregistré.

3.2.3 Le maximum lexicographique

Les cas où on cherche un maximum lexicographique plutôt qu’un minimum sont très fréquents en analyse sémantique. L’exemple initial fait d’ailleurs partie de cette catégorie. Le problème posé par la recherche d’un maximum est que celui-ci n’existe pas nécessairement, le polyèdre F pouvant parfaitement être non borné. On peut naturellement chercher dans chaque cas un changement de variable ad hoc, mais nous avons préféré développer une procédure systématique.

Reprenons le polyèdre F(z⃗) de l’équation (5) et supposons qu’il s’agisse maintenant d’en déterminer le maximum lexicographique. Nous introduisons un nouveau paramètre P et nous considérons l’intersection de F(z⃗) avec le cube : C(P) = {x⃗|x⃗ ≤ P1}, que nous noterons F(z⃗, P) ^{7}. Pour trouver son maximum, qui existe toujours, nous passons par le changement de variables:

x′ = P1 − x⃗,

ce qui nous conduit à calculer le minimum lexical de

F′(z⃗, P) = {x′|0 ≤ x′ ≤ P1, A1 − Ax′ + Bz⃗ + c⃗ ≥ 0}.  (9)

duquel on déduit trivialement le maximum de F(z⃗, P). Si F(z⃗) est borné, pour une valeur assez grande de P, F(z⃗) est entièrement contenu dans C(P), et la position du maximum ne dépend plus de P. Si par contre F(z⃗) est non borné, l’une des coordonnées du maximum sera toujours de l’ordre de P et on ne trouvera pas de solution.

On voit au total que le problème se résoud en trouvant le minimum lexical de F′(z⃗, P) et en analysant la dépendance en P du résultat. Ce travail peut être fait à l’aide du logiciel PIP, mais au prix d’une certaine perte de temps : les information obtenues pour les petites valeurs de P sont sans intérêt. C’est pour cela que le paramètre Bg a été introduit. L’essentiel du travail de PIP est de prendre des décisions relativement au signe de formes linéaires f(z⃗) . Usuellement, ceci se fait en testant la compatibilité avec le contexte des contraintes f(z⃗) ≥ 0 et f(z⃗) < 0, ce qui est une opération relativement coûteuse, qui implique un appel récursif à PIP. Dans le cas où il existe un paramètre tel que P destiné à devenir “infiniment grand”, on peut commencer par tester le signe de son coefficient : s’il est positif, la forme est positive, s’il est négatif la forme est négative, et ce n’est que s’il est nul qu’il faut faire un test de compatibilité.

71 est le vecteur dont toutes les composantes sont égales à 1.

Cette simplification des déterminations de signe est la seule modification apportée à PIP pour gérer le cas du maximum lexicographique. Tout le reste est pris en charge par la fonction Lisp lex max et par pip solution.

La séquence d’appel de lex max est la suivante:

(lex_max lien comm equa ineqs context varlist parmlist nq)

où les arguments ont exactement le même sens que pour lex min. C’est lex max qui se charge de générer le nouveau paramètre P, d’écrire les contraintes additionelles, et de faire le bon changement de variables dans les contraintes originales avant d’invoquer PIP. De même, pip solution se charge du travail inverse (l’ordre lui en est communiqué à travers le commentaire de PIP); la seule différence visible pour l’utilisateur est qu’il y a maintenant une autre réponse possible: le polyèdre original est non borné et n’a pas de maximum lexicographique, ce qui est indiqué en retournant la solution t.

Attention, dans un souci d’efficacité, PIP traite incorrectement certains cas subtils. Il existe des polyèdres non bornés qui ne contiennent aucun point entier, comme par exemple:

V = { <i, j > |28i − 4j ≥ 1, 28j − 4i ≤ 2}.

Dans un tel cas, PIP indique que V est non borné, alors qu’il faudrait répondre qu’il est vide.

lex max retourne éventuellement les mêmes messages d’erreur que lex min.

3.2.4 Exemple

Nous avons tout simplement repris l’exemple initial (4). Pour donner une idée de l’utilité des outils de manipulation de polynômes, nous avons supposé que le point de départ de notre travail était une analyse syntaxique du programme {I}. Les données sont une liste des bornes supérieures des boucles, en notation lispienne (la variable Bounds), une liste des compte-tours, (la variable Counters), la liste des indices du tableau étudié, (la variable Indices), et quelques informations auxilliaires. Le programme ci-dessous forme les équations et les inéquations en conséquence, lance le processus de résolution et imprime le résultat final dans un fichier.

Nous donnons successivement le programme principal:

(if #:system:unixp (dmc |\| () "/")(dmc |\| () "\"))
(print (loadfile (catenate (getenv "PIP") "llub" \ "poly.ll") t))
(print (loadfile (catenate (getenv "PIP") "llub" \
                           (if #:system:unixp "upip.ll"
                                                "dospip.ll")) t))
(print (loadfile (catenate (getenv "PIP") "llub" \ "bmax.ll") t))
(print (loadfile (catenate (getenv "PIP") "llub" \ "bmin.ll") t))
(print (load "convert.ll"))
(setq #:system:read-case-flag t)
(defvar Bounds '(m n))
(defvar Counters '(i j))
(defvar Indices '((+ (* i 2) j)))
(defvar Varlist '(i j))
(defvar Parmlist '(m n))
(defvar Philist '(k))
(defun makebound (x y)
       (#:p:diffpoly (convert x)(convert y)))
(defvar Domain (mapcar 'makebound Bounds Counters))
(defvar Index-equations (mapcar 'makebound Indices Philist))
(setq Parmlist (append Parmlist Philist))
(defun run ()
  (let ( (LIEN (pip_start))
         (S nil)
          )
       (pip_open)
       (lex_max LIEN '(Exemple 1) Index-equations Domain ()
                Varlist Parmlist 1)
       (pip_solve)
       (setq S (pip_solution LIEN))
       (pip_close)
       (pip_stop LIEN)
       (pprint (car S))
       (pprint (cdr S))
       )
    )

le fichier de données engendré par lex max:

(
((m n k g101) max (Exemple 1))
2 4 6 0 6 1
(
#[-2 -1 0 0 0 -1 3]
#[2 1 0 0 0 1 -3]
#[1 0 0 1 0 0 -1]
#[0 1 0 0 1 0 -1]
#[0 -1 0 0 0 0 1]
#[-1 0 0 0 0 0 1]
)
(
)
)

le fichier de résultats engendré par PIP:

(
((m n k g101) max (Exemple 1))(if #[ 2 1 -1 0 0]
(if #[ -2 0 1 0 0]
(list #[ -1 0 0 1 0]
#[ 2 0 -1 1 0]
)
(newparm 4 (div #[ 0 0 1 0 0]
 2)
)
(if #[ 0 1 -1 0 2 0]
(list #[ 0 0 0 1 -1 0]
#[ 0 0 -1 1 2 0]
)
()
)
)
()
)
)

et enfin la présentation qu’en donne pip solution:

(Exemple 1)
(if (plusp ((((k . 1)) . -1) (((m . 1)) . 2) (((n . 1)) . 1)))
  (if (plusp ((((k . 1)) . 1) (((m . 1)) . -2)))
      (list ((((m . 1)) . 1)) ((((k . 1)) . 1) (((m . 1)) . -2)))
      (if (plusp ((((k . 1)) . -1) (((n . 1)) . 1)

                  ((((div ((((k . 1)) . 1)) 2) . 1)) . 2)))
          (list (((((div ((((k . 1)) . 1)) 2) . 1)) . 1))
                ((((k . 1)) . 1)
                ((((div ((((k . 1)) . 1)) 2) . 1)) . -2)))
            ()))
    ())

A titre d’information, nous donnons ici la solution obtenue si l’on demande une résolution en rationnels ( Nq = 0).

(Exemple 1)
(if (plusp ((((k . 1)) . -1) (((m . 1)) . 2) (((n . 1)) . 1)))
  (if (plusp ((((k . 1)) . 1) (((m . 1)) . -2)))
     (list ((((m . 1)) . 1)) ((((k . 1)) . 1) (((m . 1)) . -2)))
     (list ((((k . 1)) . 1/2)) ()))
    ())

La forme ci-dessus est évidemment parfaite pour un post-traitement informatique, mais elle n’est pas très lisible. Voici d’abord une présentation plus ergonomique de la solution rationnelle:

<i,j> = if m*2 + n - k >= 0
        then if k - m*2 >= 0
             then <m,k-m*2>
             else <k/2,0>
        else <>

A l’évidence, la deuxième Solution de cette formule n’est pas entière. Il est donc nécessaire de poursuivre la résolution en introduisant des coupures. Voici le résultat final.

<i,j> = if m*2 + n - k >= 0
        then if k - m*2 >= 0
             then <m,k-m*2>
             else if n - k + (k/2)*2 >= 0
                  then <k/2, k - (k/2)*2>
                  else <>
        else <>

On observera que l’algorithme PIP a detecté un cas subtil de non-définition de A[k] : celui où n est nul et où k est impair.

4 Conclusion

Nous pensons que la version C du logiciel PIP a maintenant atteint un état quasidéfinitif. Seules des tentatives de résolution de très gros problèmes pourraient éventuellement mettre en évidence des défauts dans la gestion de la mémoire ou dans la détection des dépassements de capacité.

Naturellement, l’interface Lisp est beaucoup plus évolutif, ne serait-ce que parce que bien d’autres extensions de l’utilisation de PIP sont envisageables:

• Présence de variables non positives;

• Présence d’une fonction économique linéaire;

etc.

5 Installation de PIP

5.1 Description de la fourniture

Le logiciel PIP peut être obtenu sur simple demande auprès des auteurs. Son utilisation à des fins de recherche est libre, à condition que, en cas de publication, les auteurs originaux soient cités dans les formes habituelles. Toute utilisation commerciale est proscrite. PIP est livré sur une disquette au format MS/DOS de 360k octets, laquelle supporte l’arborescence suivante:

\---PIP---CPROG
       |--DPROG
       |--LLUB
       |--EXEMPLE

Le répertoire PIP contient uniquement le fichier source LaTEXdu présent rapport, pip.tex, dans sa version la plus récente, ainsi que le fichier artfr.sty nécessaire à son édition.

Le répertoire PIP/CPROG contient les fichiers source de PIP ainsi que deux fichiers unix.mk et dos.mk utilisés pour la construction d’un exécutable. De même, PIP/DPROG contient le seul fichier source type.h et les fichiers unix.mk et dos.mk qui permettent de construire une version 32 bits de PIP sur une machine 16 bits.

Le répertoire PIP/LLUB contient les trois fichiers poly.ll, upip.ll et dospip.ll, ainsi que le fichier d’interface oracle.c.

Le répertoire PIP/EXEMPLE contient des fichiers de problèmes permettant de vérifier le bon fonctionnement de PIP et de ses auxiliaires.

5.2 PIP

Pour construire PIP, la première chose à faire est de décider du type de programme dont vous avez besoin. Si votre ordinateur est tel qu’un int occupe 32 bits, ou bien si un int occupe 16 bits et que cela vous suffit, utilisez CPROG. Dans le cas où un int occupe 16 bits et où cela ne suffit pas, utilisez DPROG. Quelle que soit la situation, utilisez unix.mk ou dos.mk suivant le type de système que vous utilisez.

La syntaxe du fichier unix.mk est standard et donc doit pouvoir être utilisée sur n’importe quel Unix. Par contre, le fichier dos.mk est adapté au compilateur C et au make de Borland. Il peut être nécessaire de le modifier si vous utilisez un autre environnement C.

Le choix du répertoire étant réglé, sous Unix, lancez la compilation par:

       make -f unix.mk pip

Sous DOS, la commande est

       make -fdos.mk pip.exe

5.3 poly.ll, upip.ll et dospip.ll

La mise en œuvre de ces trois fichiers est très simple : il suffit de les ranger quelque part, puis de les charger à l’aide d’un appel à la fonction LOAD ou à LIBLOAD. Le chargement de upip.ll entraîne la compilation et l’édition de lien de oracle.c. Cette opération peut faire apparaître des messages d’avertissement dont on espère qu’ils seront sans conséquence.

La pratique habituelle est de n’effectuer l’opération de chargement susdite qu’une seule fois et de constituer ensuite une image mémoire.

Bibliographie

[Fea88a] Paul Feautrier. Parametric integer programming. RAIRO Recherche Opérationnelle, 22:243–268, September 1988.

[Fea88b] Paul Feautrier. Semantical analysis and mathematical programming; application to parallelization and vectorization. In Workshop on Parallel and Distributed Algorithms, Bonas, October 1988.

[INR87] INRIA. Le Lisp de l’INRIA, Le manuel de référence. 15.21 edition, December 1987.

[TF89] Nadia Tawbi et Paul Feautrier. Parallélisation automatique de programmes pour ordinateur multiprocesseur à mémoire partagée. Technical Report 285, MASI, March 1989. Journées Algorithmes Parallèles et Architectures Nouvelles.