Recognition of loop parallelisms by simulated execution

Conclusions The method of recognition of loop parallelisms based on simulation of loop execution has been described, for the sake of simplicity, within the scope of simple loop structure analysis. At the same time, the method can be effectively extended to loops of arbitrary structures including loop nests. The method allows to vary the number of analyzed passes from N₁ to N₁×N₂×...×N_j, where N_i is the number of iterations of a loop of an imbedding i. Reduction of a nest of loops to a loop of the form (1) can be carried out as follows.With a minimum size of the analyzed passes, internal loops (if necessary) are treated as being unwound into a linear sequence; with a maximum size of passes, the heading of the nest of loops is represented as DO KI=J, N, M, where K, I, J, N, and M are vectors, and a run through the values of vector I is simulated.For parallel programs executed in MINIMAX-type systems, branches are implemented in individual elementary machines. In allocating loop passes to different branches it is necessary to minimize exchange interactions taking place between machines. The simulation method makes it possible in such cases to disclose information allowing to make rational decisions.Translated from Kibernetika, No. 3, pp. 28–33, May–June, 1981.