We propose Matryoshka, a novel framework for transformer model pruning, enabling dynamic runtime controls while maintaining competitive accuracy to modern large language models (LLMs). Matryoshka incrementally constructs submodels with varying complexities, allowing runtime adaptation without maintaining separate models. Our evaluations on LLaMA-7B demonstrate that Matryoshka achieves up to 34% speedup and outperforms the quality of state-of-the-art pruning methods, providing a flexible solution for deploying LLMs.

Thanks to the advance of device scaling technologies, the capacity of SSDs is rapidly increasing. Such increase, however, comes at the cost of a huge index table requiring large DRAM. To provide reasonable performance with less DRAM, various index structures exploiting locality and regularity of I/O references have been proposed. However, they provide deteriorated performance depending on I/O patterns and storage fragmentation. This paper proposes a novel approximate index structure, called AppL, which combines memory-efficient approximate indices and an LSM-tree that has an append-only and sorted nature. AppL reduces the index size to 6-8-bits per entry, which is considerably smaller than the typical index structures requiring 32-64-bits, and maintains such high memory efficiency irrespective of locality and fragmentation. By alleviating memory pressure, AppL achieves 33.6-72.4% shorter read latency and 28.4%-83.4% higher I/O throughput than state-of-the-art techniques.

On-device machine learning applications are increasingly deployed in dynamic and open system environments, where resource availability fluctuates unpredictably. This variability, coupled with limited computing resources, poses significant challenges in achieving high responsiveness. Existing on-device machine learning frameworks typically rely on static and coarse-grained resource allocation, leading to performance degradation under resource contention. To address this, we propose FlexOn, a novel framework that combines fine-grained model segmentation and dynamic resource selection to rapidly adapt to highly dynamic runtime conditions and effectively mitigate unpredictable resource contention. A prototype built on LiteRT demonstrates significant improvements in both average and tail latencies of up to 54% and 58%, respectively, across three different embedded platforms under dynamically varying resource availability. To the best of our knowledge, this is the first work that addresses the resource contention in open embedded systems for better machine learning inference responsiveness.

Edge devices for robotics in hazardous environments, such as rescue drones, navigate complex terrains while transmitting images to remote servers for anomaly detection, including wildfires. However, these devices operate under strict resource constraints, prioritizing operational-critical tasks (e.g., autonomous navigation) while handling image-processing workloads with minimal overhead. Offloading computation to a remote server can alleviate this burden, but unstable network conditions can degrade accuracy and timeliness. To address these challenges, this paper presents a novel offloading framework that balances computational efficiency and accuracy in image-processing tasks. Specifically, it ensures (R1) a minimum accuracy level for individual image-processing tasks associated with different camera sensors and (R2) maximizes the overall image-processing accuracy across all sensors. Our approach builds on an edge-server collaborative image reconstruction architecture, where images are divided into patches and selectively reconstructed. To achieve R1 and R2, we introduce: (i) a hierarchical scheduler that effectively prioritizes patch transmissions under resource constraints and (ii) a feedback mechanism that adapts to network instability, ensuring reliable offloading and inference. Experimental results demonstrate that our framework maintains high accuracy and timely processing, even under network failures.

The Robot Operating System 2 (ROS 2) is a popular middleware for distributed robotic applications. However, achieving real-time guarantees in ROS 2 is challenging due to unpredictable delays and priority inversions. We reveal that these issues arise from the lack of consistent priority propagation across ROS 2's multi-layered communication architecture, particularly down to the kernel layer. To address this, we present CROS-RT, the first cross-layer scheduler explicitly designed to tackle the unpredictability in ROS 2 inter-process communication caused by multi-layer priority misalignment. CROS-RT ensures consistent, priority-based scheduling across the application, middleware, and kernel layers, introducing mechanisms for priority propagation, kernel-level message prioritization, and dynamic kernel thread adjustment. We have implemented and evaluated CROS-RT on the current stable release of ROS 2. Experiments demonstrate that CROS-RT enhances communication predictability, reducing the worst-case response time by up to 89.3 % over a baseline (vanilla ROS 2). Additionally, we provide an analytical model to derive upper bounds on response times, ensuring reliable realtime performance for safety-critical applications.

