Real-time object recognition on edge devices with constrained computing resources involves a trade-off between computational workload and classification accuracy. Existing classifier models are individual classifiers that are typically designed for either fast inference with reduced accuracy or high accuracy with significant computational cost. A recently proposed concept, called IDK (which stands for "I don’t know") classifiers, enables cascading multiple existing classifiers to achieve high accuracy while significantly reducing average inference time. In this work, we compose IDK classifier cascades for the Tiny ImageNet dataset. Each input is processed sequentially through classifiers—from faster, less accurate ones to slower, more accurate ones. When an upstream classifier returns a high-confidence prediction, downstream models are skipped, improving average inference time. Our experiments demonstrate that IDK classifier cascades can reduce average computation time per inference while maintaining high classification accuracy compared to state-of-the-art individual models.

Deep learning–based classifiers are widely used for perception in autonomous Cyber-Physical Systems (CPS’s). However, such classifiers rarely offer guarantees of perfect accuracy while being optimized for efficiency. To support safety-critical perception, ensembles of multiple different classifiers working in concert are typically used. Since CPS’s interact with the physical world continuously, it is not unreasonable to expect dependencies among successive inputs in a stream of sensor data. Prior work introduced a classification technique that leverages these inter-input dependencies to reduce the average time to successful classification using classifier ensembles. In this paper, we propose generalizations to this classification technique, both in the improved generation of classifier cascades and the modeling of temporal dependencies. We demonstrate, through theoretical analysis and numerical evaluation, that our approach achieves further reductions in average classification latency compared to the prior methods.

Neural Network Inference (NNI) has become a critical element in mobile and autonomous systems, particularly for time-sensitive operations like obstacle detection and avoidance. Alongside execution time, energy consumption holds significant importance in such workloads, given that power is a limited resource in these systems. Modern System-on-Chips (SoCs) in mobile and autonomous devices are equipped with a diverse range of accelerators, each characterized by distinct power and performance features. Adapting to dynamically changing physical conditions, the execution flow of these crucial workloads can be optimized to utilize multiple accelerators, allowing for a flexible trade-off between performance and energy consumption. In this study, we leverage multiple accelerators within an SoC to execute NNI using NVIDIA TensorRT. Our primary goal is to enable an energy-performance trade-off by intelligently distributing layers of a neural network between accelerators that prioritize performance and those that emphasize power efficiency. Initially, we analyze the execution time and energy characteristics of neural network layer execution on various accelerators. Subsequently, we examine various factors influencing layer execution. Finally, we propose two algorithms to determine the mapping of layers to accelerators, minimizing energy consumption while adhering to a predetermined target NN inference execution time. We evaluate our approaches on the NVIDIA AGX Orin SoC using the commonly used ResNetSO model. According to the experiment results, we suggest adopting a coarse-grained layer grouping strategy. For applications with stringent real-time requirements, it is recommended to utilize the proposed LTN approach to better achieve the target execution time. Alternatively, in other scenarios, the Knapsack approach may be chosen for potential improvements in energy consumption.

The second generation of robot operating system (ROS 2) received significant attention from the real-time system research community, mostly aiming at providing formal modeling and timing analysis. However, most of the current efforts are limited to the default scheduling design schemes of ROS 2. The unique scheduling policies maintained by default ROS 2 significantly affect the response time and acceptance rate of workload schedulability. It also invalidates the adaptation of the rich existing results related to nonpreemptive (and limited-preemptive) scheduling problems in the real-time systems community to ROS 2 schedulability analysis. This article aims to design, implement, and analyze a standard dynamic priority-based real-time scheduler for ROS 2 while handling shared resources. Specifically, we propose to replace the readySet with a readyQueue, which is much more efficient and comes with improvements for callback selection, queue updating, and a skipping scheme to avoid priority inversion from resource sharing. Such a novel ROS 2 executor design can also be used for efficient implementations of fixed priority policies and mixed-policy schedulers. Our modified executor maintains the compatibility with default ROS 2 architecture. We further identified and built a link between the scheduling of limited-preemption points tasks via the global earliest deadline first (GEDF) algorithm and ROS 2 processing chain scheduling without shared resources. Based on this, we formally capture the worst-case blocking time and thereby develop a response time analysis for ROS 2 processing chains with shared resources. We evaluate our scheduler by implementing our modified scheduler that accepts scheduling parameters from the system designer in ROS 2. We ran two case studies-one using real ROS 2 nodes to drive a small ground vehicle, and one using synthetic tasks. The second case study identifies a case where the modified executor prevents priority inversion. We also test our analysis with randomly generated workloads. In our tests, our modified scheduler performed better than the ROS 2 default. Our code is available online:https://github.com/RTIS-Lab/ROS-Dynamic-Executor.

