OPS video-demo

OPS — Optimizing parallelizing system — is a program tool oriented for development of

1. parallelizing compilers, parallel language optimizing compilers, semi-automatic parallelizing systems;
2. electronic circuits computer-aided design systems;
3. systems of automatic design of hardware based on FPGA.

An OPS is focused on different target parallel architectures. OPS development group investigates new optimizing transformations and new compilation possibilities.

Projects based on OPS:

1. IHOP - Interactive High-level Optimizing Parallelizer
2. OPS Demo
3. WebOPS tool - web interface to some features of OPS

OPS Structure

Parsers.

• C (clang)
• Fortran

Code generation.

• Transformed C code.
• C + MPI.
• C + ParDo loops marks.
• Automatic estimation of measure of inaccuracy.

Program graph models.

• Dependence graph.
• Lattice graph.
• Computation graph.
• Control flow graph.
• Call graph.

Internal representation.

Internal representation is oriented on parsers from different languages (C, FORTRAN, Pascal) usability, program transformations development flexibility and multiple architecture code generation possibility.

Transformations Library.

Implemented transformations automatically check conditions of equivalence based on dependence graph or lattice graph.

Not all program transformations check semantic correctness of applicability. It can lead to an error of the system and it should be resolved in a future versions.

Linear program fragments and expressions transformations.

• Mixed computation in arithmetic expressions.
• Substitution forward and constant propagation.
• Scalar variables renaming
• Dead code elimination.
• Swap statements

One-dimensional loops transformations.

• Loop unrolling.
• Loop canonization.
• Loop distribution.
• Loop merging.
• Removal of loop invariant.
• The splitting of the vertices (declaration of additional arrays).
• Stretching scalars (array replacing the scalar variable).
• Removal of induction variables.

Loops with linear recurrence transformations.

• Replacement of loop with two linear recurrences contain only constant coefficients onto loop without recurrence.
• Replacement of loop with one affined recurrence contain only constant coefficients onto loop without recurrence.
• Replacement of loop which calculates the sum of the series with polynomial general term onto a single formula.

Loop nests transformations.

• Loops interchange.
• Tiling.
• Non-unimodular perfect loop nests transformations.
• Loop splitting.
• Induction variables substitution
• Loop nests induction variables renaming.

Loop into loop nests transformations.

• Loop nesting
• Strip mining.

OPS transformations use service functions such as:

• Insert group of statements
• Delete group of statements
• Replace group of statements
• Substitution of subexpression into expression
• Delete expression
• Generate new declaration (variable, array, label, etc.)

Research interests of the OPS group are

• Automatic program parallelization.
• Multipipeline calculations
• Program transformations based on lattice graph
• Automatic control of calculations inaccuracy
• Automatization of program transformations development
• Automatization of electronic circuit design

OPS developers team and some other participants of our seminar (summer 2004):

(Top row from left to right) Zinovij Nis, Konstantin Gufan, Alexander Shulzhenko, Roman Morilev, Victor Petrenko, Mihail Shilov, Milena Eremeeva, Maria Tzibulina, Sergej Naumenko, Alexander Butov, Polina Shaternikova.

(Second row from left to right) Oleg Steinberg, Alexander Tuzaev, Roman Steinberg, Denis Cherdanzev, Ludmila Mironova

(From left to right) Victor Petrenko, Roman Steinberg, Sergej Naumenko, Boris J. Steinberg, Denis Cherdanzev, Alexander Shulzhenko, Alexander Butov