Browse Prior Art Database

Sequential to Parallel Transformation Algorithm

IP.com Disclosure Number: IPCOM000079779D
Original Publication Date: 1973-Sep-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 5 page(s) / 29K

Publishing Venue

IBM

Related People

Nowotny, E: AUTHOR [+2]

Abstract

A stepwise transformation process translating flow diagrams into parallel programs is described. The transformation process can be subdivided into the following principal steps: (a) The scopes of the decisions are delimited by determining the immediate postdominator for each decision. (b) A global production system describing the control flow of the sequential program is set up. (c) To describe the data flow of the program, local production systems according to the different data variables are derived from the global production system. This set of local production systems forms a parallel program which, for each value assignment, yields the same result as the original flow diagram.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 39% of the total text.

Page 1 of 5

Sequential to Parallel Transformation Algorithm

A stepwise transformation process translating flow diagrams into parallel programs is described. The transformation process can be subdivided into the following principal steps:
(a) The scopes of the decisions are delimited by determining the

immediate postdominator for each decision.
(b) A global production system describing the control flow of the

sequential program is set up.
(c) To describe the data flow of the program, local production

systems according to the different data variables are derived

from the global production system.

This set of local production systems forms a parallel program

which, for each value assignment, yields the same result as the

original flow diagram.

The sequential program to be transformed by the Sequential to Parallel Transformation Algorithm cSTPTA& is expressed in flow diagram form. Only the following boxes are assumed to occur in the flow diagram:
(a) A begin and an end box
(b) Assignment boxes (oblong-shaped)
(c) Decision boxes (pie-shaped) Those boxes are connected by directed edges. The flow diagram begins with a begin box and terminates with an end box. An arbitrary box is generally preceded by more than one box (as a result of the implicit occurrence of goto statements) and is succeeded by only one box, if it is an assignment box, and by n boxes, if it is a decision box. For the sake of simplicity, some further restrictions are assumed" (aa) Only simple data variables are considered. (bb) Only data variables are allowed to occur in an argument position. (cc) Superfluous boxes must not be included in the flow diagram. (dd) Unconditional loops must not be included either. (ee) The immediate successors of a decision have to be different from

one another.

The Transformation Algorithm includes the following steps: D1 A box T is a successor of a box S, if T is the target of an edge rooting in S.

D2 A path is a sequence of boxes each of which is either the begin

box of the path or the successor of the box preceding it.

D3 A box T is a postdominator of a box S, if each path from S to the end box contains T.

D4 A box T is the immediate postdominator of a box S, if T is a postdominator of S, and if in each nonlooping path (i.e., a path in which no boxes appear twice) from S to the end box, T is the

postdominator of S occurring first.

P1 To compute the immediate postdominator for a box K, first an arbitrary nonlooping path from box K to the program end box is

1

Page 2 of 5

constructed. The path contains all postdominators of K and the

one closest to K on the path (which generally is not identical

to the box nearest to K) is its immediate postdominator. Then

the box nearest to K is removed from the path if there is a

chain

of successors from K to a more remote box on the path (i.e., a

chain which does not extend through the nearest box). The

closest

box remaining on the path after boxes have been repeatedly

removed

in this way is the immediate postdomina...