The Program State Machine (PSM) Model of Computation o ers a rich set of modeling elements to describe behavioral and structural hierarchy, concurrency, synchronization, state transitions and timing. With the rising software complexity of today's embedded systems, the use of Real-Time Operating Systems (RTOS) has become state-of-the-art for nearly all System-on-Chip designs. Regrettably, the PSM model itself has insu cient support for the speci cation of the preemptive dynamic scheduling behavior of an RTOS. In this paper, we propose a model for dynamically dispatching PSM models on a virtual processing element. Our model aims to abstract from the targeted RTOS and the processor core through execution time annotations and a exible preemptive scheduler model. Mapping a PSM model to a set of scheduled virtual processing elements only requires minor model transformation and enables early exploration of different processing element mappings and scheduling policies. Our virtual processing model for PSMs is realized on top of the SystemC library. We evaluate the proposed virtual processing model using a Canny edge detection lter.
The development process of state-of-the-art embedded
systems is complex and a ects many di erent disciplines.
Among others, the design process requires hardware and
software design decisions. Today's system complexity of
embedded Multi-Processor System-on-Chip (MPSoC) designs
is continuing at an almost exponential rate [
To cope with the increasing complexity and the
time-tomarket pressure, new design methodologies are required. One
design challenge for embedded system designers is mapping
the functionality on the individual processing elements while
meeting the required extra-functional properties (e.g. timing
and power consumption) at minimal cost. To support this
challenge, System-Level Design Languages (SLDLs) enable
to raise the level of abstraction and support early design
decisions. In [
APPLICATION
COMM & SYNC CHANNELS
SLDL (a) specification model
APPLICATION APPLICATION APPLICATION
COCMHAMN&NSEYLSNC COCMHAMN&NSEYLSNC RTOS COCMHAMN&NSEYLSNC VIRTUALUPNRIOTCESSING RTOS MODEL INSSTRIMUUCLTAITOONRSET
SLDL SLDL SLDL (b) virtual processing model (c) architecture model (d) implementation model
In this work we focus on systems that implement their
behavior in software, which can be mapped and executed
on di erent PEs of an MPSoC. Fig. 1 (a), (c) and (d) show
the layers for executable MPSoC models proposed in [
The design step from a non-scheduled speci cation model (a) to a complete RTOS scheduled architecture model (c) is a complex re nement step. It requires to transform the application or behavioral description into a process- or threadbased model and to use the con guration and scheduling primitives of the selected RTOS. At this time the choice of the task granularity and the supported scheduling primitives have usually been taken. At this level, the comparison of di erent task granularities and di erent scheduling policies, supported by di erent RTOSs induces major redesign e ort. In this paper, we introduce a virtual processing model (b) to support a smoother re nement from the unscheduled speci cation to an RTOS scheduled architecture model for PSMs.
Our approach supports PSM modeling at the speci cation layer and enables early estimation of dynamic scheduling e ects when mapping parallel behaviors on the same PE. This step can be performed without any behavior to process or RTOS speci c re nements. This way, designers can pro t from simple speci cation model modi cations in combination with early estimated execution time annotations, thus enabling early decisions regarding PE allocation, behavior to process re nement granularity, process to PE binding and scheduling policy selection.
The rest of the paper is organized as follows. In Section 2 we analyze related work. Next, we discuss the design of the virtual processing model in Section 3. Followed by a brief description of the implementation in Section 4, we evaluate the new virtual processing model using a Canny lter for still image edge detection in Section 5. Finally, we conclude our work in Section 6.
An early proposal of a generic RTOS model based on
SystemC has been published in [
In [
An RTOS based scheduling approach with focus on
precise interrupt scheduling has been proposed in [
All mentioned solutions above work on architecture level models and allow to create and handle processes and interrupts on an RTOS speci c abstraction. Our solution addresses scheduling at a higher abstraction level and keeps communication at speci cation abstraction, thus no need for interrupts.
Several approaches based on abstract task graphs [
The proposed RTOS model in [
The timing accuracy and therefore the simulation
performance of [
A two layer for modeling approach for software task
scheduling considering shared resources has been proposed in [
We use an expressive subset of the program state machine (PSM) model of computation (MoC) to describe the functionality of a system. A hierarchical PSM model with the corresponding thread graph is shown in Fig. 2(a) and (b). A sequential composition of n behaviors describes a total execution order, denoted as a n dimensional tuple: (beh1; :::; behn). The execution starts with beh1and nishes with behn. A parallel composition of n behaviors describes a partial execution order, denoted as a set of n behaviors fbeh1; :::; behng. The parent behavior of a parallel composition of child behaviors will not nish until all child behaviors have completed (Fork-Join semantics). The nite-state machine behavior composition is a special case of a sequential execution from a start state to an end state. The execution order is de ned by state transitions.
The virtual processing model supports communication between behaviors via double handshake channels (synchronized) and shared variables (unsynchronized). A double handshake channel operates in rendezvous fashion (see Fig. 3). When the data is transferred from the sender to the receiver, both behaviors resume their execution at the same time. A
D → t2 E → t2 F → t2 [t3,t4] = fork(t2) t2H= →joint4(t3,t4) F → t2
J → t2
A → ttop b) Thread graph Processing Element: Scheduler
PE1 Strategy G → t3
Paral el:
B FSM:
C State: State: State: C1 C2 C3 E J G d) Nested behaviors
Paral el:
F
H communicating behavior can be blocked through communication for some time, until the other communication partner is ready and the handshake has been completed. To achieve a high utilization of a PE the scheduler will be able to preempt blocked behaviors.
A PE maintains a single thread of execution (i.e. a single core processor). We associate exactly one scheduler with one PE one scheduling algorithm. We use the terms simulated time and simulation time to express the amount of task execution time currently simulated. The terms simulation execution time and execution time refer to the amount of time the simulator requires on the host computer1. Fig. 2(c) shows the scheduler S which is assigned to PE1 and associated with the xed priority scheduling strategy. In this case all behaviors mapped on PE1 need a speci c xed priority, such that the scheduler can make a scheduling decision. Furthermore, we assume that computation is only in leaf behaviors (C1, C2, C3, E, G, H and J in Fig. 2), and hierarchical behaviors (A, B, C, D, and F in Fig. 2) describe the causal chain of execution in the model that must be followed by the scheduler.
We describe now the concept of scheduling for PSM models for the two requested xed priority and round robin schedul1Which is of course dependent on the host CPU, clock frequency etc. and a comparison between simulation execution times of di erent model is only possible on the same reference simulation host. ing algorithms. We decided to provide these two fundamental strategies because more complex strategies can be easily derived from them.
The xed priorities are statically de ned. The scheduler always executes the behavior that has the highest priority and is ready to execute. We are interested in making the process of priority assignment to the behaviors on the virtual processing model as simple as possible. The designer assigns xed priorities only to leaf behaviors. A hierarchical higher behavior cannot hide the priority of a leaf behavior.
Set of ready behaviors
F inner behaviors
C1, C2, C3 leaf behaviors inner behaviors
Set of ready behaviors
C1, C2, C3,
G, H leaf behaviors a) Before scheduling decision b) After simulation of behavior F
The scheduler distinguishes between inner and leaf behaviors. As shown in Fig. 4(a), the set of ready behaviors can be categorized into two subsets. Inner behaviors always have an in nite high priority and leaf behaviors have a xed priority de ned by the designer. The scheduler always prefers an inner behavior over a leaf behavior. Let's assume the behaviors C1, C2, C3, and F are ready to execute. In this situation, the scheduler selects behavior F because F is an inner behavior (see Fig. 2(c)) and has in nite priority. Behavior F has two child behaviors G and H, which are leaf behaviors. Behavior F is waiting until the child behaviors have completed. Fig. 4(b) shows both child behaviors G and H added to the set of behaviors ready to execute.
All mapped behaviors on a processing element get time slices of the same length. If a behavior has terminated, the scheduler selects immediately the next running behavior. The scheduler executes the behaviors in a circular order. If a behavior is not ready to execute, the next ready behavior with respect to the circular iteration is chosen. Fig. 5 depicts a round robin scheduling example. The parallel behaviors G and H are mapped on the same processing element. The behaviors G and H are scheduled by round robin and the time slice is 5 time units. In the following, we keep the focus on behavior G that requests once 3 and once 12 time units. The start behavior is arbitrary because the model in the gure does not de ne one; we assume the simulation starts with behavior G. Behavior G requests 3 time units, computes, and requests 5 more time units. The request of 3 time units can be consumed completely in one time slice; however, the following request is too complex. 2 more time units can be consumed after behavior H preempts behavior G and can start executing. At time 10, behavior G is active again and continues consuming the remaining 10 time units. first time request second time of 3 time units request of 12 time untis Processing Element: PE1 Behavior of G:
G
H Scheduler: Round robin, time slice: 5 time units 1. Request 3 time units G G H G H G 2. Compute something 3. Request 12 time units 0 2 4 6 8 10 12 14 16 18 20 22 24 45.. .C..ompute something simulated time 1. time 2. time 3. time slice slice slice Depending on the scheduling algorithm and the communication status, a behavior can have one of the following states (see Fig. 6): ready, running, communicating and waiting. A ready behavior can be selected by the scheduler and executed on the associated processing element. A behavior has the state running, if it is currently executing on the mapped processing element. A running behavior can be preempted in two di erent ways: (a) end of the time-slice, as de ned by the scheduling algorithm (waiting state), (b) blocked communication request on double handshake channel (communicating ). If a behavior has completed, its status is terminated. Fig. 6 shows all possible transitions between the described states.
end of communication activation
ready completed after communication communicating executes estimated
computation finished estimated computation resume running waiting
start of communication
termination preempted terminated
The class osss_processing_element represents a PE and
inherits from the osss_behaviour. Fig. 7 shows the extension of
the OSSS-Behaviour class diagram [
Fig. 8 shows an example where the behaviors B1 and B2 are mapped on the same PE under xed priority scheduling strategy. Thread t1 is associated with behavior B1 and thread t2 with behavior B2. We assume behavior B2 is running and B1 ready (see Fig. 6) at the beginning and neither B1 nor B2 have consumed any time. Thread t2 starts executing the main() function of B2 and enters the 3 milliseconds estimated waste_time() function of the scheduler, see Alg. 1. The while loop runs until the entire requested time of a timing annotation has been consumed. At the beginning of the loop, thread t2 calls the function available_time(requested_time), which asks the scheduling strategy how much of the totally requested time can be consumed. In our example, the scheduling strategy is xed priority and the current behavior has the highest priority. In this case, the xed priority scheduler accepts the complete time (i.e. 3 milliseconds). status: ready, low priority driven by thread t1 status: ready, high priority
driven by thread t2 waste_time(5ms)
B1
B2
C1 ...
We allow preemption of running behaviors. The function then of preemption is to suspend the current running process and to resume a process the scheduling algorithm has selected to be executed next. If we suspend a process waiting on a timed event,we have to interrupt the waiting process, store how much time the process has already consumed, and consume the remaining time later. For this reason, the SystemC wait() statement in Line 6 is sensitive to two di erent or-composed sets of events. The rst event max_time noti es the thread after the provided time slice of the scheduler is over. The second parameter is an or-composed event list. All behaviors that start communication add the corresponding synchronization event of the channel to that list. This mechanism allows preempting a current running behavior by a behavior with higher priority that has completed communication.
Algorithm 1 function waste time(requested time) 1: req time requested time 2: while req time > 0 do 3: max time available time(requested time) 4: start time current time 5: behavior status running 6: wait(max time or registered communication events) 7: req time req time - (current time - start time) 8: if req time = 0 then 9: return 10: else 11: behavior status waiting 12: dispatch() 13: end if 14: end while
Each PE represents a single core processor. For this reason, only one behavior can be ready for the SLDL scheduler. Otherwise, the scheduler would execute multiple behaviors in parallel on the same PE. Communicating behaviors are an exception because they are waiting for their synchronization event. If the process of a communicating behavior would be suspended, the behavior would ignore the synchronization event. The function dispatch() (see Alg. 2) guarantees this requirement. The set of behaviors is stored in two lists, namely a list for inner behaviors and a list for leaf behaviors. The rst behavior in the list of ready behaviors de nes the next running behavior. In this situation behavior B1 needs to be suspended and behavior B2 should be ready.
We decided to separate the scheduler and the scheduling strategies (see Fig. 7). The designer derives a class from osss_scheduler. The function schedule() takes a list of all leaf behaviors as argument. The function moves the next executing behavior to the beginning of the list. The function available_time de nes the size of a consumable time quantum.
In order to evaluate our proposed virtual processing model, we focus on scheduling di erent partitions of a speci cation Algorithm 2 function dispatch() 1: Unsorted List: inner behaviors, leaf behaviors 2: Process successor process null 3: Process current process get current process() 4: if inner behaviors = ; then 5: schedule(leaf behaviors) 6: successor process rst element(leaf behaviors) 7: else 8: successor process 9: end if 10: for all Behavior b in inner behavior do 11: if process(b) 6= current process and
status(b) 6= communicating then 12: suspend(process(b)) 13: end if 14: end for 15: if current process 6= successor process then 16: resume(successor process) 17: suspend(current process) 18: end if
rst element(inner behavior) model and measure the simulated time, count the scheduler calls and measure the execution time of the SystemC program. The count of scheduler calls is compared to the expected number of scheduler calls depending on the scheduling strategy. Based on the results, we can show that the communication via shared variables and double handshake channels, as well as the individual scheduler on the PEs, do not violate the causal execution order de ned in the speci cation model.
The design we use for evaluation is a Canny edge detector
[
Speci cation IndividualPE BlurX Blur2X Blur2X2Y
Simulated time [ms] 40
The following models, as shown in Fig. 9, are evaluated: Speci cation (untimed, without virtual PE), Individual PE (timed blur leaf behaviors, all behaviors mapped on a single PE), BlurX (timed blur leaf behaviors, blurX4 mapped to P E2, synchronization between P E1 and P E2 via double handshake channel (behavior blurX4 on P E2 can only start if behavior blurX_par on P E1 has been entered)), Blur2X (timed blur leaf behaviors, parallel composition of blurX3 and blurX4 mapped to P E2, synchronization of parallel composition like in BlurX) and Blur2X2Y (timed blur leaf behaviors, parallel composition of blurX3 and blurX4 and parallel composition of blurY3 and blurY4 mapped to P E2, synchronization like in Blur2X with additional synchronization barrier between sequential composition of parallel blur behaviors).
When neglecting communication (shared array access), synchronization and scheduling (including context switching) times, our model's total simulated times, as expected by Amdahl's law, are shown in Tab. 1. We compare the complexity of the di erent models using a simple Lines of Code (LoC) metric. The major e ort was to allocate new channels and behaviors for synchronization. For instance, for the model BlurX a new PE and three sync behaviors have been instantiated. Furthermore, the double handshake channel was hierarchically bound from the ports of the PE's to the ports of the blur leaf behaviors.
In the following, we discuss the simulation of the four virtual processing models using a round robin scheduler with di erent time slice granularities from 1ns up to 100; 000ns on each individual PE. We measured the number of context switches and associated them with a constant cost of 1 ms. Fig. 10 shows the simulated time of model Blur2X2Y with context switching costs for a round robin scheduling of P E1 and P E2. As expected, we can observe that ne grained time slices < 100 ns have a huge impact on the overall simulated time. On the other hand, the responsiveness (although not necessary for the image lter design) rises.
Simula'on 'me of the model Blur2X2Y with 'me
annota'ons for context switches 240,000 ]s 220,000 [em 128000,,000000 no'm 116400,,000000 a'120,000 lu100,000 ism80,000 60,000 1 10 100 1,000 10,000 Time slice of the individual schedulers [ns] 100,000 Fig. 11 visualizes the ratio between the simulated time for context switches and computation for a 20 ms leaf behavior timing annotation. When the time slice is very short, almost 70 % of the simulated time is spent on context switches. Fig. 12 shows the measured execution time of the various models on an Intel(R) Core(TM)2 Quad CPU Q9650 @ 3.00 GHz with 4 GB RAM running Fedora 12 Linux using the Context switch 2me time command. From this measurement, we can observe that the execution time of the individual models is proportional to the number of context switches, as shown in Fig. 10. We traced the individual scheduler calls and compared the Execu&on &me for round robin scheduled processing elements
Spec. Model Individual PE Blur X Blur 2X
Blur 2X 2Y 10 100 1,000 10,000 100,000
Time slice of the individual schedulers [ns] execution order of leaf behaviors (i.e. the causal chain) between the speci cation and the Virtual Processing Models. In the speci cation model, the blur behavior's execution order was blurX1, ... , blurX4, while in the di erent VPM models the execution order changed to blurX4, ... , blurX1. Even though the ordering is di erent, validity of causality for parallel compositions (partial order) only requires to be order isomorph, which is the case.
In this paper, we extended the proposed methodology in
[
This work has been partially supported by the ARAMiS project (01IS11035M) and the EMC2 collaborative ARTEMIS project (01IS14002R), both funded by the German Federal Ministry of Research and Education (BMBF).