RAMPA — CASE for portable parallel programs development

V.A.Krukov, L.A.Pozdnjakov, I.B.Zadykhailo
Keldysh Institute of Applied Mathematics, Moscow

Introduction
Purpose and composition of the RAMPA system
Fortran GNS Language
Fortran DVM Language
Norma Language
The debugging and monitoring tools
References

1. Introduction

At the present time the main way of increasing the computer power is the designing multi-processor computer systems with distributed memory. In the world there are a large number of such projects (e.g. Tera 3D, CM-5, KSR1, Paragon) aimed to the realization of the teraflop computer power up to the end of the decade. All of these systems are multi-processor systems with distributed memory consisting of thousands of processors. The design of applications software for such distributed systems meets a number of very serious troubles.

The concurrent program development needs using or creating the appropriate computing methods. To achieve the require efficiency it is necessary to go many times from the algorithm specification to the program written in programming language. And this way is much more complicated for the Parallel Computers then it is for traditional ones.

The lack of availability of concurrent algorithms and programs which the programmer could use in the work aggravates the problems arising by concurrent programs development. In this connection there is a pressing requirement to use huge banks of programs and algorithms written in sequential programming languages.

There are pure psychological problems connected with human perception of parallel algorithms. A man more naturally deals with the sequential algorithms and programs. So the transition to the distributed systems using makes the applications programmer’s work much more complicated. Moreover it strongly reduces the pace of program development. That’s why it is desirable to give a programmer an opportunity to use a traditional sequential programming languages, which are possibly modified for the increasing efficiency of the automated algorithm paralleling.

The concurrent programs worked out with language facilities which avaliable for the distributed systems require serious efforts for mapping the programs not only on computers with different architectures (sequential, SIMD processor arrays, MIMD shared memory machines), but also on the same computers with another configuration. Linking the concurrent program with using simple modules, accumulating the bank of common concurrent programs and modules are the problems to investigation.

Finally it is necessary to outline the lack of adequate techniques and facilities for concurrent programs debugging and monitoring. Also there are not avaliable instrumental systems, which allow to organize the paralleling technique teaching the wide number of specialists.

To get over difficulties pointed above and to make convinient and effective using the perspective computer systems with massive parallelism, the investigations of the computer aided system for portable concurrent programs designing (the RAMPA system) have been started at Keldysh Institute of Applied Mathematics Russian Academy of Sciences.

The RAMPA system should integrate three different approaches to constructing the programming languages for the distributed computers. These approaches based on:

the distributed system oriented languages for concurrent programming (which based on interaction by means of message passing);
the languages for sequential programming, enlarged by means of instructions for distributing the computations on system processors, which formed as sets of special comments;
non-procedural languages (specification languages).

2. Purpose and composition of the RAMPA system

The system RAMPA is designed to create, debug and monitor parallel programs for MIMD distributed-memory machines. The main programming languages are Fortran DVM and Norma [4]. Programs in these languages can be effectively mapped on various distributed systems. Using the appropriate compilers such programs will be mapped on computers with different architectures (sequential, SIMD processor arrays, MIMD shared memory machines). These programs can be easily used as modules for constructing more complex programs.That will significantly reduce the development costs of new programs and will result in establishing widely used banks of parallel algorithms.

The system will also allow the development of programs with Fortran GNS, Fortran 77 and C languages, extended with tools from
specially made library for parallel programs support. But that will make programs development more labour-consuming and programs portability much lower.

Above that, using instrumental computer (for instance IBM PC) the system could simulate the program execution for computers with different architecture and evaluate the efficiency of parallelism. The system also could help a programmer to rewrite sequential program into parallel one. Thus the system could be used for training in parallel programming.

The system under developing includes the Fortran DVM, NORMA and Fortran GNS compilers converting the program into extended Fortran 77. The system also envolves the libraries LIB-DVM and LIB-GNS for concurrent programming support and debug and monitor tools.

3. Fortran GNS Language

Fortran GNS is Fortran 77 extended in correspondence with proposals of C.A.Thole [3], based on abstract GENESIS-machine concept. According to this concept the user’s task is a set of sub-tasks which are dynamically created on the specified processors of distributed system. These sub-tasks communicate among themselves by sending and receiving messages in any of the three modes: synchronous, asynchronous and nowait.

The abstract GENESIS-mashine conception is realized as a LIB-GNS library and this makes it available both for the C and Fortran 77 programs. The following approach to the separation of duties between the library and the configuration description language (which is usually applicated for tasks mapping onto processors of distributed system) was accepted by this library realization. The library should allow to map programs onto different processors of some virtual parallel machine (GNS-machine) and should organize the communications between them. The configuration description language should allow to set an effective mapping of the virtual parallel machine onto available hardware.

The virtual parallel machine is a aggregate of rectilinear virtual processor arrangements. When the virtual machine is mapped onto a physical machine, several virtual processors can be mapped onto a single physical processor. This simplifies adaptation of programs for a specific configuration and at the same time increases our capabilities in program debugging.

The Fortran GNS language provide the following basic features for parallel application programming.

Initialization and Termination of whole application

The whole application is started by one specified initial task allocated to the specified processor. The task and the processor are specified through the programming environment (for example, as a UNIX command-line argument). This task creates further tasks on the same processor or on others.
The whole application terminates if the initial taskerminates or one of the other tasks requests an abort.

Tasks