Following the trend of increasing autonomy in real-time systems, multi-core System-on-Chips (SoCs) have enabled devices to better handle the large streams of data and intensive computation required by such autonomous systems. In modern multi-core SoCs, each L1 cache is designed to be tied to an individual processor, and a processor can only access its own L1 cache. This design method ensures the system's average throughput, but also limits the possibility of parallelism, significantly reducing the system's real-time schedulability. To overcome this problem, we present a new system framework for highly-parallel multi-core systems,Hopscotch.Hopscotchintroduces re-sizable L1 cache which is shared between processors in the same computing cluster. At execution,Hopscotchdynamically allocates L1 cache capacity to the tasks executed by the processors, unblocking the available parallelism in the system. Based on the new hardware architecture, we also present a new theoretical model and schedulability analysis providing cache size selection methods and corresponding timing guarantees for the system. As demonstrated in the evaluations,Hopscotcheffectively improves system-level schedulability with negligible extra overhead.

Developing autonomous driving models through reinforcement learning is gaining widespread prominence. However, a pervasive problem is developing obstacle avoidance systems. Specifically, optimizing path completion times while avoiding objects is an underdeveloped area of research. AWS DeepRacer’s platform provides a powerful architecture for engineering and analyzing autonomous models. Using AWS DeepRacer, we integrate two pathfinding algorithms, A* and Line-of-Sight (LoS), into this paradigm of autonomous driving. LoS is a novel algorithm that incrementally updates the model’s heading angles to amply reach its destination. We trained three types of models: Centerline, A*, and LoS. The Centerline model utilizes logic from AWS and is practically the only model used by the AWS DeepRacer community that avoids objects. We developed models from A* and LoS that outperformed the default models in time per lap while maintaining commensurate stability.

AWS DeepRacer is a fully autonomous 1/18th scale race car designed to help developers learn and practice reinforcement learning through cloud-based simulations and real-world racing. What drives the reinforcement learning model is the reward function, a way to provide positive or negative feedback to an agent, guiding its learning process in reinforcement learning by assigning numerical values. In the AWS training environment, there are multiple modes in which you can run training simulations and evaluations in. These modes include Time Trial, Object Avoidance, and a relatively new mode: Head to Bot. The research done in this project was primarily focused on testing reward functions in the Head to Bot mode as well as developing a research function that would be suited for training in this new Head to Bot mode. The developed algorithm outperformed the default Centerline reward function, as well as the Object Avoidance reward function.

Software reusability and system modularity are key features of modern autonomous systems. As a consequence, there is a rapid shift towards hierarchical and compositional architecture, as evidenced by AUTOSAR in automobiles and ROS2 in robotics. The resource-budget supply model is widely applied in the real-time analysis of such systems. Meanwhile, real-time systems with multiple critical levels have received significant attention from the research community and industry. These systems are designed with multiple execution budgets for multiple system-critical levels. Existing studies on mixedcriticality systems consider a dedicated resource supply. This paper considers a novel generalized system model with multiple execution estimations and resource-budget supplies for compositional systems. An analytical model and a demand-bound function-based schedulability test are presented for the EDFbased scheduler in the proposed compositional mixed-criticality system. A range for setting the resource supply period is derived to ensure the schedulability of workloads when supply budgets are known. The general performance of the scheduling framework and its wider applicability is further demonstrated and evaluated using synthetic workloads and resource models, where synthetic workload parameters are derived through a case study on an autonomous driving system.

