Digital Signal Processing Reference
In-Depth Information
1
for(i=0;i<K;i++)
2
for(j=0;j<N;j++) {
a[i][j] = ReadImage();
3
if(i>=2&&j>=2){
4
Sbl[i-1][j-1]=Sobel(a[i-2][j-2],a[i-1][j-2],a[i][j-2],
5
a[i-2][j-1],a[i-1][j-1],a[i][j-1],
6
a[i-2][ j],a[i-1][ j],a[i][ j]);
7
WriteImage(Sbl[i-1][j-1]);
8
}
9
}
10
Fig. 12
Merged code for the process network of Fig.
2
7.3
Blocking Writes
In deriving combined schedules, we have so far only been interested in avoiding
deadlocks. When merging several processes into a single process this is indeed
all we need to worry about. However, when using a global schedule during the
computation of valid buffer sizes, we may end up with buffer sizes that, while
not introducing any deadlocks, may impose blocking writes, impacting negatively
on the throughput of the network. In particular, iterations of different processes
that are mapped onto the same iteration in the global schedule (ignoring the extra
innermost dimension), can usually be executed in a pipelined fashion, except when
non-adjacent processes in this pipeline communicate with each other. In this case,
the computed buffer sizes may be so small that the first of these non-adjacent
processes needs to wait until the second reads from the communication channel
before proceeding onto the next iteration.
The solution is to enforce a delay between a writing process and the correspond-
ing reading process that is equal to one iteration of the writing process. This delay
ensures that the delay between non-adjacent processes in a pipeline will be large
enough to avoid blocking writes that hamper the throughput. The required delay is
the smallest variation in the iteration domain
D
of a process. Let
P
be the relation
that maps a given iteration of
D
to the previous iteration of
D
, i.e.,
i
|
i
∈
i
≺
P
(
D
)=
lexmax
{
i
→
i
,
D
∧
i
}.
(16)
The relation
P
can be computed using Operation
1
(Partial Lexicographic
Maximum). The required delay
(
D
)
η
is then the smallest difference between two
subsequent iterations, i.e.,
i
)
∈
i
}.
η
=
lexmin
{
t
|∃
(
i
→
P
(
D
)
∧
t
=
i
−
The delay is enforced by subtracting the
η
corresponding to the writing process
from each channel delay
δ
