Multidimensional Dataflow Graphs - Signal Processing Systems - page 1125

While such a polyhedral analysis is only possible for static algorithms, mul-
tidimensional dataflow by itself does not suffer from this limitation. Instead it
also permits the representation of dynamic decisions similar to one-dimensional
dynamic dataflow [ 10 ] . Furthermore models can be created that contain both one-
and multidimensional communication. Usage of finite state machines as explained
in [ 4 ] helps to classify different actor behaviors. All these aspects are explained in
Sect. 7 . As illustrated in Fig. 1 , Sects. 6 and 7 can be consulted independently of
each other.
Section 8 finally concludes this chapter addressing the generalization of sampling
patterns using a matrix notation. Consequently, it links the left and right parts of the
tree depicted in Fig. 1 .

2 Basics

MDSDF is—in principle—a straightforward extension of SDF. Figure 2 shows a
simple example.
Actor A produces three tokens taken from three rows and a single column out of
an array of tokens. We say that actor A produces

tokens. Actor B consumes
three tokens taken from three columns and a single row. We say that actor B
consumes

( 3 , 1 )

tokens. The SDF 1D repetitions vector [ 7 ] becomes a repetitions
matrix in the MDSDF case:

( 1 , 3 )

r A , 1 r A , 2
r B , 1 r B , 2

= .

R

r A , 1 defines the number of executions or firings of actor A in vertical direction
(rows). r A , 2 equals the number of firings in horizontal dimension (columns). r B , 1
and r B , 2 do the same for actor B . Every firing of actor A yields in a ( 3 , 1 ) token with

3 3

data elements. Demanding that the number of produced and read data elements shall
be the same in all dimensions leads to the following balance equation:

× 1 data elements , and every execution of actor B reads a ( 1 , 3 ) token with 1 ×

r A , 1 × 3 (rows) = r B , 1 × 1 (row)

r A , 2 × 1(column) = r B , 2 × 3(columns)

(3,1) (1,2) (1,3)

initial

A B

2

5
6

Fig. 2 A simple two-actor
MDSDF graph

4 3 1