Real-time systems are characterized by strict timing constraints represented by deadlines. Some systems are tight, such that jobs finish their execution right at the deadlines in the worst case, while others may not be so tight. Static slack is a concept that captures such non-tightness, and it can often be “stolen” to handle additional aperiodic job requests, task suspensions, and occasional task overruns. This paper identifies an interesting and direct correlation between worst-case response time (WCRT) and static slack in a deadline-driven uniprocessor system. We propose a systematic approach for safely constructing a set of Sporadic P-Servers to tightly capture the available static slack, given any feasible task set under a preemptive earliest deadline first. These P-Servers are special in that each task has only a unit-length execution budget and runs in a discrete manner. To leverage these P-Servers and “steal” the slack, we propose a novel consume-replenish algorithm to handle online hard aperiodic jobs. We also extend the theory for other applications, such as dealing with early and arbitrary self-suspensions and servicing job overruns in mixed-criticality systems without triggering a mode switch. Experiments demonstrate that the proposed theory can provide new and better schedulability in some subcases for each application.

In modern real-time heterogeneous System-on-Chips (SoCs), ensuring the predictability of interconnects is becoming increasingly important. Most of the existing interconnects are mainly designed to achieve high throughput, with their micro-architectures usually based on FIFO queues. The FIFO-based design prevents transaction prioritization based on importance and leads to occurrences of physical priority inversion. Such problems lead to difficulties in ensuring transaction predictability, especially when the system scales to a large number of elements. In this paper, we introduce AXI-Interconnect^{rt} (AXI-IC^{rt}, for short) -- a real-time AXI interconnect for heterogeneous SoCs, which redefines the micro-architecture of interconnects by enabling random accesses of buffered transactions and organizing transactions through compositional scheduling. This hardware-software co-design approach provides predictable and scalable real-time performance for highly integrated SoCs.

In safety-critical computing systems, the I/O virtualization must simultaneously satisfy different requirements, including time-predictability, performance, and energy-efficiency. However, these requirements are challenging to achieve due to complex I/O access path and resource management at the system level, lack of support from preemptive scheduling at I/O hardware level, and missing an effective energy management method. In this paper, we propose a new framework, I/O-GUARD, which reconstructs the system architecture of I/O virtualization, bringing a dedicated hardware hypervisor to handle resource management throughout the system. The hypervisor improves system real-time performance by enabling preemptive scheduling in I/O virtualization with both analytical and experimental real-time guarantees. Furthermore, we also present a dedicated energy management unit to adjustI/O-GUARD's dynamic energy using frequency scaling. Associated with that, a frequency identification algorithm is proposed to find the appropriate executing frequency at run-time. As shown in experiments,I/O-GUARDsimultaneously improves the predictability, performance and energy-efficiency compared to the state-of-the-art I/O virtualization.

While traditional real-time systems analysis requires single pessimistic estimates to represent system parameters, the mixed-criticality (MC) design proposes to use multiple estimates of system parameters with different levels of pessimism, resulting in low critical workloads sacrificed at run-time in order to provide guarantees to high critical workloads. Shortcomings of the MC design were improved recently by the precise MC scheduling technique in which the processor speed is increased at run-time to provide guarantees to both low and high critical workloads. Aiming to extend the precise MC scheduling to multiprocessor computing platforms, this paper proposes three novel scheduling algorithms that are based on virtual-deadline and fluid-scheduling approaches. We prove the correctness of our proposed algorithms through schedulability analysis and also present their theoretical effectiveness via speedup bounds and approximation factor calculations. Finally, we evaluate their performance experimentally via randomly generated task sets and demonstrate that the fluid-scheduling algorithms outperform the virtual-deadline algorithm.

