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)
Performance improvement of micro-processors gives to these chips such complexity that it is impossible to warrant the quality of their functioning. Since their creation, processors have been based on the von Neuman architecture, mainly sequential and imperative.
Parallelism seems to be a solution to easily increase the hardware architecture performance [9]. Mainly, there are two kinds of parallelism: the instruction level parallelism and the task/process parallelism, which does not play any role in the improvement of the processors [7].
Instruction-level parallelism, which is expected to significantly improve the processor performance, seems to be partially inefficient [10, 11, 23, 24]:
We propose in our thesis [15] a parallel architecture model named the static parallel architecture. It is built with popular processors, such as controllers or DSP, which share a global memory. Its originality is to avoid communication times, because the processors are directly connected to the main bus via a three states logic interface.
This architecture could be used only on condition that all the memory access conflicts are solved at compile-time. So its exploitation is closely linked to the associated development tools.
The tools developed during the research, named lambda-tools, allow graphical and hierarchical programming of the applications, high level language programming, and the execution on the parallel architecture simulator.
In an informal way, every application that can be modelled with a flow chart could be programmed with this tool chain. Thus, all state based applications could be implemented, which covers digital filters or digital electronic diagrams.
Lambda-Graph allows graphical programming of the applications [13, 14]. It is a graphical language which allows modular and polymorphic programming[3]. The drawing area supports the common creating/destroying/moving operations with the mouse, as well as the copy/paste editing operations and postscript printing.
The graphical language of lambda-graph is based on the syntactic language lambda-flow described in the next section. There is a translator between the two languages, which allows a mixed design.
The lambda-flow language is functional synchronous dataflow [1, 2, 4, 5, 6, 8, 26, 27] strongly typed that allows a modular design of the applications [20, 21].
A module is described with its interface and its body contains a set of equations: lambda-flow is not a sequential language, but a language where expressions are equations. This feature allows formal proofs and checking of the programs.
The module concept is essential for code reuse. Lambda-flow encourages a modular polymorphic design of the module (A polymorphic module does not specify the type of its entries), but with the possibility of giving a type to some entries.
One original feature of this language is that it is independent of the data handled. Data types and operator interfaces are described in algebra. They are text files dynamically loaded into the compiler. Mixed algebra could be used in the same application.
With this algebra concept, the language becomes extremely extensible and adaptable in a simple way. In addition, lambda-flow does not impose any condition of the nature of the operators which can be as simple or as complex as the user wants.
The design of the lambda-flow language liberates the user from the repetitive type declarations of the traditional typed languages. The type checking uses a complex, original and inductive algorithm.
Another original feature of lambda-flow is that it is designed over a semantic formalism named lambda-matrices, conceived during the research [22]. Lambda-matrices are based on the lambda-calculus [12, 31] which is the foundation of all functional languages [28, 29, 30].
Notably, the lambda-matrices allow formal proofs of programs [25, 32]. We have used them to show the time/resources determinisms of lambda-flow programs [4, 18]. In addition, lambda-matrices define a functional solving method that maximizes the parallelism exploitation. Mathematical foundations give to lambda-flow a great simplicity and a sound semantics.
The third original feature of lambda-flow is to be independent of the targets. Currently, the compiler is able to produce C, Scheme (Scheme is a functional form of Lisp), intel-386 assembler and the spa format (Static Parallel Architecture) especially designed for parallel processing.
A target is defined in lambda-flow in a text file with less than twenty definitions. This file is dynamically loaded with an option in the command line of the compiler.
The produced code structure is based on a main iteration. This iteration allows the task scheduling of the application to be exploited by the instruction-level parallelizing compiler.
The lambda-flow compiler is the most advanced tool available for the DOS, WINDOWS and UNIX systems.
The lambda-spac compiler is the last transformation tool of the chain. It exploits the spa format of lambda-flow in order to schedule the tasks at the instruction-level among the static parallel architecture processors.
It produces an assembler file for each processor of the architecture [16].
The simplicity of lambda-spac is mainly due to the code structure produced by lambda-flow, organized in sections based on a main loop.
Currently, the lambda-spac compiler exploits an homogeneous architecture with popular controllers. It could be extended to exploit an architecture with more complex processors, such as DSP, or a heterogeneous architecture .
Global memory access conflicts are resolved at compile-time by the compiler that inserts blank-operations where they are necessary, to avoid such conflicts. In addition, it allows some optimizations, such as entry inversion, register content management, instruction interleaving and access bus priority management.
All the optimizations yield a gain of 10% of performance however many processors in the architecture (A gain of x% means that instead of 100 units, there are obtained 100-x units).
In order to verify the concepts, we have developed a graphical simulator of the static parallel architecture, named lambda-spas [17, 19].
This simulator allows:
In order to evaluate the lambda-tools, we have used a real application from industry. It is the compression standard ADPCM, used in mobile phones.
For the user, both languages lambda-graph and lambda-flow are very flexible, and allow efficient programming with polymorphic and modular design, and code reuse.
The C code produced by lambda-flow cannot be easily compared to the code written by hand, because the structures are completely different. They can be compared by means of the number of instructions and the duration of the execution cycle. From the efficiency point of view, the results are quite similar, but the hand written code is much more compact because of the use of C functions.
With the static parallel architecture, the performance gain reaches 60% with 5 processors, compared with that of 1 processor.
The cost study shows that the parallel architecture is profitable when we have large applications and expensive processors. With small applications or cheap processors, it is better to use a single powerful processor. Conversely, with the fastest existing processor, a 60% gain cannot be obtained in another way.
The developed tools are prototypes, except the lambda-flow compiler which reaches the beta-test status.
The possible improvements are:
[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 limits 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. Messerschmitt. 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 . Cambridge Unversity Press, 1988.
[32] JE. Stoy. Denotational Semantics: The Scott-strachey Approach to Programmaing Language Semantics. MIT Press Series in Computer Science, 1977.