Информационная система "Конференции"

Abstracts

Parallel numerical algorithms

This paper is about automatic transformation of the sequential programs into parallel forms. The transformation is based on data dependence analysis. The are introduced a three-level program representation for the detection of parallelism. The representation of a source program consist of: the control flow graph (CFG); the extended information about variable occurrences into the statements; and the data dependence graph (DDG). The intermediate program representation (IPR) presented here have been used in optimizing convertor from Fortran to Potomak for supercomputer designed multiprocessor computing system institute (Taganrog). Besides this IPR have been applicated in C parallelization compiler for superprocessor nCube-2S and Linux-cluster, supported by Rostov State University. In addition, by using retranslation system the IPR can be reconverted at any time into a Fortran or C program, so user can see not only all graphs of the IPR, but also his program after some transformations. This ability can be used for an optimizing convertor Fortran-Fortran, C-Fortran, Fortran-C. The IPR given here have the next properties: CFG represents a program as a graph in which the nodes are the statements and the edge leading from node V to U means that U can be performed just after V; CFG is executable; CFG represents the loops in an evident form, so it allows such transformations as loop vectorization, interchanging, distribution and etc.; all levels of the IPR are balanced trees, which allows to gather different information quicker then another data structures. The CFG is a basis of the IPR, because it concludes the whole information about a source program and all transformation are reflected on the CFG. But before applications of any transformation data dependence between the statements should be tested. That is why data dependence graph have been intriduced. The nodes of DDG correspodns to the nodes of CFG and arcs have special marks with data dependence direction vector for iteration space of a loop nest, data dependence type and also marks point at variable occurrences caused this data dependence relation. Banerjee's equations have been used for computing data dependence relations. The level, called extended information about variable occurrences is transitional from CFG to DDG. Availability of this level in IPR make essential advantage during DDG recomputing after some CFG restructuring especially after such of them as loop peeling and loop unrolling. Using information about variable occurrences it is possible to schedule data allocation in the memory channels. The program translation into IPR described in this paper and mentioned transformations have been realized by using compiler creating system Predlog.

Note. Abstracts are published in author's edition

Mail to Webmaster

|Home Page| |English Part|

Go to Home