As the application scope of DNNs executed on microcontroller units (MCUs) extends to time-critical systems, it becomes important to ensure timing guarantees for increasing demand of DNN inferences. To this end, this paper proposes RT-MDM, the first RealTime scheduling framework for Multiple DNN tasks executed on an MCU using external memory. Identifying execution-order dependencies among segmented DNN models and memory requirements for parallel execution subject to the dependencies, we propose (i) a segment-group-based memory management policy that achieves isolated memory usage within a segment group and sharded memory usage across different segment groups, and (ii) an intra-task scheduler specialized for the proposed policy. Implementing RT-MDM on an actual system and optimizing its parameters for DNN segmentation and segment-group mapping, we demonstrate the effectiveness of RT-MDM in accommodating more DNN tasks while providing their timing guarantees.

The increasing complexity and memory demands of Deep Neural Networks (DNNs) for real-time systems pose new significant challenges, one of which is the GPU memory capacity bottleneck, where the limited physical memory inside GPUs impedes the deployment of sophisticated DNN models. This paper presents, to the best of our knowledge, the first study of addressing the GPU memory bottleneck issues, while simultaneously ensuring the timely inference of multiple DNN tasks. We propose RT-Swap, a real-time memory management framework, that enables transparent and efficient swap scheduling of memory objects, employing the relatively larger CPU memory to extend the available GPU memory capacity, without compromising timing guarantees. We have implemented RT-Swap on top of representative machine-learning frameworks, demonstrating its effectiveness in making significantly more DNN task sets schedulable at least 72% over existing approaches even when the task sets demand up to 96.2% more memory than the GPU's physical capacity.

To enhance the performance of autonomous driving, recent studies have been incorporating various tasks that require increasingly more computation. As computational demands increase, it is often difficult to achieve timely execution with the limited performance of onboard computing units alone. To address this issue, Vehicle Edge Computing (VEC), which offloads computational workloads to the edge and retrieves the results back to the vehicle, is gaining significant attention. To achieve efficient offloaded analytics via VEC, it is crucial to comprehensively consider both of the computing and network conditions of the V2X systems, as well as the vehicle energy consumption and timely execution. However, current studies have not sufficiently addressed the comprehensive modeling of computational and network loads in these V2X systems. To deal with this, we propose a Cooperative Network-Computation Load Balancing Simulator for VEC.

Deep neural networks (DNNs) have been deployed in many safety-critical real-time embedded systems. To support DNN tasks in real-time, most previous studies focused on GPU or CPU. However, Edge TPU has not yet been studied for real-time guarantees. This paper presents a real-time DNNs framework for Edge TPU to satisfy multiple DNN inference tasks’ timing requirements. The proposed framework provides 1) SRAM allocation and model partitioning techniques and 2) a MIP-based algorithm that determines the amount of SRAM and the number of segments for each task. The experiment result shows that our framework provides 79% higher schedulability than the existing Edge TPU system.

As real-time object detection systems, such as autonomous cars, need to process input images acquired from multiple cameras, they face significant challenges in delivering accurate and timely inferences often based on machine learning (ML). To meet these challenges, we want to provide different levels of object detection accuracy and timeliness to different portions within each input image with different criticality levels. Specifically, we develop DNN-SAM, a dynamic Split-And-Merge Deep Neural Network (DNN) execution and scheduling framework, that enables seamless split-and-merge DNN execution for unmodified DNN models. Instead of processing an entire input image once in a full DNN model, DNN-SAM first splits a DNN inference task into two smaller sub-tasks-a mandatory sub-task dedicated for a safety-critical (cropped) portion of each image and an optional sub-task for processing a down-scaled image–then executes them independently, and finally merges their results into a complete inference. To achieve DNN-SAM’s timely and accurate detection of objects in each image, we also develop two scheduling algorithms that prioritize sub-tasks according to their criticality levels and adaptively adjust the scale of the input image to meet the timing constraints while minimizing the response time of mandatory sub-tasks or maximizing the accuracy of optional sub-tasks. We have implemented and evaluated DNN-SAM on a representative ML framework. Our evaluation shows DNN-SAM to improve detection accuracy in the safety-critical region by $2.0-3.7\times$ and lower average inference latency by $4.8-9.7\times$ over existing approaches without violating any timing constraints.

