Publications of the project

A parallel cellular hierarchical language and its computational model
Keywords Researchers
Cellular language, parallel programming, synchronous parallelism. Dr. Pierre KUONEN (project leader), Paul-Jean CAGNARD (Ph.D. student). External: Dr. Stéphane VIALLE (Supélec Metz) and Dr. Thierry CORNU (Simulog Grenoble).
Project period Funding Agency
July 1997 - September 2000. This project is funded by the Swiss National Science Foundation (grants #21-49519.96 and #20-55271.98).
Description
ParCeL-1 is a parallel language based on agents, not unlike actor languages. Its agents are autonomous and follow a computational model in which the communications are non-blocking and the communication scheme is explicit. ParCeL-1 has a parallel implementation and runs on MIMD multi-processor architectures. The ParCel-1 compiler is running on the Cray T3D architecture since 1994 and on Intel Paragon since the beginning of 1995, and on SGI Power Challenge since 1996. Sequential implementations are also available on the most widespread UNIX systems. There are some performance problems with ParCeL-1 due to its dynamism and to the fact that the compiler has not been developed for a long period of time.
In ParCeL-2, which is meant to be a following to ParCeL-1, we want to define a virtual machine, along with a programming language, in order to achieve elegant, efficient and easy parallel and synchronous programming of algorithms in networks of processors which have a static topology. Cellular automata, in particular, lattice gas and finite element methods are examples of algorithms we are considering. An advantage of synchronous parallelism is that it provides a solution to many communication problems between processes. We also want to relate the computational model of ParCeL-2 more strongly to the Bulk Synchronous Parallel (BSP) model since it provides means of performance predictability and is more general than pure cellular programming in which cells are represented by processes which do not really execute complex computations, but do only state transitions. The computation model of ParCeL-2 can be seen as an extension of the BSP model. First, the behaviour of cells in ParCeL-2 is called semi-synchronous because cells do not have to synchronise at every time step during the computation, they have their own clock period which is a multiple of the execution environent's global clock. Second, communications between processes are only allowed through typed and unidirectional channels between them. Finally, ParCeL-2 cells can be either elementary cells, which are simple processes, or complex cells, which are cells that embed other elementary or complex cells. Thus a typical ParCeL-2 program contains a large number of fine grained processes, much more than the number of available processors, and can be represented as a multilevel directed graph where nodes symbolise cells, elementary or complex, and edges symbolise communication links. Therefore, ParCeL-2 tries to offer elegant and powerful means to create complex process topologies, along with an efficient execution environment for large numbers of cells.

Publications
Cornu T. and Vialle S., A framework for implementing highly parallel applications on MIMD architectures, in J. R. Davy and P. M. Dew, editors, Abstract Machine Models for Highly Parallel Computers, Oxford Science Publications, chapter 18, pages 314-337. Oxford University Press, 1995.
Lallement Y., Cornu T., and Vialle S., An abstract machine for implementing connectionnist and hybrid systems on multi-processor architectures, in V. K. H. Kitano and C. Suttner, editors, Parallel Processing for Artificial Intelligence, 2, Machine Intelligence and Pattern Recognition Series, pages 11-27. Elsevier Science Publishers, June 1994.
Lallement Y., Cornu T., and Vialle S., Application development under ParCel-1, in Third International Workshop on Parallel Processing for Artificial Intelligence, Montreal, August 1995.
Lallement Y., Vialle S., and Cornu T., ParCeL-1: A parallel language based on autonomous agents for connectionnist and ai applications, in Proceedings of the First Symposium on Neuro-Fuzzy Systems, Advanced Technologies'96, EPFL, Lausanne, Switzerland, August 1996.
Vialle S., Cornu T., and Lallement Y., ParCeL-1: A parallel programming language based on autonomous and synchronous actors, ACM SIGPLAN Notice, 31(8):43-51, SwissTx, August 1976.
Cagnard P.-J., Etat de l'art des langages parallèles, Internal Report 120, EPFL-DI-LITH, Lausanne, May 1999.
Cagnard P.-J., The Parallel Cellular Programming Model, in Proceeding of 8th EUROMICRO Workshop on Parallel and Distributed Processing (EURO-PDP 2000), IEEE Computer Society, pp.283-289, Rhodes, Greece, January 2000.
Kuonen P., Babin G., Abdennadher N. and Cagnard P.-J., Intensional High Performance Computing, in the Proceedings of the Workshop on Distributed Communities on the Web (DCW2000), Springer Verlag, Québec, June 2000.
Cagnard P.-J., The ParCeL-2 Programming Language, in the proceedings of Euro-Par 2000 -- Parallel Processing, München, Germany, August 2000.
Cagnard P.-J., ParCel-2: Un modèle de programmation parallèle, cellulaire, hiérarchique, thèse no 2329, Ecole Polytechnique Fédérale de Lausanne, Janvier 2001.