Конференции ИВТ СО РАН

The 3rd Russian-German School on Parallel Programming using High Performance Computation Systems

August 28 - September 8, 2006
Institute of Computational Technologies
Akademgorodok, Novosibirsk, Russia

Abstracts

August 31

Development of Formalized Methods of Parallelization of Algorithms Given by Affine Loop Nests

Adutskevich E.V.

Institute of Mathematics of NAS of Belarus (Minsk)

There are many works dealing with a problem of parallelization of sequential algorithms. Two approaches to solving this problem can be marked out. The first one consists in realization of natural parallelism of an algorithm. There are a lot of practical algorithms that possess natural parallelism so development of methods of the most effective realization of such parallelism is significant for practice. However there are important algorithms with complicated informational communications and these algorithms do not possess natural parallelism. To discover ways of parallel realization of such algorithms it is necessary to use a special mathematical tool (the second approach). A strict mathematical substantiation allows users of such tool to be convinced with the quality of application of this tool.

Mapping algorithms onto distributed memory parallel computers consists in passing the following main stages:

-- distribution of computations and data among processors,

-- determination of execution sequence of operations and data exchange order,

-- improving data locality in the processors of computing system,

-- optimization of communications necessary during realization of parallel program.

The former two stages are necessary to obtain a parallel realization of the algorithm. The latter ones are desirable to obtain effective realization.

Program execution time depends not only on the execution time of operations but also on the memory access time. The access time depends on data location in the hierarchical memory. Therefore it is desirable to solve the problem of improving data locality (fast reusing) for realization of algorithms on the computing systems.

Optimization of communications is extremely necessary for realization of algorithms on distributed memory parallel computers. It is known that during realization of algorithms on such systems communications between processors have great overheads. Therefore it is necessary to organize communications in such a way that overheads be as small as possible. Two problems should be solved for that. The first one is to reduce the amount of communications and the volume of passed data. The second one is to optimize the structure of communications (search of variants of the most effective data exchange).

The report is devoted to the development of formalized methods of solution of listed problems arising during parallelization of sequential algorithms. The kernel of the formalized parallelization methods introduced in the report is to solve an optimization problem. The result of this solution is a set of allocation functions, which determine spatial mapping of an algorithm to r-dimensional space of virtual processors, functions that determine distribution of data of an algorithm and scheduling functions, which determine the execution order of operations by processors. The optimization problem allows taking into account a large amount of conditions that influence the effectiveness of realizable program. A solution of the optimization problem can be governed by the choice of weighting coefficients. Example applications of the developed methods show that these methods allow us to achieve good results of parallelization.

Note that the formalized methods above are developed with the aim of automatization of the process of parallelization of sequential programs. A software tool is supposed to be created. Work on it is underway at Institute of Mathematics of NAS of Belarus at present.

Note. Abstracts are published in author's edition

Comments

[Home]
[Conference]