Digital Signal Processing Reference
In-Depth Information
which is also non-empty. In the second network, the channel between
b
and
c
has
mapping
M
b
→
c
=
{
b
(
w
)
→
c
(
r
1
,
r
2
)
|
0
≤
r
2
<
N
∧
r
1
=
0
∧
w
=
r
2
}.
(12)
There is no multiplicity since each write corresponds to exactly one read. There is
also no reordering, since the writes and reads occur for increasing values of
w
=
r
2
in both processes.
6.3
Internal Channels
Internal channels, i.e., channels from a process to itself, can typically be imple-
mented more efficiently than external channels. In particular, since processes are
scheduled independently there is no guarantee that when a value is read, it is already
available, or that when a value is written, there is still enough room in the channel
to hold the data. The external channels therefore need to implement both blocking
on read and blocking on write. For internal channels, there is no need for blocking.
In fact, blocking would only lead to deadlocks. Besides the blocking issue, there
are some special cases that allow for a more efficient implementation than a general
FIFO buffer.
6.3.1
Registers
The first special case is that where the FIFO buffer holds at most one value. The
FIFO buffer can then be replaced by a register. In Sect.
8
we will see how to compute
a bound on a FIFO buffer in general, but the case where this bound is one can
be detected in a simpler way. If each write
w
1
to a channel is followed by the
corresponding read
r
1
, without any other read occurring in between, then we indeed
only need room for one value. On the other hand, if there
is
an intervening read,
w
1
≺
r
1
, then we will need more storage space. As usual, we can detect this
situation by performing an emptiness check. Consider the set
r
2
≺
=
{
|∃
,
(
→
)
∈
∧
∈
∧
≺
≺
}.
T
w
1
r
1
r
2
:
w
1
r
1
M
r
2
ran
M
w
1
r
2
r
1
This set contains all writes
w
1
such that there exists a read
r
2
that occurs before
the read
r
1
that corresponds to the write
w
1
. Note that it is legitimate to compare
read and write iterations because we are dealing with internal channels and so these
iterations belong to the same iteration domain.
