scientific article; zbMATH DE number 3845030

From MaRDI portal
Publication:3314970





[For the entire collection see Zbl 0495.00002.] This paper presents one of the problems of converting a sequential program into an equivalent parallel program. The author discusses possibilities of transforming a simple repetitive statement found in the program into many such statements of the same form but covering different, i.e. independent, sets of variables taking part in the statement. The statement is considered simple if references to variables concerned may be represented by indices of the form \(ax+b\), where x is the controlled variable of the repetition with the step 1. Two such variables are then considered dependent if their indices are of the same value and at least one of the variables is being assigned to. For two different repetitions with control variables x and y respectively the dependency condition can be written as \(x\neq y\bigwedge(ax+b=\alpha y+\beta \vee \alpha x+\beta =ay+b)\). The question asked in the paper is how many independent repetitions we can get from the one found in the sequential program; in other words, how many processors can be effectively utilized in the case of a simple repetition. As an answer to the question the author presents 9 theorems and their proofs where the number sought is defined as depending on certain relations between a, b, \(\alpha\) and \(\beta\).












This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3314970)