Despite the transformative potential of Large Language Models (LLMs) in hardware design, a comprehensive evaluation of their capabilities in design verification remains underexplored. Current efforts predominantly focus on RTL generation and basic debugging, overlooking the critical domain of functional verification, which is the primary bottleneck in modern design methodologies due to the rapid escalation of hardware complexity. We present FIXME, the first end-to-end, multi-model, and open-source evaluation framework for assessing LLM performance in hardware functional verification (FV) to address this crucial gap. FIXME introduces a structured three-level difficulty hierarchy spanning six verification sub-domains and 180 diverse tasks, enabling in-depth analysis across the design lifecycle. Leveraging a collaborative AI-human approach, we construct a high-quality dataset using 100% silicon-proven designs, ensuring comprehensive coverage of real-world challenges. Furthermore, we enhance the functional coverage by 45.57% through expert-guided optimization. By rigorously evaluating state-of-the-art LLMs such as GPT-4, Claude3, and LlaMA3, we identify key areas for improvement and outline promising research directions to unlock the full potential of LLM-driven automation in hardware design verification. The benchmark is available at https://github.com/ChatDesignVerification/FIXME.

While Large Language Models (LLMs) demonstrate immense potential for automating integrated circuit (IC) development, their practical deployment is fundamentally limited by restricted context windows. Existing context-extension methods struggle to achieve effective semantic modeling and thorough multi-hop reasoning over extensive, intricate circuit specifications. To address this, we introduce ChipMind, a novel knowledge graph-augmented reasoning framework specifically designed for lengthy IC specifications. ChipMind first transforms circuit specifications into a domain-specific knowledge graph (ChipKG) through the Circuit Semantic-Aware Knowledge Graph Construction methodology. It then leverages the ChipKG-Augmented Reasoning mechanism, combining information-theoretic adaptive retrieval to dynamically trace logical dependencies with intent-aware semantic filtering to prune irrelevant noise, effectively balancing retrieval completeness and precision. Evaluated on an industrial-scale specification reasoning benchmark, ChipMind significantly outperforms state-of-the-art baselines, achieving an average improvement of 34.59% (up to 72.73%). Our framework bridges a critical gap between academic research and practical industrial deployment of LLM-aided Hardware Design (LAD).

Point-based networks achieve high accuracy by preserving the intrinsic spatial structure of point clouds. The spatial information is effectively extracted by set abstraction, a critical module for feature learning in point-based networks. However, set abstraction introduces a computational bottleneck, and naive parallelization often degrades sampling quality, leading to accuracy loss. To address these challenges, we propose Parallel-SA, a framework that accelerates point-based networks by transforming set abstraction from sequential to parallel processing without sacrificing accuracy. Parallel-SA leverages a multi-scale sampling distribution approximation to preserve sampling quality under parallel execution. In addition, it employs distribution-aware balanced partitioning and adaptive load-balancing refinement to further improve efficiency. Experiments show that Parallel-SA achieves an average 2.38× speedup in set abstraction with minimal accuracy degradation.

Numerous data-intensive applications benefit from offloading data processing to storage devices, typically Computational Storage Devices (CSD). Co-locating requests from diverse applications to one CSD offers better performance and power efficiency than dedicating CSDs to a single application. However, current CSD scheduling frameworks struggle to effectively manage contention among CPU, flash I/O, and buffer resources across requests due to less consideration in their inter-dependencies. This paper proposes REMUS, a CSD scheduling framework handling multiple requests for commercial SSD with multiple homogeneous cores. The key idea of REMUS is to allocate workloads across multiple cores based on the distribution of the Logical Block Address (LBA) of requests, and to mitigate stall time by sorting requests according to their urgency for resources, where urgency is quantified by each request’s remaining buffer capacity. Furthermore, a request batching scheme that intelligently groups the requests to be scheduled according to their characteristics is proposed to provide congestion control for REMUS and to minimize the contention it introduces. We conduct experiments on both a simulator and a real CSD platform. The experiment results show that REMUS improved throughput by 1.51× on the simulator and 1.39× on the real platform on average compared to the baselines.

As ROS 2 becomes increasingly adopted in safety-critical real-time systems, the performance of its communication layer, especially inter-process communication (IPC), has emerged as a key bottleneck. While intra-process communication benefits from zero-copy transmission, IPC suffers from significant latency due to serialization and memory copying. Existing shared memory approaches offer limited support for ROS 2 applications, as they impose strict constraints on message formats (e.g., requiring statically sized, POD-compatible types) and overlook end-to-end communication across multi-stage pipelines. In this work, we propose a novel and flexible architecture for enabling zero-copy IPC in ROS 2. Our design supports dynamically structured and non-POD message types, integrates seamlessly with the existing communication framework, and requires no modification to application logic. It consists of a Mini Memory Management System (MMS) for shared memory handling and a Message Propagation Adapter (MPA) that ensures compatibility with the ROS 2 communication framework. Our experimental results show that our method significantly reduces communication latency and supports efficient end-to-end message propagation.

In recent years, Deep Neural Networks (DNNs) have been increasingly adopted in a wide range of time-critical applications running on edge platforms equipped with heterogeneous multiprocessors. Given the limited resources available on these platforms, efficiently utilizing both CPU and GPU resources for time-sensitive DNN inference is crucial. However, this cross-processor inference paradigm poses significant challenges due to inherent performance imbalances between different processors. In this paper, we introduce BlastNet, a system that leverages duo-blocks—a novel model inference abstraction designed to enable highly efficient cross-processor, time-sensitive DNN inference. Each duo-block features a dual model structure, facilitating fine-grained, alternate inference across different processors. Duo-blocks are optimized during design and dynamically scheduled at runtime to maximize the resource utilization of CPU and GPU. To address memory constraints on edge devices, we also propose a duo-block selection algorithm that selectively constructs duo-blocks based on performance gains. BlastNet is implemented on an indoor autonomous driving platform and three popular edge platforms. Extensive evaluations demonstrate that BlastNet reduces the deadline missing rate by$35.07\,\%$with only a mere$1.63 \%$loss in model accuracy.

Whole-Slide Images (WSIs) have revolutionized medical analysis by presenting high-resolution images of the whole tissue slide. Despite avoiding the physical storage of the slides, WSIs require considerable data volume, which makes the storage and maintenance of WSI records costly and unsustainable. To this end, this work presents the first investigation of lossless compression of WSI images. Interestingly, we find that most existing compression methods fail to compress the WSI images effectively. Furthermore, our analysis reveals that the failure of existing compressors is mainly due to information irregularity in WSI images. To resolve this issue, we develop a simple yet effective lossless compressor called WISE, specifically designed for WSI images. WISE employs a hierarchical encoding strategy to extract effective bits, reducing the entropy of the image and then adopting a dictionary-based method to handle the irregular frequency patterns. Through extensive experiments, we show that WISE can effectively compress the gigapixel WSI images to 36 times on average and up to 136 times.

Verifying hardware designs in embedded systems is crucial but often labor-intensive and time-consuming. While existing solutions have improved automation, they frequently rely on unrealistic assumptions. To address these challenges, we introduce a novel framework, UVLLM, which combines Large Language Models (LLMs) with the Universal Verification Methodology (UVM) to relax these assumptions. UVLLM significantly enhances the automation of testing and repairing error-prone Register Transfer Level (RTL) codes, a critical aspect of verification development. Unlike existing methods, UVLLM ensures that all errors are triggered during verification, achieving a syntax error fix rate of 86.99% and a functional error fix rate of 71.92% on our proposed benchmark. These results demonstrate a substantial improvement in verification efficiency. Additionally, our study highlights the current limitations of LLM applications, particularly their reliance on extensive training data. We emphasize the transformative potential of LLMs in hardware design verification and suggest promising directions for future research in AI-driven hardware design methodologies. The Repo. of dataset and code: https://github.com/SEU-ACAL/reproduce-UVLLM-DAC-25/.

Neural image compression, necessary in various machine-to-machine communication scenarios, suffers from its heavy encode-decode structures and inflexibility in switching between different compression levels. Consequently, it raises significant challenges in applying the neural image compression to edge devices that are developed for powerful servers with high computational and storage capacities. We take a step to solve the challenges by proposing a new transformer-based edge-computefree image coding framework called Easz. Easz shifts the computational overhead to the server, and hence avoids the heavy encoding and model switching overhead on the edge. Easz utilizes a patch-erase algorithm to selectively remove image contents using a conditional uniform-based sampler. The erased pixels are reconstructed on the receiver side through a transformer-based framework. To further reduce the computational overhead on the receiver, we then introduce a lightweight transformer-based reconstruction structure to reduce the reconstruction load on the receiver side. Extensive evaluations conducted on a realworld testbed demonstrate multiple advantages of Easz over existing compression approaches, in terms of adaptability to different compression levels, computational efficiency, and image reconstruction quality.

Coding with hardware description languages (HDLs) such as Verilog is a time-intensive and laborious task. With the rapid advancement of large language models (LLMs), there is increasing interest in applying LLMs to assist with HDL coding. Recent efforts have demonstrated the potential of LLMs in translating natural language to traditional HDL Verilog. Chisel, a next-generation HDL based on Scala, introduces higher-level abstractions, facilitating more concise, maintainable, and scalable hardware designs. However, the potential of using LLMs for Chisel code generation remains largely unexplored. This work proposes ReChisel, an LLM-based agentic system designed to enhance the effectiveness of Chisel code generation. ReChisel incorporates a reflection mechanism to iteratively refine the quality of generated code using feedback from compilation and simulation processes, and introduces an escape mechanism to break free from non-progress loops. Experiments demonstrate that ReChisel significantly improves the success rate of Chisel code generation, achieving performance comparable to state-of-the-art LLM-based agentic systems for Verilog code generation.

As a fundamental perception task, 3D point cloud detection has become essential for applications in autonomous driving and robotics. However, point cloud detection faces significant challenges of high computational cost due to complex point processing operations. To address this issue, we propose DAWN, an acceleration framework for point cloud object detection that identifies partial similarities between adjacent frames and reduces computational cost by filtering redundant points. DAWN uses object-aware partitioning that defines boundaries based on previous detection results for localized similarity analysis. Additionally, it applies axis-sorted point selection to refine partitioning for point clouds with non-uniform distribution. An efficient 3D similarity algorithm then filters redundant points to reduce computational load. DAWN enables flexible latencyaccuracy trade-offs by tuning point filtering ratios. Experimental results show that DAWN achieves a $1.59 \times$ average speedup and up to $1.70 \times$ on state-of-the-art detection networks by filtering more than $50 \%$ of points on average, with negligible impact on accuracy.

Energy Harvesting (EH) technology has emerged to prolong the lifetime of Internet of Things (IoT) devices. However, in EH-IoTs, the reliance on external energy sources introduces challenges in maintaining up-to-date information. To quantify data freshness in such systems, researchers have introduced the Age-of-Information (AoI) metric, which measures the time elapsed since the generation of the most up-to-date information received by the user. Consequently, the problem of AoI minimization has been studied extensively in EH-IoTs to ensure timely data delivery. While data aggregation is a fundamental task for IoTs, existing works on AoI minimization in EH-IoTs have only considered scenarios where sensory data is updated by individual source nodes. The problem has not been investigated for data aggregation, in which the sensory data is aggregated from multiple source nodes. In this paper, we study the problem of AoI minimization for Data Aggregation in EHIoTs. To address this problem, we propose an energy-adaptive node scheduling algorithm consisting of both offline scheduling and online adjustment. Extensive simulations and testbed experiments verify the high performance of our algorithm in terms of AoI minimization and energy efficiency.

In Verilog code design, identifying and locating functional bugs is an important yet challenging task. Existing automatic bug localization methods have limited capabilities; they only suggest a set of potential buggy lines rather than precisely identifying the bug. Moreover, they depend on verification tools like testbenches and reference models, which require expert input and are time-consuming to develop. This paper introduces LiK (Location is Key), an open-source Large Language Model (LLM) to precisely locate functional bugs in Verilog code without the need for expert-written verification tools. LiK is developed from the open-source coding LLM Deepseek-Coder-Lite-Base-16B through a threestep training process: continuous pre-training to enhance foundational knowledge, supervised fine-tuning to learn how to output localization results, and reinforcement learning to reduce output errors. Experiment results demonstrate that LiK achieves superior functional bug localization accuracy, outperforming both the SOTA traditional method Strider, and SOTA closed-source LLMs like GPT-o1-preview and Claude-3.5-Sonnet. Moreover, integrating LiK into the SOTA LLM-based Verilog debugging tool significantly boosts its functional bug fixing success rate from $76.47 \%$ to $90.54 \%$. This underscores LiK’s potential to enhance the performance of end-to-end automatic Verilog debugging tools.

SystemVerilog Assertions (SVAs) are essential for verifying Register Transfer Level (RTL) designs, as they can be embedded into key functional paths to detect unintended behaviours. During simulation, assertion failures occur when the design’s behaviour deviates from expectations. Solving these failures, i.e., identifying and fixing the issues causing the deviation, requires analysing complex logical and timing relationships between multiple signals. This process heavily relies on human expertise, and there is currently no automatic tool available to assist with it. Here, we present AssertSolver, an opensource Large Language Model (LLM) specifically designed for solving assertion failures. By leveraging synthetic training data and learning from error responses to challenging cases, AssertSolver achieves a bug-fixing pass@1 metric of 88.54% on our testbench, significantly outperforming OpenAI’s o1-preview by up to $\mathbf{1 1. 9 7 \%}$. We release our model and testbench for public access to encourage further research: https://github.com/SEU-ACAL/reproduce-AssertSolver-DAC-25.

SystemVerilog Assertions (SVAs) are essential for verifying Register Transfer Level (RTL) designs, as they can be embedded into key functional paths to detect unintended behaviours. During simulation, assertion failures occur when the design’s behaviour deviates from expectations. Solving these failures, i.e., identifying and fixing the issues causing the deviation, requires analysing complex logical and timing relationships between multiple signals. This process heavily relies on human expertise, and there is currently no automatic tool available to assist with it. Here, we present AssertSolver, an opensource Large Language Model (LLM) specifically designed for solving assertion failures. By leveraging synthetic training data and learning from error responses to challenging cases, AssertSolver achieves a bug-fixing pass@1 metric of $88.54 \%$ on our testbench, significantly outperforming OpenAI’s o1-preview by up to $\mathbf{1 1. 9 7 \%}$. We release our model and testbench for public access to encourage further research: https://github.com/SEU-ACAL/reproduce-AssertSolver-DAC-25.

Verification presents a major bottleneck in Integrated Circuit (IC) development, consuming nearly 70% of the total development effort. While the Universal Verification Methodology (UVM) is widely used in industry to improve verification efficiency through structured and reusable testbenches, constructing these testbenches and generating sufficient stimuli remain challenging. These challenges arise from the considerable manual coding effort required, repetitive manual execution of multiple EDA tools, and the need for in-depth domain expertise to navigate complex designs. Here, we present UVM2, an automated verification framework that leverages Large Language Models (LLMs) to generate UVM testbenches and iteratively refine them using coverage feedback, significantly reducing manual effort while maintaining rigorous verification standards. To evaluate UVM2, we introduce a benchmark suite comprising Register Transfer Level (RTL) designs of up to 1.6K lines of code. The results show that UVM2reduces testbench setup time by up to 38.82× compared to experienced engineers, and achieve average code and function coverage of 87.44% and 89.58%, outperforming state- of-the-art solutions by 20.96% and 23.51%, respectively.

As end-to-end autonomous driving advances toward real-world deployment, ensuring the safety of autonomous vehicles (AVs) has become a critical requirement for their commercial viability. While rule-based AVs have traditionally undergone rigorous testing in both real-world and simulated environments before deployment, data-driven autonomous models are typically trained on real-world datasets, limiting their generalization to simulation environments. This poses a significant challenge for the development and testing of end-to-end autonomous driving. To address this issue, we propose Retrieval-Augmented Learning for Autonomous Driving (RALAD), a novel framework designed to bridge the real-to-sim gap in a cost-effective manner. RALAD consists of three key components: (1) domain adaptation via an enhanced Optimal Transport (OT) method, which retrieves the most similar scenarios between real and simulated environments; (2) feature fusion across similar scenarios, enabling the construction of a feature mapping between real-world and simulated domains; and (3) feature extraction freezing with fine-tuning on the fused features, allowing the model to learn simulation-specific characteristics through feature mapping. We evaluate RALAD on three monocular 3D object detection models, and the results demonstrate that our approach significantly improves model accuracy in simulation. Additionally, we use real autonomous vehicle for testing in real-world scenarios, and have established simulated scenes similar to reality for further testing, which illustrate the effectiveness of our method.

Autonomous machines often encounter complex timing constraints, such as those concerning end-to-end timing guarantees and real-time data fusion, etc. Tasks are often event-triggered or time-triggered at varying rates and exhibit data dependencies in between. Maintaining the real-time performance of autonomous machines becomes a highly challenging endeavor. In this paper, we formulate the workload of an autonomous machine as a hybrid Directed Acyclic Graph (DAG), which contains both time-trigger tasks and event-trigger tasks, with a distinct focus on the task of ensuring timing consistency in data fusion and adherence to end-to-end constraints within the DAG model. We design a concise mechanism to select suitable data received by a node and transmit them to successor nodes. This ensures both the timing disparity—as reflected by the differences in timestamps of the data used for fusion—and the end-to-end latency from the sensor to the controller is confined within a certain boundary. The proposed method is proven to be optimal as it always selects suitable data to guarantee the timing correctness of an autonomous machine as far as it (inherently) has the capacity. Experimental results show that our method can significantly improve the success rate of guaranteeing both timing consistency and end-to-end constraints of the autonomous machine.

As modern real-time systems become more complex, traditional deterministic analysis techniques often cannot accurately capture the system characteristics and offer meaningful design guidance. In contrast, probabilistic analysis is usually more practical and provides superior design insight while ensuring timing correctness with the required level of confidence. Earliest Deadline First (EDF) is one of the most widely used real-time scheduling algorithms. Although previous research has proposed a worst-case deadline failure probability (WCDFP) analysis for EDF, such an analysis tends to be overly pessimistic. Meanwhile, we observe that any analytical approach has inherent limitations, indicating that further reductions in WCDFP cannot be achieved solely through improved the analysis. In response to the first issue, this paper proposes a new technique to improve the accuracy of the WCDFP analysis. For the second issue, we enhance EDF by incorporating an active-dropping policy to reduce the analytical deadline failure probability. Empirical experiments demonstrate that our techniques lower the job failure probability in most tested scenarios, with especially significant improvements for task sets with high utilization.

The development of parallel computing architectures has created a growing need for scheduling real-time gang tasks, in which a specified number of threads per task must be executed simultaneously under timing constraints. However, existing approaches struggle to handle a fundamental challenge the heterogeneity in the number of threads across gang tasks. To address the challenge, this paper proposes a novel scheduling framework, called Recursive Partitioned Scheduling (RPS), in which each partition can be recursively divided into subpartitions whose assigned processor sets are disjoint and collectively equal to that of the parent, forming a tree-like hierarchical structure. RPS provides a flexible interface that allows each task to be assigned to an appropriate level in the hierarchy based on the number of threads it requires. To fully exploit RPS, we adopt fixed-priority scheduling and address two key issues. First, we develop a tight schedulability analysis, which not only utilizes the well-known exact schedulability analysis results for uniprocessor scheduling but also leverages the relationship between intra-and inter-partition interference. Second, based on the insights from the analysis, we design an effective partition generation and task assignment algorithm specialized for RPS, and further enhance it through task priority reassignment. Simulation results demonstrate that our approach significantly outperforms existing approaches in terms of schedulability.

The Robot Operating System 2 (ROS 2) has become a widely adopted middleware framework for building modular and distributed robotic systems. Its intra-process communication mechanism is designed to reduce latency by avoiding serialization and memory copying, which is often treated as a negligible or constant-cost operation in both system design and performance analysis. However, this assumption oversimplifies the underlying behavior and may lead to inaccurate performance models and misleading conclusions, especially in latency-sensitive applications. In this paper, we present a comprehensive analysis of intraprocess communication in ROS 2, revealing that its performance is highly sensitive to message configuration, workload structure, and message usage strategies. We identify a scalability risk caused by misaligned communication configurations and propose a guideline to ensure efficient and predictable intra-process communication across varying execution patterns. In addition, we uncover a performance bottleneck in the default ROS 2 implementation stemming from repeated message creation. To address this, we propose a novel message pooling mechanism that reuses message objects to exploit temporal locality and eliminate redundant allocations. Our design is fully compatible with existing ROS 2 APIs and requires no modifications to application-level code. Experimental evaluations using synthetic benchmarks and real-world case studies demonstrate substantial improvements in communication latency, validating the practicality of our design.

Most existing research in probabilistic real-time scheduling analysis has primarily focused on systems with only stochastic execution times, neglecting the stochastic nature of task release patterns in many real-world applications. Current approaches for handling stochastic release times rely on computationally expensive convolution-based methods, which has poor scalability, especially when both execution and release times are stochastic. This paper presents novel techniques to apply the Chernoff Bound approach to the analysis of systems with both stochastic execution and release times. The key challenge lies in adapting the Chernoff Bound, which traditionally operates on a fixed number of random variables, to handle the stochastic job counts resulting from stochastic release patterns. Our main contribution is a new technique for bounding convolutions involving random numbers of random variables using Chernoff principles. Through comprehensive evaluation, we demonstrate that our approach achieves several orders of magnitude speedup compared to state-of-the-art convolution-based methods while simultaneously improving analysis precision.

Parallel real-time systems often contain functionalities with complex dependencies and execution uncertainties, leading to significant timing variability which can be represented as a probabilistic distribution. However, existing timing analysis either produces a single conservative bound or incurs high computational costs due to the exhaustive enumeration of every execution scenario. This significantly hinders the exploitation of the probabilistic timing behaviours during system design, leading to sub-optimal design solutions. Modelling the system as a probabilistic directed acyclic graph ($p$-DAG), this paper presents a probabilistic response time analysis based on different longest paths of the$p$-DAG across all execution scenarios, enhancing the capability of the analysis by eliminating the need for enumeration. We first identify every longest path candidate based on the structure of$\boldsymbol{p}$-DAG and compute the probability of its occurrence, where each candidate is the longest under certain execution scenarios. Then, the worst-case interfering workload is computed for each longest path candidate, forming a complete probabilistic response time distribution with correctness guarantees. Experiments show that compared to the enumeration-based approach, the proposed analysis reduces the computation cost by six orders of magnitude while maintaining a low deviation ($\mathbf{1. 0 4 \%}$on average and below$\mathbf{5 \%}$for most$\boldsymbol{p}$-DAGs).