Different from existing MOT (Multi-Object Tracking) techniques that usually aim at improving tracking accuracy and average FPS, real-time systems such as autonomous vehicles necessitate new requirements of MOT under limited computing resources: (R1) guarantee of timely execution and (R2) high tracking accuracy. In this paper, we propose RT-MOT, a novel system design for multiple MOT tasks, which addresses R1 and R2. Focusing on multiple choices of a workload pair of detection and association, which are two main components of the tracking-by-detection approach for MOT, we tailor a measure of object confidence for RT-MOT and develop how to estimate the measure for the next frame of each MOT task. By utilizing the estimation, we make it possible to predict tracking accuracy variation according to different workload pairs to be applied to the next frame of an MOT task. Next, we develop a novel confidence-aware real-time scheduling framework, which offers an offline timing guarantee for a set of MOT tasks based on non-preemptive fixed-priority scheduling with the smallest workload pair. At run-time, the framework checks the feasibility of a priority-inversion associated with a larger workload pair, which does not compromise the timing guarantee of every task, and then chooses a feasible scenario that yields the largest tracking accuracy improvement based on the proposed prediction. Our experiment results demonstrate that RT-MOT significantly improves overall tracking accuracy by up to 1.5 ×, compared to existing popular tracking-by-detection approaches, while guaranteeing timely execution of all MOT tasks.

As multiple software components with different safety-criticality levels are integrated on a shared computing platform, a real-time embedded system becomes a mixed-criticality (MC) system, which should provide timing guarantees at all different levels of assurance to software components with different criticality levels. In the real-time systems community, the concept of an MC system is regarded as a promising, emerging solution to solve an inherent challenge of real-time systems: pessimistic reservation of computing resources, which yields a low resource-utilization for the sake of guaranteeing timing requirements. Since a timing guarantee should be provided before a real-time system starts to operate, its feasibility has been extensively studied for single-criticality systems; however, the same cannot be said for MC systems. In this article, we develop necessary feasibility tests for MC real-time embedded systems, which is the first study that yields non-trivial results for MC necessary feasibility on both uniprocessor and multiprocessor platforms. To this end, we investigate characteristics of MC necessary feasibility conditions, and identify new challenges posed by the characteristics. By addressing those challenges, we develop two collective necessary feasibility tests and their simplified versions, which are able to exploit a tradeoff between capability in finding infeasible task sets and time-complexity. The simulation results demonstrate that the proposed tests find a number of additional infeasible task sets for both uniprocessor and multiprocessor platforms, which have been proven neither feasible nor infeasible by any existing studies.

The goal of this paper is to provide worst-case timing guarantees for real-time I/O requests, while fully utilizing the potential bandwidth for non real-time I/O requests in NAND flash storage systems. We identify a trade-off between flash chip sharing and I/O workload isolation in terms of timing guarantees and bandwidth. By taking such a trade-off into account, we propose a new real-time I/O scheduling framework that enables dynamic isolation between real-time I/O requests to meet all timing constraints and co-scheduling of real-time and non realtime I/O requests to provide high bandwidth utilization. Our in-depth evaluation results show that the proposed approach outperforms existing isolation approaches significantly in terms of both schedulability and bandwidth.

Deep neural networks (DNNs) have shown remarkable success in various machine-learning (ML) tasks useful for many safety-critical, real-time embedded systems. The foremost design goal for enabling DNN execution on real-time embedded systems is to provide worst-case timing guarantees with limited computing resources. Yet, the state-of-the-art ML frameworks hardly leverage heterogeneous computing resources (i.e., CPU, GPU) to improve the schedulability of real-time DNN tasks due to several factors, which include a coarse-grained resource allocation model (one-resource-per-task), the asymmetric nature of DNN execution on CPU and GPU, and lack of schedulability-aware CPU/GPU allocation scheme. This paper presents, to the best of our knowledge, the first study of addressing the above three major barriers and examining their cooperative effect on schedulability improvement. In this paper, we propose LaLaRAND, a real-time layer-level DNN scheduling framework, that enables flexible CPU/GPU scheduling of individual DNN layers by tightly coupling CPU-friendly quantization with fine-grained CPU/GPU allocation schemes (one-resource-per-layer) while mitigating accuracy loss without compromising timing guarantees. We have implemented and evaluated LaLaRAND on top of the state-of-the-art ML framework to demonstrate its effectiveness in making more DNN task sets schedulable by 56% and 80% over an existing approach and a baseline (vanilla PyTorch), respectively, with only up to -0.4% of performance (inference accuracy) difference.

