Digital Signal Processing Reference
In-Depth Information
−
(
−
Δ
)
Lexicographic Maximum) or even directly as
lexmax
. The minimal delay
i
1
→
2
over all communication channels
δ
i
{
δ
{
δ
}
=
|
δ
≺
δ
<
δ
>
},
lexmin
j
for all
j
i
and
δ
j
for all
j
i
i
i
i
i
i
where both
i
and
j
range over all communication channels between the two
processes. That is, we select
δ
i
for the values of the parameters where it is
strictly smaller than all previous
δ
j
and smaller than or equal to all subsequent
δ
j
. The result is a polyhedral set that contains a single vector for each value of the
parameters.
Finally, we need to deal with the fact that the above procedure can set the
delay over a channel to zero, which means that the write and corresponding read
would happen simultaneously. The solution is to assign an order of execution to
the statements
within
a given iteration by introducing an extra innermost dimension
topological sort of a direct graph with as only edges those communication channels
There are nine channels between the two processes. For one of these channels, we
on this channel is constant and we obtain
{
δ
1
}
=
Δ
1
=
{
(
1
,
1
)
}
. The other channels
1
→
2
also have constant delays and the smallest of these yields
δ
=(
−
1
,−
1
)
.We
1
,
1
)
, resulting in a
1
→
2
new
. To make this delay lexicographically positive (rather than just
non-negative), we introduce an extra dimension and assign it the value 0 in
P
1
and
1in
P
2
. The new (scheduled) iteration domains are therefore
δ
of
(
0
,
0
)
3
D
1
=
{
(
i
,
j
,
0
)
∈
Z
|
0
≤
i
<
K
∧
0
≤
j
<
N
},
3
D
2
=
{
(
i
,
j
,
1
)
∈
Z
|
2
≤
i
<
K
∧
2
≤
j
<
N
}.
The corresponding schedule is
{
R
(
i
,
j
)
→
(
i
,
j
,
0
)
|
0
≤
i
<
K
∧
0
≤
j
<
N
}∪
{
S
(
i
,
j
)
→
(
i
+
1
,
j
+
1
,
1
)
|
1
≤
i
<
K
−
1
∧
1
≤
j
<
N
−
1
}.
7.2
More than Two Processes
If there are more than two processes in the network, then we can still apply
essentially the same technique as that of the previous section, but we need to be
careful about how we define the minimal delay
1
→
2
δ
