US 8,146,071 B2Granted

Pipelined parallelization of multi-dimensional loops with multiple data dependencies

AssigneeInternational Business Machines Corporation

InventorsRaul Esteban Silvera, Priya Unnikrishnan

Life of this patent

Estimating the term…

Loading patent…

Abstract

A mechanism for folding all the data dependencies in a loop into a single, conservative dependence. This mechanism leads to one pair of synchronization primitives per loop. This mechanism does not require complicated, multi-stage compile time analysis. This mechanism considers only the data dependence information in the loop. The low synchronization cost balances the loss in parallelism due to the reduced overlap between iterations. Additionally, a novel scheme is presented to implement required synchronization to enforce data dependences in a DOACROSS loop. The synchronization is based on an iteration vector, which identifies a spatial position in the iteration space of the loop. Multiple iterations executing in parallel have their own iteration vector for synchronization where they update their position in the iteration space. As no sequential updates to the synchronization variable exist, this method exploits a greater degree of parallelism.

Claims20

Dependent claims

A computer-implemented method for preparing a loop in a set of loops in computer code for parallel processing, the computer-implemented method comprising:

identifying the loop by identifying which loop in the set of loops will, during execution thereof, have an iteration vector bounded by an iteration space of the loop, wherein all data dependencies are contained within the loop;
representing each data dependency as a corresponding dependency vector Dk having elements (dk1, dk2, . . . dkn), wherein a set of dependency vectors are formed;
using the set of dependency vectors to compute a result vector C having elements c1, c2, . . . cn);
for each corresponding dependency vector in the set of dependency vectors that satisfies the equation:
C
→
=
(
C
⁡
[
1
]
C
⁡
[
2
⁢
⁢
…
⁢
⁢
n
]
)
⁢
⁢
=
(
g
⁢
⁢
c
⁢
⁢
d
⁡
(
d
1
1
,
d
1
2
,
…
⁢
⁢
d
1
k
)
max_vect
⁢
(
D
1
⁡
[
2
⁢
⁢
…
⁢
⁢
n
]
,
D
2
⁡
[
2
⁢
⁢
…
⁢
⁢
n
]
,
…
⁢
⁢
D
k
[
2
⁢
⁢
…
⁢
⁢
n
)
]
)
inserting into the loop a call to a WAIT(wI) primitive immediately prior to a lexically earliest sink statement in the loop, wherein:
“I” will represent a current value of the loop iteration vector for the loop;
(wI) is computed as wI=(I−C);
invocation of the WAIT(wI) primitive, where (wI) is within the iteration space of the loop, will, during execution of the loop, cause a first thread which processed the WAIT(wI) instruction to suspend until invocation by a second thread of a POST(pI) primitive for which pI is equal to or greater than wI for a value of (wI for which the WAIT(wI) primitive was invoked by the first thread;
invocation of the WAIT(wI) primitive, where (wI) is outside the iteration space of the loop, will be ignored;
and
inserting into the loop the POST(pI) primitive immediately following a lexically latest source statement in the loop, wherein pI=I.

102 more elements

A computer program product comprising:

a computer usable medium having computer usable program code for preparing a loop in a set of loops in computer code for parallel processing, the computer program product including:
computer usable program code for identifying the loop by identifying which loop in the set of loops will, during execution thereof, have an iteration vector bounded by an iteration space of the loop, wherein all data dependencies are contained within the loop;
computer usable program code for representing each data dependency as a corresponding dependency vector Dk having elements (dk1, dk2, . . . dkn), wherein a set of dependency vectors are formed;
computer usable program code for using the set of dependency vectors to compute a result vector C having elements c1, c2, . . . cn);
computer usable program code for, for each corresponding dependency vector in the set of dependency vectors that satisfies the equation:
C
→
=
(
C
⁡
[
1
]
C
⁡
[
2
⁢
⁢
…
⁢
⁢
n
]
)
⁢
⁢
=
(
g
⁢
⁢
c
⁢
⁢
d
⁡
(
d
1
1
,
d
1
2
,
…
⁢
⁢
d
1
k
)
max_vect
⁢
(
D
1
⁡
[
2
⁢
⁢
…
⁢
⁢
n
]
,
D
2
⁡
[
2
⁢
⁢
…
⁢
⁢
n
]
,
…
⁢
⁢
D
k
[
2
⁢
⁢
…
⁢
⁢
n
)
]
)
inserting into the loop a call to a WAIT(wI) primitive immediately prior to a lexically earliest sink statement in the loop, wherein:
“I” will represent a current value of the loop iteration vector for the loop;
(wI) is computed as wI=(I−C);
invocation of the WAIT(wI) primitive, where (wI) is within the iteration space of the loop, will, during execution of the loop, cause a first thread which processed the WAIT(wI) instruction to suspend until invocation by a second thread of a POST(pI) primitive for which pI is equal to or greater than wI for a value of (wI for which the WAIT(wI) primitive was invoked by the first thread;
and
invocation of the WAIT(wI) primitive, where (wI) is outside the iteration space of the loop, will be ignored;
and
computer usable program code for inserting into the loop the POST(pI) primitive immediately following a lexically latest source statement in the loop, wherein pI=I.

104 more elements

A data processing system comprising:

a bus;
at least one processor coupled to the bus;
a computer usable medium coupled to the bus, wherein the computer usable medium contains a set of instructions for preparing a loop in a set of loops in computer code for parallel processing, wherein the at least one processor is adapted to carry out the set of instructions to:
identify the loop by identifying which loop in the set of loops will, during execution thereof, have an iteration vector bounded by an iteration space of the loop, wherein all data dependencies are contained within the loop;
represent each data dependency as a corresponding dependency vector Dk having elements (dk1, dk2, . . . dkn), wherein a set of dependency vectors are formed;
use the set of dependency vectors to compute a result vector C having elements c1, c2, . . . cn);
for each corresponding dependency vector in the set of dependency vectors that satisfies the equation:
C
→
=
(
C
⁡
[
1
]
C
⁡
[
2
⁢
⁢
…
⁢
⁢
n
]
)
⁢
⁢
=
(
g
⁢
⁢
c
⁢
⁢
d
⁡
(
d
1
1
,
d
1
2
,
…
⁢
⁢
d
1
k
)
max_vect
⁢
(
D
1
⁡
[
2
⁢
⁢
…
⁢
⁢
n
]
,
D
2
⁡
[
2
⁢
⁢
…
⁢
⁢
n
]
,
…
⁢
⁢
D
k
[
2
⁢
⁢
…
⁢
⁢
n
)
]
)
insert into the loop a call to a WAIT(wI) primitive immediately prior to a lexically earliest sink statement in the loop, wherein:
“I” will represent a current value of the loop iteration vector for the loop;
(wI) is computed as wI=(I−C);
invocation of the WAIT(wI) primitive, where (wI) is within the iteration space of the loop, will, during execution of the loop, cause a first thread which processed the WAIT(wI) instruction to suspend until invocation by a second thread of a POST(pI) primitive for which pI is equal to or greater than wI for a value of (wI for which the WAIT(wI) primitive was invoked by the first thread;
invocation of the WAIT(wI) primitive, where (wI) is outside the iteration space of the loop, will be ignored;
and
insert into the loop the POST(pI) primitive immediately following a lexically latest source statement in the loop, wherein pI=I.

105 more elements

Dependencies are inferred from the claim text.