We study resource allocation and task scheduling for mobile artificial intelligence generated content (AIGC) in a three-layer cloud-edge-device network. Escalating industry demand for computational resources presents significant challenges in resource allocation and optimization, particularly for edge-side AIGC, which faces high computational costs and requires advanced techniques for efficient model deployment on mobile devices. Optimal resource allocation in mobile AIGC networks is naturally formulated into a 0-1 ILP, which is proven NP-hard. We reformulate the problem into both its Comp-Exp and dual forms. Then, we design an online auction framework online AIGC task scheduling (OATS) to optimize decisions on instances and time schedules, maximizing social welfare for the AIGC ecosystem. Our analysis demonstrates that OATS achieves high social welfare through appropriate bid acceptance and resource allocation. Simulation results corroborate the theoretical analysis, showcasing the efficacy of our online algorithms.

Time-sensitive networking (TSN) is increasingly applied in automotive and industrial Internet fields due to its low latency and deterministic communication. Gate control list (GCL) is foundational for deploying TSN. Currently, most scheduling research focuses on frame-to-window-based scheduling. This scheduling approach typically generates a specific window for each frame, leading to a proliferation of GCL in large networks, which increases the complexity of implementing TSN. To simplify deployment and enhance scheduling reliability, this article introduces a systematic flexible-window-based scheduling framework. Utilizing a gapless GCL design approach, it optimizes flow’s worst-case end-to-end (e2e) delays through window length design, with delays obtained through network calculus analysis. A generic solving framework based on metaheuristic algorithms is established to address this optimization problem. The scheduling framework also features a load-balanced turn prohibition routing strategy to balance link loads and avoid cyclic dependencies, alongside a K-means priority clustering method based on routing overlap to reduce the number of priorities. Simulation validation in a high-level autonomous driving vehicle’s in-vehicle network shows that the proposed method can decrease GCL numbers by nearly 90% against frame-to-window scheduling. In common industrial Internet scenario, it significantly reduces worst-case e2e delays and enhances scheduling success rates compared to the analogous scheduling method. Large-scale complex network scenario further demonstrates its scalability.

Mobile operating systems, such as Android, are increasingly used across diverse applications, where ensuring high responsiveness to user interactions is critical, particularly in mission-critical and real-time scenarios. Mobile operating systems typically process user interaction events and UI rendering on the same thread, commonly referred to as the main thread of a mobile application. As a result, user interaction handling can face significant delays when blocked by overloaded UI rendering tasks, compromising responsiveness. Existing mobile operating systems lack effective mechanisms to mitigate this issue. This paper addresses the problem by restructuring the UI rendering workflow to improve responsiveness in the presence of heavy rendering workloads. Specifically, two techniques are proposed that are tailored to whether the event handling results require screen display. Experimental results demonstrate improvements in both average-case and worst-case response times of event handling, enhancing the UI responsiveness. Although the implementation focuses on Android, the proposed approaches are adaptable to other mobile operating systems with similar rendering architectures, such as iOS and HarmonyOS.

LiDAR-based localization plays a critical role in autonomous driving and robotic navigation. However, traditional methods rely heavily on constructing high-precision point cloud maps, which is both time-consuming and labor-intensive. To address this, we propose an innovative localization approach that eliminates the need for point cloud maps by leveraging LiDAR and position-encoded landmarks. Our method encodes positional information into the shape of specially designed landmarks, strategically deployed in the environment. Subsequently, we fully leverage the advantages of LiDAR in accurately measuring distances and capturing the spatial structures of objects to detect and recognize the landmarks in the environment. By decoding the positional information embedded in the landmarks, precise vehicle localization is achieved. To overcome the limited information capacity of individual landmarks due to LiDAR’s reduced accuracy at long distances, we integrate multiple landmarks in a collaborative manner. By combining their encoded information and spatial relationships, we achieve high-precision localization without relying on point cloud maps. Experiments in CARLA and Autoware.AI simulators validate the effectiveness of our approach, offering a novel solution for LiDAR-based localization.

Parallel execution and conditional execution are increasingly prevalent in modern embedded systems. In real-time scheduling, a fundamental problem is how to upper-bound the response times of a task. Recent work applied the multi-path technique to reduce the response time bound for tasks with parallel execution, but left tasks with conditional execution as an open problem. This paper focuses on upper-bounding response times for tasks with both parallel execution and conditional execution using the multi-path technique. By designing a delicate abstraction regarding the multiple paths of various conditional branches, we derive a new response time bound. We further apply this response time bound into the scheduling of multiple parallel tasks with conditional branches. Experiments demonstrate that the proposed bound significantly advances the state-of-the-art, reducing the response time bound by 9.4% and improving the schedulability by 31.2% on average.

This article studies the response time bound of a directed acyclic graph (DAG) task. Recently, the idea of using multiple paths to bound the response time of a DAG task, instead of using a single longest path in previous results, was proposed and led to the so-called multipath bound. Multipath bounds can greatly reduce the response time bound and significantly improve the schedulability of DAG tasks. This article derives a new multipath bound and proposes an optimal algorithm to compute this bound. We further present a systematic analysis on the dominance and the sustainability of three existing multipath bounds and the proposed multipath bound. Our bound theoretically dominates and empirically outperforms all existing multipath bounds. What is more, the proposed bound is the only multipath bound that is proved to be self-sustainable.

Coarse-Grained Reconfigurable Arrays (CGRAs) are specialized accelerators commonly employed to boost performance in workloads with iterative structures. Existing research typically focuses on compiler or architecture optimizations aimed at improving CGRA performance, energy efficiency, flexibility, and area utilization, under the idealistic assumption that kernels can access all data from Scratchpad Memory (SPM). However, certain complex workloads–particularly in fields like graph analytics, irregular database operations, and specialized forms of high-performance computing (e.g., unstructured mesh simulations)–exhibit irregular memory access patterns that hinder CGRA utilization, sometimes dropping below 1.5%, making the CGRA memory-bound. To address this challenge, we conduct a thorough analysis of the underlying causes of performance degradation, then propose a redesigned memory subsystem and refine the memory model. With both microarchitectural and theoretical optimization, our solution can effectively manage irregular memory accesses through CGRA-specific runahead execution mechanism and cache reconfiguration techniques. Our results demonstrate that we can achieve performance comparable to the original SPM-only system while requiring only 1.27% of the storage size. The runahead execution mechanism achieves an average 3.04× speedup (up to 6.91×), with cache reconfiguration technique providing an additional 6.02% improvement, significantly enhancing CGRA performance for irregular memory access patterns.

Real-time systems are increasingly shifting from single processors to multiprocessors, where software must be parallelized to fully exploit the additional computational power. While the scheduling of real-time parallel tasks modeled as directed acyclic graphs (DAGs) has been extensively studied in the context of global scheduling, the scheduling and analysis of real-time DAG tasks under partitioned scheduling remain far less developed compared to the traditional scheduling of sequential tasks. Existing approaches primarily target plain fixed-priority partitioned scheduling and often rely on self-suspension–based analysis, which limits opportunities for further optimization. In particular, such methods fail to fully leverage fine-grained scheduling management that could improve schedulability. In this paper, we propose a novel approach for scheduling periodic DAG tasks, in which each DAG task is transformed into a set of real-time transactions by incorporating mechanisms for enforcing release offsets and intra-task priority assignments. We further develop corresponding analysis techniques and partitioning algorithms. Through comprehensive experiments, we evaluate the real-time performance of the proposed methods against state-of-the-art scheduling and analysis techniques. The results demonstrate that our approach consistently outperforms existing methods for scheduling periodic DAG tasks across a wide range of parameter settings.

The Deep Learning Processor Unit (DPU) released in the official Xilinx Vitis AI toolchain stands as a commercial off-the-shelf solution tailored for accelerating convolutional neural network (CNN) inference on Xilinx FPGA devices. While most FPGA accelerator focus on high performance and energy-efficiency, analyzing the worst-case execution time (WCET) bound is essential for using CNN accelerations in real-time embedded systems design. In this work, we show that in a multi-DPU environment, the observed worst-case inference time for a CNN inference task could become 3X larger w.r.t. the best case inference time, which prompts the prominent importance of a static timing analysis for FPGA-based CNN inference. We propose, to the best of the authors’ knowledge, the first static timing analysis framework for CNN inference in a multi-DPU environment. The proposed framework introduces a generalized timing behavior model for shared bus arbitration and memory access contention between parallel running DPU engines. Additionally, it incorporates a fine-grained memory access contention analysis that takes into account the characteristics of deep learning applications. For a single-DPU environment, the analysis result is 27% tighter in average compared with the state-of-the-art results. Furthermore, our proposed method produces relatively tight estimated results in the multi-DPU environment.

eBPF is an inspiring technique in Linux that allows user space processes to extend the kernel by dynamically injecting programs. However, it poses security issues, since the untrusted user code is now executed in the kernel space. eBPF utilizes a verifier to validate the safety of the provided programs, thus its correctness is of paramount importance as attackers may exploit vulnerabilities within it to inject malicious programs. Bug-finding tools like kernel fuzzers currently can detect memory bugs in eBPF system calls, but they experience difficulties in finding correctness bugs in the verifier, e.g., incorrect validations that allow the loading of unsafe programs. Because, unlike detecting memory bugs, where sanitizers can capture such errors once observed, automatically uncovering correctness bugs is very difficult, without an effective test oracle that determines if the verifier behaves correctly for given programs.

Delta compression attracts many researchers' interest for its high efficiency in eliminating redundant data. It identifies a similar block for the incoming block and stores only the differences between them. The key challenge lies in detecting suitable similar blocks. Existing approaches have their limitations. Hash-based solutions like NTransform miss many similar blocks due to the high similarity detection threshold, while complex-threshold solutions like DeepSketch and Palantir have high computation overhead.

Batteryless sensing systems rely on energy harvested from the environment to execute. However, as the harvested energy is generally weak and unstable, the system may experience frequent power failures during processing and sensing. To make forward progress across power outages, the system backs up the system state from static random access memory (SRAM) to non-volatile memory (NVM) before power failures and then restores it upon reboot. Moreover, to avoid losing the collected data, existing approaches save all the collected data from SRAM to NVM before system-off. The data saving and the frequent system reboots consume a lot of energy and time and thus cause a long blocking time. However, the data stored in SRAM can be retained for a short period even after the system is turned off, as the data retention voltage of SRAM is lower than the minimum operating voltage of the microcontroller unit (MCU). In this paper, we leverage the SRAM data retention capability to retain data with a short lifetime on SRAM, while only save data with a long lifetime to NVM. Consequently, the backup overhead is significantly reduced. However, a design challenge is to decide the turn-off voltage to minimize the blocking time. Specifically, turning off at a higher voltage leaves more energy for a longer retention time and results in lower data saving overhead. But this may also cause more on-offs, leading to more system states saving and system states restoring overhead. To address this challenge, the paper proposes a method to adaptively compute the optimal turn-off voltage. Experimental results show that the proposed method can significantly reduce the blocking time caused by data saving and system reboots. The system can collect more data and exhibits improved responsiveness in sensing the environment.

The Robot Operating System 2 (ROS) is the de-facto standard for robotic software development, with a wide application in diverse safety-critical domains. There are many efforts in testing that seek to deliver a more secure ROS codebase. However, existing testing methods are often inadequate to capture the complex and stateful behaviors inherent to ROS deployments, resulting in limited test- ing effectiveness. In this paper, we propose R2D2, a ROS system fuzzer that leverages ROS’s runtime states as guidance to increase fuzzing effectiveness and efficiency. Unlike traditional fuzzers, R2D2 employs a systematic instrumentation strategy that captures the system’s runtime behaviors and profiles the current system state in real-time. This approach provides a more in-depth understanding of system behaviors, thereby facilitating a more insightful explo- ration of ROS’s extensive state space. For evaluation, we applied it to four well-known ROS applications. Our evaluation shows that R2D2 achieves an improvement of 3.91× and 2.56× in code coverage compared to state-of-the-art ROS fuzzers, including Ros2Fuzz and RoboFuzz, while also uncovering 39 previously unknown vulnera- bilities, with 6 fixed in both ROS runtime and ROS applications. For its runtime overhead, R2D2 maintains an average execution and memory usage overhead with 10.4% and 1.0% in respect, making R2D2 effective in ROS testing.

Simulating realistic behaviors of traffic agents is pivotal for efficiently validating the safety of autonomous driving systems. Existing data-driven simulators primarily use an encoder-decoder architecture to encode the historical trajectories before decoding the future. However, the heterogeneity between encoders and decoders complicates the models, and the manual separation of historical and future trajectories leads to low data utilization. Given these limitations, we propose BehaviorGPT, a homogeneous and fully autoregressive Transformer designed to simulate the sequential behavior of multiple agents. Crucially, our approach discards the traditional separation between "history" and "future" by modeling each time step as the "current" one for motion generation, leading to a simpler, more parameter- and data-efficient agent simulator. We further introduce the Next-Patch Prediction Paradigm (NP3) to mitigate the negative effects of autoregressive modeling, in which models are trained to reason at the patch level of trajectories and capture long-range spatial-temporal interactions. Despite having merely 3M model parameters, BehaviorGPT won first place in the 2024 Waymo Open Sim Agents Challenge with a realism score of 0.7473 and a minADE score of 1.4147, demonstrating its exceptional performance in traffic agent simulation.

While large language models (LLMs) are usually deployed on powerful servers, there is growing interest in deploying them on local machines for better real-time performance, service stability, privacy, and flexibility. Unfortunately, the GPU memory on local machines is often insufficient to accommodate the entire LLM. Although running an LLM on such a GPU device is still possible by swapping data between the limited GPU memory and the abundant main memory, the slow speed of data swapping significantly hampers inference time, rendering it impractical in reality. In this paper, we propose RTiL, a systematic solution to address the above challenge. RTiL utilizes collaborative inference, which combines a lightweight LLM with the default powerful LLM. The lightweight LLM generates output tokens, which are then validated for quality by the powerful LLM. This approach allows RTiL to significantly speed up inference while maintaining the same output quality as when using the powerful LLM alone. Additionally, by delegating part of the inference workload to the CPU and optimizing data movement between main and GPU memory, we further enhance the efficiency of the inference process. Furthermore, we extend RTiL to handle requests with real-time requirements, enabling it to meet such demands by slightly trading off output quality. Through extensive experiments, we demonstrate notable improvements in inference efficiency and the ability to fulfill real-time requirements while minimizing degradation in output quality.

Multi-sensor data fusion plays a crucial role in modern autonomous systems, enabling them to perceive the surroundings from multiple dimensions. However, the accuracy of fusion output can be compromised by the temporal inconsistency of input messages from different sources. ROS provides algorithms of message synchronization to mitigate this misalignment before the data fusion process. Nevertheless, this introduces additional latency in processing each message, which influences the real-time performance of ROS systems. Previous research [1] is the first to analyze and bound the reaction latency of the ApproximateTime synchronization policy in ROS, which is essential for analyzing the system-level end-to-end reaction time. However, their bound is overly pessimistic. In this paper, we propose a safe and tight reaction latency upper bound for the ApproximateTime policy. We conduct experiments to validate its accuracy and assess its improvements compared to [1].

Fusing Radar and Lidar sensor data can fully utilize their complementary advantages and provide more accurate reconstruction of the surrounding for autonomous driving systems. Surround Radar/Lidar can provide 360° view sampling with the minimal cost, which are promising sensing hardware solutions for autonomous driving systems. However, due to the intrinsic physical constraints, the rotating speed of surround Radar, and thus the frequency to generate Radar data frames, is much lower than surround Lidar. Existing Radar/Lidar fusion methods have to work at the low frequency of surround Radar, which cannot meet the high responsiveness requirement of autonomous driving systems. This paper develops techniques to fuse surround Radar/Lidar with working frequency only limited by the faster surround Lidar instead of the slower surround Radar, based on widely-used object detection model called MVDNet. The basic idea of our approach is simple: we let MVDNet work with temporally unaligned data from Radar/Lidar, so that fusion can take place at any time when a new Lidar data frame arrives, instead of waiting for the slow Radar data frame. However, directly applying MVDNet to temporally unaligned Radar/Lidar data greatly degrades its object detection accuracy. The key information revealed in this paper is that we can achieve high output frequency with little accuracy loss by enhancing the training procedure to explore the temporal redundancy in MVDNet so that it can tolerate the temporal unalignment of input data. We explore several different ways of training enhancement and compare them quantitatively with experiments.

In safety-critical systems, timing accuracy is the key to achieving precise I/O control. To meet such strict timing requirements, dedicated hardware assistance has recently been investigated and developed. However, these solutions are often fragile, due to unforeseen timing defects. In this paper, we propose a robust and timing-accurate I/O co-processor, which manages I/O tasks using Execution Time Servers (ETSs) and a two-level scheduler. The ETSs limit the impact of timing defects between tasks, and the scheduler prioritises ETSs based on their importance, offering a robust and configurable scheduling infrastructure. Based on the hardware design, we present an ETS-based timing-accurate I/O schedule, with the ETS parameters configured to further enhance robustness against timing defects. Experiments show the proposed I/O control method outperforms the state-of-the-art method in terms of timing accuracy and robustness without introducing significant overhead.

A mixed-criticality (MC) system is a computational platform shared by tasks with two or more safety-critical levels. An important research topic related to MC systems is designing scheduling algorithms that can satisfy the computation requirements of tasks with different criticality levels. Numerous studies have focused on this topic, but only a few have considered parallel tasks. To address the research gap, we propose a dual-criticality scheduling algorithm based on federated scheduling for parallel tasks with Directed Acyclic Graph (DAG) structures. We particularly focus on the task set in which each task has a deadline longer than its release period. To the best of our knowledge, our work is the first that does not assume the constrained-or implicit-deadline in the MC DAG task model. In addition to simulation experiments, we demonstrate that our algorithm has a capacity augmentation bound of 4, providing a quantitative worst-case performance guarantee for our algorithm.

In autonomous driving (AD) systems, complex data dependencies exist between tasks with different activation rates, making it very hard to analyze the system’s timing behaviors. This paper formulates an AD system as a multi-rate directed acyclic graph (DAG) and introduces a novel reaction time bound for critical chains within this multi-rate DAG. Furthermore, we introduce a priority assignment strategy tailored to optimize priority allocation, effectively minimizing the reaction time of critical task chains. This strategy comes with theoretical guarantees, ensuring that the achieved latency bound is only slightly higher than the ideal one. Our empirical work demonstrates that the newly proposed reaction time bound outperforms current standards, achieving an average improvement of $5.46 \%$. Furthermore, our strategy for priority assignment significantly enhances the success rate of achieving timing correctness in the AD system, exceeding the baseline method by a notable $19.24 \%$.

Abstract This paper considers the real-time scheduling of a parallel task with reclaiming computing resources, which can be utilized for soft real-time tasks or switching to low-energy mode to save energy. Existing works allocate a rectangular piece of computing resources based on the worst-case characterizations of the task to guarantee the deadline, which inherently incurs severe resource wasting due to coarse-grained resource allocation. To address this resource-wasting problem, this paper proposes the ladder-like resource allocation (i.e., a series of rectangular pieces of computing resources). To characterize the ladder-like resource allocation, we present two concepts called resource distribution and allocation vector, which serve as the interfaces between hard and soft real-time tasks. For the former, we derive schedulability tests under the given two interfaces; for the latter, we discuss the methods of determining the two interfaces to reclaim computing resources. This paper is the first work to fully explore the concept of ladder-like resource allocation and its potential consequences on computing resources, soft real-time tasks, and energy. Experiments demonstrate that the proposed approach can effectively reclaim more computing resources than existing approaches while maintaining hard real-time guarantees.

With the high-performance requirement of safety-critical real-time tasks, the platforms of many-core processors with high parallelism are widely utilized, where network-on-chip (NoC) is generally employed for inter-core communication due to its scalability and high efficiency. Unfortunately, large uncertainties are suffered on NoCs from both the overly parallel architecture and the distributed scheduling strategy (e.g., wormhole flow control), which complicates the response time upper bounds estimation (i.e., either unsafe or pessimistic). For DAG-based real-time parallel tasks, to solve this problem, we propose DAG-Order, an order-based dynamic DAG scheduling approach, which strictly guarantees NoC real-time services. First, rather than build the new analysis to fit the widely used best-effort wormhole NoC, DAG-Order is built upon a kind of advanced low-latency NoC with SLT ( S ingle-cycle L ong-range T raversal) to avoid the unpredictable parallel transmission on the shared source-destination link of wormhole NoCs. Second, DAG-Order is a non-preemptive dynamic scheduling strategy, which jointly considers communication as well as computation workloads, and fits SLT NoC. With such an order-based dynamic scheduling strategy, the provably bound safety is ensured by enforcing certain order constraints among DAG edges/vertices that eliminate the execution-timing anomaly at runtime. Third, the order constraints are further relaxed for higher average-case runtime performance without compromising bound safety. Finally, an effective heuristic algorithm seeking a proper schedule order is developed to tighten the bounds. Experiments on synthetic and realistic benchmarks demonstrate that DAG-Order performs better than the state-of-the-art related scheduling methods.

DAG (directed acyclic graph) tasks are widely used to model parallel real-time workload. The real-time performance of a DAG task not only depends on its total workload, but also its graph structure. Intuitively, with the same total workload, a DAG task with looser precedence constraints tends to have better real-time performance in terms of worst-case response time. However, this paper shows that actually we can shorten the worst-case response time of a DAG task by carefully adding new edges and constructing longer paths. We develop techniques based on the state-of-the-art DAG response time analysis methods to properly add new edges so that the worst-case response time bound guaranteed by formal analysis can be significantly reduced. An approach built upon the proposed techniques is also presented to handle the scheduling of multiple DAG tasks. Experiments under different parameter settings demonstrate the effectiveness of the proposed method.

Electrophoretic displays (EPDs), also known as e-paper, offer a paper-like visual experience by reflecting ambient light, making them distinct from traditional LCD or LED displays. They are favored for their eye comfort, energy efficiency, and material flexibility, which make them appealing for a wide range of embedded devices, including eReaders, smartphones, tablets, and wearables. However, EPDs face a significant challenge: the necessity for a fast refresh rate (to maintain an acceptable display performance) introduces a pronounced ghosting effect. This effect results in noticeable color discrepancies between the displayed and source images, harming the user experience and hindering EPDs’ broader application in devices requiring dynamic content display. This article proposes a software-based solution to address the ghosting issue in EPDs. Our approach involves developing analytical models to predict the occurrence of ghosting effects and adjusting the source images to counteract the anticipated color deviations, which can reduce the perceivable ghosts on the display. Experimental evaluation conducted on real-world EPDs validates the effectiveness of our proposed approach in reducing the ghosting effect.

