Software Compilation Techniques for MPSoCs - Signal Processing Systems - page 1201

a

b

1: int b[N];
2: int A[4][N];
3: int c[4];
4:

b s

b[0]

c

A

ff1 ff2 ff3 ff4 sum

7: int i,j,s;

8:

s

b[0]

c

12:

b

s

b[0]

c

A

ff1 f2+f3 ff4 sum

s

21:}

Fig. 4 Sample program. ( a ) C implementation, ( b ) a “good” KPN representation. ( c ) A “bad”
KPN representation

the token consumption and production of an SDF actor are known beforehand, it is
possible for a compiler to compute a plausible static schedule for an SDF. For a KPN
instead, due to control dependent access to channels, it is impossible to compute a
pure static schedule.
Apart from explicitly exposing parallelism, dataflow programming models be-
came attractive mainly for two reasons. On the one hand, they are well suited
for graphical programming, similar to the block diagrams used to describe signal
processing algorithms. On the other hand, some of the underlying MoC's properties
enable tools to perform analysis and compile/synthesize the specification into
both software and hardware. Channels explicitly expose data dependencies among
computing nodes (processes or actors), and these nodes display a distributed control
flow which is easily mapped to different PEs.
To understand how dataflow models can potentially reduce the compilation
effort, an example of an application written in a sequential and in two parallel
forms is shown in Fig. 4 . Let us assume that the KPN parallel specification in
Fig. 4 b represents the desired output of a parallelizing compiler. In order to derive
this KPN from the sequential specification in Fig. 4 a , complex analyses have to be
performed. For example, the compiler needs to identify that there is no dependency
on array A among lines 11 and 16 (i.e. between processes f2 and f3 ), which
is a typical example of dataflow analysis (see Sect. 2.2.3 ) . Only for a restricted
subset of C programs, namely Static Affine Nested Loop Programs (SANLP), similar
transformations to that shown in Fig. 4 have been successfully implemented in [ 83 ] .
For more complex programs, starting from a parallel specification would greatly
simplify the work of the compiler.