Each task gets an unique identifier.
Each task use only local address spase, no shared data with other tasks.
Each task may perform I/O to a common file system.
Each task may create dynamicaly other tasks on any processors, which are alloted to the whole application. The number of tasks is not limited by the number of processors.
Once created, a task is statically allocated to a specific processor.
Each task may terminate only itself or the whole application.

Message passing

The message content is list of data objects each of which might be a scalar, an array or an array section. The list of the send command and the receive command must conform in the number of elements and in the data type and the shape of each element.
The descriptor for the destination is the identifier of the task. Multiple destinations may be specified for broadcast operations.
Messages are automatically routed to any destination task.
Asynchronous message passing uses a no-wait send and receive facility, which waits for the arrival of an appropriate message. Integer values called tags are used to distinguish between messages of different type. Matching of messages to the execution of receive statements is performed on the basis of tags and optionally on the origin of the messages. If several
messages from the same sender fulfill the request, the one sent first is used.
Alternating receiving of messages of different type and/or origin is possible.
Synchronous message passing is supported.
No-wait send and no-wait receive statements are provided for the implementation of single-buffered communication. On each side a logical variable can be tested using intrinsic calls to determine whether the message trasfer has been performed.

Reduction functions

A set of intrinsic functions supports parallel reduction functions (e.g. MAX,MIN,SUM). The reductions are applied for each of the element of the specified array valued operand over the specified tasks. Each of these tasks has to call this intrinsic, the operation is executed synchronously and the results are returned to any task involved.

4. Fortran DVM Language

The Fortram DVM compiler will produce the Fortran 77 program, which will be extended with the library LIB-DVM tools. That library in its turn is the superstructure of the LIB-GNS library.

5. Norma Language

Norma is a non-procedural language designed for numerical algorithms of solving mathematical physics problems using difference methods.

The basic idea of this language is to use the description of the problem in the form of computational formulae obtained by applied specialist as input information to run computations.

Thus Norma allows applied mathematicians to formulate their problems in their usual terms. The computational process for specific hardware architecture (parallel, vector, etc.) is organized by the translator from Norma.

Research during development and implementation of the non-procedural Norma language shows that program synthesis for the grid methods solutions of the problems of mathemaical physics can be done under practically acceptible restrictions.

Currently there exist the versions of the translator from Norma into sequential FORTRAN 77 and into vector-parallel Fortran VP (extension of Fortran 8X).

The Norma programming system has been used for applications in mathematical physics, including 3-D viscous incompressible fluid flow problems.

6. The debugging and monitoring tools

The debugging and monitoring tools are used in the following three modes:

Program execution on a parallel computer.
Program pseudo-execution on an instrumental computer by using the tracing information from the program execution on a parallel computer.
Instrumental computer simulation of the program execution on a parallel computer.

A programmer has to spend much more effort to debug a parallel program than a sequential one. It may be explained by specifics of human perception of parallel algorithms as well as a nondeterministic nature of parallel program execution. The same problems have for a long time been a challenge for designers of OS and real-time systems. Therefore it is only natural to borrow from their arsenal of debugging techniques such as tracing, the corresponding tools for automated analysis of traces and the tools for automated analysis of fixed states of program execution. Also important are visualization facilities for graphic representation of the structure of parallel programs, and their message exchange characteristics.

Debugging tools should make it possible to repeatedly run a parallel program with the same results in order to eliminate nondeterministic behavior of the program during error localization.

The following traditional interactive debugging tools will be implemented: the breakpoints setting, the visualization of values of the marked variables, etc.

The monitoring facilities can be treated as an integrated part of debugging tools since they enable programmers to gain a better understanding of his program. Among these facilities are statistics gathering software and profiling software.

By simulation of the concurrent program execution using instrumental computer the user will be able to debug Fortran DVM, NORMA, Fortran GNS programs and to debug programs written in Fortran 77 and in C languages, which extended with the LIB-GNS library tools.

Above that, using the instrumental computer for debugging could help a programmer to rewrite his sequential program into parallel one written in Fortran DVM language. In this case adding control instructions to the program will not influence on correctness of program execution but it will only effect on the estimation of program execution time.

For providing such mode the compiler will prepare program in a special manner. By the program simulation it will allow to make dynamic analysis of statement relations and to use this analysis for choosing the control instructions correctness and for estimating synchronizing and message passing time. By the simulation the user will be able to take exhaustive information about his wrong or non-optimal instructions and information about the program executing, which help him with paralleling the program.

The possibility of gradual paralleling the program with the guaranted correctness of its execution not only makes essentially easier this process but also in some cases allows to limit oneself estimating the concurrent program performance after mapping the computations onto processors (e.g. in case of using or creating the appropriate computing methods).

References

Hiranandani, S., Kennedy,K., Tseng,C. Compiling Fortran D for MIMD Distributed-Memory Machines. Comm. ACM, Vol.35,No.8 (Aug.1992),66-80.
DRAFT. High Performance Fortran. Language Specification. Version 1.0, Jan.25, 1993.
Thole, C.A.: A proposal for the Abstract GENESIS Machine. In: Report on the GENESIS definition phase October 1988 — June 1989, 1989.
A.N.Andrianov, K.N.Efimkin, I.B.Zadykhailo. The Norma language. Prepr. Keldysh Inst. of Appl. Math., N165, 1985 (In Russian).
N.A.Konovalov, V.A.Krukov, E.Z.Ljubimskij. Controlled virtual memory. Programming, N 1, 1977 (In Russian).