1An Improved Quasi-static Scheduling Algorithm for Mixed Data-Control Embedded Software EE 249 project report Cong Liu and Xuanming Dong 12/10/2001 Abstract: An embedded system is defined as a set of concurrent processes that communicate through channels. Described in flow C, each process is a sequential program that may contain data-dependent or synchronization-dependant control structures. A task is a set of sequential operations that the system will perform to respond to the inputs from the environment. The embedded software coordinates these tasks generated for input events. A software synthesis approach includes two correlated parts: scheduling and code generation. Our scheduling algorithm can guarantee that all tasks can be executed within finite memory for arbitrary input streams, and the code generated can have a smaller size than those previously used. Petri net (PN) is used the underlying model of computation (MoC) to do formal analysis and verification. 1. Introduction A reactive embedded system must respond to the inputs from the environment at the speed and with the delay dictated by the environment. The embedded software coordinates system operations. Scheduling of these operations is subject to satisfy hard time constrains, and make most use of the system resources (minimize CPU idle time). This report is organized as follow: in Section 2, system definitions, background knowledge, and underlying models are given; in Section 3, the detail about the algorithm is presented; in Section 4, some experiments and results are offered; in Section 5, some open topics are illustrated for future research directions. 2. System, Processes, and Tasks We define an embedded system as a set of concurrent processes. A set of input and out-put ports are defined for each process, and point-to-point communication between processes occurs through uni-directional channels between ports. We support multi-rate communication, in which the number of objects read or written by a process at any given time may be an arbitrary constant. A process may communicate with the environment in which the system is executed. This is done through input and output ports for which no channel is defined. Such primary input ports can belong to one of two classes, which we call controllable and uncontrollable. The latter is used to trigger an execution of the system, i.e. when the system receives an object at an uncontrollable port, it reacts to the environment by performing operations. On the other hand, the system may request the environment for further inputs through controllable ports, while this is not allowed for uncontrollable ports. Output ports are always written under system control, and the environment must be ready to accept them at any time (as allowed by the concurrent process specification). We restrict our attention to processes described as sequential programs and whose implementation is mapped as software to be executed on a programmable processor. The sequential program for each process is specified in Flow C, which is based on C, but extended to specify communication operations. It may contain both data-dependent control statements (e.g., if-then-else or arbitrary while or for loops) and synchronization-dependant control statements (e.g. SELECT). A task is generated for each input uncontrollable port, which performs the operations that required to react to an event of that port. 2.1 Static, quasi- static, and dynamic scheduling Static scheduling does most of the work at compile time, so the resulting software behavior is highly predictable, and the overhead due to task context switching is minimized. They may also achieve very high2CPU utilization if the rate of arrival of inputs to be processed from the environment has predictable regular rates that are reasonably known at compile time. Static scheduling, however, is limited to specifications without runtime choice (called Marked Graphs or Static Dataflow [2]). Researchers have recently started looking into ways of computing a static execution order for operations as much as possible, while leaving data or synchronization-dependant choices at runtime. This body of work is known as Quasi Static Scheduling (QSS). Dynamic scheduling is commonly used for a system which contains real-time controls, and the run time behavior is heavily dependent on the occurrence of external events. 2.2 Petri Net A Petri net (PN) is defined by a tuple of (P,T,F,Mo), where P, T are sets of places, and transitions respectively. F is a function from (T × P) (P × T) to non-negative integers. A marking is a function from P to non-negative integers, where its output for a place is denoted by M[p], which we call the number of tokens at p in M. If M[P] is positive, the place is said to be marked at M. Mo is a marking, which we refer to as the initial marking. A Petri net can be represented by a directed bipartite graph, where an edge [u,v] exists if F([u,v]) is positive, which is called the weight of the edge. We may call v a successor of u and u a predecessor of v, respectively. A transition is enabled at a marking M[p], if M[p] ≥ F([p,t]), for all p of P. In this case, one may fire the transition at the marking, which yields a marking M’ given by: M’[p] = M[p] – F(p,t) + F(t,p), for each p of P. In the sequel, M → M’ denotes the fact that a transition t is enabled at a marking M and M’ is obtained by firing t at M. A sequence of transitions (t1,t2,…tk)is said to be fireable from a marking M, if there exists a sequence of markings (M1, M2,…Mk) such that M1 = M and Mi → Mi+1’ holds for each I=1,2,…k. A transition is said to be a source, if F(p,t) = 0 for all p of P. A marking M’ is said to be reachable from M, if there is a sequence of transitions fireable from M that leads to M’. The set of markings reachable from the initial marking is denoted by R(M0). The reachability graph of a Petri net is a directed graph in which R(M0) is the set of nodes and each edge [M,M’] is a transition t with M → M’. The reachability tree of a Petri net is a tree in which each node is labeled with a marking of R(M0), the root node is labeled with M0, and each edge [v,v’] represents a transition with M → M’. A key notion we use in Petri nets for defining
View Full Document
Unlocking...