Texas Instruments TMS320 DSP Execution Time Model, Execution Timeline for Two Periodic Tasks

www.ti.com

Execution Time

Figure 4-1. Execution Timeline for Two Periodic Tasks

A

B

3 ms 3 ms 3 ms 3 ms

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'speriod. 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's2 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'tmeet 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'trely 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.

4.4.2 Execution Time Model

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).

Rule 24

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

42	Algorithm Performance Characterization	SPRU352G –June 2005 –Revised February 2007
		Submit Documentation Feedback