Polyhedral Process Networks - Signal Processing Systems - page 1345

before this read and let R be the relation mapping the same read iteration to all
previous read iterations, i.e.,

w | w ∈ w ) ≺

W = { r → r ∈ ran M ∧ dom M ∧ S ( S ( r ) } (17)

r | r ∈ r ≺ R = { r → r , ran M ∧ r }. (18)

Then the number n of elements in the buffer right before the execution of read r

is the number of writes to the buffer before the read, i.e., # W

( s , r )

( s , r ) , minus the number

of reads from the buffer before the given read, i.e., # R , where as usual, s are

the parameters. Both of these computation can be performed using Operation 3
(Number of Image Elements). Finally, we apply Operation 4 (Upper Bound on a
Quasi-Polynomial) to the piecewise quasi-polynomial n

( s , r )

( s , r )= # W ( s , r ) − # R ( s , r )

and the polyhedral set ran M , resulting in a piecewise quasi-polynomial u that is

an upper bound on the number of elements in the FIFO channel during the whole
execution.

( s )

Example 23. Consider once more the network in Fig. 2 . A global schedule for
this network was derived in Examples 18 and 19 , and code corresponding to this
schedule is shown in Fig. 12 . Writing the mapping ( 10 ) on the channel constructed
from the first argument to the call to Sobel in Line 6 of Fig. 1 in Example 14 in
terms of the scheduled iterators, we obtain

i , j , i = j = M = { ( 0 ) → ( i , j , 1 ) | 2 ≤ i < K ∧ 2 ≤ j < N ∧ i − 2 ∧ j − 2 }.

From this relation we derive,

i , j ,

= { ( , , ) → ( ) | ≤ < ∧ ≤ < ∧

W i j 1 0 2 i K 2 j N

i < j <

≤ − ∧ ≤ − ∧

0 K 2 0 N 2

i < i = j ≤

(( i ) ∨ ( i ∧ j )) }.

The number of image elements of this relation can be computed as

⎧
⎨

i ( N − 2 )+ j + 1 f ( i , j , 1 ) ∈ ran M ∧ i < K − 2 ∧ j < N − 2

# W ( K , N , i , j )=

( i + 1 )( N − 2 ) if ( i , j , 1 ) ∈ ran M ∧ i < K − 2 ∧ j ≥ N − 2

⎩

( K − 2 )( N − 2 ) if ( i , j , 1 ) ∈ ran M ∧ i ≥ K − 2 .

For the number of reads before a given read ( i , j , 1 ) , we similarly find

(

# R ( K , N , i , j )=

i − 2 )( N − 2 )+ j − 2 f ( i , j , 1 ) ∈ ran M .