The development of complex cyber-physical systems necessitates real-time networking with timing guarantees even in the presence of a link fault. Targeting firm real-time flows with the maximum allowable number of continuous deadline misses, this paper introduces FR-SDN, a fault-resilient SDN (Software-Defined Networking) framework that satisfies the timing requirements of firm real-time flows. To this end, we first investigate individual steps for path restoration: fault recognition, path recalculation, and path reassignment. We then design novel system architecture that reduces the delay of the fault recognition and path reassignment steps to potentially assign more time budget to the path recalculation step. Based on the calculation of tight upper-bounds on the delays in individual steps under the proposed system design, we derive a necessary feasibility condition that guarantees the timing requirements of firm real-time flows, and we calculate a time budget for the path recalculation step. Finally, we develop a multi-constrained path finding algorithm that can dynamically adjust the scope of flows to reroute according to the time budget. To the best of our knowledge, FR-SDN is the first study on adaptive path restoration for real-time flows, taking into account path restoration delay and fault tolerance constraints in case of link fault. We have implemented and evaluated FR-SDN on top of Open vSwitch to demonstrate its effectiveness, achieving an order of magnitude reduction in path restoration delay. In addition, we have deployed FR-SDN into a 1/10 scale autonomous vehicle and have shown, via an in-depth case study of adaptive cruise control, that FR-SDN is able to meet all fault tolerance requirements so that it can behave similarly as if there were no link failure.

While feasibility of timing guarantees has been extensively studied for single-criticality (SC) task systems, the same cannot be said true for mixed-criticality (MC) task systems. In particular, there exist only a few studies that address necessary feasibility conditions for MC task systems, and all of them have derived trivial results from existing SC studies that rely on simple demand-supply comparison. In this paper, we develop necessary feasibility tests for MC task systems on a uniprocessor platform, which is the first study that yields non-trivial results for MC necessary feasibility. To this end, we investigate characteristics of MC necessary feasibility conditions. Due to the existence of the mode change and consequences thereof, the characteristics pose new challenges that cannot be resolved by existing techniques for SC task systems, including how to calculate demand when the mode change occurs, how to determine the target sub-intervals for demand-supply comparison, how to derive an infeasibility condition from demand-supply comparisons with different possible mode change instants, how to select a scenario to specify the mode change instant without the target scheduling algorithm, and how to find infeasible task sets with reasonable time-complexity. By addressing those challenges, we develop a new necessary feasibility test and its simplified version. The simulation results demonstrate that the proposed tests find a number of additional infeasible task sets which have been proven neither feasible nor infeasible by any existing studies.

These days, the term of Internet of Things (IoT) becomes popular to interact and cooperate with individual smart objects, and one of the most critical challenges for IoT is to achieve efficient resource sharing as well as ensure safety-stringent timing constraints. To design such reliable real-time IoT, this paper focuses on the concept of mixed-criticality (MC) introduced to address the low processor utilization on traditional real-time systems. Although different worst-case execution time estimates depending on criticality are proven effective on processor scheduling, the MC concept is not yet mature on distributed systems (such as IoT), especially with end-to-end deadline guarantee. To the best of our knowledge, this paper presents the first attempt to apply the MC concept into interference (or jitter), which is a complicated source of pessimism when analyzing the schedulability of distributed systems. Our goal is to guarantee the end-to-end deadlines of high-criticality flows and minimize the deadline miss ratio of low-criticality flows in distributed systems. To achieve this goal, we introduce a jitter-based MC (JMC) scheduling framework, which supports node-level mode changes in distributed systems. We present an optimal feasibility condition (subject to given schedulability analysis) and two policies to determine jitter-threshold values to achieve the goal in different conditions. Via simulation results for randomly generated workloads, JMC outperforms an existing criticality-monotonic scheme in terms of achieving higher schedulability and fewer deadline misses.