ROS (Robot Operating System) is a widely used robotic software development framework. In safety-critical applications that require timing guarantees, the first generation of ROS falls short. The introduction of ROS 2 has addressed some of these limitations, but its multi-threaded executor still struggles to meet real-time requirements. To address this issue, we design a new multi-threaded executor called RTeX for ROS 2. The goal of RTeX is to improve system performance in terms of both run-time efficiency and timing predictability. We have implemented RTeX in the latest version of ROS 2 and conducted experiments on a real platform. The experimental results demonstrate that RTeX outperforms both the default ROS 2 multi-threaded executor and its state-of-the-art variant, achieving significant real-time performance improvements.

3-Dnandflash memories are the dominant storage media in modern data centers due to their high performance, large storage capacity, and low-power consumption. However, the lifetime of flash memory has decreased as technology scaling advances. Recent work has revealed that the number of achievable program/erase (P/E) cycles of flash blocks is related to the dwell time (DT) between two adjacent erase operations. A longer DT can lead to higher-achievable P/E cycles and, therefore, a longer lifetime for flash memories. This article found that the achievable P/E cycles would increase when flash blocks endure uneven DT distribution. Based on this observation, this article presents an opportunistic self-healing method to extend the lifetime of flash memory. By maintaining two groups with unequal block counts, namely, Active Group and Healing Group, the proposed method creates an imbalance in erase operation distribution. The Active Group undergoes more frequent erase operations, resulting in shorter DT, while the Healing Group experiences longer DT. Periodically, the roles of the two groups are switched based on the Active Group’s partitioning ratio. This role switching ensures that each block experiences both short and long DT periods, leading to an uneven DT distribution that magnifies the self-healing effect. The evaluation shows that the proposed method can improve the flash lifetime by 19.3% and 13.2% on average with near-free overheads, compared with the baseline and the related work, respectively.

Sensor fusion plays a critical role in modern robotics and autonomous systems. In reality, the sensor data destined for the fusion algorithm may have substantially different sampling times. Without proper management, this could lead to poor sensor fusion quality. Robot operating system (ROS) is the most popular robotic software framework, providing essential mechanisms for synchronizing messages to mitigate timing inconsistencies during sensor fusion. Recently, ROS introduced a new LatestTime message synchronization policy. In this article, we formally model the behavior of the LatestTime policy and analyze its worst-case real-time performance. Our investigation uncovers a defect of the LatestTime policy that may cause infinite latency in publishing subsequent outputs. We propose a solution to address this defect and develop safe and tight upper bounds on worst-case real-time performance, in terms of both the maximal temporal inconsistency of its outputs and the incurred latency. Experiments are conducted to evaluate the precision, safety and robustness of our theoretical results.

Time-sensitive networking (TSN) can offer deterministic low-latency communication, making it a critical solution for high-level autonomous vehicle's in-vehicle network. The deterministic transmission of TSN relies on TSN traffic scheduling. To ensure real-time transmission performance and vehicle functional safety, in-vehicle TSN scheduling aims to reduce end-to-end delay. Despite the promising potential of graph neural networks and deep reinforcement learning (DRL) in navigating complex TSN scheduling environments, its application has predominantly been limited to enhancing schedulability without a targeted focus on minimizing delays. This article introduces a DRL in-vehicle TSN scheduling framework based on the graph attention network (GAT). The scheduling problem is abstracted as a delay optimization problem and mapped to a Markov decision process (MDP), which is solved using the proximal policy optimization (PPO) algorithm. The GAT with attention mechanism is incorporated to extract critical information to enhance feature extraction and improve scheduling accuracy. This GAT-based PPO method can achieve high-precision offline scheduling through training, producing low-delay scheduling results. Simulation results demonstrate that the proposed method improves offline scheduling performance compared to other DRL-based scheduling methods. Leveraging the trained neural network, the proposed method can also deliver high robustness in online scheduling under link failure scenarios. It can produce a scheduling solution in just 3.8 s, and the scheduling results for all failure scenarios surpass those of rule-based benchmarking methods.

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.

In modern real-time heterogeneous System-on-Chips, ensuring real-time performance is increasingly important. However, with ever-increasing hardware and architectural complexity, satisfying such timing requirements becomes very challenging due to both hardware heterogeneity and the complicated access paths induced by the on-chip accelerators. In this paper, inspired by an interesting observation from accelerable real-time task scheduling, we propose a new core-accelerator interface, BlueFace, which is integrated into the memory access stage of the CPU pipeline, effectively avoiding the complicated HA access paths. The BlueFace design constructs a priority queue to schedule the HA operations at the hardware level, ensuring simultaneous throughput and real-time performance. The evaluation demonstrates the performance benefits and gives the overhead of BlueFace.

There is an increasing move towards implementing embedded real-time systems upon multiprocessors with parallel applications, which are usually modeled as Directed Acyclic Graphs (DAGs). Plentiful work has been presented to optimize the bound of Worst-Case Response Time (WCRT) since the cornerstone work proposed by Graham in 1969. However, all these works are developed on the basis of Graham’s bound and failed to tackle the root of pessimism in it. In this work, we present a novel method to optimize the WCRT bound of a DAG task by designing mutually exclusive groups so that a sequential execution is enforced for some nodes, under which the problem of bounding WCRT becomes a problem of identifying a mutually exclusive path and thus does not suffer the pessimism in Graham’s bound. Experiments are conducted to evaluate the performance of our method against other WCRT optimization approaches in the state-of-the-art.

As an Ethernet-based communication protocol with timing determinism, TSN (time-sensitive networking) has become a well-recognized promising in-vehicle network solution for increasingly automated automobiles. To satisfy the reliability requirement of safety-critical applications, existing works towards fault-tolerant TSN trade too much bandwidth for redundancy, limiting their scope of applicability. Targeting mixed-critical traffic, which is widely found in practice, we define a shared fault-tolerant segment that is compatible with the TSN standard. It serves the critical flows when faults occur, to improve their reliability and serves the non-critical flows when otherwise, to improve their quality of service (QoS). On top of this, we propose a space-time redundancy scheduling algorithm, aiming to make the most efficient use of bandwidth, i.e., to fulfill both the reliability as well as hard real-time requirements, and maximize the QoS with the least bandwidth. In essence, we formulate a bi-objective design space exploration problem with hundreds of thousands of decision variables and solve it with customized heuristics. Experimental results show that compared to the state-of-the-art methods, our reported work increases the number of critical flows that can be accommodated on a resource-constrained network by 3 to 4 times, and achieve the highest QoS with an average reduction of 60.3% in bandwidth. As the first work along sharing of bandwidth between mixed-critical traffic in fault-tolerant TSN, this idea can be further pursued towards higher efficiency and may be applied in general autonomous systems.

Many real-time systems process and react to external events by a chain of tasks, and have constraints on the maximum reaction time which describes how long it takes to respond to an external event. While a processing chain typically starts with a sampling task periodically triggered to sample the sensor data, other tasks in the chain could be triggered in two different ways: event-triggered or time-triggered, which have their own pros and cons. In this paper, we propose the third option to trigger the processing tasks in a chain, namely, the event-triggered with data refreshing approach, which combines the benefits of the event-triggered or time-triggered approaches. As the main technical contribution, we develop techniques to formally upper-bound its maximum reaction time and analytically compare it with the existing approaches. Experiments with synthetic workload are conducted to show the performance improvement by our proposed techniques.

Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. The degree of parallelism of DAG tasks is an important characterization in scheduling. This paper revisits the definition and the computing algorithms for the degree of parallelism of DAG tasks, and clarifies some misunderstandings regarding the degree of parallelism which exist in real-time literature. Based on the degree of the parallelism, we propose a real-time scheduling approach for DAG tasks, which is quite simple but rather effective and outperforms the state-of-the-art by a considerable margin.

The latency and energy consumption incurred by I/O accesses are significant in data-centric computing systems. Computational Storage Drive (CSD) can largely reduce data movement, and thus reduce I/O latency and energy consumption by offloading data-intensive processing to processors inside the storage device. In this paper, we study the problem of how to efficiently utilize the limited processing and memory resources of CSD to simultaneously serve multiple I/O requests from various applications with different real-time requirements. We proposed SERICO, a system of scheduling computational I/O requests in CSD. The key idea of SERICO is to perform admission control of real-time computational I/O requests by online schedulability analysis, to avoid wasting the processing resources and memory capacity of CSD in doing meaningless work for those requests deemed to violate the timing constraints. Each admitted computational I/O request is served in a controlled manner with carefully designed parameters, to meet its timing constraint with minimal memory cost. We evaluate SERICO with both synthetic workloads on simulators and representative applications on realistic CSD hardware. Experiment results show that SERICO significantly outperforms the default method used in the CSD device and the standard deadline-driven scheduling approach.

In automotive systems, an important timing requirement is that the time disparity (the maximum difference among the timestamps of all raw data produced by sensors that an output originates from) must be bounded in a certain range, so that information from different sensors can be correctly synchronized and fused. In this paper, we study the problem of analyzing the worst-case time disparity in cause-effect chains. In particular, we present two bounds, where the first one assumes all chains are independent from each other and the second one takes the fork-join structures into consideration to perform more precise analysis. Moreover, we propose a solution to cut down the worst-case time disparity for a task by designing buffers with proper sizes. Experiments are conducted to show the correctness and effectiveness of both our analysis and optimization methods.

Firmware update is an essential service on Internet-of-Things (IoT) devices to fix vulnerabilities and add new functionalities. Firmware update is energy-consuming since it involves intensive flash erase/write operations. Nowadays, IoT devices are increasingly powered by energy harvesting. As the energy output of the harvesters on IoT devices is typically tiny and unstable, a firmware update will likely experience power failures during its progress and fail to complete. This paper presents an approach to increase the success rate of firmware update on energy-harvesting IoT devices. The main idea is to first conduct a lightweight flash write with reduced erase/write time (and thus less energy consumed) to quickly save the new firmware image to flash memory before a power failure occurs. To ensure a long data retention time, a reinforcement step follows to re-write the new firmware image on the flash with default erase/write configuration when the system is not busy and has free energy. Experiments conducted with different energy scenarios show that our approach can significantly increase the success rate and the efficiency of firmware update on energy-harvesting IoT devices.

Robot Operating System (ROS) is a prevailing software framework for robotic appliscation development. Graphics Processing Unit (GPU) is widely used in many ROS applications as a first-order computation resource. Unfortunately, ROS does not do any resource management for GPU, and different components in a ROS application directly submit their GPU workload without coordinating with each other, which may cause severe problems in both general performance and realtime capability. This paper presents ROSGM, a real-time ROS 2G PUM anagement framework. Instead of providing a fixed GPU management policy for all scenarios, ROSGM allows the addition of any management policy as a plug-in and dynamic switching among different management policies at run-time, which is helpful since GPU management policies are typically device-dependent, and different applications or the same application in different modes may need different GPU management policies. Besides, ROSGM supports dynamic task loading and unloading for integrating additional functionalities when required at run-time. We conduct experiments to evaluate ROSGM. The results show that by properly managing the GPU resource using ROSGM, we can significantly improve the performance of ROS 2 applications. The flexibility of adding management policies as plug-ins, dynamic switching of management policies, and dynamic task loading and unloading helps improve the adaptability of ROSGM.

In the autonomous driving (AD) system, complex data dependencies exist between tasks with different activation rates, making it very hard to analyze systems’ real-time behaviors. This paper formulates the AD system as a multi-rate DAG and proposes an integrated framework to co-analyze the schedulability of individual tasks and the end-to-end latency of task chains in the multi-rate DAG. Integer linear programming (ILP) techniques are developed to guide how to drop redundant workload to increase the chance that timing requirements can be met. This paper proposed one analysis framework which enables an automated process in which designs of the AD system are created, analyzed and refined in an iterative way, i.e., the analysis result in the last iteration provides valuable guidance to redesign the AD system in the next iteration. Experiments are conducted to evaluate the performance of our analysis method.

ROS (Robot Operating System) is one of the most popular robotic software development frameworks. Robotic systems in safety-critical domains are usually subject to hard realtime constraints, so timing behaviors must be formally modeled and analyzed to guarantee that real-time constraints are always honored at run-time. Although a series of analysis techniques has been proposed to analyze the timing performance of ROS 2, the state-of-the-art still generates pessimistic results for ROS 2 systems modeled as DAG (Directed Acyclic Graph). This paper focuses on the analysis of such systems, and proposes techniques to analyze the timing performance in a more precise manner. Experiments with both randomly generated workload and a case study are conducted to evaluate and demonstrate our results.

It is our pleasure to welcome you to the 29th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2023), held in Niigata, Japan. This year, we are honored that RTCSA is sponsored by IEEE, IEEE Computer Society, and IEEE Technical Committee on Real-Time Systems (TCRTS). The objective of the conference is to bring together researchers and developers from academia and industry for advancing the technology of embedded and real-time systems and their emerging applications, including the Internet of Things (IoT) and Cyber-Physical Systems (CPS).

Analysis and optimization of end-to-end latency in cause-effect chains is an important problem in real-time systems. Under task-level fixed-priority scheduling, the end-to-end latency largely relies on the relative priority of the tasks in the chain, so previous work has tried to improve the latency via priority assignment. However, the improvement of static priority assignment is limited due to the conflict between schedulability of individual tasks and end-to-end latency of the chain, i.e., a priority assignment leading to good end-to-end latency may make the task set unschedulable. This work proposes a novel method named Dynamic Priority Inheritance Protocol (DPI) to optimize the end-to-end latency of sporadic cause-effect chains. Under DPI, the propagation delay between two communicating jobs is independent of the task relative priority. So the optimization can work on any priority assignment, and no longer conflicts with task schedulability. Moreover, we propose DPI-B, a combination of DPI and a Buffer Manipulation Protocol, for cause-effect chains that also need to meet the determinism requirement. We conduct experiments with both automotive benchmarks and randomly generated workload. The results show the effectiveness of our method in comparison with the state-of-the-art.

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.

Multi-sensor data fusion is crucial for modern autonomous systems to accurately perceive their surrounding environments and make intelligent decisions. However, as different sensor sources may have significant time disparity, it is necessary to synchronize their data before sending them to the fusion algorithm, in order to control such differences and get meaningful fusion results. This paper discusses the message synchronization policy in ROS, a popular framework for robotic systems. The ROS message synchronization policy has proven to be highly effective in reducing the time disparity, but it introduces a certain level of latency. Therefore, to use it for real-time systems, it is essential to establish an upper bound for the worst-case latency that may occur. Specifically, we analyze two key latency metrics of the ROS message synchronization policy, the passing latency and reaction latency, which are needed to analyze the end-to-end delay and reaction time on the system level. We conduct experiments under different settings to evaluate the precision of our proposed latency upper bounds against the maximum observed latency in real execution.

ROS 2, the second-generation ROS, is a popular development framework for real-time robotic software. To ensure the timing correctness of applications based on ROS 2, one must model the time delay incurred by two aspects: computation and communication. While significant work has been conducted on computing delay, formal modeling and analysis of communication delay in ROS 2 is still an open issue. In this paper, we first present a formal description on the timing behavior of inter-process communication in ROS 2 with two typical communication policies, namely the InterestTree policy and FIFO policy, and then develop analysis techniques to upper-bound the incurred delay. We conduct experiments to validate the correctness and evaluate the efficacy of our method with case studies on realistic platform.

On behalf of the IEEE Technical Committee on Real-Time Systems (TCRTS), it is our pleasure to welcome you to the 44th IEEE Real-Time Systems Symposium (RTSS 2023) during December 5 - 8, 2023 in Taipei. Over the past 44 years, RTSS has established itself as the primary forum for research in the broad field of real-time and embedded systems.

Autonomous machines are commonly subject to real-time constraints. ROS 2, a widely-used robotics framework, considers real-time capabilities as a critical factor and is constantly evolving to address these challenges, e.g., the end-to-end timing guarantee and the real-time data fusion, etc. This paper studies the ROS message synchronizer, an integral component for multi-sensor data fusion, and provides a potential direction for the synchronizer's evolution in future versions of ROS 2. For effective data fusion, input data from different sensors must be sampled at time points that align within a specific range. This paper proposes a novel message synchronization policy to meet this requirement, called the SEAM, which Synchronizes the Earliest Arrival Messages once they fall within the specified range. Unlike traditional ROS synchronizers, the SEAM does not rely on prediction information for complex optimization. Instead, it uses information from already-arrived messages to construct a feasible synchronization scheme. We demonstrate the optimality of the SEAM by proving that it always finds a feasible scheme if one indeed exists. We incorporate the SEAM into ROS 2 and conduct experiments to evaluate its effectiveness compared to traditional ROS synchronizers.

Many applications such as autonomous driving and augmented reality, require the concurrent running of multiple deep neural networks (DNN) that poses different levels of real-time performance requirements. However, coordinating multiple DNN tasks with varying levels of criticality on edge GPUs remains an area of limited study. Unlike server-level GPUs, edge GPUs are resource-limited and lack hardware-level resource management mechanisms for avoiding resource contention. Therefore, we propose Miriam, a contention-aware task coordination framework for multi-DNN inference on edge GPU. Miriam consolidates two main components, an elastic-kernel generator, and a runtime dynamic kernel coordinator, to support mixed critical DNN inference. To evaluate Miriam, we build a new DNN inference benchmark based on CUDA with diverse representative DNN workloads. Experiments on two edge GPU platforms show that Miriam can increase system throughput by 92% while only incurring less than 10% latency overhead for critical tasks, compared to state of art baselines.

We present TensorBind, a novel approach aimed at unifying different hardware architectures for compilation optimization. Our proposed framework establishes an embedding space to seamlessly bind diverse hardware platforms together. By leveraging this unified representation, TensorBind enables efficient tensor program optimization techniques across a wide range of hardware platforms. We provide experimental results demonstrating the essentiality and adaptability of TensorBind in translating tensor program optimization records across multiple hardware architectures, thus revolutionizing compilation optimization strategies and facilitating the development of high-performance compilation systems over heterogeneous devices.

Spin locks are widely used in embedded systems to coordinate mutually exclusive accesses to shared resources from different tasks. Although the design and analysis of locking protocols have been intensively studied forsequentialreal-time tasks, there have been few works on this topic forparallelreal-time tasks. In this paper, we study the analysis of parallel real-time tasks modeled by directed acyclic graphs (DAGs) under global fixed priority scheduling using both preemptable and non-preemptable spin locks to protect accesses to shared resources in three commonly used request serving orders (unordered, FIFO-order and priority-order). In particular, we develop a general schedulability analysis framework where the blocking time caused by resource contention is formally defined, so that the blocking analysis can be performed independently and easy to combine with the traditional interference analysis techniques. Moreover, we present a unified blocking analysis technique where the blocking time is analyzed in a scalable manner based on a linear-programming (LP) approach, making our method flexible and extendable. We conduct comprehensive experiments to evaluate our method with other the-state-of-the-art approaches for scheduling real-time parallel tasks using semaphores and spin locks.

A cause-effect chain is a sequence of multi-rate real-time tasks with data dependency. Cause-effect chains are generally subject to end-to-end timing constraints, especially in safety-critical systems. Communication paradigms greatly affect the end-to-end latency of cause-effect chains. This paper compares different communication paradigms (implicit communication, LET, DBP) with regards to the end-to-end latency of cause-effect chains using them, and proposes priority assignment strategies to optimize the end-to-end latency with specific communication paradigm. Experiments with synthesized data based on an automotive benchmark and randomly generated parameters are conducted to evaluate our results.

The conditional directed acyclic graph (DAG) task model can represent the conditional execution flows that commonly exist in many real-time parallel applications. Previous work has shown that by properly assigning the priority among vertices inside a nonconditional DAG task, we can reduce the task response time and achieve better system schedulability. This article studies how to apply intra-task priority assignment to conditional DAG tasks. We develop a response time bound that theoretically dominates the state-of-the-art and present a novel algorithm to compute the bound in polynomial time. We further extend the proposed approach to the general setting of multiple conditional DAG tasks. Experiments with one conditional DAG task and multiple conditional DAG tasks demonstrate that our method consistently outperforms the state-of-the-art by a considerable margin.

Real-time systems require locking protocols to coordinate access to shared resources. With the booming revolution of parallel processing technology in real-time systems, there has been some work addressing the problem of extending classic locking protocols for sequential real-time tasks to parallel tasks. However, it may not be most effective to trivially follow the progress mechanisms and queue orders designed for sequential tasks since the intrastructure information within a parallel task is not taken into consideration. This article investigates the design of locking protocols for parallel tasks using a novel mechanism—longest normal Section first (LNSF)—to consider the impact of normal sections on blocking behavior in parallel tasks and further improve real-time performance. LNSF is then implemented in a locking protocol for parallel tasks named POMIP, and associated blocking analysis techniques are presented. Empirical evaluations show that our proposed analysis dominated other state-of-the-art analysis—in best cases, the acceptance ratio of the task set can be improved by around 17%.

Energy harvesting promises to power billions of Internet of Things devices without being restricted by battery life. Since the energy harvester generally outputs weak and unstable energy, the system may suffer frequent and unpredictable power failures, thus falling into cyclically reboots without forward progress. The task-based intermittent computing system which periodically backs up system states into nonvolatile memory (NVM) is proposed to solve the nonprogress problem, with the nontrivial cost of frequent backups. How to reduce the backup overhead becomes a major research problem for intermittent computing. This article, for the first time, proposes to parallelize state backup and program execution with asynchronous direct memory access (DMA) to hide the backup latency into the program’s execution. But, straightforwardly executing the state backup and the program in parallel may cause an inconsistent system state. In specific, the system state may be modified by the program during backup, and therefore may be backed up incorrectly and further cause the system to deliver an incorrect computation result. We make a deep analysis on the system behavior and observe that, although the system state may be backed up incorrectly, the incorrect backup will be covered by the subsequent correct backups soon as the backup operations are performed frequently. In addition, only a small part of variables among all the program states may cause incorrect computation result. So, in this article, we aggressively allow incorrect backups to occur and propose a backup error detection method and a fault-tolerant backup management to guarantee the correctness of the system’s execution. To augment the parallel backup method, an adaptive execution method is further proposed to reduce the number of backups and balance the ratio between task execution time and backup latency. We design a run-time system to implement the proposed approach, and experimental results conducted on an STM32F7-based platform show that the proposed method can achieve a$2.6\times $average speedup.

