Page 113 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes The construction of rate-optimal schedules involves explicit or implicit retiming and unfolding.
Unfolding turns f consecutive iterations into a cycle in the unfolded graph. f is called the unfolding
factor. Unfolding can lead to a rate optimal schedule, at the cost of multiplying the problem
space by the unfolding factor. An unfolding factor is called an optimal unfolding factor if a rate-
optimal schedule exists with the factor. Combined with retiming, a smaller optimal unfolding
factor may be obtained.
Much work has been done on static rate-optimal scheduling of homogenous synchronous
dataflow graphs (HSDFGs), which is a special type of SDFGs. All sample rates of actors of an
HSDFG are one. In an iteration of an HSDFG, each actor acts once.

Little work, however, is concerned with general SDFGs. Theoretically, it is always possible to
convert an SDFG to its equivalent HSDFG and then use the available methods for HSDFGs.
However, converting an SDFG to an HSDFG is very time-consuming when SDFGs scale up. The
size of the HSDFG can be exponentially larger than the original SDFG in extreme cases. To the
best of our knowledge, only discusses the rate-optimal scheduling of SDFGs. It converts an
SDFG to a precedence graph, which is a reduced form of its equivalent HSDFG, then computes
the unfolding factor and schedules the precedence graph with the same method as. A precedence
graph of an SDFG has less edges than and the same number of actors as its equivalent HSDFG.
The conversion procedure is still time and space-consuming.

Did u know? Many digital signal processing algorithms, like the digital IIR-filter are
naturally described by data flow graphs.

Figure 11.1: Figure (a) The SDFG G1, where the sample rates are omitted when
they are 1 and the computation time of each actor is attached inside the node;
(b) the equivalent HSDFG of G1.

Source: http://www.es.ele.tue.nl/~mgeilen/publications/rtas2012final.pdf
A synchronous dataflow graph (SDFG) is a finite directed graph G = ,V,E,t,d, prd, cns>, in which
V is the set of actors, modelling the functional elements of the system; E is the set of directed
edges, modelling interconnections between functional elements. Each actor v is weighted with
its computation time t(v), a nonnegative integer. Each edge e is weighted with three properties:
d(e), a nonnegative integer that represents the number of initial tokens associated with e, prd(e),
a positive integer that represents the number of tokens produced onto e by each firing of the

108 LOVELY PROFESSIONAL UNIVERSITY