Page 112 - DCAP608_REAL TIME SYSTEMS

Unit 11: Application of Clock-driven Scheduling

Notes
!
Caution Intuitively, one should give hard real-time jobs higher priority than aperiodic
jobs. However, this may lengthen the response time of an aperiodic job.

11.1.3 Multi-Processors

 Searching for a feasible multiprocessor schedule is more complex than searching for a
uniprocessor schedule.
 We can construct a global clock schedule which specifies on what processor each job
executes and when the job executes.
 As long as the clock drifts on the processors are sufficiently small, we can use the
uniprocessor scheduler on each processor to enforce the execution of the jobs according to
the global schedule.

 Since the feasible multiprocessor schedule search is done offline, we can use exhaustive
and complex heuristic algorithms for this purpose.

Self Assessment

Fill in the blanks:
1. A ……………… that was undetected during debugging and testing can also cause this
problem.
2. Another way to handle ……………… is to continue to execute the offending job.
3. The schedule switchover is deferred only when some ……………… cannot complete in
time according to the new schedule.
4. A ……………… that will not execute in the new mode can be deleted and its memory space
and processor time freed.

11.2 Algorithm for Constructing Static Schedules

DSP algorithms are usually required to operate under real-time constraints and with limited
resources. We are concerned with constructing efficient static (compile-time) schedules for
multirate DSP algorithms.
Dataflow models are widely used to represent DSP applications. The one often used for multirate
DSP algorithms are synchronous dataflow graphs (SDFGs). Each node (also called actor) in an
SDFG represents a computation or function and each edge models a FIFO channel; the sample
rates of actors may differ. Practical MultiMate DSP applications modelled with SDFGs include a
spectrum analyser, a satellite receiver, etc.
DSP algorithms are non-terminating and repetitive. Static schedules are usually used for them.
A static schedule arranges computations of an algorithm to be executed repeatedly. Execution of
all the computations for the required number of times is referred to as iteration. An iteration of
an SDFG may include more than one execution, often called firing in dataflow, of an actor, and
a different number of firings for different actors. The average computation time per iteration is
called the iteration period of a schedule. DSP algorithms with recursions (or feedbacks) have an
inherent lower bound on the iteration period, referred to as the iteration bound. It is impossible
to achieve an iteration period lower than the iteration bound, even when unlimited processors
are available. A schedule whose iteration period equals the iteration bound is called a rate-
optimal schedule.

LOVELY PROFESSIONAL UNIVERSITY 107