Polyhedral Process Networks - Signal Processing Systems - page 1319

The extraction of a polyhedral model from a sequential program is available in
several modern industrial and research compilers, e.g., [ 1 , 10 , 17 , 19 ] .

Example 7. The parse_file operation of iscc parses a C file and constructs
a polyhedral model that is similar to that of Definition 4 . In particular, it returns a
list with four elements. The first contains the union of all iteration domains. The
second contains the union of all write access relation. The third contains the union
of all read access relation. The final element contains the schedule. Applying this
operation to the program in Fig. 8 (with the required declarations), results in the
following output. The program will be discussed in more detail in Sect. 6.1 .

([N] -> { S1[i] : i >= 0 and i <= N;
S2[i] : i >= 0 and i <= N },
[N] -> { S1[i] -> a[i] : i >= 0 and i <= N;
S2[i] -> b[i] : i >= 0 and i <= N },
[N] -> { S2[i] -> a[N - i] : i >= 0 and i <= N },
[N] -> { S2[i] -> [4, i]; S1[i] -> [3, i] })

3.4 Piecewise Quasi-Polynomials

As explained in Sect. 2 , each channel in the process network has a buffer of a
bounded size. If the network is parametric, then this bound will in general not simply
be a number, but rather an expression in the parameters. Some of the intermediate
steps in computing these bounds may also result in expressions involving both the
parameters and the iterators, or just the iterators if the network is non-parametric. In
both cases the expressions will be piecewise quasi-polynomials . Quasi-polynomials
are polynomial expressions that may involve integer divisions of affine expressions
in the variables. Piecewise quasi-polynomials are quasi-polynomials defined over
polyhedral pieces of the domain. More formally, they can be defined as follows.

Definition 5 (Quasi-Polynomial). A quasi-polynomial q in the integer vari-

ables x is a polynomial expression in greatest integer parts of affine expressions
in the variables, i.e., q

( x )

( x ) ∈ Q[ Q[ x ] ≤ 1 ] .

A note on the notation used in this definition. ]

is the set of polynomial expressions in z . A subscript on this notation indicates a
bound on the degree. That is,

Q is the set of rational numbers. Q[ z

] ≤ 1 represents the degree-1 polynomials in x ,i.e.,
the affine expressions in x . Here, we take the greatest integer part of each of these
affine expressions and then consider the polynomial expressions in those greatest
integer parts

Q[ x

Definition 6 (Piecewise Quasi-Polynomial). A piecewise quasi-polynomial q ( x ) ,

d d ,

with x ∈ Z consists of a finite set of pairwise disjoint polyhedral sets K i ⊆ Q

each with an associated quasi-polynomial q i ( x ) . The value of the piecewise quasi-

polynomial at x is the value of q i ( x ) with K i the polyhedral set containing x , i.e.,