In real-time embedded computing, time-predictability and performance are required simultaneously by memory transactions. However, with increasingly more elements being integrated into hardware, memory interconnects become a critical stumbling block to satisfying timing correctness, due to lack of hardware and scheduling scalability. In this paper, we propose a new hierarchically distributed memory interconnect, BlueScale, managing memory transactions using identical Scale Elements, which ensures hardware scalability. The Scale Element introduces two nested priority queues, achieving iterative compositional scheduling for memory transactions, guaranteeing transaction tasks' scheduling schedulability. Associated with the new architecture, a theoretical model is established to improve BlueScale's real-time performance.

Many safety-critical real-time systems are considered certified when they meet failure probability requirements with respect to the maximum permitted incidences of failure per hour. In this article, the mixed-criticality task model with multiple worst case execution time (WCET) estimations is extended to incorporate such system-level certification restrictions. A new parameter is added to each task, characterizing the distribution of WCET estimations—the likelihood of all jobs of a task finishing their executions within the less pessimistic WCET estimates. Efficient algorithms are derived for scheduling mixed-criticality systems represented using this model for both uniprocessor and multiprocessor platforms for independent tasks. Furthermore, a 0/1 covariance matrix is introduced to represent the failure dependency between tasks. An efficient algorithm is proposed to schedule such failure-dependent tasks. Experimental analyses show our new model and algorithm outperform current state-of-the-art mixed-criticality scheduling algorithms.

For safety-critical| computer systems, time-predictability and performance are usually required simultaneously in I/O virtualization. However, both requirements are challenging to achieve due to complex I/O access path and resource management at system level and lack of support from preemptive scheduling at I/O hardware level. In this paper, we propose a new framework, I/O-GUARD, which reconstructs the system architecture of I/O virtualization, bringing a dedicated hardware hypervisor to handle resource management throughout the system. The hypervisor improves system real-time performance by enabling preemptive scheduling in I/O virtualization with both analytical and experimental real-time guarantees. Specifically, I/O-GUARD is a First-of-Its-Kind framework for multi-/many-core I/O virtualization.

In modern, real-time heterogeneous systems, ensuring the predictability of interconnects is becoming increasingly important. Existing interconnects are mainly designed to achieve high throughput, with their micro-architectures usually based on FIFO queues. This FIFO-based design prevents prioritization of transactions based on their importance, leading to difficulties in ensuring transaction predictability, especially in a system with a large number of system components. In this paper, we introduce AXI-InterconnectRT, a real-time AXI interconnect for heterogeneous SoCs, which redefines the micro-architecture of interconnects by enabling random accesses of buffered transactions and organizing transactions using dedicated hardware units. With the new micro-architecture, AXI-InterconnectRTcan manage transactions based on their importance, guaranteeing their predictability.

Mixed-criticality (MC) scheduling has been proposed to mitigate the pessimism in real-time schedulability analysis that must provide guarantees for the worst case. In most existing work on MC scheduling, low-critical tasks are either dropped or degraded at the criticality mode switch in order to preserve the temporal guarantees for high-critical tasks. Recently, a different direction, called precise MC scheduling, has been investigated. In precise MC scheduling, no low-critical task should be dropped or degraded; instead, the platform processing capacity is augmented at mode switch to accommodate the additional workload by high-critical tasks. In contrast to prior work on this topic with respect to varying processor speed, this work investigates the precise scheduling problem of MC tasks when the number of available processors may vary at the mode switch. To address this new problem, we propose two alternative algorithms by adapting virtual-deadline-based EDF and by fluid scheduling, respectively, and provide a sufficient schedulability test for each. We also conduct schedulability experiments with randomly generated task sets to demonstrate the effectiveness of the proposed algorithms and the benefits of the new scheduling model.

