Laboratory for Parallel Program Synthesis

Head of the Laboratory: Victor MALYSHKIN

The laboratory direction includes a wide range of complex investigations in the technologies of parallel computing and parallel programs construction for MIMD multicomputers.

The academic research project Assembly System (ASSY) integrates these investigations. The basic goal of ASSY project is the development of parallel computing technologies and supporting their Parallel Assembly Programming System (PAPS) common to different large block multicomputer systems (MCS). The whole parallel program created in this PAPS is assembled out of ready-made atomic fragments of computations. Each of them can be executed on at least one processor of the MCS. Executable code keeps the fragmentation, this provides the parallelization of the program along the "seams" of assembling. If the volume of atomic fragments is small enough, then equal workload for each processor element of multicomputer can be assigned and dynamically re-balanced if necessary.
Chief application area for PAPS now is parallel realization of approximating mathematical models in physics and chemistry. Peculiarity of this area is that the atomic fragments of computation should be very small containing usually the computations inside one cell of approximating mesh only. Therefore, key problem in development of PAPS is the development of excellent algorithms of the whole computation assembling.

The following researches and sub projects are under way:

Mapping/scheduling algorithms supporting dynamic re-balancing of PE workload.
Methods, language and system of functional programming oriented to support the numerical computations.
Intelligent programming methods, non procedural facilities for parallel assembly programming languages are developed too.
The development of the intelligent tool for parallel programming support. Our parallel programming systems support explicitly 2 level programming: the level of modules creation and the level of the potentially infinite set of computations description. We try to support both. The knowledge is based on the library of modules, their properties and connections.
Non procedural facilities for the numerical problems description have been developed. They are used as a method for the generalization of the experience of the application problem solution.
Processes Flying Technology providing dynamic tuning of potentially infinite set of processes on the resources of multicomputers. Processes might be born and died during the computation. This technology provides the development of very flexible parallel programs tunable to the real behavior of the modeled or controlled object.

In our work we always use the following method. We choose a mass algorithm (problem) and the common scheme of their realization is developed. To realize this scheme a high quality hand-made parallel program is developed with some procedural language, the problems of the class are solved during some period and then only the assembly non procedural facilities (as a generalization of our experience in the solution of these problems) are developed which can be transformed successfully in a parallel program or its fragments. In this way the tools for parallel realization of different modification of Particle-In-Cell (PIC) methods have been developed. Parallel programs developed under this software are tunable to the real behavior of physical phenomenon. This is very important property of the program because of high irregularity of data and non predictability of the modeled physical phenomena (for example, plasma cloud extenuation) behavior. If this property of parallel program isn't provided, good realistic model can't be realized on multicomputers at all.

Actually every group of non procedural facilities can be used to describe some standard (non interpreted) scheme of parallel computations. The necessary semantics to solve some specific problem is defined specifically. As the non interpreted computations are defined, the automatically created target parallel program has ordinarily the same performance as a good "hand-made" program. Our nearest goal in the framework of this project is to accumulate more or less complete library of standard schemes of the parallel computations for the area of numerical computation.

Now we have a good experience in the solution of the problems in the seismic data and image processing, the modeling of the mass natural phenomena with particle-in-cell method, solution of differential equations, quantum chaos.

We are trying to integrate on the basis of the common approach the advantages and achievements of different directions and areas of computer science and programming, in order to implement their opportunities in the diverse PAPSs.

Last update Aug 28, 1996