Multidimensional Dataflow Graphs - Signal Processing Systems - page 1151

RepetitiveComponent

Tiler
= (0,0) T
F =

o

ElementaryComponent

s repetition = (3,2) T 2 0

0 1

3 0
0 3

P =

s array
= (9,6) T

s pattern = (2,3) T

s array
= (9,8) T

s pattern =(3,4) T

s array
= (2,3) T

Tiler
= (0,0) T
F =

s pattern = (1,1) T

o

Tiler
= (0,0) T

o 1 0

0 1

3 0
0 4

P =

1 0
0 1

0 1
1 0

F = P =

Fig. 18 Specification of repetitive tasks via tilers [ 5 ] . Each port is annotated with the produced
and consumed array size. The number of sub-task invocations is defined by vector s repetition .The
tiler associated to each communication edge specifies the extraction of sub-arrays

methodology. Originally developed by Thomson Marconi Sonar , 8 Array-OL serves
as model of computation for the Gaspard2 design flow and has also been integrated
into the Ptolemy framework [ 3 ] . Applications are modeled as a hierarchical task
graph consisting of (i) elementary , (ii) hierarchical , and (iii) repetitive tasks.
Elementary tasks are defined by their input and output ports as well as an associated
function that transforms input arrays on the input ports to output arrays on the
output ports. Hierarchical tasks connect Array-OL sub-tasks to acyclic graphs. Each
connection between two tasks transports a multidimensional array.
Repetitive tasks as shown exemplarily in Fig. 18 are finally the key element for
expressing data-parallelism. In principle they represent special hierarchical tasks in
which a sub-task is repeatedly applied to the input arrays. Since the different sub-
task invocations are considered as independent if not specified otherwise, they can
be executed in parallel or sequentially in any order. So-called input tilers specify for
each sub-task invocation the required part of the input arrays. These sub-arrays are
also called patterns or tiles . The produced results are combined by output tilers to
the resulting array.
Each tiler is defined by a paving and a fitting matrix as well as an origin vector
o (see Fig. 18 ) . The paving matrix P permits to calculate for each task invocation i
the origin of the input or output pattern:

∀ i , 0 ≤ i < s repetition : o i = o + P · i mod s array

s repetition defines the number of repetitions for the sub-task. s array is the size of the
complete array, the modulo operation takes into account that a toroidal coordinate
system is assumed. In other words, patterns that leave the array on the right border

8 Now Thales.