In order for real-time wireless networks (RTWNs) to achieve desired Quality of Service (QoS) for real-time sensing and control, effective packet scheduling algorithms play a critical role, especially in the presence of unexpected disturbances. Most existing solutions in the literature focus either on static or dynamic schedule construction to meet the desired QoS requirements, but have a common assumption that all wireless links are reliable. However, this assumption is not realistic in real-life settings. To address this drawback, this paper introduces a novel reliable dynamic packet scheduling framework, called RD-PaS. RD-PaS can not only construct static schedules to meet both the timing and reliability requirements of end-to-end flows in RTWNs, but also construct new schedules rapidly to handle abruptly increased network traffic induced by unexpected disturbances while minimizing the impact on existing network flows. Through judiciously sharing time slots among tasks, RD-PaS can significantly reduce the number of required time slots to meet the system reliability requirement and improve the network throughput. The functional correctness of the RD-PaS framework has been validated through its implementation and deployment on a real-life RTWN testbed. Extensive simulation-based experiments have also been performed to evaluate the effectiveness of RD-PaS, especially in large-scale network settings.

In many popular parallel programming models, e.g., OpenMP (OpenMP, 2013), applications are usually dispatched into several dedicated scheduling entities (named ”threads” in common) for which the processor time of physical platform is provided through the OS schedulers. This behavior requires for a hierarchical scheduling framework, considering each thread as a virtual processor (VP). Moreover, hierarchical scheduling allow separate applications to execute together on a common hardware platform, with each application having the “illusion” of executing on a dedicated component. However, the problem for scheduling parallel real-time tasks on virtual multiprocessor platform has not been addressed yet. An analogous approach to virtual scheduling for parallel real-time tasks is federeted scheudling, where each task exclusively executes on a set of dedicated physical processors. However, federated scheduling suffers significant resource wasting. In this article, we study the scheduling of real-time parallel task on virtual multiprocessors. As a physical processor is shared by virtual processors, tasks effectively share processors with each other. We conduct comprehensive performance evaluation to compare our proposed approach with existing methods of different types. Experiment results show that our approach consistently outperforms existing methods to a considerable extent under a wide range of parameter settings.

Modern real-time systems contain complex workloads, which are usually modeled as directed acyclic graph (DAG) tasks and deployed on multiprocessor platforms. The complex execution logic of DAG tasks results in excessive schedulability analysis overhead, and the current DAG task allocation strategy cannot efficiently utilize processor resources (inner parallelization of DAG tasks). In this article, an invalid-edge deletion (IED) method is proposed to reduce the execution complexity of the DAG tasks while guaranteeing the correctness of the execution logic. Besides, we bound the number of complete paths for DAG tasks, which re-limits the searching space of the schedulability analysis. Then, a topology-based DAG tasks allocation (TDTA) strategy is developed, which reduces the interference caused by higher-priority DAG tasks to enable the full utilization of the processor resources. The experimental results show that the IED method effectively reduces the overhead of DAG task analysis, and the performance of the TDTA strategy is better than the performance of other state-of-the-art strategies.

Locks are the most widely used mechanisms to coordinate simultaneous accesses to exclusive shared resources. While locking protocols and associated schedulability analysis techniques have been extensively studied for sequential real-time tasks, work for parallel tasks largely lags behind. In the limited existing work on this topic, a common assumption is that a critical section must execute sequentially. However, this is not necessarily the case with parallel programming languages. In this paper, we study the analysis of parallel heavy real-time tasks (the density of which is greater than 1) with critical sections in parallel structures. We show that applying existing analysis techniques directly could be unsafe or much pessimistic for the considered model, and develop new techniques to address these problems. Comprehensive experiments are conducted to evaluate the performance of our method.

In recent years, the demand for data storage space has increased dramatically due to the exponential growth of data volume. Data compression is of great significance since it saves data storage space and reduces data transfer demand. Compression algorithms based on statistical models have a much higher compression ratio than dictionary-based methods, but the high computational time cost of statistical modeling limits their wider application. In this paper, we introduce pLPAQ, an FPGA-based design of a powerful compression algorithm LPAQ based on statistical models. A novel hardware accelerator is proposed to speed up LPAQ by fully utilizing the parallelism of FPGA. Experimental results show that the proposed design can achieve a throughput of 12 MB/s on Xilinx Virtex Plus UltraScale XCVU9P card, 25x faster than executing on AMD Ryzen R7 4800U at 2.8 GHz and 80x faster compared with the naive FPGA implementation on average.

Directed acyclic graph (DAG) becomes a popular model for modern real-time embedded software. It is really a challenge to bound the worst-case response time (WCRT) of DAG task. Parallelism, dependencies and mutual exclusion become three of the most critical properties of real-time parallel tasks. Recent work applied prioritizing techniques to reduce DAG task's WCRT bound, which has well studied the first two properties, i.e., parallelism and dependencies, but leaves the mutually exclusive property as an open problem. This paper focuses on all the three properties of real-time parallel software, and investigates how to estimate the WCRT of the DAG task model with mutually exclusive vertices and under prioritized list scheduling algorithms. We derive a reasonable WCRT bound for such a complicated DAG task, and prove that the corresponding WCRT bound computation problem is strongly NP-hard. It means that there are no pseudo-polynomial time algorithms to compute the WCRT bound. For the prioritized DAG with a constant number of mutual exclusive vertices, we develop a dynamic programming algorithm that is able to estimate the WCRT bound within pseudo-polynomial time. Experiments are conducted to evaluate the performance of our analysis method implemented with different priority assignment policies against the state-of-the-art.

In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.

ROS (Robot Operating System) is currently one of the most popular development frameworks for robotic software, which is usually subject to hard real-time constraints in safe-critical domains. Designers must formally model and analyze its timing behaviors to guarantee that real-time constraints are always honored at run-time. This paper studies real-time scheduling and analysis under a multi-threaded executor in ROS 2. We present a formal description of the scheduling model of multi-threaded executors, and develop response time analysis techniques for processing chains executing on it. Moreover, we identify a risk of increasing the response time of chains that may be caused by improper design when deploying systems on multi-threaded executors, which provides a useful guidance to designers. We conduct experiments with both randomly generated workloads and case studies on a realistic ROS 2 platform to evaluate and demonstrate our results.

Due to its efficient and predictable utilization of modern computing units, recent studies have paid attention to gang scheduling in which all threads of a real-time task should be concurrently executed on different processors. However, the studies have been biased to preemptive gang scheduling, although non-preemptive gang scheduling (NPG) is practical for inherently non-preemptive tasks and tasks that incur large preemption overhead. In this paper, focusing on a new type of priority-inversion incurred by NPG, we design a generalized NPG framework, called NPG*, under which each task has an option to allow or disallow the situation that incurs the priority-inversion specialized for NPG. To demonstrate the effectiveness of NPG* in terms of timing guarantees, we target NPG*-FP by employing fixed-priority scheduling (FP) as a prioritization policy, and develop the first NPG*-FP schedulability test and its improved version under a given assignment of the allowance/disallowance option to each task. We then develop the optimal allowance/disallowance assignment algorithm, which finds an assignment (if exists) that makes a target task set schedulable by the proposed schedulability tests. Via simulations, we demonstrate that the assignment algorithm associated with the schedulability tests for NPG*-FP can find a number of additional schedulable task sets, each of which has not been covered by the traditional NPG framework.

Multi-sensor data fusion is essential in autonomous systems to support accurate perception and intelligent decisions. To perform meaningful data fusion, input data from different sensors must be sampled at time points in close propinquity to each other, otherwise the result cannot accurately reflect the status of the physical environment. ROS (Robotic Operating System), a popular software framework for autonomous systems, provides message synchronization mechanisms to address the above problem, by buffering messages carrying data from different sensors and grouping those with similar timestamps. Although message synchronization is widely used in applications developed based on ROS, little knowledge is known about its actual behavior and performance, so it is hard to guarantee the quality of data fusion. In this paper, we model the message synchronization policy in ROS and formally analyze its worst-case time disparity (maximal difference among the timestamps of the messages grouped into the same output set). We conduct experiments to evaluate the precision of the proposed time disparity upper bound against the maximal observed time disparity in real execution, and compare it with the synchronization policy in Apollo Cyber RT, another popular software framework for autonomous driving systems. Experiment results show that our analysis has good precision and ROS outperforms Apollo Cyber RT in terms of both observed worst-case time disparity and the theoretical bound.

Traditional Earth observation (EO) services using satellites mainly observe relatively large-scale objects for applications with no or weak real-time requirements. The rapid development of Low-Earth-orbit (LEO) satellites opens new opportunities to provide EO services for a much wider range of applications by collecting the observation and communication capability of many LEO satellites. The challenge is how to select and coordinate the LEO satellites to accomplish the EO task subject to strong real-time constraints. In this work, we present a holistic solution that precisely models the observation service of a single LEO satellite and allocates the work of a periodic real-time EO task to a group of LEO satellites to meet the real-time requirements. Experiments were conducted to evaluate how the parameters of the LEO satellites and the ground stations impact the satisfiability of real-time requirements. The results provide valuable guidelines for designing LEO satellites and ground stations to provide real-time object observation services.

Smart traffic is an emerging research area gaining more attention due to a class of emerging applications such as autonomous driving. Most smart traffic scenarios are outdoors, which are hard to collect traffic data and build demanding sensing systems. In this work, an indoor smart traffic testbed with an F1TENTH autonomous driving vehicle is built, allowing the collection of traffic datasets under different scenarios and performing various smart traffic tasks. This novel data collection system and collected dataset can help research teams build various smart traffic systems and evaluate indoor smart traffic datasets. The collected traffic light dataset is publicly available at the link1.

In recent years, Deep Neural Network (DNN) has been increasingly adopted by a wide range of time-critical applications running on edge platforms with heterogeneous multiprocessors. To meet the stringent timing requirements of these applications, heterogeneous CPU and GPU resources must be efficiently utilized for the inference of multiple DNN models. Such a cross-processor real-time DNN inference paradigm poses major challenges due to the inherent performance imbalance among different processors and the lack of real-time support for cross-processor inference from existing deep learning frameworks. In this work, we propose a new system named BlastNet that exploits duo-block - a new model inference abstraction to support highly efficient cross-processor real-time DNN inference. Each duo-block has a dual model structure, enabling efficient fine-grained inference alternatively across different processors. BlastNet employs a novel block-level Neural Architecture Search (NAS) technique to generate duo-blocks, which accounts for computing characteristics and communication overhead. The duo-blocks are optimized at design time and then dynamically scheduled to achieve high resource utilization of heterogeneous CPU and GPU at runtime. BlastNet is implemented on an indoor autonomous driving platform and three popular edge platforms. Extensive results show that BlastNet achieves 35.07 % less deadline missing rate with a mere 1.63% of model accuracy loss.

AI applications powered by deep learning are increasingly running on edge devices. Meanwhile, many real-world IoT applications demand multiple real-time tasks to run on the same device, for example, to achieve both object tracking and image segmentation simultaneously on an augmented reality glass. However, the current solutions can not yet support such multi-tenant real-time DNN inference on edge devices. Techniques such as on-device model compression trade inference accuracy for speed, while traditional DNN compilers mainly focus on single-tenant DNN model optimization. To fill this gap, we propose Aaron, which leverages DNN compiling techniques to accelerate multi-DNN inference on edge GPU based on compile-time kernel adaptation with no accuracy loss. Aaron integrates both DNN graph and kernel optimization to maximize on-device parallelism and minimize contention brought by concurrent inference.

In order to be deployed on storage-limited devices, blockchains generally provide lightweight clients which only store all the block headers rather than all blocks. However, a lightweight client is hard to verify a newly issued transaction, thus making the zero-confirmation transactions between lightweight clients impossible. In particular, transaction verification needs to verify that each referred output of the transaction is not previously spent. The conventional lightweight client design is unscalable as it can only support such an operation in the complexity of$O$($N_{T}$), where$N_{T}$is the total number of transactions in the system. The latest proposals suggest summarizing all the unspent outputs in an ordered Merkle tree. Therefore, a light client can request proof of presence and/or absence of an element in it to prove whether a referred output is previously spent or not, in the complexity of$O$(log($N_{U}$)), where$N_{U}$is the total number of unspent output in the system. However, updating such ordered Merkle tree is slow, thus making the system impractical—by our evaluation, when a new block is generated in Bitcoin, it takes more than one minute to update the ordered Merkle tree. We propose a practical client, TICK, to solve this problem. TICK uses the AVL hash tree to store all the unspent outputs. The AVL hash tree can be updated in the time of$O$($M$*log($N_{U}$)), where$M$is the number of elements that need to be inserted or removed from the AVL hash tree. By evaluation, when a new block is generated, the AVL hash tree can be updated within 1 s. Similarly, the proof can also be generated in the time of$O$(log($N_{U}$)). Therefore,${\textsf {TICK}}$is practical and scalable. Benefited by the AVL hash tree, a storage-limited device can efficiently and cryptographically verify transactions. In addition, rather than requiring new miners to download the entire blockchain before mining, TICK allows new miners to download only a small portion of data to start mining. We implement TICK for Bitcoin and provide an experimental evaluation on its performance by using the current Bitcoin blockchain data. Our result shows that the proof for verifying whether an output of a transaction is spent or not is only several kB. The verification is very fast—generating a proof generally takes less than 1 ms and verifying a proof even takes much less time. In addition, to start mining, new miners only need to download several GB data, rather than downloading over 230-GB data.

Pathology image segmentation is an essential step in early detection and diagnosis for various diseases. Due to its complex nature, precise segmentation is not a trivial task. Recently, deep learning has been proved as an effective option for pathology image processing. However, its efficiency is highly restricted by inconsistent annotation quality. In this article, we propose an accurate and noise-tolerant segmentation approach to overcome the aforementioned issues. This approach consists of two main parts: a preprocessing module for data augmentation and a new neural network architecture, ANT-UNet. Experimental results demonstrate that, even on a noisy dataset, the proposed approach can achieve more accurate segmentation with 6% to 35% accuracy improvement versus other commonly used segmentation methods. In addition, the proposed architecture is hardware friendly, which can reduce the amount of parameters to one-tenth of the original and achieve 1.7× speed-up.

SMART (Single-cycle Multi-hop Asynchronous Repeated Traversal) Network-on-Chip (NoC), a recently proposed dynamically reconfigurable NoC, enables single-cycle long-distance communication by building single-bypass paths directly between distant communication pairs. However, such a single-cycle single-bypass path will be readily broken when contention occurs. Thus, packets will be buffered at intermediate routers with blocking latency from other contending packets, and extra router-stage latency to rebuild the remaining path when available. In this article, we propose an effective contention-minimized routing algorithm to achieve maximal bypassing. Specifically, we identify two potential routes: direct route, with which packets can reach the destination in a single bypass; and indirect route, with which packets can reach the destination in multiple bypasses via an(multiple) intermediate router(s). The novel feature is that, contrary to an intuitive approach, not the routes with minimal distance but the indirect routes via the arbitrary intermediate routers (even if they may be non-minimal) that avoid contentions yield the minimized end-to-end latency. Evaluation on realistic benchmarks demonstrates the effectiveness of the proposed routing strategy, which achieves average performance improvement by 35.48 percent in communication latency, 28.31 percent in application schedule length, and 37.59 percent in network throughput, compared with the current routing in SMART NoCs.

Real-time systems with strict timing constraints have been widely applied in many fields. The Directed acyclic graph (DAG) task model has been widely studied and applied to model real-time systems with partial parallelism and precedence constraints in each task. Our paper focuses on the worst-case response time (WCRT) analysis of DAG tasks under partitioned scheduling on multiprocessors. We investigate a parallel structure named$Str$, which helps obtain more accurate analysis results, and propose a new offline scheduling analysis algorithm named reducing repetitive calculation (RRC). Experiments with synthetic workload are conducted to compare the results calculated by RRC and the state-of-the-art, as well as the observed average response time on a real embedded system. Results show that RRC has better performance in terms of analysis accuracy.

In mixed-criticality systems (MCSs), timely handling of I/O operations is a key for the system being successfully implemented and appropriately functioned. The I/O system for an MCS must simultaneously enable different features, including isolation/separation, timing-predictability, performance, scalability, and energy-efficiency. Moreover, such an I/O system also requires to manage I/O resource in an adaptive manner to facilitate efficient yet safe resource sharing among components of different criticality levels. Existing approaches cannot achieve all of these requirements simultaneously. This article presents a mixed-criticality I/O management framework, termed MCS-IOV. MCS-IOV is based on hardware-assisted virtualization, which provides temporal and spatial isolation and prohibits fault propagation with limited extra overhead. MCS-IOV extends a real-time I/O virtualization system, by supporting the concept of mixed criticalities and customized interfaces for schedulers, which offers good timing predictability and scalability. Finally, we introduce an energy management framework for MCS-IOV, ensuring the power-efficiency of the design. The MCS-IOV is the first systematical solution that fulfills all the requirements as a mixed-criticality I/O system.

An increasingly important trend in the design of safety-critical systems is the integration of components with different levels of criticality onto a common hardware platform. Mixed-criticality systems (MCSs) have been well researched in academia, but can be difficult to implement in industrial scenarios as the theoretical models underpinning the research do not sufficiently consider industrial safety practice and safety standards. In this article, we make the first attempt toward the implementation of the MCS theoretical model in industrial settings. To this end, we identify the pragmatic gaps between theory and practice, and then propose a generic industrial MCS architecture, termedP-MCS(Practical-MCS).P-MCSis built upon the conventional theoretical MCS model with additional considerations of industrial safety requirements: 1) runtime safety analysis, determining preserved applications in each system mode and 2) correct partitioning and isolation of different critical elements. We introduce three implementing methods forP-MCS. Corresponding to the new system architecture, we present a theoretical model and schedulability analysis (with consideration of shared resources) to ensure system predictability. Finally, we evaluate and demonstrateP-MCSin terms of system schedulability, overheads, throughput, and predictability, along with a real-world case study. As shown in the evaluation, the considerations of industrial requirements lead to extra overheads and performance reduction inP-MCS. Such weaknesses can be considerably mitigated by hardware assistance and acceleration.

Suspension-based locks are widely used in real-time systems to coordinate simultaneous accesses to exclusive shared resources. Although suspension-based locks have been well studied forsequentialreal-time tasks, little work has been done on this topic forparallelreal-time tasks. This article for the first time studies the problem of how to extend existing sequential-task locking protocols and their analysis techniques to the parallel task model. More specifically, we extend two locking protocols OMLP and OMIP, which were designed for clustered scheduling ofsequentialreal-time tasks, to federated scheduling ofparallelreal-time tasks. We present corresponding blocking analysis techniques, and developpath-orientedtechniques to analyze and count blocking time. Schedulability tests with different efficiency and accuracy are further developed. Experiments are conducted to evaluate the performance of our proposed approaches against the state-of-the-art.

All existing work on real-time scheduling of parallel task graph models with shared resources assumes that a critical section must be contained inside a single vertex. However, this assumption does not hold in many realistic parallel real-time software. In this work, we conduct the first study on real-time scheduling and analysis of parallel task graphs where critical sections are allowed to cross different vertices. We show that allowing this may potentially lead to deadlocks and the so-called resource unrelated blocking time problem. We formalize the conditions for the deadlocks and resource unrelated blocking time to happen, and propose two different solutions to address them and develop corresponding schedulability analysis techniques. We conduct comprehensive experiments to evaluate our method. The results indicate that there is a significant impact to the system schedulability when tasks incur deadlock and resource unrelated blocking. Moreover, the schedulability can benefit from the execution of workload in parallel with critical sections if tasks can be carefully designed so that all deadlocks and resource unrelated blocking time can be avoided, and our methods are efficient to determine the schedulability of systems where critical sections across different vertices exist.

It is well-known that the HVAC (heating, ventilation, and air conditioning) dominates electricity consumption in commercial buildings. In this paper, we focus on one of the core problems in building operation, namelychiller sequencingto reduce HVAC electricity consumption. Our contributions are threefold. First, we make a case for why it is important to quantify the performance profile of a chiller, namely coefficient of performance (COP), atrun-time, by developing a data-driven COP estimation methodology. Second, we show that predicting COP accurately is a non trivial problem, requiring considerable computation time. To overcome this barrier, we develop a data-driven COP prediction model and an edge-based chiller sequencing framework integrating the COP predictions, and show that they strike a good balance between electricity saving and ease of use for real-world deployment. Finally, we evaluate the performance of our scheme by applying it to real-world data, spanning four years, obtained from multiple chillers across three large commercial buildings in Hong Kong. The results show an electricity saving of over 30 percent compared to baselines. We offer our edge based data-driven chiller sequencing framework as a cost-effective and practical mechanism to reduce electricity consumption associated with HVAC operation in commercial buildings.

It becomes more and more common for people to have multiple mobile devices. This opens the opportunity of multi-surface computing in which users interact with an app using multiple devices simultaneously. Recently, a system called FLUID was developed, which can distribute User Interface (UI) elements of an app to multiple devices to support multi-surface computing. FLUID enables general, flexible and transparent multi-device interaction, which cannot be achieved by previous approaches such as screen mirroring, app migration, and customized app development on multiple devices. However, the practicality of FLUID is still severely limited because it requires that (1) the app source codes must be available and (2) the same app is pre-installed on all devices. This paper presents PRUID, a UI distribution system that is free from the above-mentioned limitations of FLUID. PRUID captures and extracts relevant information about UI elements to be distributed completely at run time, without requiring the app source code. An app-independent UI agent is designed to dock and render the UI components distributed to the guest device, so pre-installation of the app on guest devices is not required. We developed representative use cases to demonstrate the usage and evaluate the performance of PRUID. The evaluation results show that the extra overhead incurred due to the UI information extraction at run time is marginal and PRUID provides a smooth user experience.

Energy harvesting promises to power billions of Internet-of-Things devices without being restricted by battery life. The energy output of harvesters is typically weak and highly unstable, so computing systems must frequently back up program states into non-volatile memory to ensure a program will progress in the presence of frequent power failures. However, state backup is a time-consuming process. In existing solutions for this problem, state backup is conducted sequentially with program execution, which considerably impact system performance. This paper proposes techniques to parallelize state backup and program execution with asynchronous DMA. The challenge is that program states can be incorrectly backed up, which may further cause the program to deliver incorrect computation. Our main idea is to allow errors to occur in parallel state backup and program execution, and detect the errors at the end of the state backup. Moreover, we propose a technique that allows the system to tolerate backup errors during execution without harming logical correctness. We designed a run-time system to implement the proposed approach. Experimental results on an STM32F7-based platform show that execution performance can be considerably improved by parallelizing state backup and program execution.

Many computing systems, such as those powered by energy harvesting or deployed in harsh working environment, may experience unpredictable and frequent transient power failures in their life time. The systems may fail to deliver correct computation results or never progress, as computation is frequently interrupted by the power failures. A possible solution could be frequently saving program states to non-volatile memory (NVM), such as using checkpoints, so that the system can incrementally progress. However, this approach is too costly, since frequent NVM writes is time and energy consuming, and may wear out the NVM device. In this work, we propose an approach to enable a system to use volatile SRAM to correctly progress in the presence of transient power failures, since SRAM is capable of retaining its data for seconds or minutes with the charge remained in the battery/capacitor after the CPU core stops at its brown-out voltage. The main problem is to validate whether the data in SRAM are actually retained during power failures. In our approach, we validate only a subset of the program states with Cyclic Redundancy Check for efficiency. The validation technique requires maintaining a backup version of the program states, which additionally provides the system with the ability to progress incrementally. We implement a run-time system with the proposed approach. Experimental results on an MSP430 platform show that the system can correctly progress on SRAM in the presence of transient power failures with low overhead.

