Polyhedral Process Networks - Signal Processing Systems - page 1329

the appropriate communication channel, we will have essentially constructed the
communication channels. The effect of dataflow analysis can be described as the
following operation.

Operation 7 (Dataflow Analysis).
Input: ￿

n d a

A read access relation R ⊆ Z → ( Σ × Z ) → ( Σ × Z )

n d i a

￿ A list of [write] access relations W i ⊆ Z → ( Σ × Z ) × ( Σ × Z )

→ ( Σ × i Z

n d i k

￿ A schedule S ⊆ Z ) → ( Σ × Z ) such that dom ( R ∪

i W i ) ⊆

dom S

n d i d

Output: ￿ A list of polyhedral relations M i ⊆ Z → ( Σ × Z ) → ( Σ × Z )

n d

￿ A polyhedral set U ⊆ Z → ( Σ × Z )

The output satisfies the following constraints

￿ Each element in the domain of R is an element either of U or of the range of

exactly one of the mappings M i , i.e., { ran M i } ∪{ U } partitions dom R,

i

￿ If a particular element in the domain of R is in the range of one of the mappings,

i.e., ( j ) ∈ dom R ∩ ran M k , then the corresponding [write] iteration of W k ,i.e.,

M − 1
k

, was the last iteration (according to the schedule S) in any of the
domains of the input access relations W i that accessed the same array element as
(

( ( j ))

j ) , [i.e., it wrote the value read by ( j ) ] and was executed before ( j ) ,

￿ If a read iteration belongs to U , i.e., U , then this iteration accesses

an array element that was not accessed by any of the W i , [i.e., this iteration reads
an uninitialized value].

( j ) ∈ dom R ∩

Operation 7 (available in isl ) is applied for each read access in the program. The
list of access relations required in the input is constructed from all write accesses in
the program that access the same array. For each M i 0, a communication channel

is created from the process corresponding to the writing statement to the process
corresponding to the reading statement, with the given M i as mapping. The type and
buffer size are defined in the following sections. The set U in the output is assumed
to be empty.
We will now briefly sketch how Operation 7 can be implemented. For this
purpose, we will assume that the access relations have been scheduled, i.e., that
the schedule S has been applied to the domains of the access relations. We will
further assume that the input contains a single (scheduled) write access relation W .
The composition of the read access relation with the inverse of the write access
relation yields a mapping from read iterations to write iterations that wrote to the
array element accessed by the read. The one that actually wrote the value that is
read, is the one that was the (lexicographically) last to write to the element before
the read. That is, we want to compute
lexmax (

=

1 ,

W − 1 L − 1

2 d

◦ R ) ∩

+

with L 2 d + 1 the lexicographically smaller relation from ( 5 ) . The result of this
computation is the inverse of the relation M in the output.