Despite recent advances, there still remain many problems to design reliable cyber-physical systems. One of the typical problems is to achieve a seemingly conflicting goal, which is to support timely delivery of real-time flows while improving resource efficiency. Recently, the concept of mixed-criticality (MC) has been widely accepted as useful in addressing the goal for real-time resource management. However, it has not been yet studied well for real-time communication. In this paper, we present the first approach to support MC flow scheduling on switched Ethernet networks leveraging an emerging network architecture, software-defined networking (SDN). Though SDN provides flexible and programmatic ways to control packet forwarding and scheduling, it yet raises several challenges to enable real-time MC flow scheduling on SDN, including: 1) how to handle (i.e., drop or re-prioritize) out-of-mode packets in the middle of the network when the criticality mode changes and 2) how the mode change affects end-to-end transmission delays. Addressing such challenges, we develop MC-SDN that supports real-time MC flow scheduling by extending SDN-enabled switches and OpenFlow protocols. It manages and schedules MC packets in different ways depending on the system criticality mode. To this end, we carefully design the mode change protocol that provides analytic mode change delay bound, and then resolve implementation issues for system architecture. For evaluation, we implement a prototype of MC-SDN on top of Open vSwitch, and integrate it into a real world network testbed as well as a 1/10 autonomous vehicle. Our extensive evaluations with the network testbed and vehicle deployment show that MC-SDN supports MC flow scheduling with minimal delays on forwarding rule updates and it brings a significant improvement in safety in a real-world application scenario.

As modern embedded systems like cars need high-power integrated CPUs--GPU SoCs for various real-time applications such as lane or pedestrian detection, they face greater thermal problems than before, which may, in turn, incur higher failure rate and cooling cost. We demonstrate, via experimentation on a representative CPUs--GPU platform, the importance of accounting for two distinct thermal characteristics—the platform’s temperature imbalance and different power dissipations of different tasks —in real-time scheduling to avoid any burst of power dissipations while guaranteeing all timing constraints. To achieve this goal, we propose a new Real-Time Thermal-Aware Scheduling (RT-TAS) framework. We first capture different CPU cores’ temperatures caused by different GPU power dissipations (i.e., CPUs--GPU thermal coupling ) with core-specific thermal coupling coefficients. We then develop thermally-balanced task-to-core assignment and CPUs--GPU co-scheduling . The former addresses the platform’s temperature imbalance by efficiently distributing the thermal load across cores while preserving scheduling feasibility. Building on the thermally-balanced task assignment, the latter cooperatively schedules CPU and GPU computations to avoid simultaneous peak power dissipations on both CPUs and GPU, thus mitigating excessive temperature rises while meeting task deadlines. We have implemented and evaluated RT-TAS on an automotive embedded platform to demonstrate its effectiveness in reducing the maximum temperature by 6−12.2° C over existing approaches without violating any task deadline.

Safety-critical cyber-physical systems like autonomous cars require not only different levels of assurance, but also close interactions with dynamically-changing physical environments. While the former has been studied extensively by exploiting the notion of mixed-criticality (MC) systems, the latter has not, especially in conjunction with MC systems. To fill this important gap, we conduct an in-depth case study, demonstrating the importance of capturing current physical states, and introduce the problem of achieving efficient utilization of computing resources under varying physical states in MC systems. To solve this problem, we first develop a physical-state-aware MC task model, which is a generalization of the existing basic MC task model. We then propose new slack concepts tailored to the new task model, which enable efficient utilization of computing resources for MC systems. Finally, we develop a physical-state-aware dynamic slack management framework and demonstrate how to utilize the new MC task model and slack concepts towards efficient system utilization. We show, via a case study and in-depth evaluation, that the proposed framework makes 20x less low-criticality jobs dropped over a popular MC scheduling algorithm without compromising the MC-schedulability requirements.

A cyber-physical system (CPS) usually contains multiple control loops, each responsible for controlling different physical subprocesses, that run simultaneously upon a shared platform. The foremost design goal for CPSes is to guarantee system stability and control quality with limited cyber resources. We show, via an in-depth case study, that two inter-related design parameters - sampling period and consecutive control update misses - play a key role in determining stability and control performance. However, most CPS designs, such as control-schedule co-design and fault-tolerant scheduling, focus on either sampling period or control update misses alone, but not both. To remedy this problem, we propose a new CPS task model that captures both system stability and control performance in terms of sampling period and maximum allowable number of consecutive control update misses. To demonstrate the utility and power of this model, we develop two new scheduling mechanisms, offline parameter assignment and online state-aware scheduling. The former determines the sampling period and the maximum allowable number of consecutive job deadline misses for each task while preserving system stability. The latter then generates a schedule by exploiting the state of each physical subprocess to manage job deadline misses so as to improve the overall system performance without compromising system stability. Our in-depth evaluation results demonstrate that the proposed task model and the corresponding scheduling algorithm not only enable the efficient use of computing resource, but also significantly improve control performance without compromising system stability.

