Decidable Dataflow Models for Signal Processing: Synchronous Dataflow and Its Extensions - Signal Processing Systems - page 1070

Buffering requirements can be reduced if we use buffer sharing. Arc buffers can
be shared if their life-times are not overlapped with each other during an iteration of
the schedule. The life-time of an arc buffer is defined by a set of durations from the
source node invocation that starts producing a sample to the buffer to the completion
of the destination node that empties the buffer. Consider schedule

Σ 1ofFig. 2 . The

buffer life-time of arc BC consists of two durations, , in the schedule.

Since the buffer of arc AD is never empty, the buffer life-time of arc AD is the entire
duration of the schedule. If we remove the initial sample on arc AD, the buffer life-
time of arc AD consists of three durations,

{ BCC, BCC }

. Then we can share the
two arc buffers of arc AD and arc BC since their life-times are not overlapped. A
more aggressive buffer sharing technique has been developed by separating global
sample buffers and local pointer buffers in case the sample size is large in frame-
based applications [ 13 ] . The key idea is to allocate a global buffer whose size is
large enough to store the maximum amount of live samples during an iteration of
the schedule. Each arc is assigned a pointer buffer that stores pointers to the global
buffer.
Code size can also be reduced by sharing the kernel of a function block when
there are multiple instances of the same block [ 22 ] in a dataflow graph. Multiple
instances of the same block are regarded as different blocks, and the same kernel,
possibly with different local states, may appear several times in the generated
code. A technique has been proposed to share the same kernel by defining a
shared function. Separate state variables and buffers should be maintained for each
instance, which define the context of each instance. The shared function is called
with the context of an instance as an argument at the scheduled position of the
instance. To decide whether sharing a code block is beneficial or not, the overhead
and the gain of sharing should be compared. If

{ AD, AD, AD }

is an overhead that is incurred by
function sharing, R is a code block size, and n is the number of instances of a block,
the decision function for code sharing is summarized as the following inequality:
Δ

Δ

1.
For more detailed information on the code generation procedure and other issues
related with software synthesis from SDF graphs, refer to [ 2 ] .

R < ( n − 1 )

2.3 Static Scheduling Techniques

Static scheduling of an SDF graph is the key technique of static analysis that
checks the consistency of the graph and determines the memory requirement of
the generated code. Since an SDF graph imposes only partial ordering constraints
between the nodes, there exist many valid schedules and finding an optimal schedule
has been actively researched.