Response Modeling: Model Refinements for Timing Analysis of Runtime Scheduling in Real-time Streaming Systems

This thesis addresses the timing analysis for embedded real-time streaming systems using a formal model-based approach. Embedded real-time systems often run software applications that operate over a stream of input and whose functions have intrinsic timing requirements. For instance, a base-band processing application deployed on a mobile phone is used to process the radio transmission received by the device and to forward the processed output to the MAC and applications layers, and vice-versa. To meet their intended use, streaming applications like our baseband processing example must operate above a minimum throughput and within a maximum latency. At the same time, multiple applications are made to share resources on a given hardware platform to achieve maximum flexibility at the lowest cost.
Each shared resource (ex. a processor) employs a scheduling technique to provide service to each task using that resource. Resource sharing introduces delays in the execution of tasks in an application. Consequently, rigorous timing analysis of the system is required to ensure that timing requirements of the individual applications are met.

We use static dataflow as the model-of-execution for our systems. Static dataflow can conveniently model iterative pipelined executions of tasks having varying execution times, which are often conditioned by complex data- and control-dependencies. Such executions are characteristic of data-driven embedded streaming applications, like the baseband applications that we consider in this thesis. We work on a dataflow-based model-refinement technique, called response modeling, to depict the execution of individual applications for a given scheduling strategy. Starting from a dataflow model of an application that depicts the division of an application into constituent tasks, we use this model-refinement technique to replace an actor (i.e., a node in the graph) representing a task with a sub-graph. This sub-graph, also called a response model, depicts an upper-bound on the actual execution of the real task for a given scheduling technique. By applying our model-refinement to all tasks in an application we compose a model that depicts the upper-bound on the execution of the entire application. Subsequently, we use an existing timing analysis of static dataflow to obtain the latency and throughput of the refined model of our application. As the execution of the real application cannot be worse than that depicted by our model, we can use the latency and throughput of our model to verify if the timing requirements of its application are met.

This thesis focuses two scheduling techniques, namely, Time Division Multiplexing (TDM) and Preemptive Fixed Priority Scheduling (PFPS). TDM and PFPS are two of the most commonly used scheduling techniques in the industry and belong two separate categories of scheduling techniques, namely, starvation-free (TDM) and non-starvation-free (PFPS). For each candidate, we look at the state-of-the-art response modeling techniques and investigate how they could be improved to obtain more accurate results on realistic models of a given system.

The state-of-the-art response modeling techniques for TDM are either too pessimistic or very restrictive in their applicability. This thesis presents two alternative response models for TDM. The first approach exploits the fact that contiguous execution of consecutive instances of a task in TDM exhibits a cyclic pattern. By explicitly representing the execution for each instance in this pattern we construct a response model that accurately depicts the worst-case execution of that task. The second approach addresses the combination of TDM with static-ordering. In other words, instead of allocating a separate slice to each task in an application and which are mapped onto a given processor, tasks execute in a static-order within a single TDM slice. Experiments for our first approach demonstrate a 20% reduction in the resources allocated to a simplified WLAN downlink. Meanwhile, experiments for our second approach show a 40% reduction in the resource allocated to a static-order of tasks mapped to a shared processor a realistic model of a WLAN downlink in which we combine static-ordering with TDM.

Until recently, dataflow based timing analysis did not address non-starvation-free scheduling techniques, like Preemptive Fixed Priority Scheduling (PFPS). This thesis presents a response time analysis and modeling of PFPS for data-driven execution. In contrast to TDM, PFPS is a work-conserving scheduling technique that does not guarantee a minimum service to a task. In other words, if higher priority tasks execute too frequently, then a lower priority task will starve of service. Our key observation for PFPS is that data-driven execution of applications may not conform to conventional real-time event models. This thesis presents a critical-execution that minimizes the duration between the execution of consecutive instances of a higher priority task, and maximizes the execution of each instance. Using this critical execution we obtain an upper-bound on the interference a higher priority task can cause to the execution of a lower priority task. Subsequently, we define a worst-case response function for consecutive instances of a lower priority task. This worst-case response time function is then used to construct our response model for PFPS. Our experiments show that our approach has a broader applicability than the concurrently published literature on dataflow analysis of PFPS for data-driven systems. This thesis also presents two refinements to our basic technique. The first exploits the static-ordering among higher priority tasks to obtain a more accurate bound on the interference. Our ability to account for static-ordered execution of higher priority tasks demonstrates an 80% reduction in computed worst-case response time of a lower priority task as compared to a contemporary dataflow analysis.
The second refinement obtains a more accurate bound on the interference for scenarios where the higher priority tasks have a strictly periodic source.

An important objective of our work is to analyze the performance of different scheduling alternatives for the given timing requirements of systems. As a proof-of-concept, this thesis presents a quantitative comparison of scheduling techniques for an industrial case-study provided by Ericsson BV, Eindhoven, in which two 4G-LTE receivers are deployed on a proprietary heterogeneous multi-processor platform. Our study aims to find which between the two candidate scheduling techniques satisfies the timing requirements of our system at lower power consumption. Our study concludes that TDM outperforms PFPS and relatively consumes less power as compared to PFPS to satisfy the timing requirements of our system.