Thème Architectures Logicielles et Materielles
Laboratoire d'Informatique, Signaux et Systèmes
URA 1376 du CNRS et de l' Université de Nice-Sophia Antipolis
41 bd Napoléon III - 06100 - Nice - France
Tel : (33).04.93.21.79.60 (I3S)
L'accroissement incessant des performances des micro-processeurs a donné à ces circuits électroniques une complexité telle qu'il est impossible d'en garantir la sécurité de fonctionnement. Le modèle des processeurs n'a pas changé depuis sa création : il est bâti sur une architecture de von-Neumann, typiquement séquentielle.
Le parallélisme semble être une solution pour augmenter, a priori facilement, les performances des architectures matérielles [9]. Il existe principalement deux sortes de parallélisme : le parallélisme à grain fin, ou parallélisme d'instructions, et le parallélisme à gros grain, ou parallélisme de tâches. Ce dernier concerne plutôt la répartition de processus sur un réseau d'ordinateurs et il ne joue aucun rôle dans l'augmentation des performances des processeurs [7].
Le parallélisme à grain fin, dont on espère beaucoup pour augmenter les performances des micro-processeurs semble en partie inefficace [10, 11, 23, 24]. D'une part, les architectures massivement parallèles sont difficiles à programmer efficacement d'une manière automatique et d'autre part, les temps de communication des architectures basées sur des réseaux d'inter-connections sont prohibitifs par rapport aux temps d'exécution des instructions utiles.
Nous proposons dans notre thèse [15] un modèle d'architecture parallèle appelée architecture parallèle statique. Il s'agit d'une architecture construite à l'aide de processeurs communs, de type contrôleur ou DSP, partageant une mémoire globale. Son originalité est d'annuler les temps de communication entre les processeurs et la mémoire, puisque les processeurs sont directement connectés au bus, via un circuit d'interface à logique trois états.
Cette architecture n'est utilisable que si les conflits d'accès à la mémoire globale sont résolus au moment de la compilation des applications. Son exploitation dépend donc fortement des outils de développement associés.
Les outils développés durant la thèse, baptisés lambda-outils, permettent une programmation graphique et hiérarchique des applications, une programmation à l'aide d'un langage de haut niveau, leur exécution sur le simulateur de l'architecture parallèle statique.
D'une manière informelle, toute application modélisable à l'aide d'un graphe ou d'un schéma de boîtes peut être programmée avec cette chaîne d'outils. Ainsi toute application reposant sur un modèle à état est-elle programmable, ce qui couvre en particulier les filtres numériques et les circuits électroniques numériques.
Lambda-Graph permet une programmation graphique des applications [13, 14]. Il s'agit d'un langage graphique autorisant une programmation hiérarchique et modulaire [3]. La zone de dessin supporte les opérations classiques de création/destruction/déplacement des objets à l'aide du dispositif de pointage, ainsi que les opérations d'édition copier/coller et l'impression au format postscript.
Le langage graphique de lambda-graph repose sur le langage textuel lambda-flow décrit dans la section suivante. Nous avons réalisé un traducteur entre l'un et l'autre des deux langages.
Le langage lambda-flow est un langage fonctionnel dataflow synchrone [1, 2, 4, 5, 6, 8, 26, 27] fortement typé qui permet une programmation modulaire des applications [20, 21].
Un module est décrit par une interface et un corps contenant des équations : lambda-flow n'est pas un langage séquentiel, mais un langage où les expressions sont des équations, ce qui permet d'établir des preuves de programmes.
La notion de module est essentielle pour permettre la réutilisation du code. Lambda-flow encourage une conception polymorphe (sans spécification de type) des modules (Un module polymorphe n'impose pas le type de ses entrées), en donnant toutefois la possibilité de typer les entrées.
L'une des originalités de ce langage est d'être complètement indépendant des données qu'il manipule. Les types de données et l'interface des opérateurs sont décrits dans des algèbres qui sont des fichiers textes chargés dynamiquement dans le compilateur lambda-flow. Une même application peut utiliser plusieurs algèbres.
Cette notion d'algèbre est très intéressante car le langage devient extensible et adaptable d'une manière simple. De plus, lambda-flow n'impose aucune condition sur la nature des opérateurs décrits dans les algèbres, ce qui signifie qu'elles peuvent être aussi élémentaires ou aussi complexes que l'utilisateur le souhaite.
La conception de lambda-flow permet d'affranchir le programmeur des incessantes déclarations de types que l'on rencontre dans les autre langages typés. Le contrôle des types utilise un algorithme original de type inductif.
Une autre originalité de lambda-flow est de reposer sur un formalisme sémantique appelé lambda-matrices, créé durant la thèse [22]. Les lambda-matrices reposent sur le lambda-calcul [12, 31] qui est le fondement de tous les langages fonctionnels actuels [28, 29, 30].
Les lambda-matrices permettent notamment d'établir des preuves de programmes [25, 32]. Nous avons utilisé leurs propriétés sémantiques pour montrer que les programmes lambda-flow sont déterministes en temps et en ressources [4, 18] De plus, les lambda-matrices proposent une méthode de résolution qui permet une exploitation maximale du parallélisme des programmes. Les fondements mathématiques de lambda-flow lui confèrent une simplicité et une précision appréciables.
Enfin, la troisième particularité de lambda-flow est d'être indépendant des cibles. Actuellement, le compilateur permet de produire indifféremment du C, du Scheme (Scheme est une forme fonctionnelle et simplifiée de Lisp), de l'assembleur intel-386 et le format spa (spa pour Static Parallel Architecture) spécialement étudié pour être exploitable par le compilateur parallèle décrit dans la prochaine section.
Une cible est décrite dans lambda-flow par un fichier ayant une vingtaine de définitions. Ce fichier est spécifié par une option du compilateur, puis il est lu et interprété dynamiquement.
La structure du code produit est basée sur une itération. Cette itération permet un ordonnancement des tâches élémentaires de l'application, qui est exploité par le compilateur parallèle.
Le compilateur lambda-flow est l'outil le plus avancé de la chaîne d'outils. Il est écrit en C pour les systèmes dos, windows et unix.
Le compilateur lambda-spac est le dernier outil de transformation. Il exploite le format spa de lambda-flow et répartit les tâches élémentaires sur l'architecture parallèle statique.
Il produit autant de fichiers en assembleur qu'il y a de processeurs dans l'architecture [16].
La simplicité de lambda-spac provient essentiellement de la structure du code produit par lambda-flow, organisé en sections basées sur une itération principale.
Actuellement, le compilateur lambda-spac exploite une architecture homogène à processeurs communs de type micro-contrôleurs. Il permettrait aisément d'exploiter des processeurs plus complexes de type dsp et des architectures à processeurs hétérogènes.
Les conflits d'accès à la mémoire globale sont résolus par le compilateur, qui insère des instructions blanches en cas de conflits. Il permet aussi un certain nombre d'optimisations, comme l'inversion des entrées d'une tâche, la prise en compte du contenu des registres, l'entrelacement des instructions et le partage de la priorité d'accès au bus entre les processeurs.
L'ensemble de ces optimisations permet en moyenne un gain de 10% des performances, quelque soit le nombre de contrôleurs de l'architecture (Un gain de x% signifie qu'au lieu de 100 unités, on en obtient 100-x).
Pour vérifier le fonctionnement des programmes, nous avons conçu un prototype de simulateur graphique de l'architecture parallèle statique, appelé lambda-spas [17,19].
Ce simulateur permet l'exécution en pas à pas ou en animation des programmes, avec l'affichage en temps réel des différents composants, la modification du contenu de la mémoire globale ainsi que de tous les registres et la pose de points d'arrêts.
Pour évaluer les lambda-outils, nous avons traité une application réelle issue de l'industrie. Il s'agit de la norme de compression G.726, utilisée dans les téléphones portables.
Du point de vue de l'utilisateur, les langages lambda-graph et lambda-flow permettent une programmation efficace, polymorphe, et complètement modulaire, ce qui permet une réutilisation maximale du code. La programmation de la norme est immédiate, et les risques d'erreurs sont fortement réduits.
Le code C produit par lambda-flow est difficilement comparable au code qu'aurait écrit un ingénieur à la main, car leurs structures sont trop différentes. Ils ne peuvent être comparés que par le nombre d'instructions et par la durée d'un cycle d'exécution. Du point de vue de l'efficacité, les résultats sont sensiblement identiques, mais le code de l'ingénieur est beaucoup plus compact du fait de l'utilisation de fonctions C.
Par contre, l'utilisation de l'architecture parallèle statique permet un gain de performances de 60% par rapport au code séquentiel, avec 5 contrôleurs.
L'étude des coûts montre que l'utilisation de l'architecture parallèle statique est d'autant plus justifiée que la taille de l'application est importante et que le prix unitaire des contrôleurs est élevé.
Autrement dit, pour de petites applications réalisées avec des processeurs à faible prix, il est plus rentable d'utiliser un processeur plus puissant. Par contre, si le processeur est le plus rapide du marché, un gain de 60% ne peut être obtenu autrement que par le modèle proposé.
Les outils développés sont à l'état de prototypes fonctionnant convenablement, mis à part le compilateur lambda-flow qui est en phase terminale de test.
Voici les différents travaux qui restent à effectuer :
[1] Abelson, GJ. Susman, and J. Susman. Structure and Interpretation of Computer Programs. MIT Press, 1987.
[2] WB. Ackerman and JB.Dennis. VAL - A value oriented algorithmic language. Technical Report LCS/TR-218, M IT, Cambrige, MA, June 1979.
[3] EA. Ashcroft and R. Jagannathan. Operator nets. Fifth Generation ComputerArchitectures, pages 177-202, 1986.
[4] EA. Ashcroft and WW. Wadge. Lucid, a formal system for writing and proving programs. SIAM journal of Computer, 5(3)336-354, September1976.
[5] J. Backus. Can programming be liberated from the von-Neumann style? A functional style and its algebra of programs. j-CACM, 21(8):613-641, august 1978.
[6] A.Benveniste and P. LeGuernic. Hybrid dynamical systems theory and the signal language. IEEE Transactions, 35:535-546, 1990.
[7] L .Bic. A process oriented model for efficient execution of dataflow programs. Journal of Parallel and Distributed Computing , page 42-51, 1990.
[8] APW. Bohm, DC. Cann, JT. Feo, and RR. Oldehoeft. Sisal 2.0 reference manual. Report CS-91-118, Computer Architecture Department, Colorado State University, Fort Collins, CO, 1991
[9] M. Cosnard and D.Trystram. Algorithmes et architectures parallèles. Inter Edtion, 1993.
[10] DE. Culler and Arvind. Resource requirements of dataflow programs. In Proceedings 15th Annual Internationnal Symposium on Computer Architectures, pages 141-150, ACM SIGARCH, 1988.
[11] DE. Culler,KE. Schauser and Thorsten von Eicken. Two fundamental limists on dataflow multprocessing. Architectures and Compilation Techniques for Fine and Medium Grain Parallelism (A-23), pages 153-164, 1993.
[12] G. de Wailly. Implémentation des lambda-matrices à l'aide du lambda-calcul. Technical Report 95-34, I3S, july 1995.
[13] G. de Wailly. User manual of lambda-graph, the graphical interface of the functional synchronous dataflow language lambda-flow. Technical Report 95-33, July 1995.
[14] G. de Wally. A graphical interface for the functional synchronous data-flow language lambda-flow. In Dynamc Object Workshop (DOW 96)-USA, Object World East, may 1996.
[15] G. de Wailly. Modélisation fonctionnelle et graphique des applications à états en vue de leur réalisation sur architectures parallèles statiques. Master's Thesis, Université de Nice-Sophia Antipolis, january 1997
[16] G. de Wailly and F. Boéri. A parallel architecture for the lambda-matrices, a functional data-flow abstract language. Technical Report 95-42, I3S, July 1995.
[17] G. de Wailly and F. Boéri. A parallel architecture simulator for the lambda-matrices. In Association of Lisp Users Meeting and Workshop Proceeding s (LUV'95)-USA, august 1995.
[18] G. de Wailly and F. Boéri. Proofs upon basic and modularized lambda-matrices. Technical Report 95-69, I3S, December 1995.
[19] G. de Wailly and F. Boéri. A cad tool chain for signal processing applications, with parallel implementation issues. In Groningen Information Technology Conference-Holland, February1996.
[20] G.de Wailly and F. Boéri. Datalow language for signal processing modeling with parallel implementations issues. In VII Eurorean Signal Processing Conference (EUSIPCO'96)-Italy, EURASIP, septembe1996.
[21] G.de Wailly and F. Boéri. Lambda-flow: User manual. Technical Report 95-39, I3S, July 1996.
[22] G.de Wailly and F.Boéri. Specification of a functional synchronous dataflow langage for parallel implementations with the denotational semantics. In Symposium on Applied Computing (SAC'96), ACM-USA ,February 1006.
[23] J.B. Dennis. A Highly Parallel Processor Using a DataFlow Machine Language. Laboratory for Computer Science, Massachuset Institute of Technology, Cambridge, MA, 1979.
[24] Jack B.Dennis. Dataflow super-computer. Computer, 13(11)48-56, November, 1980.
[25] RW. Floyd. Assigning Meaning to Programs. In proceedings of the Symposium in Applied Mathematics. Mathematical Aspects of Computer Science 19, 1967.
[26] N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud The synchronou dataflow programming language LUSTRE. In Proceedings of the IEEE, pages 1305-1319. Published as Proceedings of the IEEE, volume 79, number 9., 1991
[27] EA. Lee and DG. Messerschimitt. Synchronous dataflow. Proceedings of the IEEE, 75(0): 1235-1245, September 1987.
[28] A. Lloyd. A practical introduction to the denotational semantics. Cambridge Computer SicenceTexts 23, 1986.
[29] B. Meyer. Introduction à la théorie des langages de programmations. InterEdition, 1992.
[30] C. Quiennec. Les langages Lisp. InterEdition, 1994.
[31] GE. Revesz. Lambda-Calculus Combinators, and Functional Programming . Cambrige Unversity Press, 1988.
[32] JE. Stoy. Denotational Semantics: The Scott-strachey Approach to Programmaing Language Semantics. MIT Press Series in Computer Science, 1977.