The Round Robin scheduling policy is used in many real-time embedded systems because of its simplicity and low overhead. In this paper, we study a variation of Round Robin used in practical systems, named Lazy Round Robin, which is simpler to implement and has lower runtime overhead than ordinary Round Robin. The key difference between Round Robin and Lazy Round Robin lies in when the scheduler reacts to newly released task instances. The Round Robin scheduler checks whether a newly released task instance is eligible for execution in the remaining part of the current round, while the Lazy Round Robin scheduler does not react to any task release until the end of the current round. This paper develops techniques to calculate upper bounds of response time of tasks scheduled by Lazy Round Robin. Experiments are conducted to evaluate our analysis techniques and compare the real-time performance of Round Robin and Lazy Round Robin.

Most parallel real-time applications can be modeled as directed acyclic graph (DAG) tasks. Intra-task priority assignment can reduce the nondeterminism of runtime behavior of DAG tasks, possibly resulting in a smaller worst-case response time. However, intra-task priority assignment incurs dependencies between different parts of the graph, making it a challenging problem to compute the response time bound. Existing work on intra-task task priority assignment for DAG tasks is subject to the constraint that priority assignment must comply with the topological order of the graph, so that the response time bound can be computed in polynomial time. In this paper, we relax this constraint and propose a new method to compute response time bound of DAG tasks with arbitrary priority assignment. With the benefit of our new method, we present a simple but effective priority assignment policy, leading to smaller response time bounds. Comprehensive evaluation with both single-DAG systems and multi-DAG systems demonstrates that our method outperforms the state-of-the-art method with a considerable margin.

Federated scheduling is a promising approach to schedule parallel real-time tasks, where each task exclusively executes on a set of dedicated processors. However, federated scheduling suffers significant resource wasting since a task typically only uses part of the processing capacity allocated to it, while the unused part cannot be shared with other tasks. To solve this problem, we present a virtually-federated scheduling approach, which both enjoys the good analyzability of federated scheduling and allows tasks to efficiently share processors with others. The main idea is to construct virtual processors on physical processors, and let a task exclusively execute on a set of virtual processors. As a physical processor is shared by virtual processors, tasks effectively share processors with each other. On the other hand, as each task exclusively executes on its own virtual processor set, the good analyzability of federated scheduling can be carried into to our virtually-federated scheduling approach. We conduct comprehensive performance evaluation to compare our proposed approach with existing methods of different types. Experiment results show that our approach consistently outperforms existing methods to a considerable extent under a wide range of parameter settings.

OpenMP is a promising framework for developing parallel real-time software on multi-cores. Recently, many graph-based task models representing realistic features of OpenMP task systems have been proposed and analyzed. However, all previous studies did not model the loop structures, which is common in OpenMP task systems. In this paper, we formulate the workload of OpenMP task systems with loop structures as the cyclic graph model and study how to compute safe upper bounds for the worstcase response time (WCRT). The loop structures combined with the creation of tasks and conditional branches result in a large state space. Simply unrolling the loop and/or enumerating all the possible execution flows would be computationally intractable. As the major technical contribution, we develop a linear-time dynamic programming algorithm to compute the WCRT bound without unrolling loops or explicitly enumerating the execution flows. Experiments with both synthetic task graphs and realistic OpenMP programs are conducted to evaluate the performance of our method.

Locking protocol is an essential component in resource management of real-time systems, which coordinates mutually exclusive accesses to shared resources from different tasks. Although the design and analysis of locking protocols have been intensively studied for sequential real-time tasks, there has been a little work on this topic for parallel real-time tasks. In this article, we study the analysis of parallel real-time tasks using spin locks to protect accesses to shared resources in three commonly used request serving orders (unordered, FIFO-order, and priority-order). A remarkable feature making our analysis method more accurate is to systematically analyze the blocking time which may delay a task's finishing time, where the impact to the total workload and the longest path length is jointly considered, rather than analyzing them separately and counting all blocking time as the workload that delays a task's finishing time, as commonly assumed in the state-of-the-art.

Multi-cores are becoming mainstream hardware platforms for embedded and real-time systems. To fully utilize the processing capacity of multi-cores, software should be parallelized. Recently, much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs (DAG), motivated by the parallel task structures supported by popular parallel programming frameworks such as OpenMP. The DAG-based task models in existing real-time scheduling research assume well-nested graph structures recursively composed by single-source-single-sink parallel and conditional components. However, realistic OpenMP task systems in general have more flexible structures that do not comply with those assumptions. In this article, we model the behavior of general OpenMP task systems with non-well-nested structures. The worst-case response time analysis problem for such systems is more difficult due to the flexible graph structure. As the major technical contribution, we develop two efficient algorithms to compute the worst-case response time bounds, with different trade-offs between efficiency and precision. Evaluation with both randomly generated task graphs and realistic OpenMP programs shows good performance of our approaches in terms of both precision and efficiency.

Driven by industry demand, there is an increasing need to develop real-time multiprocessor systems which contain shared resources. The Multiprocessor Stack Resource Policy (MSRP) and Multiprocessor resource sharing Protocol (MrsP) are two major protocols that manage access to shared resources. Both of them can be applied to Fixed-Priority Preemptive Scheduling (FPPS), which is enforced by most commercial real-time systems regulations, and which requires task priorities to be assigned before deployment. Along with MSRP and MrsP, there exist two forms of schedulability tests that bound the worst-case blocking time due to resource accesses: the traditional ones being more widely adopted and the more recently developed holistic ones which deliver tighter analysis. On uniprocessor systems, there are several well-established optimal priority assignment algorithms. Unfortunately, on multiprocessor systems with shared resources, the issue of priority assignment has not been adequately understood. In this article, we investigate three mainstream priority assignment algorithms-Deadline Monotonic Priority Ordering (DMPO), Audsley's Optimal Priority Assignment (OPA), and Robust Priority Assignment (RPA), in the context of partitioned multiprocessor systems with shared resources. Our contributions are multifold: First, we prove that DMPO is optimal with the traditional schedulability tests. Second, two counter examples are given as evidence that DMPO is not optimal with the tighter holistic schedulability tests. Third, we then analyze the pessimism arising from the adoption of OPA and RPA with the holistic tests. Lastly, we propose a Slack-based Priority Ordering (SPO) algorithm that minimises such pessimism, and has polynomial time complexity. Comprehensive experiments show that SPO outperforms (i.e., results in a larger number of schedulable systems) DMPO, OPA, and RPA in general with the holistic schedulability tests, by up to 15 percent. With the theoretical contributions, this paper is a useful guide to priority assignment in real-time partitioned multiprocessor systems with shared resources.

The communication latency in traditional network-on-chip (NoC) with hop-by-hop traversal is inherently restricted by the distance between source-destination communicating pairs. SMART, as one of the dynamically reconfigurable NoC architectures, enables the new feature of single-cycle long-distance communication by building a direct bypass path between distant cores dynamically at runtime. With the increasing of the number of integrated cores in multi/many-core systems, SMART has been deemed a promising communication backbone in such systems. However, SMART is generally optimized for average-case performance for best-effort traffics, not offering real-time guaranteed services for real-time traffics, and thus SMART often shows extremely poor real-time performance (e.g., schedulability). To make SMART latency-predictable for real-time traffics, by combining with the single-cycle bypass forwarding technique, in this article, we first propose a priority-preemptive scheduling to allow contending packets to be arbitrated according to predefined priorities. Based on the priority-based scheduling, for the real-time packet flows with given flow mapping and predefined priorities, we then propose a real-time communication analysis model, by considering shared virtual channels (or priority levels) and arbitrary-deadline real-time packet flows, to predict theworst-case communication latencyand validate the schedulability. Through theoretical and experimental comparison, theworst-case communication latencyof the analyzed packet flows is reduced significantly compared with that of the traditional priority-preemptive NoCs with hop-by-hop traversal and the original distance-based SMART, thus improving the schedulability.

Research on modeling and analysis of real-time computing systems has been done in two areas, model checking and real-time scheduling theory. In model checking, an expressive modeling formalism such as timed automata (TA) is used to model complex systems, but the analysis is typically very expensive due to state-space explosion. In real-time scheduling theory, the analysis techniques are highly efficient, but the models are often restrictive. In this paper, we aim to exploit the possibility of applying efficient analysis techniques rooted in real-time scheduling theory to analysis of real-time task systems modeled by timed automata with tasks (TAT). More specifically, we develop efficient techniques to analyze the feasibility of TAT-based task models (i.e., whether all tasks can meet their deadlines on single-processor) using demand bound functions (DBF), a widely used workload abstraction in real-time scheduling theory. Our proposed analysis method has a pseudo-polynomial time complexity if the number of clocks used to model each task is bounded by a constant, which is much lower than the exponential complexity of the traditional model-checking based analysis approach (also assuming the number of clocks is bounded by a constant). We apply dynamic programming techniques to implement the DBF-based analysis framework, and propose state space pruning techniques to accelerate the analysis process. Experimental results show that our DBF-based method can analyze a TAT system with 50 tasks within a few minutes, which significantly outperforms the state-of-the-art TAT-based schedulability analysis tool TIMES.

OpenMP is a popular programming framework in both general and high-performance computing and has recently drawn much interest in embedded and real-time computing. Although the execution semantics of OpenMP are similar to the DAG task model, the constraints posed by the OpenMP specification make them significantly more challenging to analyze. A tied task is an important feature in OpenMP that must execute on the same thread throughout its entire life cycle. A previous work [1] succeeded in analyzing the real-time scheduling of tied tasks by modifying the Task Scheduling Constraints (TSCs) in OpenMP specification. In this article, we also study the real-time scheduling of OpenMP task systems with tied tasks but without changing the original TSCs. In particular, we propose a partitioning-based algorithm, P-EDF-omp, by which the tied constraint can be automatically guaranteed as long as an OpenMP task system can be successfully partitioned to a multiprocessor platform. Furthermore, we conduct comprehensive experiments with both synthetic workloads and established OpenMP benchmarks to show that our approach consistently outperforms the work in [1] -even without modifying the TSCs.

SMART, a recently proposed dynamically reconfigurable NoC, enables single-cycle long-distance communication by building single-bypass paths. However, such a single-cycle single-bypass path will be broken when contention occurs. Thus, lower-priority packets will be buffered at intermediate routers with blocking latency from higher-priority packets, and extra router-stage latency to rebuild remaining path, reducing the bypassing benefits that SMART offers. In this paper, we for the first time propose an effective routing strategy to achieve nearly contention-free bypassing in SMART NoC. Specifically, we identify two different routes for communication pairs: direct route, with which data can reach the destination in a single bypass; and indirect route, with which data can reach the destination in two bypasses via an intermediate router. If a direct route is not found, we would alternatively resort to an indirect route in advance to eliminate the blocking latency, at the cost of only one router-stage latency. Compared with the current routing, our new approach can effectively isolate conflicting communication pairs, greatly balance the traffic loads and fully utilize bypass paths. Experiments show that our approach makes 22.6% performance improvement on average in terms of communication latency.

Most current real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Existing worst-case response time (WCRT) bounds (e.g., Graham's bound) derived for DAGs may be very pessimistic. No one precisely knows the gap between the WCRT bound and the actual WCRT. In this paper, we aim to derive the exact WCRT of a DAG task under the list scheduling upon multi-core platforms. We encode the WCRT analysis problem into a satisfaction modular theoretical (SMT) formulation based on insights into the list scheduling algorithm, and prove that our SMT program can solve the WCRT precisely, providing an accurate baseline to measure the tightness of the existing WCRT bounds. Experiments show that our method significantly improves the tightness of the WCRT bound, and is practically quite efficient, e.g., it can analyze DAGs with more than 40 vertices in a few seconds.

Real-time scheduling and locking protocols are fundamental facilities to construct time-critical systems. For parallel real-time tasks, predictable locking protocols are required when concurrent sub-jobs mutually exclusive access to shared resources. This paper for the first time studies the distributed synchronization framework of parallel real-time tasks, where both tasks and global resources are partitioned to designated processors, and requests to each global resource are conducted on the processor on which the resource is partitioned. We extend the Distributed Priority Ceiling Protocol (DPCP) for parallel tasks under federated scheduling, with which we proved that a request can be blocked by at most one lower-priority request. We develop task and resource partitioning heuristics and propose analysis techniques to safely bound the task response times. Numerical evaluation (with heavy tasks on 8-, 16-, and 32-core processors) indicates that the proposed methods improve the schedulability significantly compared to the state-of-the-art locking protocols under federated scheduling.

The hardness of analyzing conditional directed acyclic graph (DAG) tasks remains unknown so far. For example, previous researches asserted that the conditional DAG's volume can be solved in polynomial time. However, these researches all assume well-nested structures that are recursively composed by single-source-single-sink parallel and conditional components. For conditional DAGs in general that do not comply with this assumption, the hardness and algorithms of volume computation are still open. In this paper, we construct counterexamples to show that previous work cannot provide a safe upper bound of the conditional DAG's volume in general. Moreover, we prove that the volume computation problem for conditional DAGs is strongly $\mathcal{N}\mathcal{P}$-hard. Finally, we propose an exact algorithm for computing the conditional DAG's volume. Experiments show that our method can significantly improve the accuracy of the conditional DAG's volume estimation.

FPGA vendors provide OpenCL software development kits for easier programmability, with the goal of replacing the time-consuming and error-prone register-transfer level (RTL) programming. Many studies explore optimization methods (e.g., loop unrolling, local memory) to accelerate OpenCL programs running on FPGAs. These programs typically follow the default OpenCL execution model, where a kernel deploys multiple work-items arranged into work-groups. However, the default execution model is not always a good fit for an application mapped to the FPGA architecture, which is very different from the multithreaded architecture of GPUs, for which OpenCL was originally designed. In this work, we identify three other execution models that can better utilize the FPGA resources for the OpenCL applications that do not fit well into the default execution model. These three execution models are based on two OpenCL features devised for FPGA programming (namely, single work-item kernel and OpenCL channel). We observe that the selection of the right execution model determines the performance upper bound of a particular application, which can vary by two orders magnitude between the most suitable execution model and the most unsuitable one. However, there is no way to select the most suitable execution model other than empiricall exploring the optimization space for the four of them, which can be prohibitive. To help FPGA programmers identify the right execution model, we propose Boyi, a systematic framework that makes automatic decisions by analyzing OpenCL programming patterns in an application. After finding the right execution model with the help of Boyi, programmers can apply other conventional optimizations to reach the performance upper bound. Our experimental evaluation shows that Boyi can 1) accurately determine the right execution model, and 2) greatly reduce the exploration space of conventional optimization methods.

Mixed-Criticality System (MCS) has been considered widely within academic literature, but is proving difficulty to implement in industry as the theoretical models underpinning the research do not always consider industrial safety standards and practice (e.g., DO-178C, ISO26262, and EN50128). This paper analyses and formalises the mismatches between theoretical models and industrial standards, and presents a generic industrial MCS architecture, termed as Z-MCS. Z-MCS is built upon the conventional theoretical MCS model (i.e., Adaptive Mixed-Criticality), but with additional satisfaction on the industrial safety requirements: i). run-time safety analysis, which determines preserved applications in each system mode; ii). correct partitioning and isolation of different critical elements with temporal, spatial and fault isolation. Furthermore, three implementing methods of Z-MCS are proposed, with a generic schedulability analysis for timing guarantee. Finally, we evaluate and demonstrate Z-MCS in terms of system schedulability and overheads, along with a real-world case study. In addition, this paper is the first attempt for connecting the theoretical MCS model with the industrial context.

ROS (Robot Operating System) is currently the most popular robotic software development framework. Robotic software in safe-critical domain are usually subject to hard real-time constraints, so designers must formally model and analyze their timing behaviors to guarantee that real-time constraints are always honored at runtime. This paper studies real-time scheduling and analysis of processing chains in ROS2, the second-generation ROS with a major consideration of real-time capability. First, we study response time analysis of processing chains on ROS2 executors. We show that the only existing result of this problem is both optimistic and pessimistic, and develop new techniques to address these problems and significantly improve the analysis precision. Second, we reveal that the response time of a processing chain on an executor only depends on its last scheduling entity (callback), which provides useful guidance for designers to improve not only the response time bound, but also the actual worst-case/average response time of the system at little design cost. We conduct experiments with both randomly generated workload and a case study on realistic ROS2 platforms to evaluate and demonstrate our results.

Utilization bound is a well-known concept in real-time scheduling theory for sequential periodic tasks, which can be used both for quantifying the performance of scheduling algorithms and as efficient schedulability tests. However, the schedulability of parallel real time task graphs depends on not only utilization, but also another parameter tensity, the ratio between the longest path length and period. In this paper, we use utilization-tensity bounds to better characterize the schedulability of parallel real-time tasks. In particular, we derive utilization-tensity bounds for parallel DAG tasks under global EDF scheduling, which facilitate significantly more precise schedulability analysis than the state-of-the-art analysis techniques based on capacity augmentation bound and response time analysis. Moreover, we apply the above results to the federated scheduling paradigm to improve the system schedulability by choosing proper scheduling strategies for tasks with different workload and structure features.

OpenMP is a promising framework to develop parallel real-time software on multi-cores. Although similar to the DAG task model, OpenMP task systems are significantly more difficult to analyze due to constraints posed by OpenMP specifications. One of the most interesting features in OpenMP is the support for nested parallelism, enjoying benefits in enhancing performance transparency of parallel libraries and promoting reuse of black-box code. Previous researches on DAG task scheduling mainly restrict to only one level of parallelism. The problem whether OpenMP tasks with multiple levels of parallelism are suitable to real-time systems remains open. In this paper, we study the real-time scheduling and analysis of OpenMP task systems supporting nested parallelism. First, we show that under existing scheduling algorithms in OpenMP implementations, nested parallelism indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we propose a new scheduling algorithm and develop two sound response time bounds by considering the trade-off between simplicity and analysis precision. Experiments demonstrate the efficiency of our methods.

Multicore processors have become mainstream computation platforms not only for general and high-performance computers but also for real-time embedded systems. To fully utilize the computation power of multicores, software must be parallelized. Recently, there has been a rapidly increasing interest in real-time scheduling of parallel real-time tasks, but the field is still much less mature than traditional real-time scheduling of sequential tasks. In this article, we study the real-time scheduling and techniques for parallel real-time tasks based on decomposition, where a task graph is transferred to a set of independent sporadic tasks. In particular, we propose new decomposition strategies that better explore the structure feature of each task to improve schedulability. We develop schedulability tests for the global earliest deadline first (EDF) scheduling algorithm based on decomposition and three types of its variants, with their own pros and cons in different aspects. We conduct experiments to evaluate the real-time performance of our proposed scheduling algorithms against the state-of-the-art scheduling and analysis methods of different types.

Energy harvesting promises to power billions of Internet-of-Things devices without being restricted by battery life. The energy output of harvesters is typically tiny and highly unstable, so the computing system must store program states into nonvolatile memory frequently to preserve the execution progress in the presence of frequent power failures. Task-based intermittent computing is a promising paradigm to provide such capability, where each task executes atomically and only states across task boundaries need to be saved. This article presents LATICS, a low-overhead adaptive task-based intermittent computing system, which dynamically decides the granularity of atomic execution to avoid unnecessarily frequent state saving when energy supply is sufficient. The novel feature of LATICS is to drastically reduce the amount of states to be saved at task boundaries compared with existing solutions. Notably, we disclose that skipping state saving at some task boundary may cause the system to store more states at other places, and thus leads to higher overall overhead. Therefore, LATICS enforces mandatory state saving at certain task boundaries regardless of the current energy condition to reduce state saving overhead. We implement LATICS on a real energy-harvesting platform based on MSP430 and experimentally compare against the state-of-the-art under different settings. The experimental results show that LATICS significantly reduces state saving overhead and improves execution efficiency compared to existing solutions.

Capacity augmentation bound (CAB) is a widely used quantitative metric in theoretical analysis for directed acyclic graph (DAG) parallel real-time tasks, which reveals the key factors the schedulability of DAG tasks heavily depending on: the normalized utilization (the ratio of the total utilization to the core numbers) and the tensity (the maximum ratio of task's longest path length to task's deadline). However, CAB requires both factors of a schedulable task system to be capped by the same threshold. A task system with a normalized utilization slightly larger than that threshold but very small tensity, or very smaller normalized utilization but slightly larger than that threshold has good chance to be scheduled are both denied by CAB. To this end, we propose a new concept called capacity augmentation function (CAF) to better characterize the schedulability of parallel real-time tasks, which provides a more loose and different threshold for both factors. In particular, we derive a CAF-based linear-time schedulability test for real-time constrained-deadline DAG tasks under global EDF, which entirely dominates the state-of-the-art CAB-based test for constrained-deadline settings. Finally, we conduct experiments to compare the acceptance ratio of our CAF-based test with the existing schedulability tests also having linear-time complexity. The results show that CAF-based test significantly outperforms the existing linear-time schedulability test under different parameter settings.

The demand bound function (DBF) is a powerful abstraction to analyze the feasibility/schedulability of real-time tasks. Computing the DBF for expressive system models, such as graph-based tasks, is typically very expensive. In this article, we develop new techniques to drastically improve the DBF computation efficiency for a representative graph-based task model, digraph real-time tasks (DRT). First, we apply the well-known quick processor-demand analysis (QPA) technique, which was originally designed for simple sporadic tasks, to the analysis of DRT. The challenge is that existing analysis techniques of DRT have to compute the demand for each possible interval size, which is contradictory to the idea of QPA that aims to aggressively skip the computation for most interval sizes. To solve this problem, we develop a novel integer linear programming (ILP)-based analysis technique for DRT, to which we can apply QPA to significantly improve the analysis efficiency. Second, we improve the task utilization computation (a major step in DBF computation for DRT) efficiency from pseudo-polynomial complexity to polynomial complexity. Experiments show that our approach can improve the analysis efficiency by dozens of times.

Timing analysis of real-time systems must consider cache-related pre-emption delay (CRPD) costs when pre-emptive scheduling is used. While most previous work on CRPD analysis only considers instruction caches, the CRPD incurred on data caches is actually more significant. The state-of-the-art CRPD analysis methods are based on useful cache block (UCB) calculation. Unfortunately, as shown in this article, directly extending the existing UCB calculation techniques from instruction caches to data caches will lead to both unsoundness and significant imprecision. To solve these problems, we develop a new UCB calculation technique for data caches, which redefines the analysis unit (to address the unsoundness in the existing method) and precisely captures the dynamic cache access behavior by taking the temporal scopes of memory blocks into consideration. The experimental results show that our new technique yields substantially tighter CRPD estimations comparing with the state-of-the-art.