Following the trend of increasing autonomy in cyber-physical systems, parallel embedded architectures have enabled devices to better handle the large streams of data and intensive computation required by such autonomous systems. However, while the explosion of highly-parallel platforms has seen a proportional growth in the number of applications/devices that utilize these platforms, the embedded systems community's understanding of how to build time-predictable, safety-critical systems with parallel platforms has not kept pace. As a well-motivated but challenging parallel scheduling model, gang scheduling requires all parallel threads of each parallel task to simultaneously execute in unison, which is in contrast to traditional, multi-threaded parallel scheduling, where a parallel task may spawn multiple threads, and each thread will be scheduled independently of other threads of the same task. While increasing research efforts on hard real-time (HRT) gang scheduling have recently been seen, the problem of gang scheduling in the context of soft real-time (SRT) systems, where provably bounded deadline tardiness can be tolerated, has hardly been studied yet. In this article, we derive and prove the first tardiness bounds for sporadic gang task systems under preemptive GEDF scheduling. A total utilization bound for SRT-schedulability is required for ensuring such tardiness bounds but it is shown to be tight with respect to the platform capacity and maximum parallelism-induced idleness. Furthermore, we also empirically evaluate the effects of different degrees of task parallelism upon the SRT-schedulability.

Increasingly complex and integrated systems design has led to more timing uncertainty, which may result in pessimism in time-sensitive system design and analysis. To mitigate such pessimism, mixed-criticality (MC) design for real-time systems has been proposed, where highly critical tasks, often with extremely pessimistic execution time estimates, can share the processor with less critical ones in a manner that the latter is sacrificed, completely or partially, to guarantee temporal correctness to the former, when the extremely pessimistic scenario does happen. In contrast to such sacrifice of tasks, the precise MC scheduling model has recently been investigated, where all tasks, including less critical ones, must fully complete their execution in all circumstances. Meanwhile, the processor may operate at a degraded speed when the tasks' runtime behaviors are far from the extreme pessimistic estimates and would recover to the full processing speed once the extremely pessimistic scenario does happen.

In order to mitigate the pessimism in parameter estimation in real-time systems, mixed-criticality (MC) scheduling has been proposed and studied. In light of the first MC scheduling work focusing on multiple estimates on the worst-case execution times (WCETs), a few following works also have extended this approach to other dimensions, such as periods, relative deadlines, and processor speeds. Nonetheless, in most existing work on MC scheduling, a flat-structured scheduling approach is assumed, whereas compositional real-time systems with hierarchical scheduling are of great interest, especially for large-scale real-time systems. In this work, we aim to extend the fundamental ideas and frameworks of MC scheduling to another dimension, namely the budget estimation. To illustrate this approach, we form up a specific scheduling problem in the context of a single virtual processor characterized by the periodic resource model and propose a virtual-deadline-based algorithm to solve it. Furthermore, we have developed a polynomial-time schedulability test and have proved a speed-up bound for the proposed algorithm. We have also derived a range for setting the resource period to ensure schedulability when the bandwidth and task set are given. Moreover, we have conducted schedulability studies and presented our simulation experiment results to evaluate the proposed model and algorithm.

In mixed-criticality systems, mode switch is a key strategy which dynamically provides a balance between system performance and safety. In conventional MCS frameworks, mode switch is triggered by the over-execution of a task; i.e., a task overruns the less pessimistic worst-case execution time. In cyber-physical systems, the data volume generated by I/O affects and can even dominate task computation time. With this in mind, we introduce a novel MCS architecture, termed Pythia-MCS, which predicts task execution time according to I/O run-time behaviors. With the new feature of future-prediction, the Pythia-MCS provides more timely, but still accurate, mode switch. We also present a new theoretical model (quarter-clairvoyance), which guarantees the timing predictability of the design, and a new schedulability analysis for the Pythia-MCS, which demonstrates improved schedulability compared to conventional MCS frameworks. The Pythia-MCS is the first MCS framework enabling the clairvoyance functionality.

Mixed-criticality (MC) scheduling has been proposed for embedded real-time systems to alleviate the dilemma between runtime resource utilization and worst-case temporal guarantees for critical functions. The approach of dropping all low-criticality tasks upon a mode switch has been criticized for potentially over-degraded performance. In this paper, we focus on the graceful degradation for MC scheduling by providing bounded lateness for certain low-critical tasks. We define MCQOS-schedulability that massages the required bounded lateness into the definition of conventional MC-schedulability. A virtual deadline based scheduler (EDF-VDS) is proposed with utilization-based MCQOS-schedulability test and and closed-form lateness bounds.

