Polyhedral Process Networks - Signal Processing Systems - page 1324

4.3 Parametric Counting

An important step in the buffer size computation is the computation of the number
of elements in the buffer before a given read. We will be able to reduce this
computation to that of counting of the number of elements in the image of a
polyhedral relation R , denoted # R , for which we will use the following operation.

Operation 3 (Number of Image Elements).
Input: a polyhedral relation R :

→ Σ × Z

d 1 → Σ × Z d 2 → B n

Z

Output: a piecewise quasi-polynomial
q :

n d 1

Z → ( Σ × Z ) → Q : ( s , ( t )) → q ( s , ( t )) = # R ( s , ( t ))

Example 11. Consider the set D 1 from ( 2 ) inExample 3 . Applying Operation 3
to this polyhedral set results in the piecewise quasi-polynomial of Example 8 . In
iscc , we can perform

card [N] -> { S1[i] : 0 <= i < N and i % 3 = 0 };
to obtain

[N] -> { ([(2 + N)/3]) : N >= 1 }

Operation 3 can be performed using barvinok [ 23 , 25 ] .

4.4 Computing Parametric Upper Bounds

As explained in the previous section, Operation 3 can be used to compute the
number of elements in a buffer at any given time. When allocating memory for
this buffer, we need to know the maximal number of elements that will ever have to
reside in the buffer. As usual, we want to perform this computation parametrically.
In general, computing the actual maximum may be too difficult, however. We
therefore settle for computing an upper bound that is hopefully reasonably close
to the maximum.

Operation 4 (Upper Bound on a Quasi-Polynomial).
Input: ￿

n d

A piecewise quasi-polynomial q : Z → ( Σ × Z ) → Q

n d

￿ A bounded polyhedral set S : Z → ( Σ × Z ) → B , the domain over

which to compute the upper bound
Output: A piecewise quasi-polynomial u :

n

Z → Q such that

u ( s ) ≥ max q ( s , ( t )) ∀ s ∈ pdom S

( t ) ∈ S ( s )