Dispatch Sequences for Embedded Control ? Models Rajeev Alur and Arun Chandrashekharapuram Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104-6389, U.S.A. Abstract We consider the problem of mapping a set of control components to an executable implementation. The standard approach to this problem involves mapping control blocks to periodic tasks, and then generating a schedule. This schedule is platform- dependent, and its execution requires real-time operating system support. We pro- pose an alternative approach which involves generating a dispatch sequence of con- trol blocks in a platform-independentmanner. Oursolution relieson assigningrela- tive complexity and relative importance measures to control components, and is an adaptation of the classical scheduling algorithms such as earliest-deadline-(cid:12)rst. We showthebene(cid:12)tsofourapproachusingsimulationexperimentsontwo case studies. Key words: Embedded software, Real-time scheduling, Model-based design 1 Introduction Contemporary industrial control design already relies heavily on tools such as Simulink for mathematical modeling and simulation. Even though many such tools support implementation via automatic code generation from the model, many issues relevant to correctness and optimalityofthe implementationwith respect to the timed semantics of the model are not satisfactorily addressed, andistailoredtoaspeci(cid:12)cplatform.Consequently, analysisresultsestablished ? ApreliminaryversionofthispaperappearsinProceedings of the 11th IEEE Real- Time and Embedded Technology and Applications Symposium (RTAS),pp.508{518, 2005. Thisresearch was partiallysupportedby the US NationalScience Foundation under awards ITR/SY 0121431 and CCR-0410662. Email address: alur,[email protected](Rajeev Alur and Arun Chandrashekharapuram). Preprint submitted to Elsevier Science 8 December 2005 for the model are not meaningful for the implementation and the code cannot be ported across platforms posing challenges for system integration. These challenges motivate our research. In this paper, we focus on generating an executable implementation from a set B of control blocks. A control block computes outputs that in(cid:13)uence other blocks or the environment being controlled. The control model has a well- de(cid:12)ned timed semantics (either continuous or discrete) that can be used for simulation and analysis. Typically, the implementation relies on the support o(cid:11)ered by a real-time operating system for scheduling periodic tasks. Each control block Bi is compiled into an executable code in a host language such as C, and the control designer speci(cid:12)es a period (cid:26)i for the corresponding task. To implement the resulting periodic tasks on a speci(cid:12)c platform, one needs to determine the worst-case-execution-time (cid:28)i for each block Bi, and check whether the task set is schedulable using standard scheduling algorithms such as earliest-deadline-(cid:12)rst (EDF) or rate monotonic scheduling (c.f. [4,17]). While the real-time scheduling based implementation o(cid:11)ers a separation of concerns using the abstraction of real-time tasks with periods and deadlines, it can hinder portability of control designs across platforms. As a concrete example, consider vision-based navigation of an autonomous robot trying to reach a target in a room full of obstacles. One control block computes the estimates of the obstacles while the other decides the trajectory based on the current estimates. Mapping these blocks to two tasks with speci(cid:12)c periods introduces an abstraction that is not relevant to the high-level model or its goals. There are no hard real-time requirements in this application, and the performance can be measured by the time taken by the robot to reach the target. If the WCET (worst-case execution time) analysis on a particular pro- cessor reveals that the tasks are not schedulable, then in fact, the periods should be increased. If the analysis says that the tasks are schedulable, then it produces a schedule, which is a mapping from time slots to the tasks. This schedule is platform-dependent as it depends on the platform-speci(cid:12)c WCET estimates. Moreover, executing the schedule requires real-time support from the operating system while the current trend in many application domains such as robotics is to employ commonly available computing platforms such as .NET [6]. Furthermore, since the scheduler views the tasks as periodic, it may leave the processor idle, thereby preventing improved performance. In the proposed solution, our goal is to produce a dispatch sequence of blocks, rather than periodic tasks. The dispatch sequence is simply a string of control blocks, and is platform-independent. Unlike a schedule, a dispatch sequence has no notion of time slots or other real-time requirements. Ideally, we would like the sequence to be such that, on any given platform, it follows the ref- erence trajectory of the continuous time model as best as one can on that platform. This goal is hard to quantify abstractly, and even if one could (cid:12)nd 2 a concrete measure for speci(cid:12)c applications (for instance, the total distance traveled in the above robot example), we are not aware of any methods to generate sequences that optimize this measure in an eÆcient way. In this pa- per, we formulate the sequence generation problem, and propose a possible r solution. We associate with each control block Bi a measure (cid:28)i of relative r r complexity and a measure (cid:26)i of relative importance. The (cid:28)i value is supposed r to capture the computation time of Bi relative to the other blocks, and the (cid:26)i value is supposed to capture in a relative manner, how updating the output of Bi impacts the environment. We use the appropriately tightly scaled ver- r r sions of (cid:26) values as periods and of (cid:28) values as WCET estimates to generate sequences of blocks using the classical real-time scheduling algorithms such as non-preemptive EDF and EDF. Since EDF is preemptive and we want to gen- erateanexecutablesequenceofblocks,thissteprequiresmodeltransformation via block-code-splitting.The output of our strategy is a platform-independent and untimed sequence of blocks: executing this sequence does not require pre- emption or any support from real-time scheduler, and its ability to follow the reference trajectory on a particular platform depends on the processing power of the platform. The rest of the paper is organized as follows. Section 2 describes our model for control blocks along with a continuous time and a discrete time seman- tics for the same. Section 3 describes the classical real-time scheduling based approach by formalizing schedules, schedule semantics and strategies for gen- erating schedules using periods and WCET estimates. Section 4 de(cid:12)nes the notion of a dispatch sequence, the associated semantics, and proposes strate- gies for generating dispatch sequences inspired by scheduling techniques, but using the notions of relative complexity and relative importance. Section 5 de- scribes simulationexperiments on two examples, one forrobotnavigation,and one for controlling heaters across multiple rooms, demonstrating the bene(cid:12)ts of the proposed approach. We conclude with directions for future research in Section 6. Related Work: Bridging the gap between high-level modeling or programming abstractions, and implementation platforms has been identi(cid:12)ed as a key challenge for em- bedded software research by many researchers (c.f. [19,18]). Programming abstractions for embedded real-time controllers include synchronous reactive programming (languages such as Esterel and Lustre [3,10,9]), and the re- lated Fixed Logical Execution Time (FLET) assumption used in the Giotto project [12,13]. While these provide schedule-independent semantics, they do not address the problem of mapping continuous time controllers to an exe- cutable implementation. Recently, the problem of generating code from timed and hybrid automata has been considered in [1,14,21], but in these papers 3 the focus has been on choosing the sampling period so as to avoid errors due to switching and communication. The work on mapping Simulink blocks to Lustre focuses on signal dependencies [5]. Model-based development of em- bedded systems is also promoted by other projects with orthogonal concerns: Ptolemy supports integration of heterogeneous models of computation [7] and GME supports integration of multipleviews of the system [16]. There is a rich literature on sampled control systems with a focus on understanding the gap between continuous and discrete controllers, determining the correct sampling period, and compensating for the computation delays in the design of control laws (c.f. [2]). In scheduling literature, while many variations of the basic pe- riodic scheduling problem have been explored, the focus is on determining a platform-dependent mapping from time slots to tasks. The most relevant of these is control-aware scheduling [20], where periods for tasks are determined by optimizing a performance index. 2 Modeling Controllers In this section, we describe the model of a real-time control system and the desired semantics for the model. 2.1 Model Let X be a (cid:12)nite set of environment variables modeling the physical world to be controlled, and U be a (cid:12)nite set of control variables to be computed by the control software. Each variable has a type, which typically is IR, the set of reals. A state over a set W of variables is a mapping from W to values. We use QW to denote the set of all states over W. A control model is given by M = hMC;MEi, where MC is the controller model and ME is the environment model. The controller model MC consists of a (cid:12)nite set B of control blocks, where each control block Bi in B has the following components: (cid:15) A set of input variables Yi (cid:18) (X [ U), which the block reads to do its computation. (cid:15) A set of output variables Ui (cid:18) U, which the block writes after its computa- tion. (cid:15) A relation fi (cid:18) QYi (cid:2)QUi, de(cid:12)ning the computation of the block. 0 (cid:15) A set of initial states Qi (cid:18) QUi for the output variables of the block. The following properties must be satis(cid:12)ed by MC: 4 (cid:15) Every output variable must be computed by a unique block. That is, for all i;j with i 6= j, Ui \Uj must be empty, and [jUj must equal U. (cid:15) Consider a directed graph BG whose nodes are control blocks and where there is an edge from Bi to Bj if Bj reads an output variable computed by Bi. Then BG must be acyclic. The environment model ME is given by (cid:15) A relation gx (cid:18) QX (cid:2)QU (cid:2)IR for every environment variable x 2 X. This relation is used to de(cid:12)ne the rate of change of x in terms of the current state. 0 (cid:15) A set of initial states Q (cid:18) QX for the environment variables. We have allowed our models to be nondeterministic, but this choice is not central to this paper, and in many cases, the computation of each control block Bi is de(cid:12)ned by a function fi : QYi ! QUi, and the rate of change of an environment variable x is given by a function gx : QX (cid:2)QU ! IR. 2.2 Robot Navigation Example Consider a robot R which can move on a 2-D plane (see Figure 1). Initially R is at the ((cid:12)xed) starting point S. Its goal is to reach a ((cid:12)xed) target point T, without colliding with any of the stationary circular obstacle-disks O1;O2 and O3 on the plane. The robot moves in the direction (cid:18) at a constant speed vR. It can estimate the obstacles only approximately, and we assume that the estimate is a circle whose center coincides with the center of the obstacle (xc;yc) and whose radius r is always larger than the actual radius r0. The estimation rule is given by 2 2 2 r = r0 +( (xc (cid:0)x) +(yc (cid:0)y) (cid:0)r0) =500 q where (x;y) is the current position of R. The estimate r is smaller if R is closer to the obstacle. Based on the estimated radiiof the 3 obstacles from the current position, the robot computes (cid:18) as follows : (cid:12)rst, it checks if the direct path from the current position (x;y) to the target T faces no obstruction | if so, it proceeds in that direction. If not, it computes the slopes of the tangents fromthe current positiontothe estimatedobstaclecircles,andchecks whether rays along the tangents face any obstruction. Then, among the rays without any obstruction, it chooses to go along that ray which makes the least angle with the direct path to the target. Figure 1 shows a snapshot of the robot position during its motion, along with the estimated obstacle radii and the selected direction of motion. 5 Environment x T y e 1 Controller B 3 e O1 e2 0 B 0 O2 e 3 e 1 v B1 O3 R R e (x, y) 2 B2 S Fig. 1. Robot navigation example Figure 1 also shows a block diagram of the model. The environment variables are the coordinates (x;y) of the robot position. The initial values of (x;y) are the coordinates of S. The di(cid:11)erential equations governing the rates of change of x and y are : x_ = vR cos(cid:18); y_ = vR sin(cid:18): The control variablesare e0;e1;e2; and (cid:18), where ei is the estimateofthe radius of obstacle Oi. There are four control blocks B0;:::;B3. The control block Bi, for 0 (cid:20) i (cid:20) 2, is used to estimate radius of the obstacle Oi. Its input variables are x and y, and its output variable is ei. The control block B3 is used to calculate (cid:18). Its input variables are e0;e1;e2;x; and y, and its output variable is (cid:18). The initialvalues of ei are the estimates from S, and that of (cid:18) is the angle computed using the initial values of ei. 2.3 Semantics Given a model M over variables X and U, a trajectory for M is a function : IR ! QX[U. A semantics for a model M, denoted [[M]], is a set of trajectories for M. Two semantics, continuous time and parameterized discrete time, are described below. 2.3.1 Continuous Time Semantics The continuous time semantics for a model M, denoted [[M]]C, evaluates all control variables at every point in the continuous time domain. It consists of the trajectories satisfying the following constraints: for all t 2 IR;t (cid:21) 0 and 6 for all Bi 2 B we have 0 _ (0)(X) 2 Q ; ( (t)(X); (t)(U); (t)(X)) 2 gx; (1) and 0 (0)(Ui) 2 Qi; ( (t)(Yi); (t)(Ui)) 2 fi: (2) 2.3.2 Parameterized Discrete Time Semantics TheparameterizeddiscretetimesemanticsforamodelM evaluatesthecontrol variables with a sampling period of (cid:1), and a zero-order hold. So, all control outputs are piecewise-constant, the pieces being of length (cid:1). Let tk = k(cid:1) for k 2 IN. Given a (cid:1) > 0, the discrete time semantics for M, (cid:1) denoted by [[M]]D,is aset oftrajectories satisfyingthe followingconstraints, besides (1) : for all Bi 2 B and for all k 2 IN, 0 (0)(Ui) 2 Qi; ( (tk)(Yi); (tk)(Ui)) 2 fi; and for tk(cid:0)1 (cid:20) t < tk; t 2 IR, (t)(Ui) = (tk(cid:0)1)(Ui): We note that the continuous time semantics is the ideal semantics for any given model. The discrete time semantics introduces an error into the model because of the zero-order hold for (cid:1) intervals. We may want to de(cid:12)ne the error using some metric over trajectories, but it is diÆcult to quantify the errors abstractly. For speci(cid:12)c applications, such as those evaluated in this paper, we can (cid:12)nd some concrete measures to quantify the performance of a trajectory, and use them to compare any two trajectories. In our robot navigation example, total distance traveled from the start position to the target is a reasonable measure of performance. 3 Schedule-based Implementation In this section, we discuss some standard implementation strategies to gener- ate real-time tasks from a given model M = hMC;MEi. We (cid:12)rst de(cid:12)ne the notion of a schedule and then discuss the standard platform-dependent ways of computing schedules. 7 We assume henceforth that the minimum time unit of execution of a control task is 1. That is, the values of the control variables can be updated by any controlfunction onlyinintervalsofone timeunit.Thissimpli(cid:12)esthe notation, otherwise we would need de(cid:12)nitions parameterized by (cid:1) as in case of discrete- time semantics. 3.1 Schedule and Schedule Semantics A schedule is a mapping from time slots to blocks, which indicates the block thatexecutes ineachtimeslot.Theschedule semanticsforaschedule istheset of trajectories obtained by executing the blocks according to the schedule: an instantiationofablockexecutesonlyinthetimeslotsgivenbytheschedule;its inputvalues areread atthe beginningofthe (cid:12)rst timeslotofits execution and the control outputs computed by the block are updated at the end of the last slot of its execution. This type of predictable execution can be implemented using the time-triggered architecture [17]. + Formally, a schedule sch for M is a function sch : IN ! B [B [f?g, where + + B = fBi j Bi 2 Bg isused to denote the completionof the current instances of the corresponding tasks, and ? denotes idle. The connotation of a schedule is as follows. Let slot k denote the time interval [k (cid:0)1;k]. Then for k (cid:21) 1, Bi means Bi executes in slot k but fi is not yet computed. 8 sch(k) = >>>>><Bi+ means Bi executes and (cid:12)nishes computation of fi in slot k. ? means the processor is idle in slot k. >>>>>: Given a schedule sch, the semantics associated with the model M, denoted by [[M]]sch, is a set of trajectories obtained by executing the blocks according to + + sch. For example, consider the schedule B0B1B1 B0 B1 :::. Block B0 starts executing at time t = 0 after reading its inputs and executes in time slot 1. It is then preempted at time t = 1 when B1 starts executing. Block B0 again executes in time slot 4, and (cid:12)nishes its execution in that time slot. The values computed by B0 are updated at the end of slot 4. We assume that reading and updating take zero computation time. Therefore, (t)(U0) = q0 for some 0 q0 2 Q0 for 0 (cid:20) t < 4, and (4)(U0) = f0( (0)(Y0)). Formally, [[M]]sch consists of the trajectories satisfying the following con- straints, besides (1): for all k 2 IN and all Bi 2 B, 8 0 (0)(Ui) 2 Qi (t)(Ui) = (k(cid:0)1)(Ui) for (k(cid:0)1) < t < k + 0 (k)(Ui) 2 fi( (l)(Yi)) if sch(k) = Bi , where l is the smallest l such that 0 + sch(l’) = Bi and 8j : l < j < k : sch(j) 6= Bi ; 0 l = k if no such index l exists. (k)(Ui) = (k(cid:0)1)(Ui) otherwise : 3.2 Algorithms for Computing Schedules Given a model M, the following steps are typically followed: (1) We (cid:12)rst generate one task Ti for each block Bi in the model. The code executed by the task will be the function fi, and the values used as input for variables in Yi will be the most recently computed values for those variables. (2) We then assign a period (cid:26)(Bi), where (cid:26) : B ! IN, to each task Ti. The period (cid:26)(Bi), also denoted by (cid:26)i, is independent of the platform on which the tasks are going to be executed. That is, as long as the task set is schedulable, the periods remain the same. They are usually assigned by control engineers to satisfy the performance requirements of the control model such as stability, ability to track a given trajectory, etc. (c.f. [2]). The relative deadline of Ti is equal to (cid:26)i, and this means that the task must be executed once every period. (3) Then, given an execution platform F, we compute (cid:28) : B ! IN, where (cid:28)(Bi), also denoted as (cid:28)i, is the Worst-Case-Execution-Time (WCET) of Bi on F. The WCETs can be estimated using well-known WCET estimation methods (c.f. [11]). (4) Given (cid:26) and (cid:28), we can execute the tasks using a real-time operating system (RTOS) that includes a real-time scheduler for periodic tasks. The RTOS typically uses well-known hard real-time scheduling algorithms for executing the tasks. We use two scheduling algorithms in this paper: the earliest-deadline-(cid:12)rst (EDF) algorithm and the non-preemptive earliest- deadline-(cid:12)rst (NPEDF) algorithm. The EDF (c.f. [4]) algorithm is a preemp- tivealgorithm.Whenanewtaskisreleasedorwhenthecurrenttaskcompletes execution, it schedules the task with the earliest deadline among all active tasks. The NPEDF algorithm (c.f. [15]) schedules the task with the earliest deadline among all active tasks, if the processor is idle or the currently exe- cuting task has (cid:12)nished execution. 9 (cid:26) (cid:28) Task F1 F2 F3 T0 120 ms 12 ms 24 ms 28 ms T1 120 ms 12 ms 24 ms 28 ms T2 120 ms 12 ms 24 ms 28 ms T3 24 ms 3 ms 6 ms 7 ms Fig. 2. Sample periods and execution times for robot navigation example Foragiven(cid:26)and(cid:28),ifthetasksetisschedulablebyEDF,itproducesaperiodic schedule sch,and the semantics[[M]]EDF((cid:26);(cid:28)) isde(cid:12)ned tobe [[M]]sch.Ifthe task set is not schedulable using EDF, then the semantics [[M]]EDF((cid:26);(cid:28)) is unde(cid:12)ned. The semantics associated withthe NPEDF algorithm[[M]]NPEDF((cid:26);(cid:28)) isde(cid:12)ned in a similar way. We call this approach platform dependent since the schedule depends on the concrete values of the WCET estimates (cid:28). Note that the only feature of the platform relevant in our context is its processing power, which is captured by the WCET estimates (cid:28). Consider the robotnavigationexampleagain.Forthis model,fourtasks would be generated: Ti, 0 (cid:20) i (cid:20) 2, for estimating the radii of the obstacles, and T3 for calculating (cid:18) based on the estimates. An assignment of periods for the tasks, and WCET estimates on three di(cid:11)erent platforms F1, F2 and F3 is given in Figure 2. Platform F1 is the fastest while F3 is the slowest. The tasks are schedulable by NPEDF (a schedulability test for NPEDF can be found in [15]) on F1 and F2 but not on F3. For t 2 [1::120] (120 is the LCM of the periods of the tasks), the schedule produced by NPEDF on F1 and F2 is shown in Figure 3. The schedule produced by EDF on F2 is also shown. The notation [i : t1(cid:0)t2] means that block Bi executes continuously from time slot + t1 to time slot t2 but without completing its execution, and [i : t1(cid:0)t2] means that Bi executes continuously from time slot t1 to time slot t2 and completes its execution at t2. We (cid:12)rst note here that the periods (and therefore deadlines) assigned to the tasks are arti(cid:12)cial. For example, if a task set is not schedulable, the control engineer might be able to increase the periods without violating the perfor- mance requirements of the control model. Here, we can increase the periods slightly to render the tasks schedulable on F3. Further, we observe that there are a lot of idle times on F1, whereas executing the control tasks without any idle times (that is, executing the next block in sequence immediately after a block (cid:12)nishes execution) can improve performance. The goal in this case is to 1 approximate the discrete semantics [[M]]D (and hence the continuous seman- 10