Mixed-criticality (MC) scheduling of sequential tasks (with no intra-task parallelism) has been well-explored by the real-time systems community. However, till date, there has been little progress on MC scheduling of parallel tasks. MC scheduling of parallel tasks is highly challenging due to the requirement of various assurances under different criticality levels. In this work, we address the MC scheduling of parallel tasks of gang model that allows workloads to execute on multiple cores simultaneously. Such a workload model represents an efficient mode-based parallel processing scheme with many potential applications. To schedule such task sets, we propose a new technique GEDF-VD, which integrates Global Earliest Deadline First (GEDF) and Earliest Deadline First with Virtual Deadline (EDF-VD). We prove the correctness of GEDF-VD and provide a detailed quantitative evaluation in terms of speedup bound in both the MC and the non-MC cases. Specifically, we show that GEDF provides a speedup bound of 2 for non-MC gang tasks, while the speedup for GEDF-VD considering MC gang tasks is √5 + 1. Experiments on randomly generated gang task sets are conducted to validate our theoretical findings and to demonstrate the effectiveness of the proposed approach.

The scheduling of mixed-criticality (MC) systems with graceful degradation is considered, where LO-criticality tasks are guaranteed some service in HI mode in the form of minimum cumulative completion rates. First, we present an easy to implement admission-control procedure to determine which LO-criticality jobs to complete in HI mode. Then, we propose a demand-bound-function-based MC schedulability test that runs in pseudo-polynomial time for such systems under EDF-VD scheduling, wherein two virtual deadline setting heuristics are considered. Furthermore, we discuss a mechanism for the system to switch back from HI to LO mode and quantify the maximum time duration such recovery process would take. Finally, we show the effectiveness of our proposed method by experimental evaluation in comparison to state-of-the-art MC schedulers.

OpenVX is a recently ratified standard that was expressly proposed to facilitate the design of computer-vision (CV) applications used in real-time embedded systems. Despite its real-time focus, OpenVX presents several challenges when validating real-time constraints. Many of these challenges are rooted in the fact that OpenVX only implicitly defines any notion of a schedulable entity. Under OpenVX, CV applications are specified in the form of processing graphs that are inherently considered to execute monolithically end-to-end. This monolithic execution hinders parallelism and can lead to significant processing-capacity loss. Prior work partially addressed this problem by treating graph nodes as schedulable entities, but under OpenVX, these nodes represent rather coarse-grained CV functions, so the available parallelism that can be obtained in this way is quite limited. In this paper, a much more fine-grained approach for scheduling OpenVX graphs is proposed. This approach was designed to enable additional parallelism and to eliminate schedulability-related processing-capacity loss that arises when programs execute on both CPUs and graphics processing units (GPUs). Response-time analysis for this new approach is presented and its efficacy is evaluated via a case study involving an actual CV application.

It has long been known that the global earliest-deadlinefirst (GEDF) scheduler is soft real-time (SRT) optimal for sporadic task systems executing on identical multiprocessor platforms, regardless of whether task execution is preemptive or non-preemptive. This notion of optimality requires deadline tardiness to be provably bounded for any feasible task system. In recent years, there has been interest in extending these SRT optimality results to apply to uniform heterogeneous platforms, in which processors may have different speeds. However, it was recently shown that nonpreemptive GEDF is not SRT optimal on such platforms. The remaining case, preemptive GEDF, has turned out to be quite difficult to tackle and has remained open for a number of years. In this paper, this case is resolved by showing that preemptive GEDF is indeed SRT optimal on uniform platforms, provided a certain job migration policy is used.

A real-time multiprocessor synchronization problem is studied herein that has not be extensively studied before, namely, the management of replicated resources where tasks may require multiple replicas to execute. In prior work on replicated resources, k-exclusion locks have been used, but this restricts tasks to lock only one replica at a time. To motivate the need for unrestricted replica sharing, two use cases are discussed that reveal an interesting tradeoff: in one of the use cases, blocking is the dominant lock-related factor impacting schedulability, while in the other, lock/unlock overheads are. Motivated by these use cases, three replica-allocation protocols are presented. In the first two, the lock/unlock logic is very simple, yielding low overheads, but blocking is not optimal. In the third, blocking is optimal (ignoring constant factors), but additional lock/unlock overhead is incurred to properly order lock requests. Experiments are presented that examine the overhead/blocking tradeoff motivated by these protocols in some detail.