In this paper, we present the first approach to support mixed-criticality (MC) flow scheduling on switched Ethernet networks leveraging an emerging network architecture, Software-Defined Networking (SDN). Though SDN provides flexible and programmatic ways to control packet forwarding and scheduling, it yet raises several challenges to enable real-time MC flow scheduling on SDN, including i) how to handle (i.e., drop or reprioritize) out-of-mode packets in the middle of the network when the criticality mode changes, and ii) how the mode change affects end-to-end transmission delays. Addressing such challenges, we develop MC-SDN that supports real-time MC flow scheduling by extending SDN-enabled switches and OpenFlow protocols. It manages and schedules MC packets in different ways depending on the system criticality mode. To this end, we carefully design the mode change protocol that provides analytic mode change delay bound, and then resolve implementation issues for system architecture. For evaluation, we implement a prototype of MC-SDN on top of Open vSwitch, and integrate it into a real world network testbed as well as a 1/10 autonomous vehicle. Our extensive evaluations with the network testbed and vehicle deployment show that MC-SDN supports MC flow scheduling with minimal delays on forwarding rule updates and it brings a significant improvement in safety in a real-world application scenario.

With an increasing demand for complex and powerful system-on-chips, modern real-time automotive systems face significant challenges in managing on-chip-temperature. We demonstrate, via real experiments, the importance of accounting for dynamic ambient temperature and task-level power dissipation in resource management so as to meet both thermal and timing constraints. To address this problem, we propose RT-TRM, a real-time thermal-aware resource management framework. We first introduce a task-level dynamic power model that can capture different power dissipations with a simple task-level parameter called the activity factor. We then develop two new mechanisms, adaptive parameter assignment and online idle-time scheduling. The former adjusts voltage/frequency levels and task periods according to the varying ambient temperature while preserving feasibility. The latter generates a schedule by allocating idle times efficiently without missing any task/job deadline. By tightly integrating the solutions of these two mechanisms, we can guarantee both thermal and timing constraints in the presence of dynamic ambient temperature variations. We have implemented RT-TRM on an automotive microcontroller to demonstrate its effectiveness, achieving better resource utilization by 18.2% over other runtime approaches while meeting both thermal and timing constraints.

Real-time scheduling for Mixed-Criticality (MC) systems has received a growing attention as real-time embedded systems accommodate various tasks with different levels of criticality. While many studies have addressed how to guarantee timing requirements for MC systems with uniprocessor and multiprocessors, most of them have focused on supporting preemptive tasks. On the other hand, there have been few studies to address non-preemptive scheduling especially for MC multiprocessor platforms, in which the jobs under execution cannot be preempted by other jobs. In this paper, we develop schedulability tests for non-preemptive scheduling, which is the first attempt for MC multiprocessor systems. To this end, we first generalize an existing NP-EDF (Non-Preemptive Earliest Deadline First) schedulability test developed for single-criticality multiprocessor systems, towards for MC multiprocessor systems. For the generalization, we introduce new timing guarantee techniques for the system transition between two different criticalities, which is one of the key features in MC systems. We next extend the proposed NP-EDF schedulability test towards NP-EDFVD (NP-EDF with Virtual Deadlines) that is specialized for MC systems, and pose a virtual deadline assignment problem. We develop an optimal virtual deadline assignment policy using a control knob of the system-level deadline-reduction parameter and then a suboptimal one for the task-level parameter. Our simulation results demonstrate that the NP-EDFVD schedulability test with the proposed virtual deadline assignment policies finds a number of additional schedulable task sets, which are not schedulable by the NP-EDF schedulability test.

