Digital Signal Processing Reference
In-Depth Information
a
b
c
T1
T2
T3
DS1
DSn
DS 1
DSn
DS1
DS2
T1
Tn
T1
Fig. 7
Kinds of parallelism: (
a
)DLP,(
b
) TLP, (
c
)PLP
models provide support for DLP. For instance, an
OpenMP for
directive tells the
compiler or the runtime system that the iterations of the loop are independent
from each other and can therefore be parallelized.
Task (or functional) Level Parallelism
(TLP)
: In TLP different tasks can compute
Tasks may have dependencies to each other, but once a task has its data ready, it
can execute in parallel with the already running tasks in the system.
Pipeline Level Parallelism
(PLP)
: In PLP a computation is broken into a sequence
of tasks and these tasks are repeated for different data sets. In this sense, PLP can
be seen as a mixture of DLP and TLP. Following the principle of pipelining, a task
with DLP can be segmented in order to achieve a higher throughput. At a given
time, different tasks of the original functionality are executed concurrently on
different data sets. This kind of parallelism is e.g. exploited in the programming
models targeting network processors.
Exploiting these kinds of parallelism is a must for an MPSoC compiler, which has
to be therefore equipped with powerful flow and dependence analysis capabilities.
2.2.3
Flow and Dependence Analysis
Flow analysis includes both control and data flow. The result of these analyses can
be summarized in a CDFG, as discussed at the beginning of this section. Data flow
analysis serves to gather information at different program points, e.g. about available
defined variables (
reaching definitions
) or about variables that will be used later in
which a reaching definitions analysis is carried out. The analysis tells, for example,
that the value of variable
c
in line
5
can come from three different definitions in
lines
2
,
7
and
10
.
