Multidimensional Dataflow Graphs - Signal Processing Systems - page 1148

Fig. 16 Multidimensional

data data

FIFO

wr_req rd_req

empty

B C

full

wr_count rd_count

token . In other words, the read and write order is not the

same anymore, preventing the use of traditional FIFOs for communication synthesis.
However, as soon as the read and write orders are fixed, it is possible to embed
this kind of communication into a FIFO-like primitive, called multidimensional
FIFO . It provides the same interface than a classical FIFO as depicted in Fig. 16 .
The data ports transport the proper data in form of multidimensional arrays. In
other words, the data port for the read interface provides access to all data elements
belonging to the currently processed sliding window. The write interface accepts all
data elements that need to be written for the currently generated output token. A full
query reveals whether the source can write the next multidimensional output token.
Similarly, and empty query indicates whether the next sliding window is already
available or not. A write counter is able to predict how many multidimensional
tokens can be written by the source without any firing of the sink. Similarly, a read
counter indicates how many sliding windows can be accessed by the sink without
any further firing of the source.
In order to clarify the internal operation of the multidimensional FIFO, consider
again Fig. 15 . The processing order and thus the read and write orders are considered
to be fixed. Hence, after the first firing of actor B , the multidimensional FIFO can
derive that the first sliding window is available for actor C . The FIFO is hence not
empty anymore, and actor C can access all data elements belonging to this window.
Once the read operation is terminated, actor C can request a new read. Because of the
processing order of actor C , the next required data element is situated in the lower
left corner of the input array. Since it is not already available, an empty-condition
is signaled. This remains even true, when actor B fires the second time, because the
data element produced during this invocation is not the one required next by actor C .
Hence, the data element written by actor B needs to be buffered for later use. This
situation only changes after actor B has finished the fourth firing, resulting in the
data element required next by actor C . Note that this condition allows actor C to fire
twice, because all required data elements are already available.
By tracking which data elements will still be read later on by the sink, the
multidimensional FIFO can also perform the buffer management. This includes both
the decision at which address to write a given data element as well as taking care
that data elements will not be overwritten when still needed. The corresponding
principles can be implemented both in hardware and software. The mathematical
analysis necessary for this purpose can be found in [ 12 ] . Note that the same
principles can also be applied to examples where both the source and the sink
write or read tokens consisting of more than one data element. In particular, both
overlapping windows as well border processing discussed in Sect. 4 are supported.
It only requires to assume a fixed processing order, which might however vary for
the different actors of the dataflow graph.

( 0 , 1 ) after token ( 1 , 0 )