Continuous technology scaling in manycore systems leads to severe overheating issues. To guarantee system reliability, it is critical to accurately yet efficiently monitor runtime temperature distribution for effective chip thermal management. As an emerging communication architecture for new-generation manycore systems, optical network-on-chip (ONoC) satisfies the communication bandwidth and latency requirements with low power dissipation. Moreover, observation shows that it can be leveraged for runtime thermal sensing. In this article, we propose a brand-new on-chip thermal sensing approach for ONoC-based manycore systems by utilizing the intrinsic thermal sensitivity of optical devices and the inter-processor communications in ONoCs. It requires no extra hardware but utilizes existing optical devices in ONoCs and combines them with lightweight software computation in a hardware-software collaborative manner. The effectiveness of the our approach is validated both at the device level and the system level through professional photonic simulations. Evaluation results based on synthetic communication traces and realistic benchmarks show that our approach achieves an average temperature inaccuracy of only 0.6648 K compared to ground-truth values and is scalable to be applied for large-size ONoCs.

Energy-efficiency is a critical requirement for computation-intensive real-time applications on multi-core embedded systems. Multi-core processors enable intra-task parallelism, and in this work, we study energy-efficient real-time scheduling of constrained deadline sporadic parallel tasks, where each task is represented as a directed acyclic graph (DAG). We consider a clustered multi-core platform where processors within the same cluster run at the same speed at any given time. A new concept named speed-profile is proposed to model per-task and per-cluster energy-consumption variations during run-time to minimize the expected long-term energy consumption. To our knowledge, no existing work considers energy-aware real-time scheduling of DAG tasks with constrained deadlines, nor on a clustered multi-core platform. The proposed energy-aware real-time scheduler is implemented upon an ODROID XU-3 board to evaluate and demonstrate its feasibility and practicality. To complement our system experiments in large-scale, we have also conducted simulations that demonstrate a CPU energy saving of up to 67 percent through our proposed approach compared to existing methods.

Communication contention and thermal susceptibility are two potential issues in optical network-on-chip (ONoC) architecture, which are both critical for ONoC designs. However, minimizing conflict and guaranteeing thermal reliability are incompatible in most cases. In this paper, we present a routing criterion in the network level. Combined with device-level thermal tuning, it can implement thermal-reliable ONoC. We further propose two routing approaches (including a mixed-integer linear programming (MILP) model and a heuristic algorithm (CAR)) to minimize communication conflict based on the guaranteed thermal reliability, and meanwhile, mitigate the energy overheads of thermal regulation in the presence of chip thermal variations. By applying the criterion, our approaches achieve excellent performance with largely reduced complexity of design space exploration. Evaluation results on synthetic communication traces and realistic benchmarks show that the MILP-based approach achieves an average of 112.73% improvement in communication performance and 4.18% reduction in energy overhead compared to state-of-the-art techniques. Our heuristic algorithm only introduces 4.40% performance difference compared to the optimal results and is more scalable to large-size ONoCs.

This paper for the first time studies the scheduling and analysis of parallel real-time tasks with semaphores. In parallel task systems, each task may issue multiple requests to a semaphore, which raises new challenges to the design and analysis problems. We propose a new locking protocol LPP that limits the maximal number of requests to a semaphore by a task that can block other tasks at any time. We develop analysis techniques to safely bound the task response times, with which we prove that the best real-time performance is achieved if only one request to a semaphore by a task is allowed to block other tasks at a time. Experiments under different parameter settings are conducted to compare our proposed protocol and analysis techniques with the state-of-the-art spinlock protocol and analysis techniques for parallel real-time tasks.

Synchronous parallel tasks are widely used in HPC for purchasing high average performance, but merely consider how to guarantee good timing predictabilities. OpenMP is a promising framework for multi-core real-time embedded systems. The synchronous OpenMP tasks are significantly more difficult to schedule and analyze due to constraints posed by OpenMP specifications. An important OpenMP feature is tied task, which must execute on the same thread during the whole life cycle. This paper designs a novel method, called group scheduling, to schedule synchronous OpenMP tasks, which divides tasks into several groups, and assigns some of them to dedicated cores, in order to isolate tied tasks. We derive a linear-time computable response time bound. Experiments with both randomly generated and realistic OpenMP tasks show that our new bound significantly outperforms the existing bound.

Real-time and embedded systems are shifting from single-core to multi-core processors, on which software must be parallelized to fully utilize the computation capacity of hardware. Recently much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs (DAG). However, most of these studies assume tasks to have implicit or constrained deadlines. Much less work considered the general case of arbitrary deadlines (i.e., the relative deadline is allowed to be larger than the period), which is more difficult to analyze due to intra-task interference among jobs. In this paper, we study the analysis of Global Earliest Deadline First (GEDF) scheduling for DAG parallel tasks with arbitrary deadlines. We develop new analysis techniques for GEDF scheduling of a single DAG task, which not only outperform the state-of-the-art in general evidenced by empirical evaluation, but also guarantee a better capacity augmentation bound 2.41 (the best known result is 2.5). The proposed analysis techniques are also extended to and evaluated with the case of multiple DAG tasks using the federated scheduling approach.

In this paper, we for the first time utilize the micro-ring resonators (MRs) in optical networks-on-chip (ONoCs) to implement thermal sensing without requiring additional hardware or chip area. The challenges in accuracy and reliability that arise from fabrication-induced process variations (PVs) and device-level wavelength tuning mechanism are resolved. We quantitatively model the intrinsic thermal sensitivity of MRs with finegrained consideration of wavelength tuning mechanism. Based on it, a novel PV-tolerant thermal sensor design is proposed. By exploiting the hidden ‘redundancy’ in wavelength division multiplexing (WDM) technique, our sensor achieves accurate and efficient temperature measurement with the capability of PV tolerance. Evaluation results based on professional photonic component and circuit simulations show an average of 86.49% improvement in measurement accuracy compared to the state-of-the-art on-chip thermal sensing approach using MRs. Our thermal sensor achieves stable performance in the ONoCs employing dense WDM with an inaccuracy of only 0.8650 K.

As the shared last level cache (LLC) in multicore processors has been shown to be a critical resource for system performance, much work has been proposed for improving the quality of service (QoS) and throughput on LLC. Cache Allocation Technology (CAT) and Adaptive Cache Replacement Policies (ACRP) are two of the techniques that are featured in recent Intel processors. CAT implements way partitioning and provides the ability to control the cache space allocation among cores. ACRP works with multiple replacement policies and enables the cache to adapt to the cache replacement policy with less cache misses. In this paper, we first show an interesting finding that ACRP technique can violate the performance isolation provided by CAT. We find the cause for this problem is that the ACRP chooses the cache replacement policy upon the global information even although the cache space partitioning is being enabled by CAT. As the result, the cache/performance isolation can be impaired by the interference on cache replacement policy. To deal with this problem, we propose a low overhead method to predict the worst execution time degradation caused by the replacement policy adaptation. Thus, in the partitioned cache space, if the worst execution time estimated by our method is not beyond the response time required for this program, the QoS for this program can be quaranteed no matter how the cache replacement policies alternate.

We propose an approach to calculate delay bound for multiprocessor real-time systems scheduled by GEDF. Different from most existing analysis techniques analyzing sporadic tasks, we consider bursty tasks which have more general arrival patterns. In detail, we use shapers to eliminate burst in original system inputs and generate sporadic job sequences, and then calculate the delay bound of each task. To further improve our approach, we design a heuristic algorithm to make as more tasks as possible to meet their deadlines by adjusting settings of shapers. Experiments show that the proposed algorithm can lead to improvement of acceptance ratio and the delay bound derived is much smaller than that by compared existing work.

DAG task model is a general parallel task model that has been widely concerned and studied by researchers. The combination of mixed-criticality and DAG task model makes it difficult to analyze system behaviors. Under federated mixed-criticality scheduling algorithm, tasks are physically isolated with regard to computation resources, which leads to lower analysis complexity and better performance. However, federated mixed-criticality scheduling algorithm suffers resource waste as in federated scheduling, and almost half of processor resources can be wasted in extreme cases. In this paper, we address the problem and propose a novel semi-federated mixed-criticality algorithm (SFMC). SFMC combines semi-federated scheduling with mixed-criticality systems, whose original architecture is changed to a dual-hierarchical one. When analyzing the combined system, we first allocate finer-grained processor resources to each MC DAG task, then we prove the correctness of the SFMC algorithm in both normal and critical states. The proposed algorithm is evaluated on randomly generated independent DAG task sets based on OpenMP benchmarks. Experiment results present that our algorithm has better performance on schedulability than the federated mixed-criticality scheduling algorithm.

With the growth of computation-intensive real-time applications on multi-core embedded systems, energy-efficient real-time scheduling becomes crucial. Multi-core processors enable intra-task parallelism, and there has been much progress on exploiting that, while there has been only a little progress on energy-efficient multi-core real-time scheduling as yet. In this work, we study energy-efficient real-time scheduling of constrained deadline sporadic parallel tasks, where each task is represented as a directed acyclic graph (DAG). We consider a clustered multi-core platform where processors within the same cluster run at the same speed at any given time. A new concept named speed-profile is proposed to model per-task and per-cluster energy-consumption variations during run-time to minimize the expected long-term energy consumption. To our knowledge, no existing work considers energy-aware real-time scheduling of DAG tasks with constrained deadlines, nor on a clustered multi-core platform. The proposed energy-aware realtime scheduler is implemented upon an ODROID XU-3 board to evaluate and demonstrate its feasibility and practicality. To complement our system experiments in large-scale, we have also conducted simulations that demonstrate a CPU energy saving of up to 57% through our proposed approach compared to existing methods.

Existing DAG-based task models in real-time scheduling research assume well-nested structures recursively composed by single-source-single-sink parallel and conditional components. However, realistic OpenMP task systems in general have more flexible structures that do not comply with this assumption. In this paper, we model the behaviors of general OpenMP task systems with non-well-nested branching structures and study the problem of how to bound their worst-case response times (WCRT). A naive solution is to apply the established WCRT bound for DAG tasks without conditional branches to the exponentially many possible execution flows, which has exponential time complexity. In this paper, we develop a linear-time algorithm to efficiently calculate WCRT bounds for OpenMP task systems with non-well-nested branching structures. Experiments with both synthetic task graphs and realistic OpenMP programs are conducted to evaluate the performance of our method.

Real-Time Calculus (RTC) is a powerful framework for modeling and analyzing complex networked real-time systems. RTC builds up on and shares many similarities with Network Calculus (NC), but some concepts are not completely the same in RTC and NC. One of the most important properties in NC is pay-burst-only-once, which can improve the precision of end-to-end performance analysis. Naturally, people would expect the pay-burst-only-once property to also hold in RTC. In fact, some existing work has used it in some performance analysis problems. Unfortunately, the pay-burst-only-once property has never been proved in RTC. There are even some results seeming to be against the pay-burst-only-once property in RTC. In this paper, we prove that the pay-burst-only-once property indeed holds in RTC.

In mixed-criticality systems, timely handling of I/O is a key for the system being successfully implemented and functioning appropriately. The criticality levels of functions and sometimes the whole system are often dependent on the state of the I/O. An I/O system for a MCS must provide simultaneously isolation/separation, performance/efficiency and timing-predictability, as well as being able to manage I/O resource in an adaptive manner to facilitate efficient yet safe resource sharing among components of different criticality levels. Existing approaches cannot achieve all of these requirements simultaneously. This paper presents a MCS I/O management framework, termed MCS-IOV. MCS-IOV is based on hardware assisted virtualisation, which provides temporal and spatial isolation and prohibits fault propagation with small extra overhead in performance. MCS-IOV extends a real-time I/O virtualisation system, by supporting the concept of mixed criticalities and customised interfaces for schedulers, which offers good timing-preditability. MCS-IOV supports I/O driven criticality mode switch (the mode switch can be triggered by detection of unexpected I/O behaviors, e.g., a higher I/O utilization than expected) and timely I/O resource reconfiguration up on that. Finally, We evaluated and demonstrate MCS-IOV in different aspects.

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.

Suspension-based locks are widely used in realtime systems to coordinate simultaneous accesses to exclusive shared resources. Although suspension-based locks have been well studied for sequential real-time tasks, little work has been done on this topic for parallel real-time tasks. This paper for the first time studies the problem of how to extend existing sequential-task locking protocols and their analysis techniques to the parallel task model. More specifically, we extend two locking protocols OMLP and OMIP, which were designed for clustered scheduling of sequential real-time tasks, to federated scheduling of parallel real-time tasks, and develop path-oriented techniques to analyze and count blocking time. Experiments are conducted to evaluate the performance of our proposed approaches and compare them against the state-of-the-art.

Spin-Torque Transfer Magnetic RAM (STT-RAM), one of the emerging nonvolatile memory (NVM) technologies explored as the replacement for SRAM memory architectures, is particularly promising due to the fast access speed, high integration density, and zero standby power consumption. Recently, hybrid deigns with SRAM and STT-RAM buffers for routers in Network-on-Chip (NoC) systems have been widely implemented to maximize the mutually complementary characteristics of different memory technologies, and leverage the efficiency of intra-router latency and system power consumption. With the realization of Processing-in-Memory enabled by STT-RAM, in this paper, we novelly offload the execution from processors to the STT-RAM based on-chip routers to improve the application performance. On top of the hybrid buffer design in routers, we further present system-level approaches, including an ILP model and polynomial-time heuristic algorithms, to fine-tune the application mapping and scheduling on NoCs, with the objectives of improving system performance-energy efficiency. Network overhead caused by flit conflict in conventional communication circumstances can be ideally avoided by computing the contended flits in intermediate routers; meanwhile, the pressure of heavy workload on processors can be relieved by transferring partial operations to routers, such that network latency and system power consumption can be significantly reduced. Experimental results demonstrate that application schedule length and system energy consumption can be reduced by 35.62, 32.87 percent on average, respectively, in extensive evaluation experiments on PARSEC benchmark applications. In particular, the achievements of application performance and energy efficiency, averagely 36.44 and 33.19 percent, for the CNN application AlexNet have verified the practicability and effectiveness of our presented approaches.

Cyborg insects have attracted great attention as the flight performance they have is incomparable by micro aerial vehicles and play a critical role in supporting extensive applications. Approaches to construct cyborg insects consist of two major issues: 1) the stimulating paradigm and 2) the control policy. At present, most cyborg insects are constructed based on invasive methods, requiring the implantation of electrodes into neural or muscle systems, which would harm the insects. As the control policy is basically manual control, the shortcomings of which lie in the requirement of excessive amount of experiments and focused attention. This paper presents the design and implementation of a noninvasive and much safer cyborg insect system based on visual stimulation. The tethered paradigm is adopted here and we look at controlling the flight behavior of bumblebees, especially the abdominal-waving behavior, in the context of a model-free reinforcement learning problem. The problem is formulated as a finite and deterministic Markov decision process, where the agent is designed to change the abdominal-waving behavior from the initial state to the target state. Sarsa with transformed reward function which can speed up the learning process is employed to learn the optimal control policy. Learned policies are compared to the stochastic one by evaluating the results of ten bumblebees, demonstrating that abdominal-waving state can be modulated to approximate the target state quickly with small deviation.

In this paper, we propose a novel approach to schedule conditional DAG parallel tasks, with which we can derive safe response time upper bounds significantly better than the state-of-the-art counterparts. The main idea is to eliminate the notorious timing anomaly in scheduling parallel tasks by enforcing certain order constraints among the vertices, and thus the response time bound can be accurately predicted off-line by somehow “simulating” the runtime scheduling. A key challenge to apply the timing-anomaly free scheduling approach to conditional DAG parallel tasks is that at runtime it may generate exponentially many instances from a conditional DAG structure. To deal with this problem, we develop effective abstractions, based on which a safe response time upper bound is computed in polynomial time. We also develop algorithms to explore the vertex orders to shorten the response time bound. The effectiveness of the proposed approach is evaluated by experiments with randomly generated DAG tasks with different parameter configurations.

With the fast growth of civil drones, their security problems meet significant challenges. A commercial drone may be hijacked by a GPS-spoofing attack for illegal activities, such as terrorist attacks. The target of this article is to develop a technique that only uses onboard gyroscopes to determine whether a drone has been hijacked. Ideally, GPS data and the angular velocities measured by gyroscopes can be used to estimate the acceleration of a drone, which can be further compared with the measurement of the accelerometer to detect whether a drone has been hijacked. However, the detection results may not always be accurate due to some calculation and measurement errors, especially when no hijacking occurs in curve trajectory situations. To overcome this, in this article, we propose a novel and simple method to detect hijacking only based on gyroscopes’ measurements and GPS data, without using any accelerometer in the detection procedure. The computational complexity of our method is very low, which is suitable to be implemented in the drones with micro-controllers. On the other hand, the proposed method does not rely on any accelerometer to detect attacks, which means it receives less information in the detection procedure and may reduce the results accuracy in some special situations. While the previous method can compensate for this flaw, the high detection results also can be guaranteed by using the above two methods. Experiments with a quad-rotor drone are conducted to show the effectiveness of the proposed method and the combination method.

Real-time and embedded systems are shifting from single-core to multi-core processors, on which the software must be parallelized to fully utilize the computation capacity of the hardware. Recently, much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs (DAG). However, most of these studies assume tasks to have implicit or constrained deadlines. Much less work considered the general case of arbitrary deadlines (i.e., the relative deadline is allowed to be larger than the period), which is more difficult to analyze due to intra-task interference among jobs. In this article, we study the analysis of Global Earliest Deadline First (GEDF) scheduling for DAG parallel tasks with arbitrary deadlines. We develop new analysis techniques for GEDF scheduling of a single DAG task and this new analysis techniques can guarantee a better capacity augmentation bound 2.41 (the best known result is 2.5) in the case of a single task. Furthermore, the proposed analysis techniques are also extended to the case of multiple DAG tasks under GEDF and federated scheduling. Finally, through empirical evaluation, we justify the out-performance of our schedulability tests compared to the state-of-the-art in general.

Heterogenerous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of typed scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the non-self-sustainability problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its non-self-sustainability problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are more precise than the existing bound while having good scalability.

Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. However, no existing work has explored the execution order of eligible vertices within a DAG task. In this paper, we show that this intra-task vertex execution order has a large impact on system schedulability and propose to control the execution order by vertex-level priority assignment. We develop analysis techniques to bound the worst-case response time for the proposed scheduling strategy and design heuristics for proper priority assignment to improve system schedulability as much as possible. We further extend the proposed approach to the general setting of multiple recurrent DAG tasks. Experiments with both realistic parallel benchmark applications and randomly generated workload show that our method consistently outperforms state-of-the-art methods with different task graph structures and parameter configurations.

Heterogenerous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of typed scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the non-self-sustainability problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its non-self-sustainability problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are significantly more precise than the existing bound while having good scalability.

Mixed-criticality models are an emerging paradigm for the design of real-time systems because of their significantly improved resource efficiency. However, formal mixed-criticality models have traditionally been characterized by two impractical assumptions: once any high-criticality task overruns, all low-criticality tasks are suspended and all other high-criticality tasks are assumed to exhibit high-criticality behaviors at the same time. In this paper, we propose a more realistic mixed-criticality model, called the flexible mixed-criticality (FMC) model, in which these two issues are addressed in a combined manner. In this new model, only the overrun task itself is assumed to exhibit high-criticality behavior, while other high-criticality tasks remain in the same mode as before. The guaranteed service levels of low-criticality tasks are gracefully degraded with the overruns of high-criticality tasks. We derive a utilization-based technique to analyze the schedulability of this new mixed-criticality model under EDF-VD scheduling. During run time, the proposed test condition serves an important criterion for dynamic service level tuning, by means of which the maximum available execution budget for low-criticality tasks can be directly determined with minimal overhead while guaranteeing mixed-criticality schedulability. Experiments demonstrate the effectiveness of the FMC scheme compared with state-of-the-art techniques.

In this paper, we study the scheduling problem of the imprecise mixed-criticality model (IMC) under earliest deadline first with virtual deadline (EDF-VD) scheduling upon uniprocessor systems. Two schedulability tests are presented. The first test is a concise utilization-based test which can be applied to the implicit deadline IMC task set. The suboptimality of the proposed utilization-based test is evaluated via a widely-used scheduling metric, speedup factors. The second test is a more effective test but with higher complexity which is based on the concept of demand bound function (DBF). The proposed DBF-based test is more generic and can apply to constrained deadline IMC task set. Moreover, in order to address the high time cost of the existing deadline tuning algorithm, we propose a novel algorithm which significantly improve the efficiency of the deadline tuning procedure. Experimental results show the effectiveness of our proposed schedulability tests, confirm the theoretical suboptimality results with respect to speedup factor, and demonstrate the efficiency of our proposed algorithm over the existing deadline tunning algorithm. In addition, issues related to the implementation of the IMC model under EDF-VD are discussed.

Dark silicon is the phenomenon that a fraction of many-core chip has to be turned off or run in a low-power state in order to maintain the safe chip temperature. System-level thermal management techniques normally map application on non-adjacent cores, while communication efficiency among these cores will be oppositely affected over conventional network-on-chip (NoC). Recently, SMART NoC architecture is proposed, enabling single-cycle multi-hop bypass channels to be built between distant cores at runtime, to reduce communication latency. However, communication efficiency of SMART NoC will be diminished by communication contention, which will in turn decrease system performance. In this paper, we first propose an Integer-Linear Programming (ILP) model to properly address communication problem, which generates the optimal solutions with the consideration of inter-processor communication. We further present a novel heuristic algorithm for task mapping in dark silicon many-core systems, called TopoMap, on top of SMART architecture, which can effectively solve communication contention problem in polynomial time. With fine-grained consideration of chip thermal reliability and inter-processor communication, presented approaches are able to control the reconfigurability of NoC communication topology in task mapping and scheduling. Thermal-safe system is guaranteed by physically decentralized active cores, and communication overhead is reduced by the minimized communication contention and maximized bypass routing. Performance evaluation on PARSEC shows the applicability and effectiveness of the proposed techniques, which achieve on average 42.5 and 32.4 percent improvement in communication and application performance, and 32.3 percent reduction in system energy consumption, compared with state-of-the-art techniques. TopoMap only introduces 1.8 percent performance difference compared to ILP model and is more scalable to large-size NoCs.

