Texas Instruments TMS320 DSP 사용자 설명서

3 ms

3 ms

3 ms

3 ms

A

B

Idle

In this case, both task A and B meet their deadlines and we have more than 18% (1 ms every 6 ms) of the
CPU idle.

Suppose we now increase the amount of processing that task B must perform very slightly, say to
1.0000001 ms every 3 ms. Notice that task B will miss its first deadline because task A consumes 2 ms of
the available 3 ms of task B's period. This leaves only 1 ms for B but B needs just a bit more than 1 ms to
complete its work. If we make task B higher priority than task A, task A will miss its deadline line because
task B will consume more than 1 ms of task A's 2 ms period.

In this example, we have a system that has over 18% of the CPU MIPS unused but we cannot complete
both task A and B within their real-time deadlines. Moreover, the situation gets worse if you add more
tasks to the system. Liu and Layland proved that in the worst case you may have a system that is idle
slightly more than 30% of the time that still can't meet its real-time deadlines!

The good news is that this worst-case situation does not occur very often in practice. The bad news is that
we can't rely on this not happening in the general situation. It is relatively easy to determine if a particular
task set will meet its real-time deadlines if the period of each task is known and its CPU requirements
during this period are also known. It is important to realize, however, that this determination is based on a
mathematical model of the software and, as with any model, it may not correspond 100% with reality.
Moreover, the model is dependent on each component accurately characterizing its performance; if a
component underestimates its CPU requirements by even 1 clock cycle, it is possible for the system to
fail.

Finally, designing with worst-case CPU requirements often prevents one from creating viable combinations
of components. If the average case CPU requirement for a component differs significantly from its worst
case, considerable CPU bandwidth may be wasted.

In this section, we describe a simple execution time model that applies to all eXpressDSP-compliant
algorithms. The purpose of this model is to enable system integrators to quickly assess the viability of
certain algorithm combinations, rationally compare different algorithm implementations, and enable the
creation of automatic design tools that optimize CPU utilization. While far from perfect, the model
described below significantly improves our ability to integrate algorithms into a system.

All algorithms must be characterized as periodic execution of one or more functions. For example, a voice
encoder may be implemented to operate on a frame of data that represents 22.5 ms of voice data. In this
case, the period is 22.5 ms (because every 22.5 ms a new frame of data is available for processing) and
the deadline is also 22.5 ms (because there is no need to complete the processing ahead of the time that
the next frame of data is available).

All algorithms must characterize the typical period and worst-case execution time for each operation.

42

SPRU352G – June 2005 – Revised February 2007