Many approaches have been proposed to enable disparate real-time software components to share a physical multiprocessor platform by giving each component the "illusion" of executing on a dedicated virtual platform. Such an illusion is supported by specifying a supply interface that indicates how computation time is made available to a component over time. A number of approaches for defining such interfaces have been proposed: so many that sifting through them all can be confusing for the practitioner. In the case of soft real-time applications, one particular proposed interface-minimum-parallelism (MP) supply-has been shown to enable the co-scheduling of different components with no utilization loss. In the case of hard real-time applications, it follows from prior work that MP supply easily dominates other choices if the simplifying assumption is made that supply is allocated on different processors using a common, synchronized allocation period. The main contribution of this paper is to show that the dominance of MP supply is retained if this simplifying assumption is removed, provided the period of allocation is defined properly. This result suggests that MP supply should be the focus in future work on real-time multiprocessor virtualization.

A semi-partitioned scheduler called EDF-tu is presented that is the first such scheduler to be optimal on uniform heterogeneous multiprocessors. EDF-tu utilizes an adjustable allocation parameter called a frame to schedule tasks that migrate. The frame size F must divide all task periods to ensure hard real-time optimality, but for any choice of F, maximum deadline tardiness is at most F. Thus, the proper selection of F hinges on runtime overheads (which are higher when F is smaller) and the strength of the real-time guarantee desired. When determining which tasks must migrate, new issues specific to heterogeneous platforms arise that have not been explored before. It is shown via counterexamples that resolving such issues differently from EDF-tu can render feasible task systems unschedulable.

Many safety critical real-time systems are considered certified when they meet failure probability requirements with respect to the maximum permitted incidences of failure per hour. In this paper, the mixed-criticality task model with multiple worst case execution time (WCET) estimations is extended to incorporate such system-level certification restrictions. A new parameter is added to each task, characterizing the distribution of the WCET estimations -- the likelihood of all jobs of a task finishing their executions within the less pessimistic WCET estimate. An efficient algorithm named LFF-Clustering is derived for scheduling mixed-criticality systems represented by this model. Experimental analyses show our new model and algorithm out-perform current state-of-the-art mixed-criticality scheduling algorithms.

Under the definition of soft real-time (SRT) correctness that requires deadline tardiness to be bounded, both the pre-emptive and non-pre-emptive global EDF (GEDF) schedulers are known to be SRT-optimal on identical multiprocessors. This paper considers the potential extension of these results to uniform heterogeneous multiprocessors. In the pre-emptive case, it is shown that such an extension is possible for two-processor platforms but unlikely for platforms of more than two processors, unless fundamentally new proof techniques are developed. In the non-pre-emptive case, it is shown that no work-conserving scheduler, including GEDF, can be SRT-optimal on uniform multiprocessors, even if the number of processors is limited to two.

In the automotive industry, there is currently great interest in supporting driver-assist and autonomouscontrol features that utilize vision-based sensing through cameras. The usage of graphics processing units (GPUs) can potentially enable such features to be supported in a cost-effective way, within an acceptable size, weight, and power envelope. OpenVX is an emerging standard for supporting computer vision workloads. OpenVX uses a graph-based software architecture designed to enable efficient computation on heterogeneous platforms, including those that use accelerators like GPUs. Unfortunately, in settings where real-time constraints exist, the usage of OpenVX poses certain challenges. For example, pipelining is difficult to support and processing graphs may have cycles. In this paper, graph transformation techniques are presented that enable these issues to be circumvented. Additionally, a case-study evaluation is presented involving an OpenVX implementation in which these techniques are applied. This OpenVX implementation runs atop a previously developed GPU-management framework called GPUSync. In this case study, the usage of GPUSync's GPU management techniques along with the proposed graph transformations enabled computer vision workloads specified using OpenVX to be supported in a predictable way.