Dynamic Dataflow Graphs - Signal Processing Systems - page 915

7.4 Parameterized Polyhedral Process Networks

Parameters that appear in a SANLP program are static. In a DANLP, parameters can
be dynamic. A polyhedral process network [ 73 ] that is input-output equivalent to
such a DANLP program is, then, a parameterized polyhedral process network called
P 3 Nin[ 78 ] .

Remark. There are two assumptions here. First, dynamic conditions, dynamic loop
bounds and dynamic while-loops are left out to focus only on dynamic parameters.
Second, values of the dynamic parameters are obtained from the environment.
The formal definition of a P 3 Nisgivenin[ 78 ] , and is only slightly different from
the definition given in [ 73 ] . Although the consistency of a P 3 N has to be checked
at run-time, still some analysis can be done at compile-time. A simple example of a
P 3 N is shown in Fig. 18 .
Figure 18 a is a static PPN, process P3 of which is shown in Fig. 18 b . Figure 18 c
is a P 3 N version of the PPN in Fig. 18 a . Process P 3oftheP 3 NinFig. 18 c isshown
in Fig. 18 d . The PPN and the P 3 Nhavethesame dataflow topology. Processes P2
and P3 in the P 3 NinFig. 18 c are reconfigured by two parameters M and N whose
values are updated from the environment at run-time using process Ctrl and FIFO
channels ch7 , ch8 ,and ch9 .TheP 3 N shown in Fig. 18 c may be derived from a
sequential program, yet it can also be constructed from library elements as in [ 31 ] .
Recall from [ 73 ] that a parametric polyhedron P ( p ) is defined as

d + 1 T m × d

P ( p )= { ( w , x 1 ,..., x d ) ∈ Q | A · ( w , x 1 ,..., x d ) ≥ B · p + b } with A ∈ Z , B ∈

m . For nested loop programs, w is to be interpreted as the one-
dimensional while(1) index, and d as the depth of a loop nest. For a particular
value of w the polyhedron gets closed, i.e., it becomes a polytope. The parameter
vector p is bounded by a polytope

m × n

Z and c ∈ Z

n

.
The domain D P of a process is defined as the set of all integral points in its
underlying parametric polyhedron, i.e., D P = P P (

P p = { p ∈ Q | C · p ≥ d }

1 . The domains D IP and
D OP of an input port IP and an output port OP , respectively, of a process are
subdomains of the domain of that process.
The following four notions play a role in the operational semantics of a P 3 N:

d +

p ) ∩ Z

￿ Process iteration.

￿ Process cycle.

￿ Process execution.

￿ Quiescent point.

A process iteration of process P is a point D P , where the following

operations are performed sequentially: reading a token from each IP for which
(

( w , x 1 ,..., x d ) ∈

w , x 1 ,..., x d ) ∈ D IP , executing process function F P , and writing a token to each

OP for which ( w , x 1 ,..., x d ) ∈ D OP .

A process cycle CYC P ( S, p ) ⊂ D P is the set of lexicographically ordered points

= S ∈ Z + . The lexical ordering is typically imposed ∈ D P for a particular value of w

by a loop nest.