Rate Monotonic Scheduling

Rate Monotonic Scheduling Using CSIM Data Flow Graph Tool
There are several tools for capturing, modeling, and simulating signal processing data flow graph applications. However, some applications require combining data flow driven scheduling with rate monotonic scheduling. Rate monotonic scheduling is a paradigm used widely to guarantee real-time operation. In the past, scheduling of rate-monotonic tasks required the use of spreadsheets or textual based data entry and was disconnected from the data flow graphic entry and operation. The CSIM tool-set has extended its data-flow graphic entry capability to include tasks that are driven by rate-monotonic scheduling.

The key to enabling rate monotonic tasks in CSIM is the use of GEN nodes which generate periodic pulses at specified rates. The GEN nodes may be mapped to a single timing device such as the generic_pe. The generic_pe can model any number of timers as specified by the GEN nodes.

A simple example is shown in the following data flow graph:

Data Flow Graph

The diagram shows three processing threads. Each thread is to be executed periodically at different rates. Each thread is thus triggered by a different GEN node. The top thread is to be executed at a period of T1, The middle thread is to be executed at a period of 2*T1 and the bottom thread is to be executed at a period of 4*T1. Each thread is mapped to a different processor, so that they can run in parallel. The resulting simulation timeline is shown in the following plot:

Timeline

The Timer shows that a GEN1 pulse is generated every 100 micro-seconds, a GEN2 pulse every 200 micro-seconds and a GEN3 pulse every 400 micro-seconds. Tasks A1 and B1 are executed on processor PE1 every 100 micro-seconds. Tasks A2 and B2 are executed on processor PE2 every 200 micro-seconds and tasks A3 and B3 are executed on PE3 every 400 micro-seconds. The processors will generate warnings if ever the tasks have not completed before the next monotonic deadline.

Multiple monotonic processing threads may be mapped to the same processor if it appears that the tasks will be completed within their time frames, even though the tasks are executed serially. Otherwise it is better to use the multi_priority_pe. The multi_priority_pe is a multi-tasking pe model that keeps separate threads for each processing stream. Each processing stream is assigned a different priority, presumably the tasks occurring at a higher rate having a higher priority. Tasks ready at a higher priority will be executed before lower priority tasks.

To fully accommodate rate-monotonic modeling, some additional features are used. One is the ability to assign tasks to different processing threads of the multi_priority_pe with the appropriate priorities. The other is the loop-back capability in CSIM which generates loop instructions for the generic_pe or multi_priority_pe.  This simplifies the program files which would otherwise unroll loops into linear streams of instructions.

Both features may be provided by attaching a loop attribute to a loop-back arc in the CSIM GUI. The nodes that reside within the loop will be assigned to a separate processing thread and will be given a priority based on the relative rate of their GEN node or otherwise specified by the user.