In the real-time systems community, many studies have addressed how to efficiently utilize a multiprocessor platform so as to accommodate as many periodic/sporadic real-time tasks as possible without violating any timing constraints. The scheduling theory has sufficiently matured for a set of implicit-deadline tasks (the relative deadline equal to the period), yielding a class of optimal scheduling algorithms. However, the same does not hold for a set of constrained-deadline tasks (the relative deadline no larger than the period) in that those task sets have been fully covered by neither existing implicit-deadline optimal scheduling algorithms nor heuristic scheduling algorithms., In this paper, we propose a scheduling framework that not only takes advantage of both existing implicit-deadline optimal and heuristic algorithms, but also surpasses both in finding schedulable constrained-deadline task sets. The proposed framework logically divides a given task set into the higher- and lower-priority classes and schedules the classes using an implicit-deadline optimal algorithm and a heuristic algorithm, respectively. Then, while the proposed framework guarantees schedulability of tasks in the higher-priority class by the target implicit-deadline optimal algorithm, we need to address the following technical issues for enabling tasks in the lower-priority class to efficiently reclaim remaining processor capacity while guaranteeing their schedulability: (i) division of a given task set into the two classes, (ii) selection/development of scheduling algorithms for the two classes, and (iii) development of a schedulability test for the framework with given (i) and (ii). We present a general case showing how to address (i)-(iii), and then a specific case addressing how to further improve schedulability by utilizing characteristics of the specific case. Our simulation results demonstrate that the proposed framework outperforms all existing scheduling algorithms in covering schedulable task sets; in particular, if we focus on task sets with the system density larger than the number of processors, the framework finds up to 446.3% additional schedulable task sets, compared to task sets covered by at least one of existing scheduling algorithms.

Recent embedded systems are becoming integrated systems with components of different criticality. To tackle this, mixed-criticality systems aim to provide different levels of timing assurance to components of different criticality levels while achieving efficient resource utilization. Many approaches have been proposed to execute more lower-criticality tasks without affecting the timeliness of higher-criticality tasks. Those previous approaches however have at least one of the two limitations; i) they penalize all lower-criticality tasks at once upon a certain situation, or ii) they make the decision how to penalize lower-criticality tasks at design time. As a consequence, they under-utilize resources by imposing an excessive penalty on low-criticality tasks. Unlike those existing studies, we present a novel framework, called MC-ADAPT, that aims to minimally penalize lower-criticality tasks by fully reflecting the dynamically changing system behavior into adaptive decision making. Towards this, we propose a new scheduling algorithm and develop its runtime schedulability analysis capable of capturing the dynamic system state. Our proposed algorithm adaptively determines which task to drop based on the runtime analysis. To determine the quality of task dropping solution, we propose the speedup factor for task dropping while the conventional use of the speedup factor only evaluates MC scheduling algorithms in terms of the worst-case schedulability. We apply the speedup factor for a newly-defined task dropping problem that evaluates task dropping solution under different runtime scheduling scenarios. We derive that MC-ADAPT has a speedup factor of 1.619 for task drop. This implies that MC-ADAPT can behave the same as the optimal scheduling algorithm with optimal task dropping strategy does under any runtime scenario if the system is sped up by a factor of 1.619.

With the widespread adoption of multi-core architectures, it is becoming more important to develop software in ways that takes advantage of such parallel architectures. This particularly entails a shift in programming paradigms towards fine-grained, thread-parallel computing. Many parallel programming models have been introduced for targeting such intra-task thread-level parallelism. However, most successful results on traditional multi-core real-time scheduling are focused on sequential programming models. For example, thread-level parallelism is not properly captured into the concept of interference, which is key to many schedulability analysis techniques. Thereby, most interference-based analysis techniques are not directly applicable to parallel programming models. Motivated by this, we extend the notion of interference to capture thread-level parallelism more accurately. We then leverage the proposed notion of parallelism-aware interference to derive efficient EDF schedulability tests that are directly applicable to parallel task models, including DAG models, on multi-core platforms, without knowing an optimal schedule. Our evaluation results indicate that the proposed analysis significantly advances the state-of-the-art in global EDF schedulability analysis for parallel tasks. In particular, we identify that our proposed schedulability tests are adaptive to different degrees of thread-level parallelism and scalable to the number of processors, resulting in substantial improvement of schedulability for parallel tasks on multi-core platforms.

In this paper, we propose an accurate cycle estimation framework which allows to use multiple instruction set simulators to simulate not only processors but also diverse peripheral devices. An instruction set simulator runs on a host machine to mimic functional behaviors of instructions running on a target hardware. It allows to estimate the execution time of software in a fast and accurate way and validate a system even when its target hardware does not yet exist or is not available.

