Ce texte donne quelques points de repère pour s'orienter dans le projet de INF124, dédié aux calculs de relations. L'objectif du projet, indiqué sur le site de l'UE http://www-verimag.imag.fr/~perin/enseignement/L1/inf124/projet/ est rappelé ici : placer au mieux les instructions d'un programme sur un processeur multi-coeurs à l'aide d'un algorithme qui construit une relation d'ordre entre instructions et qui place sur les coeurs les instructions minimales pour la relation d'ordre. Des exemples de programmes et de placements sont sur le site. PRÉLIMINAIRE ------------ Pour les explications on a une petite difficulté de vocabulaire, puisque l'on doit parler de deux sortes de programmes : - les programmes C à écrire ou compléter - les programmes manipulés par ces programmes C, donc vus comme des DONNÉES (on verra qu'ils sont codés sous forme de tableaux). Pour distinguer ces derniers, on les appelle ici des D-programmes. STRUCTURE DES PROGRAMMES À RÉALISER ----------------------------------- Tout d'abord on aura besoin de quelques résultats issus des TP précédents. TP1 : relation_affichage.c relation_operation.c TP2 : relation_cloture.c Comme d'habitude, le programme principal à compiler est issu de main.sql.c. Ici, on décommentera - au début : l'inclusion de comparaison_semi_ring.c - l'inclusion de relation_affichage.c et de relation_operation.c mises pour TP1 et de relation_cloture.c mise pour TP2 - en fin de fichier : l'inclusion de relation_ordre.c et de projet.c Il faudra en particulier fabriquer ce dernier à partir de projet.sql.c, qui lui même inclut program.c, program_execution.c, program_au_hasard.c, program_placement.c et program_test.c. Parmi ces derniers, le seul qui demande à être complété est program_placement.c, les autres vous procurent différentes bibliothèques. Il faudra également compléter comparaison_semi_ring.c à partir de comparaison_semi_ring.sql.c ainsi que relation_ordre.c à partir de relation_ordre.sql.c. Pour cela il faut préalablement comprendre les explications ci-dessous. CONSEILS POUR LA MISE AU POINT ------------------------------ Pour les programmes d'une taille conséquente, il n'est pas recommandé de tout écrire de A à Z, puis de compiler et essayer sur la totalité. Au contraire, précéder de façon incrémentale, sachant qu'une exécution de votre programme va fonctionner en plusieurs phases consécutives se traduisant chacune par le calcul et l'affichage de quelque chose. Le principe est de faire en sorte que votre programme soit TOUJOURS COMPILABLE même si le travail n'est pas fini. - Se concentrer sur la première phase, la faire fonctionner en "neutralisant" les parties de code auxquelles on ne s'est pas encore attaqué. Neutraliser veut dire que les fonctions non réalisées sont laissées vides (on ne s'intéresse pas à leur résultat de toute façon), de sorte que l'ensemble soit compilable. Exécuter et vérifier que les résultats sont probants, sinon continuer la mise au point de cette phase - Une fois la 1ère phase en état de marche, faire de même avec la seconde phase. - Et ainsi de suite. LES D-PROGRAMMES ET LEUR EXÉCUTION SÉQUENTIELLE ----------------------------------------------- Les D-programmes sont des séquences d'instructions numérotées de la forme : 7: x4 := 52 + x13 + x0 ; 7 est le numéro de l'instruction, x4, x13 et x0 sont des variables. Les instructions sont numérotées de façon consécutive, le D-programme s'exécute intuitivement : instruction 0, puis instruction 1, etc. jusqu'à la dernière. CODAGE ------ D'une manière générale chaque instruction est variable := constante + autres_opérandes cest-à-dire une expression est une somme dont les opérandes sont - le premier : une constante entière - les suivants : jusqu'à 3 variables Comme ces instructions ont une forme simple, on peut les représenter par un tableau à 6 colonnes, indexé par le numéro d'instruction. La première colonne donne le nombre de colonnes significatives, compris entre 3 et 6 (chaque instructions peut comporter entre 1 et 4 opérandes. La seconde colonne donne le numéro de la variable affectée, par exemple 3 pour x3 La troisième colonne est la constante en premier opérande de la somme. Les 3 dernières colonnes donnent des numéros de variables, ou bien un entier arbitraire non significatif. Par exemple l'instruction ci-dessus est codée par 5, 4, 52, 13, 0, -1. La valeur -1 est arbitraire, car le 5 au début indique que seules les 5 premières valeurs sont significatives. Les fonctions de manipulation de D-programmes codés ainsi sont fournies dans program.sql.c RELATIONS DE PRÉCÉDENCE ----------------------- L'objectif est de paralléliser l'exécution d'une séquence d'instructions en faisant en sorte d'obtenir un résultat identique à l'exécution séquentielle. Le modèle d'exécution parallèle considéré est le suivant : - la mémoire du processeur est partagée par tous les coeurs - l'exécution de l'ensemble est cadencée par des tops d'horloge partagés, c'est-à-dire qu'à chaque top, chaque coeur considère une instruction unique var := constante + autres_opérandes : il lit les entiers contenus les variables de autres_opérandes, calcule leur somme additionnée à la constante, écrit le résultat dans la variable en membre gauche ; au top suivant, chaque coeur considère son instruction suivante. Pour simplifier le problème on considère que l'on n'a pas de limitation sur le nombre de coeurs disponibles. Pour un D-programme séquentiel de n instructions, il n'est pas utile d'avoir plus de n coeurs de toute façon : cela correspondrait au cas où toutes ses instructions peuvent s'effectuer en parallèle. Par exemple, le D-programme séquentiel suivant : x0 = 1; x1 = 3; x2 = 0; x4 = 1; peut x'exécuter complètement en parallèle sur 4 coeurs avec le même effet x0 = 1 || x1 = 3 || x2 = 0 || x4 = 1; En revanche le D-programme séquentiel suivant : x0 = 1; x0 = 3 + x0; x0 = 2 + x0; x0 = 1 + x0; ne peut pas être parallélisé du tout, il devra s'exécuter sur 1 coeur. Les commentaires en début du fichier program_placement.sql.c indiquent les 3 situations qui forcent une précédence entre deux instructions i et j. Deux d'entre elles sont strictes (noté i < j), indiquant que la date d'exécution de i doit être strictement avant celle de i. Une troisième situation (notée i <= j) impose que la date d'exécution de i soit avant, ou la même que celle de i. Ces situations peuvent se cumuler, ce qui fait que l'on peut avoir à la fois i <= j et i < j, auquel cas on devra bien sûr retenir la plus exigeante i < j. Noter que les 3 situations indiquées correspondent à des comparaisons immédiates. Or si l'on a, par exemple i <= j et j < k, il en résulte indirectement que i < k (i doit s'éxécuter strictement avant k). Techniquement, il serait trop compliqué de gérer les relations < et <= séparément. Étant donné un D-programme (codé sous forme de tableau comme indiqué ci-dessus) on va donc dans un premier temps l'analyser et produire un premier tableau Before représentant la relation de précédence immédiate avec la convention décrite ci-dessous. Ensuite, on calculera la clôture (ou fermeture) transitive de Before. Ce calcul est obtenu gratuitement à partir des TP antérieurs, une fois que l'on a défini correctement le semi-anneau approprié. Dans un second temps on devra donc compléter le fichier comparaison_semi_ring.sql.c et, dans un troisième temps, calculer la fermeture transitive (on la conserve dans le même tableau Before). Enfin, pour effectuer les placements d'instructions, on cherche les instructions qui peuvent s'exécuter simultanément à la date 0 : ce sont les instructions j pour lesquelles il n'existe aucune instruction i telle que i < j. Pour cela il conviendra d'utiliser la fonction relation_minimum à compléter dans relation_ordre.c (voir également les explications dans program_placement.sql.c). Ensuite on écrème les instructions placées (au moyen de relation_forget, à compléter dans relation_ordre.c) et on recommence parmi les restantes pour trouver celles qui peuvent s'exécuter simultanément à la date 1 ; et ainsi de suite. A chacune de ces dates correspond un "ligne" (lors de l'affichage, les instructions exécutées simultanément sont imprimées sur la même ligne). Cette partie du projet correspond à la fonction fill_line (à écrire) dans le fichier program_placement.c. LE SEMI-ANNEAU PERTINENT POUR CE PROJET --------------------------------------- Comme indiqué ci-dessus, on représente la combinaison entre < et <= au moyen d'une "relation généralisée" Before, c'est-à-dire un tableau à 2 dimensions Before dont les élements sont dans {0, 1, 2} : - si Before[i][j] = 2, cela signifie que l'on a i < j ; - si Before[i][j] = 1, cela signifie que l'on a i <= j sans avoir i < j : on retient i <= j - si Before[i][j] = 0, cela signifie que l'on n'a ni i <= j : on le note i ? j On travaille donc sur un semi-anneau dans lequel : - le rôle de la disjonction x \/ y est joué par max (x, y) - le rôle de la conjonction x /\ y est joué par min (x*y, 2), où * est le produit ; pour s'en convaincre, on examine la comparaison résultant entre deux instructions i et k suivant les 9 comparaisons existant entre i et j d'une part, j et k d'autre part pour un j fixé - les valeurs pertinentes pour zero et unit sont les éléments neutres des opérations précédentes Voir les commentaires dans comparaison_semi_ring.sql.c. FICHIERS DISPONIBLES -------------------- Fichier principal comme d'habitude : main.sql.c, incluant ici - le semi-anneau des comparaisons : comparison_semi_ring.sql.c - la relation d'ordre : relation_ordre.sql.c - le programme principal : projet.sql.c incluant lui-même - la représentation des D-programmes : program.sql.c - la génération de programmes aléatoires : program_au_hasard.sql.c - l'exécution d'un programme : program_execution.sql.c - le placement du programmes sur un multi-coeur : program_placement.sql.c - des programmes pour tester vos placements : program_test.sql.c Reprendre également certains fichiers provenant TP précedents. TP1 : relation_affichage.c relation_operation.c TP2 : relation_cloture.c ERRATUM ------- Rectifier la constante dans program.c, c'est en réalité #define NB_COEUR NB_INSTRUCTION