The existing mixed-criticality (MC) real-time task models assume that once any high-criticality task overruns, all high-criticality jobs execute up to their most pessimistic WCET estimations simultaneously in a one-shot manner. This is very pessimistic in the sense of unnecessary resource overbooking. In this paper, we propose a more generalized mixed-critical real-time task model, called flexible MC model with multiple-shot transitions (FMC-MST), to address this problem. In FMC-MST, high-criticality tasks can transit multiple intermediate levels to handle less pessimistic overruns independently and to nonuniformly scale the deadline on each level. We develop a run-time schedulability analysis for FMC-MST under EDF-VD scheduling, in which a better tradeoff between the penalties of low-criticality tasks and the overruns of high-criticality tasks is achieved to improve the service quality of low-criticality tasks. We also develop a resource optimization technique to find resource-efficient level-insertion configurations for FMC-MST task systems under MC timing constraints. Experiments demonstrate the effectiveness of FMC-MST compared with the state-of-the-art techniques.

Capacity augmentation bound is a widely used quantitative metric in theoretical studies of schedulability analysis for directed acyclic graph (DAG) parallel real-time tasks, which not only quantifies the suboptimality of the scheduling algorithms, but also serves as a simple linear-time schedulability test. Earlier studies on capacity augmentation bounds of the sporadic DAG task model were either restricted to a single DAG task or a set of tasks with implicit deadlines. In this paper, we consider parallel tasks with constrained deadlines under global earliest deadline first policy. We first show that it is impossible to obtain a constant bound for our problem setting, and derive both lower and upper bounds of the capacity augmentation bound as a function with respect to the maximum ratio of task period to deadline. Our upper bound is at most 1.47 times larger than the optimal one. We conduct experiments to compare the acceptance ratio of our capacity augmentation bound with the existing schedulability test also having linear-time complexity. The results show that our capacity augmentation bound significantly outperforms the existing linear-time schedulability test under different parameter settings.

Timing analysis of real-time tasks under preemptive scheduling must take cache-related preemption delay (CRPD) into account. Typically, a task may be preempted more than once during the execution in each period. To bound the total CRPD of${k}$preemptions, existing CRPD analysis techniques estimate the CRPD at each program point, and use the sum of the${k}$-largest CRPD among all program points as the total CRPD upper bound. In this paper, we disclose that the above-mentioned approach, although works well for instruction caches, leads to significant overestimation when dealing with data caches. This is because on data caches, the CRPD of preemptions at different program points may have correlations, and the total CRPD of multiple preemptions is in general smaller than the simple sum of the worst-case CRPD of each preemption. To address this problem, we propose a new technique to efficiently explore the correlation among the CRPD of different preemptions, and thus more precisely calculate the total CRPD. Experiments with benchmark programs show that the proposed technique leads to substantially tighter total CRPD estimation with multiple preemptions comparing with the state-of-the-art.

This work studies energy-aware real-time scheduling of a set of sporadic Directed Acyclic Graph (DAG) tasks with implicit deadlines. While meeting all real-time constraints, we try to identify the best task allocation and execution pattern such that the average power consumption of the whole platform is minimized. To our knowledge, this is the first work that addresses the power consumption issue in scheduling multiple DAG tasks on multi-cores and allows intra-task processor sharing. First, we adapt the decomposition-based framework for federated scheduling and propose an energy-sub-optimal scheduler. Then, we derive an approximation algorithm to identify processors to be merged together for further improvements in energy-efficiency. The effectiveness of the proposed approach is evaluated both theoretically via approximation ratio bounds and also experimentally through simulation study. Experimental results on randomly generated workloads show that our algorithms achieve an energy saving of 60% to 68% compared to existing DAG task schedulers.

The IEC standard WIA-PA is a communication protocol for industrial wireless sensor networks. Its special features, including a hierarchical topology, hybrid centralized-distributed management and packet aggregation make it suitable for large-scale industrial wireless sensor networks. Industrial systems place large real-time requirements on wireless sensor networks. However, the WIA-PA standard does not specify the transmission methods, which are vital to the real-time performance of wireless networks, and little work has been done to address this problem. In this article, we propose a real-time aggregation scheduling method for WIA-PA networks. First, to satisfy the real-time constraints on dataflows, we propose a method that combines the real-time theory with the classical bin-packing method to aggregate original packets into the minimum number of aggregated packets. The simulation results indicate that our method outperforms the traditional bin-packing method, aggregating up to 35% fewer packets, and improves the real-time performance by up to 10%. Second, to make it possible to solve the scheduling problem of WIA-PA networks using the classical scheduling algorithms, we transform the ragged time slots of WIA-PA networks to a universal model. In the simulation, a large number of WIA-PA networks are randomly generated to evaluate the performances of several real-time scheduling algorithms. By comparing the results, we obtain that the earliest deadline first real-time scheduling algorithm is the preferred method for WIA-PA networks.

ARM's big. LITTLE architecture coupled with Heterogeneous Multi-Processing (HMP) has enabled energy-efficient solutions in the dark silicon era. System-level techniques activate nonadjacent cores to eliminate chip thermal hotspot. However, it unexpectedly increases communication delay due to longer distance in network architectures, and in turn degrades application performance and system energy efficiency. In this paper, we present a novel hierarchical hardware-software collaborated approach to address the performance/temperature conflict in dark silicon many-core systems. Optimizations on interprocessor communication, application performance, chip temperature and energy consumption are well isolated and addressed in different phases. Evaluation results show that on average 22.57% reduction of communication latency, 23.04% improvement on energy efficiency and 6.11°C reduction of chip peak temperature are achieved compared with state-of-the-art techniques.

On-chip communication is the bottleneck of system performance for NoC-based MPSoCs. SMART, a recently proposed NoC architecture, enables single-cycle multi-hop communications. In SMART NoCs, unconflicted messages can go through an express bypass and the communication efficiency is significantly improved, while conflicted messages have to be buffered for guaranteed delivery with extra delays. Therefore, that performance of SMART NoC may be seriously degraded when communication contention increases. In this paper, we present task mapping techniques to address this problem for SMART NoCs, with the consideration of communication contention, rather than inter-processor distance, by minimizing conflicts and thus maximizing bypass utilization. We first model the entire problem by ILP formulations to find the theoretically optimal solution, and further propose polynomial-time algorithms for contention-aware task mapping and message priority assignment. Communicating tasks can be mapped to distant processors in SMART NoCs as long as conflict-free communication paths can be established and bypass can be enabled. Evaluation results on real benchmarks show an average of 44.1% and 32.8% improvement in communication efficiency and application performance compared to state-of-the-art techniques. The proposed heuristic algorithms only introduce 1.9% performance difference compared to the ILP model and are more scalable to large-size NoCs.

The fast growth of civil drones raises significant security challenges. A legitimate drone may be hijacked by GPS spoofing for illegal activities, such as terrorist attacks. The target of this paper is to develop techniques to let drones detect whether they have been hijacked using onboard motion sensors (accelerometers and gyroscopes). Ideally, the linear acceleration and angular velocity measured by motion sensors can be used to estimate the position of a drone, which can be compared with the position reported by GPS to detect whether the drone has been hijacked. However, the position estimation by motion sensors is very inaccurate due to the significant error accumulation over time. In this paper, we propose a novel method to detect hijacking based on motion sensors measurements and GPS, which overcomes the accumulative error problem. The computational complexity of our method is very low, and thus is suitable to be implemented in the micro-controllers of drones. Experiments with a quad-rotor drone are conducted to show the effectiveness of the proposed method.

In this work, we study energy-aware real-time scheduling of a set of sporadic Directed Acyclic Graph (DAG) tasks with implicit deadlines. While meeting all real-time constraints, we try to identify the best task allocation and execution pattern such that the average power consumption of the whole platform is minimized. To the best of our knowledge, this is the first work that addresses the power consumption issue in scheduling multiple DAG tasks on multi-cores and allows intra-task processor sharing. We first adapt the decomposition-based framework for federated scheduling and propose an energy-sub-optimal scheduler. Then we derive an approximation algorithm to identify processors to be merged together for further improvements in energy-efficiency and to prove the bound of the approximation ratio. We perform a simulation study to demonstrate the effectiveness and efficiency of the proposed scheduling. The simulation results show that our algorithms achieve an energy saving of 27% to 41% compared to existing DAG task schedulers.

Optical networks-on-chip (ONoCs) is a new promising communication paradigm that upgrades the traditional on-chip networks (NoCs) with the ultra-high communication bandwidth and low latency. Silicon microring resonators (MRRs), as a critical component of ONoCs used to implement the selection and redirection of optical signals, are inherently sensitive to the environmental temperature. The applicability of the ONoCs is essentially restricted by the performance of these optical devices that relies on the thermal conditions of the chip. In this paper, we study the thermo-optic effects of the MRRs quantitatively, build and verify the models of the MRRs based on the finite-difference time-domain (FDTD) method. We present formal relationship models between the temperature of a MRR and its optical losses and resonance wavelength. For the first time, the variation between the two types of MRRs, the parallel microring resonators (PMRs) and the crossing microring resonators (CMRs), are systematically addressed, which greatly improves the accuracy and applicability of the models. The results presented in this paper are systematically verified using professional optics methodology, and can be widely applied for accurate and efficient analysis of the thermo-optic effects in different domains of the ONoC community.

Real-time Calculus (RTC) is a non-stochastic queuing theory to the worst-case performance analysis of distributed real-time systems. Workload as well as resources are modelled as piece-wise linear, pseudo-periodic curves and the system under investigation is modelled as a sequence of algebraic operations over these curves. The memory footprint of computed curves increases exponentially with the sequence of operations and RTC may become computationally infeasible fast. Recently, Finitary RTC has been proposed to counteract this problem. Finitary RTC restricts curves to finite input domains and thereby counteracts the memory demand explosion seen with pseudo periodic curves of common RTC implementations. However, the proof to the correctness of Finitary RTC specifically exploits the operational semantic of the greed processing component (GPC) model and is tied to the maximum busy window size. This is an inherent limitation, which prevents a straight-forward generalization. In this paper, we provide a generalized Finitary RTC that abstracts from the operational semantic of a specific component model and reduces the finite input domains of curves even further. The novel approach allows for faster computations and the extension of the Finitary RTC idea to a much wider range of RTC models.

Static timing analysis is crucial for design of realtime systems. While the worst-case execution time of a task is typically computed or measured in a single task environment, the presence of caches imposes additional cache related preemption delay (CRPD) cost to the lower priority tasks in a preemptive multi-tasking system. In this work, we show that existing instruction CRPD analysis techniques cannot be straightforwardly extended for safe and precise data CRPD analysis. In order to capture the dynamic behavior of the data memory references, we introduce the notion of temporal scopes into the abstract cache state (ACS) to capture the data memory blocks that must or may reside in the cache during certain time intervals of program execution. Based on the improved ACS representation, we present a temporal scope aware useful cache block (UCB) calculation for safe and tight estimation of the data CRPD cost. Experimental results show that the proposed technique leads to substantially tighter CRPD estimation, and is applicable to programs with complex data reference patterns.

The charging power supply for batteries may be variable under many circumstances, e.g., when using solar panels or air-driven generators as the energy source. The mismatch between the voltages of the power supply and the battery may cause significant charging inefficiency. In this paper, we use reconfigurable batteries to solve this voltage mismatch problem. We develop algorithms to dynamically decide the battery connections, to both minimize the voltage mismatch and maintain SOC balancing among difference batteries. We build a hardware prototype to implement and validate our method and use simulation experiments to empirically evaluate its performance.

Real-time systems are shifting from single-core to multi-core processors. Software must be parallelized to fully utilize the computation power of multi-core architecture. OpenMP is a popular parallel programming framework in general and high-performance computing, and recently has drawn a lot of interests in embedded and real-time computing. Much recent work has been done on real-time scheduling of OpenMP-based parallel workload. However, these studies conduct evaluations with randomly generated task systems, which cannot well represent the structure features of OpenMP workload. This paper presents a benchmark suite, ompTGB, to support research on real-time scheduling of OpenMP-based parallel tasks. ompTGB does not only collect realistic OpenMP programs, but also models them into task graphs so that the real-time scheduling researchers can easily understand and use them. We also present a new response time bound for a subset of OpenMP programs and use it to demonstrate the usage of ompTGB.

Federated scheduling is a promising approach to schedule parallel real-time tasks on multi-cores, where each heavy task exclusively executes on a number of dedicated processors, while light tasks are treated as sequential sporadic tasks and share the remaining processors. However, federated scheduling suffers resource waste since a heavy task with processing capacity requirement x+epsilon (where x is an integer and 0 epsilon 1) needs x+1 dedicated processors. In the extreme case, almost half of the processing capacity is wasted. In this paper we propose the semi-federate scheduling approach, which only grants x dedicated processors to a heavy task with processing capacity requirement x+epsilon, and schedules the remaining epsilon part together with light tasks on shared processors. Experiments with randomly generated task sets show the semi-federated scheduling approach significantly outperforms not only federated scheduling, but also all existing approaches for scheduling parallel real-time tasks on multi-cores.

OpenMP is a promising framework for developing parallel real-time software on multi-cores. Although similar to the DAG task model, OpenMP task systems are significantly more difficult to analyze due to constraints posed by the OpenMP specification. An important feature in OpenMP is tied tasks, which must execute on the same thread during the whole life cycle. Although tied tasks enjoy benefits in simplicity and efficiency, it was considered to be not suitable to real-time systems due to its complex behavior. In this paper, we study the realtime scheduling and analysis of OpenMP task systems with tied tasks. First, we show that under the existing scheduling algorithms in OpenMP, tied tasks indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we proposed a new scheduling algorithm and developed two response time bounds for it, with different trade-off between simplicity and analysis precision. Experiments with both randomly generated OpenMP task systems and realistic OpenMP programs show that the response time bounds obtained by our approach for tied task systems are very close to that of untied tasks.

Real-Time Calculus (RTC) is a powerful framework for modeling and worst-case performance analysis of networked systems. GPC and AND are two fundamental components in RTC, which model priority-based resource arbitration and synchronization operations, respectively. In this paper, we revisit GPC and AND. For GPC, we develop tighter output arrival curves to more precisely characterize the output event streams. For AND, we first identify a problem in the existing analysis method that may lead to negative values in the output curves, and present corrections to the problem. Then we generalize AND to synchronize more than two input event streams. We implement our new theoretical results and conduct experiments to evaluate their performance. Experiment results show significant improvement of our new methods in analysis precision and efficiency.

The charging and discharging procedure of a battery is a typical electrochemical process, which can be modeled as a dynamic system. State of charge (SoC) is a commonly used measure to quantify the charge stored in the battery in relation to its full capacity. Recent efforts of optimizing battery performance require more accurate SoC information. The noise in sensor readings makes the estimation even more challenging, especially in battery-operated systems where the supply voltage of the sensor keeps changing. Traditionally used methods of Coulomb counting and extended Kalman filter suffer from the accumulation of noise and common phenomenon of biased noise, respectively. The traditional approach of dealing with ever-increasing demand for accuracy is to develop more complicated and sophisticated solutions, which generally require special models. A key challenge in the adoption of such systems is the inherent requirement of specialized knowledge and hit-and-trial-based tuning. In this paper, we explore a new dimension from the perspective of a self-tuning algorithm, which can provide accurate SoC estimation without error accumulation by creating a negative feedback loop and enhancing its strength to penalize the estimation error. Specifically, we propose a novel method, which uses a battery model and a conservative filter with a strong feedback, which guarantees that worst-case amplification of noise is minimized. We capitalize on the battery model for data fusion of current and voltage signals for SoC estimation. To compute the best parameters, we formulate the linear matrix inequality conditions, which are optimally solved using open-source tools. This approach also features a low computational expense during estimation, which can be used in real-time applications. Thorough mathematical proofs, as well as detailed experimental results, are provided, which highlight the advantages of the proposed method over traditional techniques.

Real-time task models have evolved from periodic models to more sophisticated graph-based ones like the Digraph Real Time task model (DRT) to specify branching and loop structures of real-time embedded software. For independent DRT tasks, efficient techniques for schedulability analysis have been developed in previous work. In this paper, we extend the DRT model to specify inter-task synchronization through a rendezvous mechanism. We present an abstraction technique for static priority schedulability analysis of the corresponding tasks. Our experiments show that, despite the high computational complexity of the problem, the proposed technique scales very well for large sets of dependent tasks.

Real-time task graphs are used to describe complex real-time systems with non-cyclic timing behaviors. The workload of such systems are typically bursty, which may degrade their schedulability even with sufficient resource in the long term. In this paper, we propose to use task graph transformation to improve system schedulability. The idea is to insert artificial delays to the release times of certain vertices of a task graph to get a new graph with a smoother workload, while still meeting the timing constraints of the original task graph. Delaying the release time of a vertex may smoothen the workload of some paths of the task graph, but at the same time make the workload of other paths even more bursty. We developed efficient techniques to search for an appropriate release time delay for each vertex. Experiments with randomly generated task systems show that the proposed transformation method can make a significant number of task systems that was originally unschedulable to become schedulable, and the transformation procedure is very efficient and can easily handle large-scale task graph systems in very short computation time.

Real-time systems are shifting from single-core to multi-core processors, on which software must be parallelized to fully utilize the additional computation power. Recently different types of scheduling algorithms and analysis techniques have been proposed for parallel real-time tasks modeled as directed acyclic graphs (DAG). However, this field is still much less mature than traditional real-time scheduling of sequential tasks. In this paper, we study the decomposition-based scheduling for parallel real-time tasks, where a task graph is transferred to a set of independent sporadic tasks. In particular, we proposed a new decomposition strategy that better explores the feature of each task, represented by its structure characteristic value, to improve schedulability. The structure characteristic values do not only provide a clear guidance in task decomposition, but also can be directly used for schedulability tests, as well as to quantify the suboptimality of our scheduling algorithm in terms of capacity augmentation bounds. We conduct comprehensive experiments to evaluate the real-time performance of our proposed scheduling algorithm, against the state-of-the-art scheduling and analysis methods of different types. Experiment results show that our method consistently outperforms all of the previous methods under different parameter settings.

This paper studies real-time scheduling of mixed-criticality systems where low-criticality tasks are still guaranteed some service in the high-criticality mode, with reduced execution budgets. First, we present a utilization-based schedulability test for such systems under EDF-VD scheduling. Second, we quantify the suboptimality of EDF-VD (with our test condition) in terms of speedup factors. In general, the speedup factor is a function with respect to the ratio between the amount of resource required by different types of tasks in different criticality modes, and reaches 4/3 in the worst case. Furthermore, we show that the proposed utilization-based schedulability test and speedup factor results apply to the elastic mixed-criticality model as well. Experiments show effectiveness of our proposed method and confirm the theoretical suboptimality results.

In the formal analysis of real-time systems, modeling of branching codes and modeling of intratask parallelism structures are two of the most important research topics. These two real-time properties are combined, resulting in the fork-join real-time task (FJRT) model, which extends the digraph-based task model with forking and joining semantics. We prove that the EDF schedulability problem on a preemptive uniprocessor for the FJRT model is coNP-hard in the strong sense, even if the utilization of the task system is bounded by a constant strictly less than 1. Then, we show that the problem becomes tractable with some slight structural restrictions on parallel sections, for which we propose an exact schedulability test with pseudo-polynomial time complexity. Our results thus establish a borderline between the tractable and intractable FJRT models.

The analysis of global multiprocessor scheduling is more difficult than its uniprocessor counterpart. Due to the unknown critical instant, existing techniques use over-approximations of task interference for efficient yet pessimistic analysis. In this paper, we proposed a new technique to improve the precision of interference estimation. The key is to identify and resolve contradicting assumptions made in the analysis procedure. The resulting new analysis method improves the analysis precision at the price of a higher complexity. Then we introduce techniques to optimize the new method for better efficiency. Experiments with randomly generated task sets are conducted to evaluate both the precision and efficiency of the proposed new method.

This paper studies the performance analysis problem of energy-harvesting real-time network systems in the Real-Time Calculus (RTC) framework. The behavior of an energy-harvesting node turns out to be a generalization of two known components in RTC: it behaves like an AND connector if the capacitor used to temporally store surplus energy has unlimited capacity and there is no energy loss, while it behaves like a greedy processing component (GPC) if the size of the capacitor is zero and thus surplus energy is lost or passed to other nodes immediately. In this paper, methods are developed to analyze the worst-case performance, in terms of delay and backlog, of energy-harvesting nodes as well as compute upper/lower bounds of their data and energy outputs. Moreover, with the proposed analysis methods, we disclose some interesting properties of the worst-case behaviors of energy-harvesting systems, which provide useful information to guide system design. Experiments are conducted to evaluate our theoretical contributions and also confirm that the disclosed properties are not just the result of our analysis, but indeed hold in realistic system behaviors.

Recently there is a growing interest of incorporating cellular architecture (with wired base stations and last-hop wireless connections) into fieldbuses to support mobile real-time applications. A promising trend is that such cellular fieldbuses will go multichannel multiradio, due to the wide availability of cheap multichannel commercial-off-the-shelf (COTS) wireless nodes, and the rise of 4G and future cellular technologies. For multichannel multiradio cellular fieldbuses, per-flow real-time schedulability guarantee in the inter-cell level has not yet been well studied. Particularly, unlike 3G cellular networks, which use static FDMA/CDMA to isolate cells, the multichannel multiradio feature allows neighboring cells to use the same radio frequency channel at different time-slots, or the same time-slot at different radio frequency channels. How to carry out channel time-slot scheduling is therefore the focus of this paper. To address this issue, we propose a greedy scheduling algorithm, together with a polynomial time closed-form schedulability test. The relationship between the schedulability test result, greedy scheduling schedulability, and schedulability is explored. We prove the equivalence of the three for chained cellular fieldbus topology, a typical topology with broad applications. This also implies the optimality of greedy scheduling, and the sufficiency and necessity of the schedulability test in the context of chained topology. To demonstrate and validate these schedulability theories, we carry out a case study on a classic admission planning problem. The schedulability test not only serves as a planning constraint, but also guides us to propose an approximation algorithm to solve the NP-hard admission planning problem. Comparisons to exhaustive search corroborate the validity of our schedulability theories.

Scheduling mixed-criticality systems that integrate multiple functionalities with different criticality levels into a shared platform appears to be a challenging problem, even on single-processor platforms. Multi-core processors are more and more widely used in embedded systems, which provide great computing capacities for such mixed-criticality systems. In this paper, we propose a partitioned scheduling algorithm MPVD to extend the state-of-the-art single-processor mixed-criticality scheduling algorithm EY to multiprocessor platforms. The key idea of MPVD is to evenly allocate tasks with different criticality levels to different processors, in order to better explore the asymmetry between different criticality levels and improve the system schedulability. Then we propose two enhancements to further improve the schedulability of MPVD. Experiments with randomly generated task sets show significant performance improvement of our proposed approach over existing algorithms.