Motivated by the cutting-edge two-type heterogeneous multicore chips, such as ARM's big.LITTLE, that offer a practical support for migration, this paper studies the global (or fully-migrative) approach to two-type heterogeneous multicore scheduling. Our goal is to design an optimal fully-migrative scheduling framework. To achieve this goal in an efficient and simple manner, we break the scheduling problem into two subproblems: workload assignment and schedule generation. We propose a per-cluster workload assignment algorithm, called Hetero-Split, that determines the fractions of workload of each task to be assigned to both clusters without losing feasibility with the complexity of O(n log n), where n is the number of tasks. Furthermore, it provides a couple of important properties (e.g., a dual property) that help to generate an optimal schedule efficiently. We also derive scheduling guidelines to design optimal schedulers for two-type heterogeneous multicore platforms, called Hetero-Fair. By tightly coupling the solutions of Hetero-Split and Hetero-Fair, we develop the first optimal two-type heterogeneous multicore scheduling algorithm, called Hetero-Wrap, that has the same complexity (O(n)) as in the identical multicore case. Finally, concerning a practical point of view, we derive the first bounds on the numbers of intra-and inter-cluster migrations under two-type heterogeneous multicore scheduling, respectively.

The trend towards multi-core/many-core architectures is well underway. It is therefore becoming very important to develop software in ways that take advantage of such parallel architectures. This particularly entails a shift in programming paradigms towards fine-grained, thread-parallel computing. Many parallel programming models have been introduced targeting such intra-task thread-level parallelism. However, most successful results on traditional multi-core real-time scheduling are focused on sequential programming models. For example, thread-level parallelism is not properly captured into the concept of interference, which is key to many schedulability analysis techniques. Thereby, most interference-based analysis techniques are not directly applicable to parallel programming models. Motivated by this, we extend the notion of interference to capture thread-level parallelism more accurately. We then leverage the proposed notion of parallelism-aware interference to derive efficient EDF schedulability tests that are directly applicable to synchronous parallel task models on multi-core platforms. Our evaluation results indicate that the proposed analysis significantly advances the state-of-the-art in EDF schedulability analysis for synchronous parallel tasks.

Unlike uniprocessor scheduling, EDF (categorized into job-level fixed-priority (JFP) scheduling) shows relatively poor performance on global multiprocessor scheduling. As no other global JFP multiprocessor algorithms are illuminated beyond EDF, this work proposes one, called EQDF (earliest quasi-deadline first), as a generalization of EDF. We define the quasi-deadline of a job as a weighted sum of its absolute deadline (capturing "urgency") and its worst case execution time (capturing "parallelism") with a system-level control knob to balance urgency and parallelism effectively. This paper then seeks to explore how it can improve the schedulability of global JFP scheduling. In addition to providing a new schedulability analysis for EQDF scheduling, it addresses the problem of priority assignment under EQDF by controlling the system-level control knob. It presents optimal and heuristic solutions to the problem subject to our proposed EQDF analysis. Our empirical results show the proposed heuristic solution outperforms EDF significantly, giving close to optimal results.

In global real-time multiprocessor scheduling, a recent analysis technique for Task-level Fixed-Priority (TFP) scheduling has been shown to outperform many of the analyses for Job-level Fixed-Priority (JFP) scheduling on average. Since JFP is a generalization of TFP scheduling, and the TFP analysis technique itself has been adapted from an earlier JFP analysis, this result is counter-intuitive and in our opinion highlights the lack of good JFP scheduling techniques. Towards generalizing the superior TFP analysis to JFP scheduling, we propose the Smallest Pseudo-Deadline First (SPDF) JFP scheduling algorithm. SPDF uses a simple task-level parameter called pseudo-deadline to prioritize jobs, and hence can behave as a TFP or JFP scheduler depending on the values of the pseudodeadlines. This natural transition from TFP to JFP scheduling has enabled us to incorporate the superior TFP analysis technique in an SPDF schedulability test. We also present a pseudo-deadline assignment algorithm for SPDF scheduling that extends the well-known Optimal Priority Assignment (OPA) algorithm for TFP scheduling. We show that our algorithm is optimal for the derived schedulability test, and also present a heuristic to overcome the computational complexity issue of the optimal algorithm. Our simulation results show that the SPDF algorithm with the new analysis significantly outperforms state-of-the-art TFP and JFP analysis.