Page 114 - DCAP608_REAL TIME SYSTEMS

Unit 11: Application of Clock-driven Scheduling

source actor of e, cns(e), a positive integer that represents the number of tokens consumed from Notes
e by each firing of the sink actor of e. These numbers are also called the delay, production rate
and consumption rate, respectively. The source actor and sink actor of e are denoted as src(e) and
snk(e), respectively. If prd(e) = cns(e) = 1 for each e 2 E, then we say that G is a homogeneous
SDFG (HSDFG).

Notes A special class of algorithms can be modelled by a synchronous data flow (SDF)
graph for which efficient implementation methods exist.
The edge e with source actor u and sink actor v is denoted by e = hu; vi. The set of incoming edges
to actor v is denoted by InE (v), and the set of outgoing edges from v by OutE(v). An initial delay
distribution of the SDFG G is a vector containing delays on all edges of G, denoted as d(G). An
SDFG G is sample rate consistent if and only if there exists a positive integer vector q(V) such
that for each edge e in G,

e
( q src ( )) prd ( ) ( q snk ( )) cns ( ).
e
e
e
where (1) is called a balance equation. The smallest q is called the repetition vector. We use q to
represent the repetition vector directly.
Example: A balance equation can be constructed for each edge of G1 in Fig. 11.1 (a). By
solving these balance equations, we have G1’s repetition vector q = [2, 1, 1].
One iteration of an SDFG G is a firing sequence in which each actor v occurs exactly q(v) times.

Example: An iteration of G1 in Fig. 11.1 (a), for example, includes two firings of actor A
and one firing of B and C, respectively.

Self Assessment

Fill in the blanks:
5. ……………… are usually required to operate under real-time constraints and with limited
resources.
6. The construction of rate-optimal schedules involves ……………… retiming and unfolding.
7. It is always possible to convert an SDFG to its equivalent ……………… and then use the
available methods for HSDFGs.
8. The average computation time per iteration is called the ……………… of a schedule.
9. A ……………… arranges computations of an algorithm to be executed repeatedly.

11.3 Pros and Cons of Clock-Driven Scheduling

The advantages of clock-driven scheduling are discussed below:

 Conceptual simplicity
 complex dependencies, communication delays, resource contentions can be
considered when developing the schedule

LOVELY PROFESSIONAL UNIVERSITY 109