Response Time Analysis (RTA) is one of the key problems in real-time system design. This paper proposes new RTA methods for EDF scheduling, with general system models where workload and resource availability are represented by request/demand bound functions and supply bound functions. The main idea is to derive response time upper bounds by lower-bounding the slack times. We first present a simple over-approximate RTA method, which lower bounds the slack time by measuring the “horizontal distance” between the demand bound function and the supply bound function. Then we present an exact RTA method based on the above idea but eliminating the pessimism in the first analysis. This new exact RTA method, not only allows to precisely analyze more general system models than existing EDF RTA techniques, but also significantly improves analysis efficiency. Experiments are conducted to show efficiency improvement of our new RTA technique, and tradeoffs between the analysis precision and efficiency of the two methods in this paper are discussed.

A recent trend in the theory of real-time scheduling is to consider generalizations of the classical periodic task model. Work on the associated schedulability and feasibility problems has resulted in algorithms that run efficiently and provide exact results. While these analyses give black-and-white answers about whether timing constraints are being met or not, response-time analysis adds a quantitative dimension. This brings new challenges for models more expressive than the classical periodic task model. An exact quantification of response time is difficult because of non-deterministic task behavior and a lack of combinable task-local worst cases. Therefore, previous approaches all make a trade-off between efficiency and precision, resulting in either prohibitively slow analysis run-times or imprecise over-approximate results. In this paper, we show that analysis can be both exact and efficient at the same time. We develop novel response-time characterizations to which we apply combinatorial abstraction refinement. Our algorithms for static-priority and EDF scheduling give exact results and are shown to be efficient for typical problem sizes. We advance the state-of-the-art by providing the first exact response-time analysis framework for graph-based task models.

The design and implementation of caches on a given platform has significant impacts to many areas in computer system design. On chip-multiprocessors (CMP), new cache architectures are proposed to meet the rapidly increasing performance requirements. However, the cache architectures are usually not well-documented for commercial processors. This raises difficulties for people to precisely understand the working principle of many components of the processors, not only the cache itself, but also the related components like the whole memory subsystem. This paper aims at disclosing the working principle of the last level cache of Intel Ivy Bridge processors. First, we identify the address translation logic on this cache. Second, we disclose the replacement policy of the cache. This is a dynamic insertion replacement policy, which is very different from the widely used LRU policy and its variants. Although this replacement policy has been proposed in academic literatures, our work is the first one showing it is actually used in commercial processors. To show the significance of our discovery, we design a methodology to generate controllable cache miss sequences under this new cache, and apply it to the design of a benchmark to model the memory concurrency. Evaluations on physical machines are conducted to show the effectiveness of the proposed method.

Virtualization techniques are gaining significant interests in embedded real-time system design. However, existing virtualization platforms lack strong performance isolation among virtual machines. In this work we propose a method to monitor and control the shared memory accesses of individual virtual machines on multi-core processors with Xen hypervisor, to enhance the performance isolation among virtual machines and improve the timing predictability of real-time applications. Experiments with the SPEC2006 benchmark programs are conducted to validate the proposed method.

Most mixed-criticality scheduling algorithms have the problem of service interruption for low-critical tasks, which has prompted several recent studies on providing various service guarantees for such tasks. In this paper, focusing on dual-criticality systems, we explore the best achievable service guarantees for low-critical tasks in different running modes and investigate their trade-offs. Specifically, the Elastic Mixed-Criticality (E-MC) task model is first extended to allow each low-critical task to have a pair of small and large periods, which represent its service guarantees in the low and high running modes, respectively. To improve system schedulability under a mode-switch EDF scheduler, virtual deadlines for high-critical tasks are also incorporated. Then, we develop new demand bound functions (DBFs) following a unified approach and analyze the corresponding schedulability conditions. The service guarantees for low-critical tasks are explored via the adjustment of their paired periods. We show that, compared to the state-of-the-art solution, the proposed schedulability test derived from the refined DBFs can accommodate smaller periods and thus achieve better service guarantees for low-critical tasks. Moreover, there are some interesting trade-offs between the service guarantees and a few guidelines are attained for properly specifying them.

We address the problem of schedulability analysis for a set of sporadic tasks with arbitrary deadlines running on a multiprocessor system with global fixed-priority preemptive scheduling.

The response time analysis problem is intractable for most existing real-time task models, except the simplest ones. Exact solutions for this problem in general have exponential complexity, and may run into scalability problems for large-scale task systems. In this paper, we study approximate analysis for static-priority scheduling of the Digraph Real-Time task model, which is a generalization of most existing graph-based real-time task models. We present two approximate analysis methods RBF and IBF, both of which have pseudo-polynomial complexity. We quantitatively evaluate their analysis precision using the metric speedup factor. We prove that RBF has a speedup factor of 2, and this is tight even for dual-task systems. The speedup factor of IBF is an increasing function with respect to k, the number of interfering tasks. This function converges to 2 as k approaches infinity and equals 1 when k = 1, implying that the IBF analysis is exact for dual-task systems. We also conduct simulation experiments to evaluate the precision and efficiency of RBF and IBF with randomly generated task sets. Results show that the proposed approximate analysis methods have very high efficiency with low precision loss.

A large class of embedded systems is distinguished from general-purpose computing systems by the need to satisfy strict requirements on timing, often under constraints on available resources. Predictable system design is concerned with the challenge of building systems for which timing requirements can be guaranteed a priori . Perhaps paradoxically, this problem has become more difficult by the introduction of performance-enhancing architectural elements, such as caches, pipelines, and multithreading, which introduce a large degree of uncertainty and make guarantees harder to provide. The intention of this article is to summarize the current state of the art in research concerning how to build predictable yet performant systems. We suggest precise definitions for the concept of “predictability”, and present predictability concerns at different abstraction levels in embedded system design. First, we consider timing predictability of processor instruction sets. Thereafter, we consider how programming languages can be equipped with predictable timing semantics, covering both a language-based approach using the synchronous programming paradigm, as well as an environment that provides timing semantics for a mainstream programming language (in this case C). We present techniques for achieving timing predictability on multicores. Finally, we discuss how to handle predictability at the level of networked embedded systems where randomly occurring errors must be considered.

Most previous work on cache analysis for WCET estimation assumes a particular replacement policy called LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very unpredictable. However, most commercial processors are actually equipped with these non-LRU policies, since they are more efficient in terms of hardware cost, power consumption and thermal output, while still maintaining almost as good average-case performance as LRU. In this work, we study the analysis of MRU, a non-LRU replacement policy employed in mainstream processor architectures like Intel Nehalem. Our work shows that the predictability of MRU has been significantly underestimated before, mainly because the existing cache analysis techniques and metrics do not match MRU well. As our main technical contribution, we propose a new cache hit/miss classification, k -Miss, to better capture the MRU behavior, and develop formal conditions and efficient techniques to decide k -Miss memory accesses. A remarkable feature of our analysis is that the k -Miss classifications under MRU are derived by the analysis result of the same program under LRU. Therefore, our approach inherits the advantages in efficiency and precision of the state-of-the-art LRU analysis techniques based on abstract interpretation. Experiments with instruction caches show that our proposed MRU analysis has both good precision and high efficiency, and the obtained estimated WCET is rather close to (typically 1%∼8% more than) that obtained by the state-of-the-art LRU analysis, which indicates that MRU is also a good candidate for cache replacement policies in real-time systems.

Although most previous work in cache analysis for WCET estimation assumes the LRU replacement policy, in practise more processors use simpler non-LRU policies for lower cost, power consumption and thermal output. This paper focuses on the analysis of FIFO, one of the most widely used cache replacement policies. Previous analysis techniques for FIFO caches are based on the same framework as for LRU caches using qualitative always-hit/always-miss classifications. This approach, though works well for LRU caches, is not suitable to analyze FIFO and usually leads to poor WCET estimation quality. In this paper, we propose a quantitative approach for FIFO cache analysis. Roughly speaking, the proposed quantitative analysis derives an upper bound on the “miss ratio” of an instruction (set), which can better capture the FIFO cache behavior and support more accurate WCET estimations. Experiments with benchmarks show that our proposed quantitative FIFO analysis can drastically improve the WCET estimation accuracy over pervious techniques (the average overestimation ratio is reduced from around 70% to 10% under typical setting).

Scheduling mixed-criticality systems is a challenging problem. Recently a number of new techniques are developed to schedule such systems, among which an approach called OCBP has shown interesting properties and drawn considerable attentions. OCBP explores the job-level priority order in a very flexible manner to drastically improve the system schedulability. However, the job priority exploration in OCBP involves nontrivial overheads. In this work, we propose a new algorithm LPA (Lazy Priority Adjustment) based on the OCBP approach, which improves the state-of-the-art OCBP-based scheduling algorithm PLRS in both schedulability and run-time efficiency. Firstly, while the time-complexity of PLRS' online priority management is quadratic, our new algorithm LPA has linear time-complexity at run-time. Secondly, we present an approach to calculate tighter upper bounds of the busy period size, and thereby can greatly reduce the run-time space requirement. Thirdly, the tighter busy period size bounds also improve the schedulability in terms of acceptance ratio. Experiments with synthetic workloads show improvements of LPA in all the above three aspects.

Real-Time Calculus (RTC) is a powerful framework to analyze real-time performance of distributed embedded systems. However, RTC may run into serious analysis efficiency problems when applied to systems of large scale and/or with complex timing parameter characteristics. The main reason is that many RTC operations generate curves with periods equal to the hyper-period of the input curves. Therefore, the analysis in RTC has exponential complexity. In practise the curve periods may explode rapidly when several components are serially connected, which leads to low analysis efficiency. In this work, we propose Finitary RTC to solve the above problem. Finitary RTC only maintains and operates on a limited part of each curve that is relevant to the final analysis results, which results in pseudo-polynomial computational complexity. Experiments show that Finitary RTC can drastically improve the analysis efficiency over the original RTC. The original RTC may take hours or even days to analyze systems with complex timing characteristics, but Finitary RTC typically can complete the analysis in seconds. Even for simple systems, Finitary RTC also typically speeds up the analysis procedure by hundreds of times. While getting better efficiency, Finitary RTC does not introduce any extra pessimism, i.e., it yields analysis results as precise as the original RTC.

Future embedded real-time systems will be deployed on multi-core processors to meet the dramatically increasing high-performance and low-power requirements. This trend appeals to generalize established results on uniprocessor scheduling, particularly the various utilization bounds for schedulability test used in system design, to the multiprocessor setting. Recently, this has been achieved for the famous Liu and Lay land utilization bound by applying novel task splitting techniques. However, parametric utilization bounds that can guarantee higher utilizations (up to 100%) for common classes of systems are not yet known to be generalizable to multiprocessors as well. In this paper, we solve this problem for most parametric utilization bounds by proposing new task partitioning algorithms based on exact response time analysis. In addition to the worst-case guarantees, as the exact response time analysis is used for task partitioning, our algorithms significantly improve average-case utilization over previous work.

Most previous work in cache analysis for WCET estimation assumes a particular replacement policy called LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very "unpredictable". However, most commercial processors are actually equipped with these non-LRU policies, since they are more efficient in terms of hardware cost, power consumption and thermal output, but still maintaining almost as good average-case performance as LRU. In this work, we study the analysis of MRU, a non-LRU replacement policy employed in mainstream processor architectures like Intel Nehalem. Our work shows that the predictability of MRU has been significantly underestimated before, mainly because the existing cache analysis techniques and metrics, originally designed for LRU, do not match MRU well. As our main technical contribution, we propose a new cache hit/miss classification, k-Miss, to better capture the MRU behavior, and develop formal conditions and efficient techniques to decide the k-Miss memory accesses. A remarkable feature of our analysis is that the k-Miss classifications under MRU are derived by the analysis result of the same program under LRU. Therefore, our approach inherits all the advantages in efficiency, precision and composability of the state-of-the-art LRU analysis techniques based on abstract interpretation. Experiments with benchmarks show that the estimated WCET by our proposed MRU analysis is rather close to (5% # 20% more than) that obtained by the state-of-the-art LRU analysis, which indicates that MRU is also a good candidate for the cache replacement policy in real-time systems.

Previous works on real-time task graph models have ignored the crucial resource sharing problem. Due to the non-deterministic branching behavior, resource sharing in graph-based task models is significantly more difficult than in the simple periodic or sporadic task models. In this work we address this problem with several different scheduling strategies, and quantitatively evaluate their performance. We first show that a direct application of the well-known EDF+SRP strategy to graph-based task models leads to an unbounded speedup factor. By slightly modifying EDF+SRP, we obtain a new scheduling strategy, called EDF+saSRP, which has a speedup factor of 2. Then we propose a novel resource sharing protocol, called ACP, to better manage resource sharing in the presence of branching structures. The scheduling strategy EDF+ACP, which applies ACP to EDF, can achieve a speedup factor of 1.618, the golden ratio.

In formal analysis of real-time systems, a major concern is the analysis efficiency. As the expressiveness of models grows, so grows the complexity of their analysis. A recently proposed model, the digraph real-time task model (DRT), offers high expressiveness well beyond traditional periodic task models. Still, the associated feasibility problem on preemptive uniprocessors remains tractable. It is an open question to what extent the expressiveness of the model can be further increased before the feasibility problem becomes intractable. In this paper, we study that tractability border. We show that system models with the need for global timing constraints make feasibility analysis intractable. However, our second technical result shows that it remains tractable if the number of global constraints is bounded by a constant. Thus, this paper establishes a precise borderline between tractability and intractability.

Models for real-time systems have to balance the inherently contradicting goals of expressiveness and analysis efficiency. Current task models with tractable feasibility tests have limited expressiveness, restricting their ability to model many systems accurately. In particular, they are all recurrent, preventing the modeling of structures like mode switches, local loops, etc. In this paper, we advance the state-of-the-art with a model that is free from these constraints. Our proposed task model is based on arbitrary directed graphs (digraphs) for job releases. We show that the feasibility problem on preemptive uniprocessors for our model remains tractable. This even holds in the case of task systems with arbitrary deadlines.

Networks-on-Chip (NoC) has been introduced to offer high on-chip communication bandwidth for large scale multi-core systems. However, the communication bandwidth between NoC chips and off-chip memories is relatively low, which seriously limits the overall system performance. So optimizing the off-chip memory communication efficiency is a crucial issue in the NoC system design flow. In this paper, we present a memory access aware mapping algorithm for NoC, which explores SDRAM access parallelization in order to offer higher off-chip memory communication efficiency, and eventually achieve higher overall system performance. To the best of our knowledge, this is the first work to consider off-chip memory communication efficiency in application mapping on NoC. Experimental results showed that, comparing with classical NoC mapping algorithms, our algorithm can significantly improve the memory utilization and overall system throughput (on average 60% improvement).

An increasing trend in embedded system design is to integrate components with different levels of criticality into a shared hardware platform for better cost and power efficiency. Such mixed-criticality systems are subject to certifications at different levels of rigorousness, for validating the correctness of different subsystems on various confidence levels. The real-time scheduling of certifiable mixed-criticality systems has been recognized to be a challenging problem, where using traditional scheduling techniques may result in unacceptable resource waste. In this paper we present an algorithm called PLRS to schedule certifiable mixed-criticality sporadic tasks systems. PLRS uses fixed-job-priority scheduling, and assigns job priorities by exploring and balancing the asymmetric effects between the workload on different criticality levels. Comparing with the state-of-the-art algorithm by Li and Baruah for such systems, which we refer to as LB, PLRS is both more effective and more efficient: (i) The schedulability test of PLRS not only theoretically dominates, but also on average significantly outperforms LB's. (ii) The run-time complexity of PLRS is polynomial (quadratic in the number of tasks), which is much more efficient than the pseudo-polynomial run-time complexity of LB.

Liu and Layland discovered the famous utilization bound for fixed-priority scheduling on single processor systems in the 1970's. Since then, it has been a long standing open problem to find fixed-priority scheduling algorithms with the same bound for multiprocessor systems. In this paper, we present a partitioning-based fixed-priority multiprocessor scheduling algorithm with Liu and Layland's utilization bound.

It is predicted that multicores will be increasingly used in future embedded real-time systems for high performance and low energy consumption. The major obstacle is that we may not predict and provide any guarantee on real-time properties of software on such platforms. The shared memory bus is among the most critical resources, which severely degrade the timing predictability of multicore software due to the access contention between cores. In this paper, we study a multicore architecture where each core has a local L1 cache and all cores use a shared bus to access the off-chip memory. We use Abstract Interpretation (AI) to analyze the local cache behavior of a program running on a dedicated core. Based on the cache analysis, we construct a Timed Automaton (TA) to model when the programs access the memory bus. Then we model the shared bus also using timed automata. The TA models for the bus and programs will be explored using the UPPAAL model checker to find the WECTs for the respective programs. Based on the presented techniques, we have developed a tool for multicore timing analysis, which allows automatic generation of the TA models from binary code and WCET estimation for any given TA model of the shared bus. Extensive experiments have been conducted, showing that the combined approach can significantly tighten the estimations. As examples, we have studied the TDMA and FCFS buses, of which the WCET bounds can be tightened by up to 240% and 82% respectively, compared with the worst-case bounds estimated based on worst-case bus access delay.

Synchronous dataflow (SDF) is a well-known model of computation for dataflow-oriented applications such as embedded systems for signal processing and multimedia. It is important to minimize the buffer size requirements of applications generated from SDF graphs, since memory space is often a scarce resource in these systems due to cost or power consumption constraints. Some authors have proposed to use model-checking for finding the minimum buffer size requirements, but the scalability of model-checking is limited by state space explosion. In this paper, we present several techniques for reducing state space size and improving scalability of model-checking by exploiting problem-specific properties of SDF graphs.

The major obstacle to use multicores for real-time applications is that we may not predict and provide any guarantee on real-time properties of embedded software on such platforms; the way of handling the on-chip shared resources such as L2 cache may have a significant impact on the timing predictability. In this paper, we propose to use cache space isolation techniques to avoid cache contention for hard real-time tasks running on multicores with shared caches. We present a scheduling strategy for real-time tasks with both timing and cache space constraints, which allows each task to use a fixed number of cache partitions, and makes sure that at any time a cache partition is occupied by at most one running task. In this way, the cache spaces of tasks are isolated at run-time.

Recently, there have been several promising techniques developed for schedulability analysis and response time analysis for multiprocessor systems based on over-approximation. This paper contains two contributions. First, to improve the analysis precision, we apply Baruah's window analysis framework to response time analysis for poradic tasks on multiprocessor systems where the deadlines of tasks are within their periods. The crucial observation is that for global fixed priority scheduling, a response time bound of each task can be efficiently estimated by fixed-point computation without enumerating all the busy window sizes as in for schedulability analysis. The technique is proven to dominate theoretically state-of-the-art techniques for response time analysis for multiprocessor systems. Our experiments also show that the technique results in significant performance improvement compared with several existing techniques for multiprocessor schedulability analysis. As the second main contribution of this paper, we extend the proposed technique to task systems with arbitrary deadlines, allowing tasks to have deadlines beyond the end of their periods. This is a non-trivial extension even for single-processor systems. To our best knowledge, this is the first work of response time analysis for multiprocessor systems in this setting, which involves sophisticated techniques for the characterization and computation of response time bounds.

Static path analysis is a key process of Worst Case Execution Time (WCET) estimation, the objective of which is to find the execution path that has the largest execution time. Currently, there is an argument in the research community whether model checking is another good solution for WCET analysis, besides ILP. To our knowledge, no paper so far has addressed this argument with real performance data. In this paper, we implement both ILP and model checking for static path analysis of WCET, and the experiment results show that ILP yields very good performance, while model checking only works well for simple programs, and it is inclined to scalability problems when dealing with programs that have complex structures and large loop counts.

As Moore's law comes to an end, multi-processor (MP) systems are becoming increasingly important in embedded systems design, hence real-time schedulability analysis for MP systems has become an important research topic. In this paper, we present an exact method for schedulability analysis of global multiprocessor scheduling with either fixed-priority (FP) or earliest-deadline-first (EDF) algorithms using the model-checker NuSMV. Compared to safe but pessimistic schedulability tests based on processor utilization bounds, model-checking can provide an exact answer to the schedulability of a taskset, as well as quantitative information on each task's best-case and worst- case response times.

We study the schedulability analysis problem for nonpreemptive scheduling algorithms on multiprocessors. To our best knowledge, the only known work on this problem is the test condition proposed by Baruah for non-preemptive EDF scheduling, which will reject a task set with arbitrarily low utilization if it contains a task whose execution time is equal or greater than the minimal relative deadline among all tasks. In this paper, we firstly derive a linear-time test condition which avoids the problem mentioned above, by building upon previous work for preemptive multiprocessor scheduling. This test condition works on not only non-preemptive EDF, but also any other work-conserving non-preemptive scheduling algorithms. Then we improve the analysis and present test conditions of pseudo-polynomial time-complexity for Non-preemptive Earliest Deadline First scheduling and Non-preemptive Fixed Priority scheduling respectively. Experiments with randomly generated task sets show that our proposed test conditions, especially the improved test conditions, have significant performance improvements compared with [BAR-EDFnp].

Field Programmable Gate Arrays (FPGAs) are very popular in today's embedded systems design, and Partial Runtime-Reconfigurable (PRTR) FPGAs allow HW tasks to be placed and removed dynamically at runtime. Hardware task scheduling on PRTR FPGAs brings many challenging issues to traditional real-time scheduling theory, which have not been adequately addressed by the research community compared to software task scheduling on CPUs. In this article, we consider the schedulability analysis problem of HW task scheduling on PRPR FPGAs. We derive utilization bounds for several variants of global preemptive/nonpreemptive EDF scheduling, and compare the performance of different utilization bound tests.

Reconfigurable devices, such as field programmable gate arrays (FPGAs), are very popular in today's embedded systems design due to their low-cost, high-performance and flexibility. Partially runtime-reconfigurable (PRTR) FPGAs allow hardware tasks to be placed and removed dynamically at runtime. Hardware task scheduling on PRTR FPGAs brings many challenging issues to traditional real-time scheduling theory, which have not been adequately addressed by the research community compared to software task scheduling on CPUs. In this paper, we consider the schedulability analysis problem of HW task scheduling on PRPR FPGAs. We derive utilization bound tests for two variants of global EDF scheduling, and use synthetic tasksets to compare performance of the tests to existing work and simulation results.

In this paper, we address the problem of static scheduling and software synthesis for dataflow graphs with the symbolic model-checker NuSMV using a two-step process: first use model-checking to obtain a static schedule with the objective of minimizing the data buffer size, then synthesize efficient code from the static schedule with the objective of minimizing code size and performance overheads due to runtime dynamic decisions. We show the effectiveness of these techniques using a number of digital signal processing examples.