Adversarial patch attacks inject localized perturbations into images to mislead deep vision models. These attacks can be physically deployed, posing serious risks to real-world applications. In this paper, we propose CertMask, a certifiably robust defense that constructs a provably sufficient set of binary masks to neutralize patch effects with strong theoretical guarantees. While the state-of-the-art approach (PatchCleanser) requires two rounds of masking and incurs O(n^2) inference cost, CertMask performs only a single round of masking with O(n) time complexity, where n is the cardinality of the mask set to cover an input image. Our proposed mask set is computed using a mathematically rigorous coverage strategy that ensures each possible patch location is covered at least k times, providing both efficiency and robustness. We offer a theoretical analysis of the coverage condition and prove its sufficiency for certification. Experiments on ImageNet, ImageNette, and CIFAR-10 show that CertMask improves certified robust accuracy by up to +13.4% over PatchCleanser, while maintaining clean accuracy nearly identical to the vanilla model.

Sensor fusion algorithms combine data from multiple sensors to produce more accurate and reliable results. However, temporal misalignment between sensors, caused by factors such as clock drift, jitter or networking delays, can significantly degrade fusion quality. Prior work on modeling temporal misalignment in sensor fusion algorithms assumes that in the ideal case all samples should be aligned with the same reference time point. We show that this assumption limits its applicability when samples are intentionally taken at different time points, e.g., when a single sensor is sampled multiple times or when sensors operate at different frequencies. In this paper, we introduce alignment sets, which allow system designers to explicitly specify the intended alignment between samples. This flexibility enables more precise temporal misalignment measures that better reflect the actual requirements of sensor fusion scenarios. We prove that alignment sets generalize the prior definitions of temporal misalignment of sensor fusion algorithms. We also provide an evaluation on a camera-LiDAR fusion pipeline for 3D object detection, showing that alignment sets provide more accurate misalignment measures and robustness estimates.

Cyber-physical systems typically have non-functional tasks to infrequently take care of some hardware and software components for maintaining correct functionality. For example, infrequently, sensors must be calibrated and endurance-limited memories must be wear-leveled. We study how a real-time system, consisting of care-taking tasks and sporadic real-time tasks, can be optimized and analyzed. We introduce a novel model to describe such systems and show how to intuitively utilize existing real-time scheduling theory to guarantee timeliness in this scenario. This is, however, very pessimistic since the care-taking tasks are executed infrequently, compared to the sporadic tasks utilizing the same components. We, therefore, examine how to properly handle care-taking tasks by controlling when to release them to avoid unnecessary interference spikes by proposing a low-overhead care-taking-task releaser. We demonstrate the improvements of schedulability using synthetic benchmarks, supported by an implementation for the proposed care-taking-task releaser in FreeRTOS and a case study for non-volatile memory.

Abstract Recent advances in large language model (LLM) pruning have shown state-of-the-art (SotA) compression results in post-training and retraining-free settings while maintaining high predictive performance. However, previous research mainly considered calibrating based on English text, despite the multilingual nature of modern LLMs and their frequent use in non-English languages. This analysis paper conducts an in-depth investigation of the performance and internal representation changes associated with pruning multilingual language models for monolingual applications. We present the first comprehensive empirical study, comparing different calibration languages for pruning multilingual models across diverse languages, tasks, models, and SotA pruning techniques. We further analyze the latent subspaces, pruning masks, and individual neurons within pruned models. Our results reveal that while calibration on the target language effectively retains perplexity and yields high signal-to-noise ratios, it does not consistently improve downstream task performance. Further analysis of internal representations at three different levels highlights broader limitations of current pruning approaches: While they effectively preserve dominant information like language-specific features, this is insufficient to counteract the loss of nuanced, language-agnostic features that are crucial for knowledge retention and reasoning.

Ensuring predictable and deterministic behavior in distributed cyber-physical systems (CPS) is essential for guaranteeing safety, reliability, and real-time behavior. However, achieving this predictability is challenging due to network uncertainties, asynchronous execution, and complex timing interactions.

NVMe SSDs offer unprecedented capacity and bandwidth and upcoming PCIe standards promise even more. However, the underlying technology, NAND memory, already struggles with significant heat and power consumption challenges. Just like microprocessors before, NAND also experiences Dark Silicon, preventing performance from improving at the same pace as capacity. Much of the power (and thus heat) within a NAND chip results from transferring data at a high rate, another symptom of a compute-centric style of processing. Therefore, we argue for data-centric Processing-in-NAND (PiN). However, PiN comes with significant challenges, such as limited capabilities and the need to cope with bit-flip errors. Even beyond Processing-in-Memory (PiM), databases may soon have to accept that memory is not error-free, an assumption that comes at a significant cost in power, capacity and performance. Our discussion indicates that no PiN design will serve as a singular, universally applicable solution to the limit of bandwidth scaling. Instead, successful integration into database architecture requires carefully identifying PiN-compatible functionality and abstractions, and cooperation with other innovations, such as Computational Storage and CXL. Lastly, we analyze the fundamental error tolerance of Bloom filters and binary sketches as PiM-compatible data structures, which we believe may be of independent interest.

We present a post-hoc approach for scenario-based testing of automated driving systems, enabling the analysis of safety and correctness for (cooperative) automated driving systems in many scenarios without conducting tests for individual scenarios. The system under test is operated in its physical environment’ and data is recorded during operation. Then, driving scenarios are identified in this data and functional requirements are checked, yielding pass or fail verdicts for individual scenarios. We validate the envisioned post-hoc approach in a single-case mechanism experiment by the example of a platooning controller, identifying a previously unknown bug in the tested system, as well as a functional insufficiency concerning the intended operational design domain.

The immense model sizes of large language models (LLMs) challenge deployment on memory-limited consumer GPUs. Although model compression and parameter offloading are common strategies to address memory limitations, compression can degrade quality, and offloading maintains quality but suffers from slow inference. Speculative decoding presents a promising avenue to accelerate parameter offloading, utilizing a fast draft model to propose multiple draft tokens, which are then verified by the target LLM in parallel with a single forward pass. This method reduces the time-consuming data transfers in forward passes that involve offloaded weight transfers. Existing methods often rely on pretrained weights of the same family, but require additional training to align with custom-trained models. Moreover, approaches that involve draft model training usually yield only modest speedups. This limitation arises from insufficient alignment with the target model, preventing higher token acceptance lengths. To address these challenges and achieve greater speedups, we propose SubSpec, a plug-and-play method to accelerate parameter offloading that is lossless and training-free. SubSpec constructs a highly aligned draft model by generating low-bit quantized substitute layers from offloaded target LLM portions. Additionally, our method shares the remaining GPU-resident layers and the KV-Cache, further reducing memory overhead and enhance alignment. SubSpec achieves a high average acceptance length, delivering 9.1$\times$ speedup for Qwen2.5 7B on MT-Bench (8GB VRAM limit) and an average of 12.5$\times$ speedup for Qwen2.5 32B on popular generation benchmarks (24GB VRAM limit).

Self-suspension behavior happens when a job has to wait for some activity to complete and results in substantial schedulability degradation in real-time systems. Despite extensive studies for self-suspending real-time task systems, the state of the art has barely addressed the optimality of the scheduling algorithms, especially for tasks with dynamic self-suspension. In this paper, we explore optimal priority assignment for periodic real-time tasks with dynamic self-suspension under Task-level Fixed-Priority (T-FP) scheduling. To that end, we provide exact schedulability tests for frame-based and synchronous harmonic tasks. We show that the Suspension-Aware Deadline-Monotonic (SADM) priority assignment is an optimal fixed-priority scheduler for many scenarios. Further, for cases where SADM is not optimal, we adopt Audsley's Optimal Priority Assignment (OPA) approach to derive an optimal fixedpriority assignment. Evaluation results show that the exact tests outperform state-of-the-art schedulability tests from the literature, and that optimal priority assignments significantly improve schedulability over classical priority assignments.

The Robot Operating System 2 (ROS 2) is a widely used middleware that provides software libraries and tools for developing robotic systems. In these systems, tasks are scheduled by ROS 2 executors. Since the scheduling behavior of the default ROS 2 executor is inherently different from classical real-time scheduling theory, dedicated analyses or alternative executors requiring substantial changes to ROS 2 have been developed. In 2023, the events executor was introduced into ROS 2. It features an events queue and allows the possibility to make scheduling decisions immediately after a job is completed. In this paper, we show that with minor modifications of the events executor, a large body of research results from classical real-time scheduling theory becomes directly applicable to ROS 2. This enables analytical bounds on the worst-case response time and the end-to-end latency, outperforming bounds for the default ROS 2 executor in many scenarios. Our solution is easy to integrate into existing ROS 2 systems since it requires only minor modifications of the events executor, which is natively included in ROS 2. The evaluation results show that our ROS 2 events executor with minor modifications can have significant improvement in terms of dropped jobs, worst-case response time, end-to-end latency, and performance compared to the default ROS 2 executor.

While preemptive Earliest-Deadline-First (EDF) has been studied extensively in real-time systems, there are only few results when considering tasks with dynamic self-suspension behavior scheduled under EDF. Furthermore, all schedulability tests that have been developed in this context are based on analyzing specific intervals, hindering the performance of the analytical tightness of the result. In this work, we develop a schedulability test for EDF, built on a dynamic interval extension. That is, whenever the analysis cannot derive a decision to conclude the schedulability test, we iteratively extend the analysis interval to include additional carry-in jobs into the analysis. This is achieved by specifying execution-exceedance requirement for infeasibility of the system, i.e., by specifying how much workload must be accumulated within a certain time interval to achieve a deadline miss. Our approach outperforms all previous analyses and is the first to surpass the schedulability guarantees that can be provided for Deadline-Monotonic (DM) scheduling for dynamic self-suspending tasks, hence achieving a milestone in the analysis of EDF scheduling.

Abstract We propose two complementary research directions, “Time for ML” and “ML for Time”, that we believe to be critical for the deployment of machine-learning (ML) applications in time-sensitive applications. “Time for ML” refers to ML systems that are aware of and can adapt to dynamic time constraints regarding their execution, while “ML for Time” refers to ML systems that are aware of and can deal with data’s temporal aspects, such as misalignment. We believe these two directions are complementary and can be combined to provide more robust and reliable machine learning systems.

No abstract available.

We study a graph partition problem where the input is a directed acyclic graph (DAG) representing tasks as vertices and dependencies between tasks as arcs. The goal is to assign the tasks to k heterogeneous machines in a way that minimizes the total energy consumed for completing the tasks. We first show that the problem is NP -hard. Then, we present polynomial-time algorithms for two special cases: one where there are only two machines, and another where the input DAG is a directed path. Finally, we examine a variant where there are only two machines, with one capable of executing a limited number of tasks, and demonstrate that this special case remains computationally hard.

In many applications of cyber-physical systems, a sequence of tasks is necessary to perform a certain functionality. For example, from a sensor to an actuator, the first task reads the sensor value (cause), the second task processes the data, and the third task produces an output for the actuator (an effect is triggered). For such scenarios, the end-to-end timing properties (the so-called end-to-end latency) of the sequence of tasks (the so-called cause-effect chain) are of importance. This tutorial recaps different metrics for the end-to-end latency of cause-effect chains, and summarizes fundamental properties and existing analytical results in a systematic manner. To that end, this tutorial has a special focus on the reaction time (how fast can a reaction be in the worst case) and the data age (how old is the data source of an actuation in the worst case). The goal of this tutorial is to provide a systematic view of the fundamental end-to-end timing properties of cause-effect chains and offer an outlook of possible research directions in the near future. Furthermore, we extend the proof of one fundamental property in the literature to comply with the current state-of-the-art definition of end-to-end latencies.

Releasing jobs and performing scheduling decisions in real-time operating systems (RTOSes) is often realized within tick interrupts. In each tick interrupt, a set of tasks that are waiting to release new jobs, namely, the waiting set, is inspected to determine the jobs that should be released at this tick. Such a waiting set is sorted whenever a job has finished, by which the release process can be efficiently achieved. However, the overhead of sorting can vary vastly depending on the task set, which has to be taken into account in the worst-case timing analysis. Moreover, the tick interrupt in common practices is backed by a single hardware timer that is configured to trigger interrupts, either with a fixed period or reconfigured to the next release time (so-called one-shot timer). Since not necessarily at every interrupt a job will be released, several tick interrupts might be redundant. For the one-shot timers, the reconfiguration during runtime also incurs overheads at a variable interval. To reduce such variability and amount of overhead, in this work, we propose LazyTick which partitions the task set and distributes the subsets over multiple timers. Specifically, we propose two job release procedures with constant operations overhead—one for harmonic task sets and one for non-harmonic task sets. We implemented the support for multiple hardware timers in FreeRTOS and conducted intensive experimental evaluations. The evaluation shows that LazyTick can reduce the variability in overhead by up to ≈ 5 × in peak and ≈ 3× on average in comparison to the default implementation. Additionally, the combined overhead of the job release process is reduced by up to ≈ 6.1 × in peak and ≈ 3.6× on average.

To design performant, expressive, and reliable cyber-physical systems (CPSs), researchers extensively perform quasi-static scheduling for concurrent models of computation (MoCs) on multi-core hardware. However, these quasi-static scheduling approaches are developed independently for their corresponding MoCs, despite commonality in the approaches. To help generalize the use of quasi-static scheduling to new and emerging MoCs, this article proposes a unified approach for a class of deterministic timed concurrent models (DTCMs), including prominent models such as synchronous dataflow (SDF), Boolean-controlled dataflow (BDF), scenario-aware dataflow (SADF), and Logical Execution Time (LET). In contrast to scheduling techniques tailored exclusively to specific MoCs, our unified approach leverages a common intermediate formalism called state space finite automata (SSFA), bridging the gap between high-level MoCs and executable schedules. Once identified as DTCMs, new MoCs can directly adopt SSFA-based scheduling, significantly easing adoption. We show that quasi-static schedules facilitated by SSFA are provably free from timing anomalies and enable straightforward worst-case makespan analysis. We demonstrate the approach using the reactor model—an emerging discrete-event MoC—programmed using the Lingua Franca ( LF ) language. Experiments show that quasi-statically scheduled LF programs exhibit lower runtime overhead compared to the dynamically scheduled LF programs, and that the analyzable worst-case makespans enable compile-time deadline checking.

We introduce and study transfer schedulability , a novel concept that describes how properties of a reference schedule derived from a scheduling algorithm \(\mathcal {A}\) are transferred onto another scheduling algorithm \(\mathcal {B}\) for a given task system and fixed arrival times. Specifically, we say schedulability is transferred from \(\mathcal {A}\) to \(\mathcal {B}\) if the task set is schedulable under \(\mathcal {B}\) whenever all deadlines are met in the reference schedule produced by \(\mathcal {A}\) . We identify a sufficient criterion for schedulability to be transferred on uniprocessor systems, which we verify with the Rocq proof assistant, and based on this criterion develop runtime mechanisms that enforce transfer schedulability. We relate transfer schedulability to prior approaches from the literature and demonstrate how the concept can be utilized to avoid timing anomalies and lower runtime scheduling overheads. We demonstrate that transfer schedulability can be utilized to prevent timing anomalies for non-preemptive scheduling, self-suspending tasks, and directed acyclic graph (DAG) tasks where the edges induce delays. Our evaluation on synthesized task sets shows improved schedulability compared to standard scheduling algorithms. We also evaluated the number of interventions necessary to transfer schedulability, and additionally demonstrate that the proposed runtime mechanisms eliminate timing anomalies (like a completely static, fully table-driven approach) while achieving a response-time distribution closely resembling those of classic dynamic, event-driven schedulers like EDF.

In many machine learning applications, e.g., tree-based ensembles, floating point numbers are extensively utilized due to their expressiveness. Even if floating point hardware is present in general computing systems, using integer operations instead of floating point operations promises to reduce operation overheads and improve the performance. In this paper, we provide FLInt, a full precision floating point comparison for random forests, by only using integer and logic operations. The usage of FLInt basically boils down to a one-by-one replacement of conditions: For instance, a comparison statement in C: if(pX [3]<=(float)10.074347) becomes if ((*(((int*) (pX)) +3)) <= ((int) (0×41213087))). Experimental evaluation on X86 and ARMv8 desktop and server class systems shows that the execution time can be reduced by up to ≈ 30% with our novel approach.

With the rapid development of the Internet of Things, machine learning applications on edge devices with limited resources face challenges due to large data scales and irregular memory access patterns. Non-volatile memory (NVM) technologies provide promising solutions by offering larger capacity, low leakage power, and data persistence. In this paper, we discuss the potential of NVM technology in enhancing machine learning applications by improving energy efficiency and reducing latency through in-memory computation and different NVM write modes. The insights from this analysis provide valuable guidance to device researchers and system architects working to develop highperformance systems for machine learning and accelerators in large-scale search applications using NVMs.

Arising popularity for resource-efficient machine learning models makes random forests and decision trees famous models in recent years. Naturally, these models are tuned, optimized, and transformed to feature maximally low-resource consumption. A subset of these strategies targets the model structure and model logic and therefore induces a trade-off between resource-efficiency and prediction performance. An orthogonal set of approaches targets hardware-specific optimizations, which can improve performance without changing the behavior of the model. Since such hardware-specific optimizations are usually hardware-dependent and inflexible in their realizations, this paper envisions a more general application of such optimization strategies at the level of programming languages. We therefore discuss a set of suitable optimization strategies first in general and envision their application in LLVM IR, i.e. a flexible and hardware-independent ecosystem.

Sensor fusion is the process of combining data from multiple sensors for acquiring a more accurate and comprehensive understanding of the observed environment. However, temporal misalignments between sensors can lead to incorrect fusion results, while the temporal robustness of sensor fusion algorithms is still a relatively unexplored research topic. To address this gap, we define three types of temporal robustness for sensor fusion: reference-point-based, strong sample-point-based, and weak sample-point-based temporal robustness. These definitions provide a framework to quantitatively evaluate the temporal robustness of sensor fusion functions. We also investigate the case where only a part of the sensors are misaligned. Furthermore, we consider potential probabilistic aspects for the proposed definitions. We assess the temporal robustness of a state-of-the-art fusion method in the context of 3D object detection, where camera and LiDAR data are fused. Our empirical evaluation shows that the examined fusion methods exhibit moderate robustness against temporal misalignment of images, but are especially sensitive to LiDAR misalignment. Our findings call attention to the necessity of providing robustness guarantees for sensor fusion functions against temporal misalignment.

In many modern safety-critical cyber-physical sys-tems, such as in the automotive or robotic domain, the appli-cation complexity requires the use of multi-core platforms to execute all workloads under strict hard real-time constraints. The sporadic DAG task model is a parallel task model adept at representing tasks comprised of subtasks, which possess internal data flow and precedence constraints induced by synchronization. A significant challenge to the system's performance and its real-time verification stems from the communication-centric nature of applications in these domains. Inter-core communication, required for data sharing among sub tasks across different cores, depends on either a shared bus or a network-on-chip, culminating in significant overhead due to latency, congestion, and synchronization. To improve performance and reduce these overheads, it is advantageous to execute subtasks, those that either exchange large volumes of data or access the same data, on a singular physical processor, thereby utilizing more efficient intra-core communication. In this paper, we tackle this issue by introducing the DAG task model with execution groups, incorporating a constraint that mandates the execution of grouped sub tasks on the same pro-cessor. We provide an analysis of worst-case response times and propose optimizations for our DAG task model with execution groups, subsequently evaluating our approach against existing solutions. The evaluation results demonstrate that our approach, even with the imposition of group execution constraints, remains competitive in comparison to existing approaches that do not take group execution constraints into account. Additionally, we explore implementation strategies and potential extensions for multi-task systems.

Modern robot systems, like autonomous vehicles, are complex, distributed systems that consist of many interacting components. End-to-end timing latency guarantees are key properties of such systems. They upper bound the data processing time and provide a predictable timing behavior. The Robot Operating System 2 (ROS 2) is a widely used and highly configurable set of software libraries for creating and deploying robot systems. It features a custom scheduler to execute time-triggered and event-triggered tasks and uses Data Distribution Services (DDS) for the communication between different system components. The data propagations between ROS 2 system components form cause-effect chains, which can be analyzed to determine the maximum reaction time (longest time between occurrence of an external cause and the earliest time when this external cause is fully processed) and maximum data age (longest time between the moment of a sensor measurement and the latest moment where an effect is based on this sensor measurement). In this paper, we provide an analysis of the end-to-end latencies in multi-executor ROS 2 systems to upper bound the end-to-end latencies of cause-effect chains in ROS 2 systems. Furthermore, we introduce an optimization using constrained programming that determines the optimal system configuration to minimize the end-to-end latencies for ROS 2 systems. We evaluate our upper-bound analysis to determine the end-to-end latencies of cause-effect chains in an autonomous driving-software stack for oval racing used in the Indy Autonomous Challenge and apply our optimization method to reduce the end-to-end latency upper bound, measured maximum, and measured mean by up to 50.2 %, 19.8 %, and 7.2 %, respectively.

Real-time tasks often exhibit correlated execution-time distributions due to common factors such as shared caches, resources, and inputs. Yet state-of-the-art probabilistic analysis still overlooks the impact of correlation, a gap that has been highlighted as a major open problem in the field. This paper responds to the open problem with the first correlation-aware analysis (CAA) of periodic tasks with stochastic execution times. The proposed analysis, which derives response-time distributions to infer upper bounds on deadline-failure probabilities, applies to a novel task model that incorporates information about both intra- and inter-task dependencies. In addition, the paper shows how to statistically infer the two model parameters using confidence intervals obtained via nonparametric bootstrapping. Notably, the inference method described is distribution-agnostic, meaning that it does not assume any particular probability distribution a priori, thereby eliminating a major risk of misclassifying the ground-truth execution behavior. By design, CAA dominates state-of-the-art correlation-tolerant analysis (CTA). The significantly better accuracy of CAA is demonstrated via experiments with synthetically generated workloads, while a case study based on the WATERS’ 17 industrial challenge provides a proof-of-concept of the statistical inference method.

The robot operating system 2 (ROS 2) is a widely used collection of tools and libraries for building robot applications. It is designed to be flexible and easy to use when creating complex robot systems with many interacting components.Since its alpha version release in 2015, ROS 2 provides two options in a multithreading operating system, namely the single-threaded executor and the multithreaded executor. The single-threaded executor is starvation-free by design (i.e., every task is eventually executed) even in over-utilized systems, since the set of eligible task instances (called wait set) is only refilled once all the task instances in the wait set are executed. The multithreaded executor extends this mechanism to multiple threads that manage the wait set collaboratively. While intuitively this extension preserves the starvation-free property, and analyses for the multithreaded executor even build upon this assumption, the multithreaded executor has not been shown to be starvation-free.In this work, we examine the mechanism of the multithreaded executor in ROS 2 and demonstrate that it is prone to starvation, i.e., some tasks may never be executed even in under-utilized systems. This indicates risks for multithreaded executors in the current ROS 2 design and further leads to counterexamples to the state-of-the-art response-time analyses by Jiang et al. (RTSS 2022) and Sobhani et al. (RTAS 2023). We propose a minimal change in the software architecture of the ROS 2 multithreaded executor to enable starvation- and deadlock-free behavior. We empirically test that we prevent starvation in concrete ROS 2 system configurations, and show that our solution incurs a negligible overhead using the autoware reference benchmark. Moreover, we prove that our solution is starvation- and deadlock-free using formal proofs and model checking.

Cyber-Physical Systems (CPS) are increasingly pervasive in modern society due to their growing use in many complex applications of our everyday life, such as autonomous delivery drones and medical robotics. These systems, interacting with the environment, are often mission- or safety-critical systems and must therefore satisfy strict dependability requirements. Such requirements include reliability, maintainability, and availability goals, but also specific constraints, including performance, power, energy, or timing. It is arguably crucial for safety-critical CPS to provide dependability against faults incurred by mobile and dynamic physical environments, which is very challenging, especially if fault tolerance is provided at the cost of time and computation. Hardware is getting more and more complex and the semiconductor scaling is pushing towards the smallest size possible, both with the goal to increase the available computational power. These two trends, in addition to the employment of emerging technologies, like non-volatile memory, increase the reliability threats. Safety-critical hardware struggles to provide sufficient computational capabilities to modern applications, which often need to resort to Commercial Off-The-Shelf (COTS) components rather than specialized and faulttolerant hardware. Hence, the use of COTS is leading to a shift from fault-tolerance to fault-resilience: the hardware is no longer considered capable of tolerating any fault, thus modern systems need to be designed, at hardware and software levels, in a way that are able to self-recover from errors. Novel techniques, solutions, algorithms, and tools are thus needed to tackle the design and development of CPS that needs to guarantee dependability and safety. This special issue offers substantial contributions in several fields, with the goal of improving their resilience against faults. To accommodate the numerous submissions, this special issue is divided into two parts. Part I includes 8 papers published in this issue, while the remaining papers will be featured in Part II, which will appear in a subsequent issue.

This paper explores the challenges and opportunities of integrating non-volatile memories (NVMs) into embedded systems for machine learning. NVMs offer advantages such as increased memory density, lower power consumption, non-volatility, and compute-in-memory capabilities. The paper focuses on integrating NVMs into embedded systems, particularly in intermittent computing, where systems operate during periods of available energy. NVM technologies bring persistence closer to the CPU core, enabling efficient designs for energy-constrained scenarios. Next, computation in resistive NVMs is explored, highlighting its potential for accelerating machine learning algorithms. However, challenges related to reliability and device non-idealities need to be addressed. The paper also discusses memory-centric machine learning, leveraging NVMs to overcome the memory wall challenge. By optimizing memory layouts and utilizing probabilistic decision tree execution and neural network sparsity, NVM-based systems can improve cache behavior and reduce unnecessary computations. In conclusion, the paper emphasizes the need for further research and optimization for the widespread adoption of NVMs in embedded systems presenting relevant challenges, especially for machine learning applications.

This lightning talk introduces the motivations of the needs of formal properties that can be used modularly to compose safe and tight analysis and optimization for the scheduler design and schedulability test problems for cyber-physical real-time systems. The key challenge is the correct and precise translation from different schedule functions to proper mathematical properties that can be further used for property-based modulable designs.

The rise of in-memory databases and systems with considerably large memories and cache sizes requires the rethinking of the proper implementation of index structures like B+-trees in such systems. While disk block-sized nodes and binary search were considered as good in the past, smaller node sizes and cache-friendly linear search within nodes can be noticeably more performant nowadays. Considering the probabilistic distribution of lookup values to the B+-tree as part of a memory-friendly and cache-aware layout is a consequent next step, which is studied in this paper. Favoring frequently visited nodes and paths in the regard of cache hits can improve the overall performance of the tree and, thus, of the entire database system. We provide such an optimized B+-tree layout, which takes the probabilistic distribution of the lookup values as a basis. Experimental evaluation shows that choosing rather small node sizes in combination with our optimization algorithm can improve the performance by up to in comparison to a default baseline.

In the near future, smart cities are expected to become more prevalent, with Uncrewed Aerial Vehicles (UAVs) playing a key role in making cities more efficient and sustainable. Effective path planning is essential for the safe and efficient integration of drones into urban airspace. However, one potential limitation of UAVs is that they may not have sufficient computing power to perform real-time contingency planning when encountering obstacles. To address this challenge, this work proposes edge-assisted offloading scenarios where contingency planning is considered as a resource-intensive task that can be offloaded to nearby edge nodes. We implemented and compared various strategies for generating offloading plans in a robot swarm simulator based on latency and cost metrics. Our evaluation revealed that the offloading plans generated using the genetic algorithm tended to perform better in terms of average latency or cost per offloading, albeit with higher runtime overhead compared to the other strategies.

Neural processing units (NPUs) have become indispensable for meeting the high computational demands of deep neural networks (DNNs). They provide a very efficient solution, thanks to having a huge MAC array that enables massive parallelism. Nevertheless, such an architecture exhibits excessive on-chip power densities leading to a localized hot-spot that seriously heats its surroundings. This work demonstrates how the on-chip temperatures induced by the MAC array create a spatial thermal gradient through the on-chip SRAM memory. This makes the memory regions sensitive to different error probabilities (Perror), leading to significant accuracy drops when DNNs are being executed. To surmount this challenge, we employ on-chip superlattice thermoelectric (TEC) cooling devices that effectively reduce the memory temperature. Although scaling the memory voltage makes SRAM cells more sensitive to errors, it significantly decreases the leakage power, which compensates for the power consumed by the incorporated TEC devices. Furthermore, operating the SRAM at a lower voltage and temperature substantially increases its lifetime because voltage and temperature are key stimuli of transistor aging. By running multi-physics simulations using commercial finite-element tools and SPICE simulations for the 14nm FinFET technology, we accurately derive the relation between the Perror in different memory regions and the corresponding cooling cost. We then propose a three-stage temperature-aware layer-wise memory mapping that exploits different degrees of the sensitivity of NN layers to errors towards maximizing the DNN accuracy while minimizing the cooling cost. Experimental results reveal that our method notably improves the DNN accuracy compared to existing temperature-oblivious memory mapping.

Timing guarantee is an important aspect and must be ensured for every individual task in real-time systems. Even for periodic tasks, providing timing guarantees for segmented self-suspending tasks is challenging due to timing anomalies, i.e., the reduction of execution or suspension time of some jobs enlarges the response time of another job. The existing worstcase response time analyses for sporadic self-suspending tasks are only over-approximations and lead to overly pessimistic results. In this paper, we focus on eliminating timing anomalies without negative impacts on the worst-case response time (WCRT) analysis when scheduling periodic tasks with segmented selfsuspension behavior. We propose two treatments, segment release time enforcement and segmentpriority modification, and prove that both treatments eliminate timing anomalies. In our evaluation, the proposed treatments achieve higher acceptance ratios in terms of schedulability compared to state-of-the-art scheduling algorithms. We also implement the segment-level fixed-priority scheduling mechanism on RTEMS, and showcase the validity of the treatment segment priority modification.

Safety-critical systems are often subjected to transient faults. Since these transient faults may lead to soft errors that cause catastrophic consequences, error-handling must be addressed by design. Full-protection against faults is too costly in terms of resource usage. A common approach to relax the resource demands and limit the impact of errors is to consider (m, k)-constraints, which requires that at least m jobs out of any k consecutive jobs are error-free. To assure (m, k)-compliance, static patterns are widely used to select the job execution modes, i.e., either in an error-free mode at the cost of increased worst-case execution time or in an error-prone mode with the advantage of less execution time. Although static patterns have been shown to be effective in energy-aware designs, resource over-provision is inevitable due to the relatively low rate of error probability. In this work, we propose two dynamic (and adaptive) approaches that allow the scheduler to opportunistically select execution modes based on the error-history of the past jobs and the actual error probability. We firstly propose a Markov chain based solution if the error-probability is known and static and secondly a reinforcement learning-based approach that can handle unknown error probabilities. Experimental evaluations show that our approaches outperform the state-of-the-art in most of the evaluated cases in terms of average utilization for each task and the overall utilization for multitask systems.

Self-suspension introduces further complexity in the scheduling of real-time tasks. As a result, the proofs of optimality for the typical Earliest-Deadline-First (EDF) and Deadline-Monotonic (DM) scheduling do not hold. The EDF-Like scheduling algorithms allows to optimize the scheduling algorithm by setting relative priority points. In this work, we show that a tuning process of the relative priority points leads to significantly better (analytical) schedulability guarantees. Moreover, we discuss open problems and alternative approaches.

ROS 2 is a framework consisting of software libraries for developing robot systems, such as autonomous driving systems, that consist of multiple interacting components. In ROS 2, each component is implemented as a node, which contains time-triggered and event-triggered tasks. These tasks communicate with each other via ROS 2 topics or shared memory, and are scheduled by a ROS 2 executor. In ROS 2 systems, the system configuration and callback execution can have a significant impact on system performance, including end-to-end latencies, message loss, and memory usage. In this paper, we provide a bound on the timer period of ROS 2 timers to prevent sensor undersampling, and a subscription buffer size limit to prevent message loss and minimize memory usage. Furthermore, we explain the occurrence of message loss and high end-to-end latencies in ROS 2 systems, which are caused by the system configuration and subscription buffer size choice. Based on our observations, we propose a callback-prioritization heuristic to reduce end-to-end latencies and subscription buffer sizes. We demonstrate our findings using case studies based on Autoware.Universe and provide further evaluation to highlight the benefits of our heuristic.

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.

By taking inspiration from the operation of biological brains, emerging brain-inspired hardware has the potential to revolutionize the way computations are performed. Brain-inspired computing can be realized using both classical CMOS and emerging beyond-CMOS technologies, whereas the latter holds the promise to provide substantial energy savings akin to the employment of non-volatile memories. One way to implement highly efficient brain-inspired AI applications is through analog computing schemes, such as Integrate-and-Fire (IF) Spiking Neural Networks (SNNs), which can be implemented using both CMOS and beyond-CMOS technologies as synaptic storage. However, managing the inherent degradation of computing accuracy in analog circuits and mitigating their effects on the predictive accuracy of AI systems remains a key challenge due to the inherent nature of analog computing.In this paper, we discuss how the aforementioned challenges can be addressed. In the first part, we present our SPICE-Torch, a framework that connects low-level SPICE simulations of circuits and memories performing analog computations with high-level accuracy evaluations of NN models based on PyTorch. Furthermore, we present an example of neuromorphic optimization using classical CMOS technology. In the second part, we introduce memristors as an emerging beyond-CMOS technology that can retain their state without any outside influence and are well-suited for brain-inspired neuromorphic hardware. We demonstrate that brain-inspired hardware, realized using classical CMOS or beyond-CMOS technologies, has the potential to revolutionize the way we process information and solve complex computation problems. Nevertheless, to harness its full potential, reliability issues have to be managed carefully and HW/SW codesign is key. Our presented framework SPICE-Torch, which connects low-level SPICE simulations of circuits performing analog computations with high-level accuracy evaluations of NN models based on PyTorch is available as open-source in https://github.com/myay/SPICE-Torch.

Modern low power distributed systems tend to integrate machine learning algorithms. In resource-constrained setups, the execution of the models has to be optimized for performance and energy consumption. Racetrack memory (RTM) promises to achieve these goals by offering unprecedented integration density, smaller access latency, and reduced energy consumption. However, to access data in RTM, it needs to beshiftedto theaccess portfirst. We investigate decision trees and develop placement strategies to reduce the total number of shifts in RTM. Decision trees allow profiling during training, resulting in tree paths' access probabilities. We map tree nodes to RTM so that the total number of shifts is minimal. Concretely, we present two different placement approaches: 1) where tree nodes are closely packed and placeduniformlyin a single RTM location and 2) where decision tree nodes aredecomposedto separate RTM blocks. We discuss theoretical cost models for both approaches, we formally prove an upper bound of$4\times$for the unified and an upper bound of$12\times$for the decomposed organization towards the optimal placement. We conduct a thorough experimental evaluation to compare our algorithms to the state-of-the-art placement strategies Our experimental evaluations show that theunifiedanddecomposedsolutions reduce the number of shifts by$58.1\%$and$80.1\%$, respectively, leading to a$53.8\%$and$46.3\%$reduction in the overall runtime and$52.6\%$and$61.7\%$reduction in the energy consumption, compared to a naive baseline.

To utilize the performance benefits of heterogeneous multicore platforms in real-time systems, we need task models that expose the parallelism and heterogeneity of the workload, such as typed DAG tasks, as well as scheduling algorithms that effectively exploit this information. In this paper, we introducetype-aware federated schedulingalgorithms for sporadic typed DAG tasks with implicit deadlines running on a heterogeneous multicore platform with two different types of cores. In type-aware federated scheduling, a task can be executed in one of the three strategies:Exclusive Allocation,Semi-Exclusive Allocation, andSequential and Share. InExclusive Allocation, clusters of cores of both core types are exclusively allocated to tasks, while cores of only one type are exclusively allocated to tasks inSemi-Exclusive Allocation. The workload of the other type from tasks inSemi-Exclusive Allocationand the workload from tasks inSequential and Shareshare the cores that are not exclusively allocated to any task. We prove that our type-aware federated scheduling algorithm has a capacity augmentation bound of 7.25. We also show that no constant capacity augmentation bound can be obtained withoutSemi-Exclusive Allocation. Compared to the state of the art, the type-aware federated scheduling algorithm achieves better schedulability, especially for task sets with skewed workload.

Increasing performance needs of modern cyber-physical systems leads to multiprocessor architectures being increasingly utilized. To efficiently exploit their potential parallelism in hard real-time systems, appropriate task models and scheduling algorithms that allow to provide timing guarantees are required. Such scheduling algorithms and the corresponding worst-case response time analyses usually suffer from resource over-provisioning due to pessimistic analyses based on worst-case assumptions. Hence, scheduling algorithms and analyses with high resource efficiency are required. A prominent fine-grained parallel task model is the directed-acyclic-graph (DAG) task model that is composed of precedence constrained subjobs. This paper studies the hierarchical real-time scheduling problem of sporadic arbitrary-deadline DAG tasks. We propose a parallel path progression scheduling property that is implemented with only two distinct subtask priorities, which allows to quantify the parallel execution of a user chosen collection of complete paths in the response time analysis. This novel approach significantly improves the state-of-the-art response time analyses for parallel DAG tasks for highly parallel DAG structures and can provably exhaust large core numbers. Two hierarchical scheduling algorithms are designed based on this property, extending the parallel path progression properties and improve the response time analysis for sporadic arbitrary-deadline DAG task sets.

Emerging non-volatile memory yields, alongside many advantages, technical shortcomings, such as reduced cell lifetime. Although many wear-leveling approaches exist to extend the lifetime of such memories, usually a trade-off for the granularity of wear-leveling has to be made. Due to iterative write schemes (repeatedly sense and write), wear-out of memory in certain systems is directly dependent on the written bit value and thus can be highly imbalanced, requiring dedicated bit-wise wear-leveling. Such a bit-wise wear-leveling so far has only be proposed together with a special hardware support. However, if no dedicated hardware solutions are available, especially for commercial off-the-shelf systems with non-volatile memories, a software solution can be crucial for the system lifetime. In this work, we propose entirely software-based bit-wise wearleveling, where the position of bits within CPU words in main memory is rotated on a regular basis. We leverage the LLVM intermediate representation to adjust load and store operations of the application with a custom compiler pass. Experimental evaluation shows that the lifetime by applying local rotation within the CPU word can be extended by a factor of up to 21×. We also show that our method can incorporate with coarser-grained wear-leveling, e.g. on block granularity and assist achievement of higher lifetime improvements.

Solving constraint satisfaction problems (CSPs) is in high demand for various applications. SNN serves as a competitive annealing machine that can solve the CSP more efficiently than well-known Metropolis sampling and Hopfield networks. NVM-based crossbars with analog Integrate and Fire (IF) neurons can evolve the state of SNN to solve CSP more efficiently. However, analog computations inherently suffer from imprecisions in NVM cells, e.g., current variation, OFF-state leakage, and temperature-induced drift. We are the first to analyze the impacts of various memory technologies, including 2T-NOR, FeFET, WOx ReRAM, and HfOx ReRAM, on solving the Ising model, Sudoku, and Traveling-salesman-problem (TSP). The results show that both 2T-NOR Flash and FeFET with normalized standard deviation( ${\sigma}/{u}$ ) $<$ $5\%$ and ON-OFF ratio $>$ $1000$ are both ideal candidates as synapse devices at room temperature, while other devices suffer from the effects of current variation and OFF-state leakage, which would require the neuron circuits to have infeasible membrane capacitance size. However, the drift of cell current and the reduction of the ON-OFF ratio drops the success rate as the temperature increases. The success rate of solving TSP drops by 60 $\%$ and 90 $\%$ while the temperature increases from 300K to 358K for 2T-NOR and FeFET, respectively. Throughout the simulation, we show that the transistor-based memory is suggested to be a synapse device. Yet, we also find that the tolerance of temperature is inevitable under limited capacitance. Exploration of temperature-tolerated design of circuit and memory design is still in demand for future works.

Real-time systems require the formal guarantee of timing constraints, not only for the individual tasks but also for the end-to-end latency of data flows. The data flow among multiple tasks, e.g., from sensors to actuators, is described by a cause-effect chain, independent from the priority order of the tasks. In this article, we provide an end-to-end timing-analysis for cause-effect chains on asynchronized distributed systems with periodic task activations, considering the maximum reaction time (MRT) (i.e., the duration of data processing) and the maximum data age (MDA) (i.e., the worst-case data freshness). We first provide an analysis of the end-to-end latency on one local electronic control unit (ECU) that has to consider only the jobs in a bounded time interval. We extend our analysis to globally asynchronized systems by exploiting a compositional property to combine the local results. Throughout synthesized data based on an automotive benchmark as well as on randomized parameters, we show that our analytical results improve the state-of-the-art.

In many embedded systems, for instance, in the automotive, avionic, or robotics domain, critical functionalities are implemented via chains of communicating recurrent tasks. To ensure safety and correctness of such systems, guarantees on the reaction time, that is, the delay between a cause (e.g., an external activity or reading of a sensor) and the corresponding effect, must be provided. Current approaches focus on the maximum reaction time, considering the worst-case system behavior. However, in many scenarios, probabilistic guarantees on the reaction time are sufficient. That is, it is sufficient to provide a guarantee that the reaction does not exceed a certain threshold with (at least) a certain probability. This work provides such probabilistic guarantees on the reaction time, considering two types of randomness: response time randomness and failure probabilities. To the best of our knowledge, this is the first work that defines and analyzes probabilistic reaction time for cause-effect chains based on sporadic tasks.

No abstract available.

Resistive memory-based computing-in-memory (CIM) has been considered as a promising solution to accelerate convolutional neural networks (CNN) inference, which stores the weights in crossbar memory arrays and performs in-situ matrix-vector multiplications (MVMs) in an analog manner. Several techniques assume that a whole crossbar can operate concurrently and discuss how to efficiently map the weights onto crossbar arrays. However, in practice, the accumulated effect of per-cell current deviation and Analog-to-Digital-Converter overhead may greatly degrade inference accuracy, which motivates the concept of Operation Unit (OU), by which an operation per cycle in a crossbar only involve limited wordlines and bitlines to preserve satisfactory inference accuracy. With OU-based operations, the mapping of weights and scheduling strategy for parallelizing CNN convolution operations should take the cost of communication overhead and resource utilization into consideration to optimize the inference acceleration. In this work, we propose the first optimization framework named SPATEM, that efficiently executes MVMs with OU-based operations on ReRAM-based CIM accelerators. It decouples the design space into tractable steps, models the expected inference latency, and derives an optimized spatial-temporal-aware scheduling strategy. By comparing with state-of-the-arts, the experimental result shows that the derived scheduling strategy of SPATEM achieves on average 29.24% inference latency reduction with 31.28% less communication overhead by exploiting more originally unused crossbar cells.

A visionary computing paradigm is to train resource efficient neural networks on the edge using dedicated low-power accelerators instead of cloud infrastructures, eliminating communication overheads and privacy concerns. One promising resource-efficient approach for inference is binarized neural networks (BNNs), which binarize parameters and activations. However, training BNNs remains resource demanding. State-of-the-art BNN training methods, such as the binary optimizer (Bop), require to store and update a large number of momentum values in the floating point (FP) format.

While academia favours general research that is applicable to a large class of systems, this paper highlights the necessity of research into specific scenarios and aims to increase its acceptance in the real-time systems community. We argue that such research is not only motivated by greater applicability to industry, but that specialization can also provide valuable information from a purely academic perspective. In addition, the trade-offs between generalization and specialization are examined, considering not only theoretical performance, but also the impact on essential non-functional properties that are important for industry, namely composability, robustness, extensibility, and parametric simplicity.

In the domain of embedded systems, modern SoCs (System-on-Chips) increasingly employ dedicated hardware to improve the performance of specialized tasks. The herein generated performance benefits come at the cost of increased coordination complexity of multiple tasks accessing these various hardware units in varying alternating sequences. For example, a task may first execute on a processor and then proceed execution on a GPU. This problem is even more complex in the case of real-time constraints, i.e., the execution within formally guaranteed time bounds. Real-time constraints may lead to severe resource under-utilization if the scheduling algorithms are not properly designed. A solution to this problem is self-suspension and segment-level fixed-priority scheduling. In this approach, tasks are divided into successive alternating segments of computation and self-suspension. The task may self-suspend if it tries to access a hardware resource that is already held by another task. In this paper, we propose and discuss different implementations of the segmented self-suspension task model in the FreeRTOS real-time operating system. Moreover, we evaluate the overhead of the different implementations on the OM40007 IoT-module from NXP.

In soft real-time systems, tasks may occasionally miss their deadlines. This possibility has triggered research on probabilistic timing analysis for the execution time of a single program and probabilistic response time analysis of concurrently executed tasks. Under fixed-priority preemptive uniprocessor scheduling, it was shown that the classical critical instant theorem (for deriving the worst-case schedulability or response time) by Liu and Layland (in JACM 1973) can be applied to analyze the worst-case deadline failure probability (WCDFP) and the worst-case response time exceedance probability (WCRTEP). In this work, we present a counterexample for this result, showing that the WCDFP and WCRTEP derived by the classical critical instant theorem is unsound. We further provide two sound methods: one is to account for one additional carry-in job of a higher-priority task and another is to sample and inflate the execution time of certain jobs without adding one additional carry-in job. We show that these two methods do not dominate each other and, in the evaluation, apply them to two well-known approaches based on direct convolution and Chernoff bounds.

In real-time systems, schedulability analyses provide the required timing guarantees. However, current suspension-aware analyses are limited to Task-Level Fixed-Priority (TFP) scheduling or Earliest-Deadline-First (EDF) scheduling of constrained-deadline self-suspending task systems. In this work, we provide a unifying schedulability analysis for uniprocessor Global EDF-Like (GEL) schedulers of arbitrary-deadline task sets. While analyses for EDF-Like schedulers are rare, many widely used scheduling algorithms can be considered as EDF-Like, for example, EDF, First-In-First-Out (FIFO), Earliest-Quasi-Deadline-First (EQDF), and Suspension-Aware EDF (SAEDF). Therefore, the provided analysis is applicable to those algorithms. It can be applied to TFP scheduling as well. Our analysis is the first suspension-aware schedulability analysis for arbitrary-deadline sporadic real-time task systems under Job-Level Fixed-Priority (JFP) scheduling, such as EDF, and the first unifying suspension-aware schedulability analysis framework that covers a wide range of scheduling algorithms. Through numerical simulations, we show that our analysis improves the state of the art for constrained-deadline EDF scenarios.

Modern autonomous vehicle platforms feature many interacting components and sensors, which add to the system complexity and affect their performance. A key aspect for such platforms are end-to-end timing guarantees, which are required for safe and predictable behavior in every situation. One widely used tool to develop such autonomous systems is the Robot Operating System 2 (ROS2), which allows creating robot applications composed of several components that communicate with each other to form complex systems. Furthermore, it guarantees real-time constraints and provides reliable timing behavior using a custom scheduler design that manages the execution of all components. These components and their data propagation form multiple cause-effect chains that can be analyzed to determine two key metrics: maximum reaction time (which is the maximum time for the system to react to an external input) and maximum data age (which equals the maximum time between sampling and the output of the system being based on that sample). However, an end-to-end analysis for cause-effect chains in ROS2 systems has not been provided yet. In this paper, we provide a theoretical upper bound for the end-to-end timing of a ROS2 system on a single electronic control unit (ECU). Additionally, we show how to simulate a ROS2 system to get a lower bound for the timing analysis and introduce an online end-to-end timing measurement method for existing ROS2 systems. We evaluate our methods with a basic autonomous navigation system and determine the timing behavior for different components and sensor configurations.

This special issue features research and engineering topics in the domain of real-time systems, covering efficient, robust, and practical techniques to design and optimize real-time systems.In particular, the current issue features four papers: • Profile-driven Memory Bandwidth Management for Accelerators and CPUs inQoS-enabled Platforms.• Design Optimization for Real-Time Systems with Sustainable Schedulability Analysis.• Robust and Accurate Regression-Based Techniques for Period Inference in Real-Time Systems.• A Comprehensive Survey of Industry Practice in Real-Time Systems.The first paper by Parul Sohal, Rohan Tabish, Renato Mancuso, and Ulrich Drepper deals with the performance bottleneck of the main memory subsystems when considering both CPUs and accelerators.Specifically, this paper combines classical CPU-centric bandwidth regulation techniques with state-of-the-art hardware support for memory traffic shaping via the ARM QoS extensions.This paper addresses both the technological capabilities and limitations as well as the theoretical foundations.The second paper by Yecheng Zhao, Runzhi Zhou, and Haibo Zeng considers the urgent need for efficient optimization techniques that can handle large-scale systems.By leveraging the sustainability of schedulability analysis applicable for a large class of real-time systems, this paper develops an optimization framework for the design of real-time systems.Specifically, a counterexample-guided iterative procedure is proposed to efficiently learn from an unschedulable solution.

The performance of multiprocessor synchronization and locking protocols is a key factor to utilize the computation power of multiprocessor systems under real-time constraints. While multiple protocols have been developed in the past decades, their performance highly depends on the task partition and prioritization. The recently proposed Dependency Graph Approach showed its advantages and attracted a lot of interest. It is, however, restricted to task sets where each task has at most one critical section. In this article, we remove this restriction and demonstrate how to utilize algorithms for the classical job shop scheduling problem to construct a dependency graph for tasks with multiple critical sections. To show the applicability, we discuss the implementation in$\text{LITMUS}^{\text{RT}}$and report the overheads. Moreover, we provide extensive numerical evaluations under different configurations, which in many situations show significant improvement compared to the state-of-the-art.

Ferroelectric FET (FeFET) is a highly promising emerging non-volatile memory (NVM) technology, especially for binarized neural network (BNN) inference on the low-power edge. The reliability of such devices, however, inherently depends on temperature. Hence, changes in temperature during run time manifest themselves as changes in bit error rates. In this work, we reveal the temperature-dependent bit error model of FeFET memories, evaluate its effect on BNN accuracy, and propose countermeasures. We begin on the transistor level and accurately model the impact of temperature on bit error rates of FeFET. This analysis reveals temperature-dependent asymmetric bit error rates. Afterwards, on the application level, we evaluate the impact of the temperature-dependent bit errors on the accuracy of BNNs. Under such bit errors, the BNN accuracy drops to unacceptable levels when no countermeasures are employed. We propose two countermeasures: (1) Training BNNs for bit error tolerance by injecting bit flips into the BNN data, and (2) applying a bit error rate assignment algorithm (BERA) which operates in a layer-wise manner and does not inject bit flips during training. In experiments, the BNNs, to which the countermeasures are applied to, effectively tolerate temperature-dependent bit errors for the entire range of operating temperature.

To avoid race conditions and ensure data integrity, resource synchronization protocols have been widely studied in real-time systems for decades, providing systematical policies to guarantee a bound on priority inversion-induced blocking time and the avoidance of deadlocks. However, the corresponding realization is often based on assumed abstractions and necessary adaptions in a real-time operating system, by which the theoretically proven properties of such a protocol may not be delivered, leading to potential mismatches. To prevent such mismatches, in this work, we propose to contract the obligations of involved primitives and operations, and apply the deductive verification on a corresponding implementation. To this end, we present a modularized verification framework and demonstrate its applicability by verifying the official implementation of the immediate ceiling priority protocol (ICPP) and the multiprocessor resource sharing protocol (MrsP) in RTEMS, resulting in the discovery of long-stayed mismatches for both synchronization protocols. To resolve them, we provide a possible remedy for the ICPP and an additional precondition regarding nested locking for the MrsP.

Specialized hardware accelerators beyond von-Neumann, that offer processing capability in where the data resides without moving it, become inevitable in data-centric computing. Emerging non-volatile memories, like Ferroelectric Field-Effect Transistor (FeFET), are able to build compact Logic-in-Memory (LiM). In this work, we investigate the probability of error (Perror) in FeFET-based XNOR LiM, demonstrating the new trade-off between the speed and reliability. Using our reliability model, we present how Binarized Neural Networks (BNNs) can be proactively trained in the presence of XNOR-induced errors towards obtaining robust BNNs at the design time. Furthermore, leveraging the trade-off between Perror and speed, we present a run-time adaptation technique, that selectively trades-off Perror and XNOR speed for every BNN layer. Our results demonstrate that when a small loss (e.g., 1%) in inference accuracy could be accepted, our design-time and run-time techniques provide error-resilient BNNs that exhibit 75% and 50% (FashionMNIST) and 38% and 24% (CIFAR10) XNOR speedups, respectively.

For timing-sensitive edge applications, the demand for efficient lightweight machine learning solutions has increased recently. Tree ensembles are among the state-of-the-art in many machine learning applications. While single decision trees are comparably small, an ensemble of trees can have a significant memory footprint leading to cache locality issues, which are crucial to performance in terms of execution time. In this work, we analyze memory-locality issues of the two most common realizations of decision trees, i.e., native and if-else trees. We highlight that both realizations demand a more careful memory layout to improve caching behavior and maximize performance. We adopt a probabilistic model of decision tree inference to find the best memory layout for each tree at the application layer. Further, we present an efficient heuristic to take architecture-dependent information into account thereby optimizing the given ensemble for a target computer architecture. Our code-generation framework, which is freely available on an open-source repository, produces optimized code sessions while preserving the structure and accuracy of the trees. With several real-world data sets, we evaluate the elapsed time of various tree realizations on server hardware as well as embedded systems for Intel and ARM processors. Our optimized memory layout achieves a reduction in execution time up to 75 % execution for server-class systems, and up to 70 % for embedded systems, respectively.

In-memory wear-leveling has become an important research field for emerging non-volatile main memories over the past years. Many approaches in the literature perform wear-leveling by making use of special hardware. Since most non-volatile memories only wear out from write accesses, the proposed approaches in the literature also usually try to spread write accesses widely over the entire memory space. Some non-volatile memories, however, also wear out from read accesses, because every read causes a consecutive write access. Software-based solutions only operate from the application or kernel level, where read and write accesses are realized with different instructions and semantics. Therefore different mechanisms are required to handle reads and writes on the software level. First, we design a method to approximate read and write accesses to the memory to allow aging aware coarse-grained wear-leveling in the absence of special hardware, providing the age information. Second, we provide specific solutions to resolve access hot-spots within the compiled program code (text segment) and on the application stack. In our evaluation, we estimate the cell age by counting the total amount of accesses per cell. The results show that employing all our methods improves the memory lifetime by up to a factor of 955×.

Modern distributed low power systems tend to integrate machine learning algorithms, which are directly executed on the distributed devices (on the edge). In resource constrained setups (e.g. battery driven sensor nodes), the execution of the machine learning models has to be optimized for execution time and energy consumption. Racetrack memory (RTM), an emerging non-volatile memory (NVM), promises to achieve these goals by offering unprecedented integration density, smaller access-latency and reduced energy consumption. However, in order to access data in RTM, it needs to be shifted to the access port first, resulting in latency and energy penalties. In this paper, we propose B.L.O. (Bidirectional Linear Ordering), a novel domain-specific approach for placing decision trees in RTMs. We reduce the total amount of shifts during inference by exploiting the tree structure and estimated access probabilities. We further apply the state-of-the-art methods to place data structures in RTM, without exploiting any domain-specific knowledge, to the decision trees and compare them to B. L.O. We formally prove that the B.L.O. solution has an approximation ratio of 4, i.e., its number of shifts is guaranteed to be at most 4 times the optimal number of shifts for a given decision tree. Throughout the experimental evaluation, we show that for the realistic use case B.L.O. empirically outperforms the state-of-the-art data placement method on average by 54.7% in terms of shifts, 19.2% in terms of runtime and 19.2% in terms of energy consumption.

To overcome the memory wall in neural network (NN) inference systems, recent studies have proposed to use approximate memory, in which the supply voltage and access latency parameters are tuned, for lower energy consumption and faster access at the cost of reliability. To tolerate the occuring bit errors, the state-of-the-art approaches apply bit flip injections to the NNs during training, which require high overheads and do not scale well for large NNs and high bit error rates. In this work, we focus on binarized NNs (BNNs), whose simpler structure allows better exploration of bit error tolerance metrics based on margins. We provide formal proofs to quantify the maximum number of bit flips that can be tolerated. With the proposed margin-based metrics and the well-known hinge loss for maximum margin classification in support vector machines (SVMs), we are able to construct a modified hinge loss (MHL) to train BNNs for bit error tolerance without any bit flip injections. Our experimental results indicate that the MHL enables the possibility for BNNs to tolerate higher bit error rates than with bit flip training and, therefore, allows to further lower the requirements on approximate memories used for BNNs.

Future computing platforms are facing a paradigm shift with the emerging resistive memory technologies. First, they offer fast memory accesses and data persistence in a single large-capacity device deployed on the memory bus, blurring the boundary between memory and storage. Second, they enable computing-in-memory for neuromorphic computing to mitigate costly data movements. Due to the non-ideality of these resistive memory devices at the moment, we envision that cross-layer design is essential to bring such a system into practice. In this paper, we showcase a few examples to demonstrate how cross-layer design can be developed to fully exploit the potential of resistive memories and accelerate its adoption for future computing platforms.

The goal of this special session paper is to introduce and discuss different emerging technologies for logic circuitry and memory as well as new lightweight architectures for neural networks. We demonstrate how the ever-increasing complexity in Artificial Intelligent (AI) applications, resulting in an immense increase in the computational power, necessitates inevitably employing innovations starting from the underlying devices all the way up to the architectures. Two different promising emerging technologies will be presented: (i) Negative Capacitance Field-Effect Transistor (NCFET) as a new beyond-CMOS technology with advantages for offering low power and/or higher accuracy for neural network inference. (ii) Ferroelectric FET (FeFET) as a novel non-volatile, area-efficient and ultra-low power memory device. In addition, we demonstrate how Binarized Neural Networks (BNNs) offer a promising alternative for traditional Deep Neural Networks (DNNs) due to its lightweight hardware implementation. Finally, we present the challenges from combining FeFET-based NVM with NNs and summarize our perspectives for future NNs and the vital role that emerging technologies may play.

Gang scheduling has long been adopted by the high-performance computing community as a way to reduce the synchronization overhead between related threads. It allows for several threads to execute in lock steps without suffering from long busy-wait periods or be penalized by large context-switch overheads. When combined with non-preemptive execution, gang scheduling significantly reduces the execution time of threads that work on the same data by decreasing the number of memory transactions required to load or store the data. In this work, we focus on two main types of gang tasks: rigid and moldable. A moldable gang task has a presumed known minimum and maximum number of cores on which it can be executed at runtime, while a rigid gang task always executes on the same number of cores. This work presents the first response-time analysis for non-preemptive moldable gang tasks. Our analysis is based on the notion of schedule abstraction; a new approach for response-time analysis with the promise of high accuracy. Our experiments on periodic rigid gang tasks show that our analysis is 4.9 times more successful in identifying schedulable tasks than the existing utilization-based test for rigid gang tasks.

The goal of this special session paper is to introduce and discuss different breakthrough technologies as well as novel architectures and how they together may reshape the future of Artificial Intelligent. Our aim is to provide a comprehensive overview on the latest advances in brain-inspired computing and how the latter can be realized when emerging technologies, using beyond-CMOS devices, are coupled with novel computing paradigms that go beyond von Neumann architectures. Different emerging technologies like Ferroelectric Field-Effect Transistor (FeFET), Phase Change Memory (PCM), and Resistive RAM (ReRAM) are discussed, demonstrating their promising capability in building neuromorphic computing architectures that are inspired by nature. In addition, this special session paper discusses various novel concepts such as Logic-in-Memory (LIM), Processing-in-Memory (PIM), and Spiking Neural Networks (SNNs) towards exploring the far-reaching consequences of beyond von Neumann computing on accelerating deep learning. Finally, the latest trends in brain-inspired computing are summarized into algorithm, technology, and application-driven innovations towards comparing different PIM architectures.

Spiking Neural Networks (SNNs) are considered the third generation of NNs and can reach similar accuracy as conventional deep NNs, but with a considerable improvement in efficiency. However, to achieve high accuracy, state-of-the-art SNNs employ stochastic spike coding of the inputs, requiring multiple cycles of computation. Because of this and due to the nature of analog computing, it is required to accumulate and hold the charges of multiple cycles, necessitating a large membrane capacitor. This results in high energy, long latency, and expensive area costs, constituting one of the major bottlenecks in analog SNN implementations. Membrane capacitor size determines the precision of the firing time. Hence reducing the capacitor size considerably degrades the inference accuracy. To alleviate this, we focus on bridging the gap between binarized NNs (BNNs) and SNNs. BNNs are rapidly emerging as an attractive alternative for NNs due to their high efficiency and error tolerance. In this work, we evaluate the impact of deploying error-resilient BNNs, i.e. BNNs that have been proactively trained in the presence of errors, on analog implementation of SNNs. We show that for BNNs, the capacitor size and latency can be reduced significantly compared to state-of-the-art SNNs, which employ multi-bit models. Our experiments demonstrate that when error-resilient BNNs are deployed on analog-based SNN accelerator, the size of the membrane capacitor is reduced by 50%, the inference latency is decreased by two orders of magnitude, and energy is reduced by 57% compared to the baseline 4-bit SNN implementation, under minimal accuracy cost.

Real-time systems require the formal guarantee of timing-constraints, not only for the individual tasks but also for the data-propagation paths. A cause-effect chain describes the data flow among multiple tasks, e.g., from sensors to actuators, independent from the priority order of the tasks. In this paper, we provide an end-to-end timing-analysis for cause-effect chains on asynchronized distributed systems with periodic task activations, considering the maximum reaction time (duration of data processing) and the maximum data age (worst-case data freshness). On one local electronic control unit (ECU), we present how to compute the exact local (worst-case) end-to-end latencies when the execution time of the periodic tasks is fixed. We further extend our analysis to globally asynchronized systems by combining the local results. Throughout synthesized data based on an automotive benchmark as well as on randomized parameters, we show that our analytical results improve the state-of-the-art for periodic task activations.

Multiprocessor resource synchronization and locking protocols are of great importance to utilize the computation power of multiprocessor real-time systems. Hence, in the past decades a large number of protocols have been developed and analyzed. The recently proposed dependency graph approach has significantly improved the schedulability for frame-based and periodic real-time task systems. However, the dependency graph approach only supports non-nested resource access, i.e., each critical section can only access one shared resource. In this paper, we develop a dependency graph based protocol that allows nested resource access, where a critical section can access multiple shared resources at the same time. First, constraint programming is applied to construct a dependency graph that determines the execution order of critical sections. Afterwards, a schedule is generated based on this order. To show the feasibility of our proposed protocol, we provide extensive numerical evaluations under different configurations. The evaluation results show that our approach has very good performance with respect to schedulability for frame-based and periodic real-time task systems, whereas the existing results applicable for sporadic task systems have worse performance under such a limited setting.

Probabilistic timing guarantees enable a tradeoff between system safety and hardware costs in embedded real-time systems. A key metric for assessing whether timing requirements can be satisfied with sufficiently high probability is the worst-case deadline failure probability (WCDFP). This paper studies the WCDFP under earliest-deadline first (EDF) scheduling for tasks with several probabilistic execution modes (e.g., a low-needs "typical" mode and a resource-intensive "exceptional" mode). Under EDF, no known approach can bound the WCDFP for practically sized workloads since the time complexity of prior approaches is exponential in the number of jobs.This paper examines the structure of the EDF WCDFP problem and establishes a safe, efficiently computable over-approximation by restricting the analysis to a set of specific intervals and providing a criterion to stop the derivation early without risking under-approximation. The analysis first assumes independent jobs and is then extended to handle dependencies (i.e., acyclic task chains). An evaluation shows that (i) even if 99.9999% of the jobs must meet their deadlines, a significantly higher utilization is possible than in the deterministic case, (ii) the analysis is scalable to 30 tasks with more than 1060jobs in the hyperperiod, and (iii) assuming independence in the presence of dependent tasks can severely under-estimate the WCDFP.

Numerical simulations often play an important role when evaluating and comparing the performance of schedulability tests, as they allow to empirically demonstrate their applicability using synthesized task sets under various configurations. In order to provide a fair comparison of various schedulability tests, von der Brüggen et al. presented the first version of an evaluation framework for self-suspending task sets. In this work-in-progress, we further enhance the framework by providing more features to ease the use, e.g., Python 3 support, an improved GUI, multiprocessing, Gurobi optimization, and external task evaluation. In addition, we integrate the state-of-the-arts we are aware of into the framework. Moreover, the documentation is improved significantly to simplify the application in further research and development. To the best of our knowledge, the framework contains all suspension-aware schedulability tests for uniprocessor systems and we aim to keep it up-to-date.

In real-time scheduling theory, self-suspension describes the behavior that a job can suspend itself from the ready state and thus be exempted from the scheduling for the suspension duration. This behavior makes it non-trivial to resort to established concepts such as the busy-interval analysis to self-suspending task sets which is required to analyze the worst-case response time of tasks with backlog, e.g., arbitrary-deadline task sets. In this paper, we present a novel suspension-aware busy-interval analysis for dynamic self-suspension tasks where the inter-arrival time of subsequent jobs can be bounded by an arrival curve. Based on the general analysis, we provide worst-case response time analyses and hence sufficient schedulability tests for fixed-priority preemptive uniprocessor scheduling algorithms for arrival-curve constrained and sporadic self-suspension task systems with arbitrary deadlines. Moreover, we provide evaluations based on synthetically generated task sets that show that our method indeed exploits the optimism that is introduced when enlarging the relative deadline of tasks. We demonstrate that our approach improves the state of the art by considering arrival curves that are obtained from tasks with release jitter.

Cyber-physical systems (CPS) increasingly use multicore processors in order to satisfy power and computational requirements. To exploit the architectural parallelism offered by the multicore processors, parallel task models and appropriate scheduling algorithms have to be provided. Directed-acyclic graphs (DAGs) are prominent models to express parallelism and precedence constraints. In classic real-time systems, all tasks have to comply with strict timing constraints, which however result in resource underutilization due to pessimistic assumptions. Applications in CPS that have traditionally been considered as hard real-time such as control algorithms have demonstrated inherent robustness that can tolerate occasional deadline misses. In this paper, we propose a hierarchical scheduling algorithm and probabilistic response-time analyses for probabilistic conditional DAG tasks that allow to guarantee a bounded probability for k consecutive deadline misses without enforcing late jobs to be immediately aborted.

Abstract The predictive performance of a machine learning model highly depends on the corresponding hyper-parameter setting. Hence, hyper-parameter tuning is often indispensable. Normally such tuning requires the dedicated machine learning model to be trained and evaluated on centralized data to obtain a performance estimate. However, in a distributed machine learning scenario, it is not always possible to collect all the data from all nodes due to privacy concerns or storage limitations. Moreover, if data has to be transferred through low bandwidth connections it reduces the time available for tuning. Model-Based Optimization (MBO) is one state-of-the-art method for tuning hyper-parameters but the application on distributed machine learning models or federated learning lacks research. This work proposes a framework $$\textit{MODES}$$ MODES that allows to deploy MBO on resource-constrained distributed embedded systems. Each node trains an individual model based on its local data. The goal is to optimize the combined prediction accuracy. The presented framework offers two optimization modes: (1) $$\textit{MODES}$$ MODES -B considers the whole ensemble as a single black box and optimizes the hyper-parameters of each individual model jointly, and (2) $$\textit{MODES}$$ MODES -I considers all models as clones of the same black box which allows it to efficiently parallelize the optimization in a distributed setting. We evaluate $$\textit{MODES}$$ MODES by conducting experiments on the optimization for the hyper-parameters of a random forest and a multi-layer perceptron. The experimental results demonstrate that, with an improvement in terms of mean accuracy ( $$\textit{MODES}$$ MODES -B), run-time efficiency ( $$\textit{MODES}$$ MODES -I), and statistical stability for both modes, $$\textit{MODES}$$ MODES outperforms the baseline, i.e., carry out tuning with MBO on each node individually with its local sub-data set.

Abstract This paper provides counterexamples for the slack enforcement mechanisms to handle segmented self-suspending real-time tasks by Lakshmanan and Rajkumar (Proceedings of the Real-Time and Embedded Technology and Applications Symposium (RTAS), pp 3–12, 2010).

Dynamic power management (DPM) reduces the power consumption of a computing system when it idles, by switching the system into a low power state for hibernation. When all processors in the system share the same component, e.g., a shared memory, powering off this component during hibernation is only possible when all processors idle at the same time. For a real-time system, the schedulability property has to be guaranteed on every processor, especially if idle intervals are considered to be actively introduced. In this work, we consider real-time systems with hybrid shared-memory architectures, which consist of shared volatile memory (VM) and non-volatile memory (NVM). Energy-efficient execution is achieved by applying DPM to turn off all memories during the hibernation mode. Towards this, we first explore the hybrid memory architectures and suggest a task model, which features configurable hibernation overheads. We propose a multi-processor procrastination algorithm (HEART), based on partitioned earliest-deadline-first (pEDF) scheduling. Our algorithm facilitates reducing the energy consumption by actively enlarging the hibernation time. It enforces all processors to idle simultaneously without violating the schedulability condition, such that the system can enter the hibernation state, where shared memories are turned off. Throughout extensive evaluation of HEART, we demonstrate (1) the increase in potential hibernation time, respectively the decrease in energy consumption, and (2) that our algorithm is not only more general but also has better performance than the state of the art with respect to energy efficiency in most cases.

Emerging non-volatile memory (NVM) architectures are considered as a replacement for DRAM and storage in the near future, since NVMs provide low power consumption, fast access speed, and low unit cost. Due to the lower write-endurance of NVMs, several in-memory wear-leveling techniques have been studied over the last years. Since most approaches propose or rely on specialized hardware, the techniques are often evaluated based on assumptions and in-house simulations rather than on real systems. To address this issue, we develop a setup consisting of a gem5 instance and an NVMain2.0 instance, which simulates an entire system (CPU, peripherals, etc.) together with an NVM plugged into the system. Taking a recorded memory access pattern from a low-level simulation into consideration to design and optimize wear-leveling techniques as operating system services allows a cross-layer design of wear-leveling techniques. With the insights gathered by analyzing the recorded memory access patterns, we develop a software-only wear-leveling solution, which does not require special hardware at all. This algorithm is evaluated afterwards by the full system simulation.

Controller Area Network (CAN) is the prevailing solution for connecting multiple electronic control units (ECUs) in automotive systems. Every broadcast message on the bus is received by each bus participant and introduces computational overhead to the typically resource-constrained ECUs due to interrupt handling. To reduce this overhead, hardware message filters can be applied. However, since such filters are configured according to the message identifiers (IDs) specified in the system, the filter quality is limited by the nature of the ID-assignment. Although hardware message filters are highly relevant for industrial applications, so far, only the optimization of the filter design, but not the related optimization of ID-assignments has been addressed in the literature.In this work, we explicitly focus on the optimization of message ID-assignments against the background of hardware message filtering. More precisely, we propose an optimization algorithm transforming a given ID-assignment in such a way that, based on the resulting IDs, the quality of hardware message filters is improved significantly, i.e., the computational overhead introduced to each ECU is minimized, and, moreover, the priority order of the system remains unchanged. Conducting comprehensive experiments on automotive benchmarks, we show that our proposed algorithm clearly outperforms optimizations based on the conventional method simulated annealing with respect to the achieved filter quality as well as to the runtime.

For many cyber-physical systems, e.g., IoT systems and autonomous vehicles, offloading workload to auxiliary processing units has become crucial. However, since this approach highly depends on network connectivity and responsiveness, typically only non-critical tasks are offloaded, which have less strict timing requirements than critical tasks. In this work, we provide two protocols allowing to offload critical and non-critical tasks likewise, while providing different service levels for non-critical tasks in the event of an unsuccessful offloading operation, depending on the respective system requirements. We analyze the worst-case timing behavior of the local cyber-physical system and, based on these analyses, we provide a sufficient schedulability test for each of the proposed protocols. In the course of comprehensive experiments, we show that our protocols have reasonable acceptance ratios under the provided schedulability tests. Moreover, we demonstrate that the system behavior under our proposed protocols is strongly dependent on probability of unsuccessful offloading operations, the percentage of critical tasks in the system, and the amount of offloaded workload.

Model-based Optimization (MBO) is a method to optimize expensive black-box functions that uses a surrogate to guide the search. We propose two practical approaches that allow MBO to optimize black-box functions where the relation between input and output changes over time, which are known as dynamic optimization problems (DOPs). The window approach trains the surrogate only on the most recent observations, and the time-as-covariate approach includes the time as an additional input variable in the surrogate, giving it the ability to learn the effect of the time on the outcomes. We focus on problems where the change happens systematically and label this systematic change concept drift. To benchmark our methods we define a set of benchmark functions built from established synthetic static functions that are extended with controlled drifts. We evaluate how the proposed approaches handle scenarios of no drift, sudden drift and incremental drift. The results show that both new methods improve the performance if a drift is present. For higher-dimensional multimodal problems the window approach works best and on lower-dimensional problems, where it is easier for the surrogate to capture the influence of the time, the time-as-covariate approach works better.

Localization of objects in cluttered scenes with machine learning methods is a fairly young research area. Despite the high potential of object localization for full process automation in Industry 4.0 and logistical environments, 3D data sets for such applications to train machine learning models are not openly available and only few publications have been made on that topic. To the authors knowledge, this is the first publication that describes a self-supervised and fully automated deep learning approach for object pose estimation using simulated 3D data. The solution covers the simulated generation of training data, the detection of objects in point clouds using a fully convolutional voting network and the computation of the pose for each detected object instance.

The increasing availability of heterogeneous ambient sensing systems challenges the according information processing systems to analyse and compare a variety of different systems in a single scenario. For instance, localization of objects can be performed by image processing systems as well as by radio based localization. If such systems are utilized to localize the same objects, synergy of the outputs is important to enable comparable and meaningful analysis. This demo showcases the practical deployment and challenges of such an example system.

Inter-core communication is a central challenge in many-core systems for which Network-on-chips (NoCs) have been demonstrated to scale well and to provide good overall performance. However, not only the distributed structure but also the link switching of NoCs have imposed a great challenge in the design and analysis for real-time systems where timing verification is mandatory. NoC protocols like worm-hole switching are designed with scalability and flexibility in mind, thus the existing link switching protocols usually consider each single link to be scheduled independently. The flexibility of such link-based arbitrations allows each packet to be distributed over multiple switches but also increases the number of possible link states (the number of flits in a buffer) that have to be considered in the worst-case timing analysis for real-time systems. To achieve timing predictability by design, we propose a family of less flexible switching protocols, called Simultaneous Progressing Switching Protocols (SP2), in which the links used by a flow either all simultaneously transmit one flit (if it exists) of this flow or none of them transmits any flit of this flow. Based on the all-or-nothing property of Sp2, we reduce the schedulability of the NoC to the uniprocessor self-suspension scheduling problem. Moreover, the proposed approach is not limited to any specific underlying routing protocols, which are usually constructed for deadlock avoidance instead of timing predictability.

Self-suspension behavior has been demonstrated to appear in complex cyber-physical real-time systems, e.g., multiprocessor locking protocols, computation offloading, and multicore resource sharing, as demonstrated in (Chen et al. ( 2019 ), Section 2). Although the impact of self-suspension behavior has been investigated since 1990, the literature of this research topic has been flawed as reported in the review by Chen et al. ( 2019 ).

While the earliest-deadline-first (EDF) scheduling algorithm has extensively been utilized in real-time systems, there is almost no literature considering EDF for task sets with dynamic self-suspension behavior. To be precise, there is no specialized result for uniprocessor systems, besides the trivial suspension-oblivious approach. The work by Liu and Anderson (in ECRTS 2013) and Dong and Liu (in RTSS 2016) for suspension-aware multiprocessor global EDF can also be applied to uniprocessor systems and therefore be considered the state-of-the-art. In this work, two novel schedulability analyses (one for sporadic and one for periodic task sets) for suspension-aware EDF on uniprocessor systems are proposed, which outperform the state-of-the-art on such systems in empirical and theoretical comparison. We further show that the analysis by Dong and Liu is in fact not suspension-aware for uniprocessor systems.

introduction Share on Introduction to the Special Issue on Languages, Compilers, Tools, and Theory of Embedded Systems: Part 1 Authors: Aviral Shrivastava View Profile , Jian-Jia Chen View Profile , Youtao Zhang View Profile Authors Info & Claims ACM Transactions on Embedded Computing SystemsVolume 19Issue 5September 2020 Article No.: 30pp 1–3https://doi.org/10.1145/3417732Online:26 September 2020Publication History 0citation62DownloadsMetricsTotal Citations0Total Downloads62Last 12 Months22Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper presents an approach to optimize the quality of computer vision tasks in resource-constrained devices by using different execution versions of the same task. The execution versions are generated by dropping irrelevant contents of the input images or other contents that have marginal effect on the quality of the result. Our execution model is designed to support the edge computing paradigm, where the tasks can be executed remotely on edge nodes either to improve the quality or to reduce the workload of the local device. We also propose an algorithm that selects the suitable execution versions, which includes selecting the configuration and the location of the execution, in order to maximize the total quality of the tasks based on the available resources. The proposed approach provides reliable and adaptive task execution by using several execution versions with various performance and quality trade-offs. Therefore, it is very beneficial for systems with resource and timing constraints such as portable medical devices, surveillance video cameras, wearable systems, etc. The proposed algorithm is evaluated using different computer vision benchmarks.

In soft real-time systems, applications can tolerate rare deadline misses. Therefore, probabilistic arguments and analyses are applicable in the timing analyses for this class of systems, as demonstrated in many existing researches. Convolution-based analyses allow to derive tight deadline-miss probabilities, but suffer from a high time complexity. Among the analytical approaches, which result in a significantly faster runtime than the convolution-based approaches, the Chernoff bounds provide the tightest results. In this paper, we show that calculating the deadline-miss probability using Chernoff bounds can be solved by considering an equivalent convex optimization problem. This allows us to, on the one hand, decrease the runtime of the Chernoff bounds while, on the other hand, ensure a tighter approximation since a larger variable space can be searched more efficiently, i.e., by using binary search techniques over a larger area instead of a sequential search over a smaller area. We evaluate this approach considering synthesized task sets. Our approach is shown to be computationally efficient for large task systems, whilst experimentally suggesting reasonable approximation quality compared to an exact analysis.

In the field of automotive engineering, broadcast buses, e.g., Controller Area Network (CAN), are frequently used to connect multiple electronic control units (ECUs). Each message transmitted on such buses can be received by each single participant, but not all messages are relevant for every ECU. For this purpose, all incoming messages must be filtered in terms of relevance by either hardware or software techniques. We address the issue of designing hardware filter configurations for clients connected to a broadcast bus in order to reduce the cost, i.e., the computation overhead, provoked by undesired but accepted messages. More precisely, we propose an SMT formulation that can be applied to i) retrieve a (minimal) perfect filter configuration, i.e., no undesired messages are received, ii) optimize the filter quality under given hardware restrictions, or iii) minimize the hardware cost for a given type of filter component and a maximum cost threshold.

In computing systems, a job may suspend itself (before it finishes its execution) when it has to wait for certain results from other (usually external) activities. For real-time systems, such self-suspension behavior has been shown to induce performance degradation. Hence, the researchers in the real-time systems community have devoted themselves to the design and analysis of scheduling algorithms that can alleviate the performance penalty due to self-suspension behavior. As self-suspension and delegation of parts of a job to non-bottleneck resources is pretty natural in many applications, researchers in the operations research (OR) community have also explored scheduling algorithms for systems with such suspension behavior, called the master-slave problem in the OR community. This paper first reviews the results for the master-slave problem in the OR literature and explains their impact on several long-standing problems for scheduling self-suspending real-time tasks. For frame-based periodic real-time tasks, in which the periods of all tasks are identical and all jobs related to one frame are released synchronously, we explore different approximation metrics with respect to resource augmentation factors under different scenarios for both uniprocessor and multiprocessor systems, and demonstrate that different approximation metrics can create different levels of difficulty for the approximation. Our experimental results show that such more carefully designed schedules can significantly outperform the state-of-the-art.

When considering recurrent real-time tasks in multiprocessor systems, access to shared resources, via so-called critical sections, can jeopardize the schedulability of the system. The reason is that resource access is mutual exclusive and a task must finish its execution of the critical section before another task can access the same resource. Therefore, the problem of multiprocessor synchronization has been extensively studied since the 1990s, and a large number of multiprocessor resource sharing protocols have been developed and analyzed. Most protocols assume work-conserving scheduling algorithms which make it impossible to schedule task sets where a critical section of one task is longer than the relative deadline of another task that accesses the same resource. The only known exception to the work-conserving paradigm is the recently presented Dependency Graph Approach where the order in which tasks access a shared resource is not determined online, but based on a pre-computed dependency graph. Since the initial work only considers frame-based task systems, this paper extends the Dependency Graph Approach to periodic task systems. We point out the connection to the uniprocessor non-preemptive scheduling problem and exploit the related algorithms to construct dependency graphs for each resource. To schedule the derived dependency graphs, List scheduling is combined with an earliest-deadline-first heuristic. We evaluated the performance considering synthesized task sets under different configurations, where a significant improvement of the acceptance ratio compared to other resource sharing protocols is observed. Furthermore, to show the applicability in real-world systems, we detail the implementation in LITMUSRTand report the resulting scheduling overheads.

Effectively handling precedence constraints and resource synchronization is a challenging problem in the era of multiprocessor systems even with massively parallel computation power. One common approach is to apply list scheduling to a given task graph with precedence constraints. However, in some application scenarios, such as the OpenMP task model and multiprocessor partitioned scheduling for resource synchronization using binary semaphores, several operations can be forced to be tied to the same processor, which invalidates the list scheduling. This paper studies a special case of this challenging scheduling problem, where a task comprised of (at most) three subtasks is executed sequentially on the same processor and the second subtasks of the tasks may have sequential dependencies, e.g., due to synchronization. We demonstrate the limits of existing algorithms and provide effective heuristics considering preemptive execution. The evaluation results show a significant improvement, compared to the existing multiprocessor partitioned scheduling strategies.

Machine learning techniques such as model-based optimization are frequently used to solve expensive problems. Since a sequential execution of these algorithms is time-intensive due to the problem complexity, several attempts have been made to parallelize existing approaches. However, no state-of-the-art technique is able to efficiently exploit the full potential of multi-core architectures up to now. In this work, we propose a flexible extension to the Resource-Aware Model-Based Optimization framework (RAMBO) adopting multi-core scheduling techniques, which allows to use the available resources in a more efficient way and thus reduces the time required to solve expensive optimization problems.

In general computing systems, a job (process/task) may suspend itself whilst it is waiting for some activity to complete, e.g., an accelerator to return data. In real-time systems, such self-suspension can cause substantial performance/schedulability degradation. This observation, first made in 1988, has led to the investigation of the impact of self-suspension on timing predictability, and many relevant results have been published since. Unfortunately, as it has recently come to light, a number of the existing results are flawed. To provide a correct platform on which future research can be built, this paper reviews the state of the art in the design and analysis of scheduling algorithms and schedulability tests for self-suspending tasks in real-time systems. We provide (1) a systematic description of how self-suspending tasks can be handled in both soft and hard real-time systems; (2) an explanation of the existing misconceptions and their potential remedies; (3) an assessment of the influence of such flawed analyses on partitioned multiprocessor fixed-priority scheduling when tasks synchronize access to shared resources; and (4) a discussion of the computational complexity of analyses for different self-suspension task models.

Predictable scheduling and resource sharing primitives are fundamental aspects of real-time systems. To prevent race conditions, access to shared resources must ensure mutual exclusion, e.g., using semaphores. Further, real-time locking protocols are required to avoid un-controlled priority inversions. For uniprocessor systems, the Priority Ceiling Protocol (PCP) has been widely accepted and supported in real-time operating systems. However, it remains arguable as to whether there exists a preferable approach for resource sharing in multiprocessor systems. In this paper, we show that the proposed Resource-Oriented Partitioned (ROP) scheduling with a distributed resource sharing policy, originating from the concept of the Distributed Priority Ceiling Protocol (DPCP), can achieve a non-trivial speedup factor guarantee. Specifically, we prove that the proposed R-PCP-rm-rm algorithm achieves a speedup factor of $11-6/(m+1)$11-6/(m+1) on a platform consisting of $m$m processors, where each job of a task may request at most one shared resource at most one time. Our empirical evaluations show that the proposed algorithm is highly effective in terms of task sets deemed schedulable.

A cause-effect chain is used to define the logical order of data dependent tasks, which is independent from the execution order of the jobs of the (periodic/sporadic) tasks. Analyzing the worst-case End-to-End timing behavior, associated to a cause-effect chain, is an important problem in embedded control systems. For example, the detailed timing properties of modern automotive systems are specified in the AUTOSAR Timing Extensions. In this paper, we present a formal End-to-End timing analysis for distributed systems. We consider the two most important End-to-End timing semantics, i.e., the button-to-action delay (termed as the maximum reaction time ) and the worst-case data freshness (termed as the maximum data age ). Our contribution is significant due to the consideration of the sporadic behavior of job activations, whilst the results in the literature have been mostly limited to periodic activations. The proof strategy shows the (previously unexplored) connection between the reaction time (data age, respectively) and immediate forward (backward, respectively) job chains. Our analytical results dominate the state of the art for sporadic task activations in distributed systems and the evaluations show a clear improvement for synthesized task systems as well as for a real world automotive benchmark setting.

This paper explores the probability of deadline misses for a set of constrained-deadline sporadic soft real-time tasks on uniprocessor platforms. We explore two directions to evaluate the probability whether a job of the task under analysis can finish its execution at (or before) a testing time point t. One approach is based on analytical upper bounds that can be efficiently computed in polynomial time at the price of precision loss for each testing point, derived from the well-known Hoeffding's inequality and the well-known Bernstein's inequality. Another approach convolutes the probability efficiently over multinomial distributions, exploiting a series of state space reduction techniques, i.e., pruning without any loss of precision, and approximations via unifying equivalent classes with a bounded loss of precision. We demonstrate the effectiveness of our approaches in a series of evaluations. Distinct from the convolution-based methods in the literature, which suffer from the high computation demand and are applicable only to task sets with a few tasks, our approaches can scale reasonably without losing much precision in terms of the derived probability of deadline misses.

The sporadic task model is often used to analyze recurrent execution of tasks in real-time systems. A sporadic task defines an infinite sequence of task instances, also called jobs, that arrive under the minimum inter-arrival time constraint. To ensure the system safety, timeliness has to be guaranteed in addition to functional correctness, i.e., all jobs of all tasks have to be finished before the job deadlines. We focus on analyzing arbitrary-deadline task sets on a homogeneous (identical) multiprocessor system under any given global fixed-priority scheduling approach and provide a series of schedulability tests with different tradeoffs between their time complexity and their accuracy. Under the arbitrary-deadline setting, the relative deadline of a task can be longer than the minimum inter-arrival time of the jobs of the task. We show that global deadline-monotonic (DM) scheduling has a speedup bound of 3-1/M against any optimal scheduling algorithms, where M is the number of identical processors, and prove that this bound is asymptotically tight.

The optimization of learning has always been of particular concern for big data analytics. However, the ongoing integration of machine learning models into everyday life also demand the evaluation to be extremely fast and in real-time. Moreover, in the Internet of Things, the computing facilities that run the learned model are restricted. Hence, the implementation of the model application must take the characteristics of the executing platform into account Although there exist some heuristics that optimize the code, principled approaches for fast execution of learned models are rare. In this paper, we introduce a method that optimizes the execution of Decision Trees (DT). Decision Trees form the basis of many ensemble methods, such as Random Forests (RF) or Extremely Randomized Trees (ET). For these methods to work best, trees should be as large as possible. This challenges the data and the instruction cache of modern CPUs and thus demand a more careful memory layout. Based on a probabilistic view of decision tree execution, we optimize the two most common implementation schemes of decision trees. We discuss the advantages and disadvantages of both implementations and present a theoretically well-founded memory layout which maximizes locality during execution in both cases. The method is applied to three computer architectures, namely ARM (RISC), PPC (Extended RISC) and Intel (CISC) and is automatically adopted to the specific architecture by a code generator. We perform over 1800 experiments on several real-world data sets and report an average speed-up of 2 to 4 across all three architectures by using the proposed memory layout. Moreover, we find that our implementation outperforms sklearn, which was used to train the models by a factor of 1500.

Infrastructure-as-a-Service (IaaS) is a popular form of cloud computing that provides virtualized computing resources. The current trend of IaaS is moving from virtual machine-based into container-based. In this paper, we study the energy-efficient resource allocation problem for container-based virtualization in a data center. Our goal is to minimize the energy consumption by determining 1) the number of cores allocated to a container, 2) the operating frequency of the container, and 3) the deployment of the container to server. Every container has to meet its service level agreement (SLA). We propose dynamic programming algorithms that can be used under different scenarios, depending on the affordable time complexity. The performance of the proposed algorithms is evaluated with energy consumption data collected from experiments.

In real-time systems, in addition to the functional correctness recurrent tasks must fulfill timing constraints to ensure the correct behavior of the system. Partitioned scheduling is widely used in real-time systems, i.e., the tasks are statically assigned onto processors while ensuring that all timing constraints are met. The decision version of the problem, which is to check whether the deadline constraints of tasks can be satisfied on a given number of identical processors, has been known NP-complete in the strong sense. Several studies on this problem are based on approximations involving resource augmentation, i.e., speeding up individual processors. This paper studies another type of resource augmentation by allocating additional processors, a topic that has not been explored until recently. We provide polynomial-time algorithms and analysis, in which the approximation factors are dependent upon the input instances. Specifically, the factors are related to the maximum ratio of the period to the relative deadline of a task in the given task set. We also show that these algorithms unfortunately cannot achieve a constant approximation factor for general cases. Furthermore, we prove that the problem does not admit any asymptotic polynomial-time approximation scheme (APTAS) unless P=NP when the task set has constrained deadlines, i.e., the relative deadline of a task is no more than the period of the task.

In this paper, we present a middleware to save energy in mobile computing devices that offload tasks to a remote server in the cloud. Saving energy in these devices is very important to prolong the battery life and avoid overheating. The middleware uses an available nearby device called auxiliary server either as a surrogate for the remote one, or as a proxy to pass the data between the mobile device and the remote server. The main idea is to reduce the energy consumption of the communication with the remote server by using a high-speed or a low-power local connection with the auxiliary server instead. The paper also analyzes when it is beneficial to use the auxiliary server based on the response time from the remote server and the bandwidth of the remote connection. The proposed middleware is evaluated using different benchmarks, including commonly used applications in mobile devices, and simulations. Furthermore, it is compared to state-of-the art approaches in this area. The experiments show that The middleware is energy-efficient especially when the bandwidth of the remote communication is relatively low or the server is overloaded.

Many practical real-time systems must be able to sustain several reliability threats induced by their physical environments that cause short-term abnormal system behavior, such as transient faults. To cope with this change of system behavior, online adaptions, which may introduce a high computation overhead, are performed in many cases to ensure the timeliness of the more important tasks while no guarantees are provided for the less important tasks. In this work, we propose a system model which does not require any online adaption, but, according to the concept of dynamic real-time guarantees, provides full timing guarantees as well as limited timing guarantees, depending on the system behavior. For the normal system behavior, timeliness is guaranteed for all tasks; otherwise, timeliness is guaranteed only for the more important tasks while bounded tardiness is ensured for the less important tasks. Aiming to provide such dynamic timing guarantees, we propose a suitable system model and discuss, how this can be established by means of partitioned as well as semi-partitioned strategies. Moreover, we propose an approach for handling abnormal behavior with a longer duration, such as intermittent faults or overheating of processors, by performing task migration in order to compensate the affected system component and to increase the system's reliability. We show by comprehensive experiments that good acceptance ratios can be achieved under partitioned scheduling, which can be further improved under semi-partitioned strategies. In addition, we demonstrate that the proposed migration techniques lead to a reasonable trade-off between the decrease in schedulability and the gain in robustness of the system. The presented approaches can also be applied to mixed-criticality systems with two criticality levels.

This paper studies the problem of scheduling a set of hard real-time sporadic tasks that may access CPU cores and a shared resource. Motivated by the observation that the CPU resource is often abundant compared to the shared resources in multi-core and many-core systems, we propose to resolve this problem from a counter-intuitive shared-resource-centric perspective, focusing on judiciously prioritizing and scheduling tasks' requests in a limited preemptive manner on the shared resource while viewing the worst-case latency a task may experience on the CPU cores as suspension delays. We develop a rather comprehensive set of task partitioning algorithms that partition tasks onto the shared resource with the objective of guaranteeing schedulability while minimizing the required size of the shared resource, which plays a critical role in reducing the overall cost and complexity of building resource-constrained embedded systems in many application domains. A GPU-based prototype case study and extensive simulation-based experiments have been conducted, which validate both our shared-resource-centric scheduling philosophy and the efficiency of our suspension-based partitioning solutions in practice.

Timeliness is an important feature for many embedded systems. Although soft real-time embedded systems can tolerate and allow certain deadline misses, it is still important to quantify them to justify whether the considered systems are acceptable. In this paper, we provide a way to safely over-approximate the expected deadline miss rate for a specific sporadic real-time task under fixed-priority preemptive scheduling in uniprocessor systems. Our approach is compatible with the existing results in the literature that calculate the probability of deadline misses either based on the convolution-based approaches or analytically. We demonstrate our approach by considering randomly generated task sets with an execution behavior that simulates jobs that are subjected to soft errors incurred by hardware transient faults under a given fault rate. To empirically gather the deadline miss rates, we implemented an event-based simulator with a fault-injection module and release the scripts. With extensive simulations under different fault rates, we evaluate the efficiency and the pessimism of our approach. The evaluation results show that our approach is effective to derive an upper bound of the expected deadline miss rate and efficient with respect to the required computation time.

Self-suspending behavior in real-time embedded systems can have a major and non-trivial negative impact on timing predictability. In this work, we investigate how to analyze the schedulability of segmented self-suspending task systems under a fixed-priority assignment. For this purpose, we introduce the multi-segment workload function as well as the maximum workload function in order to quantify the maximum interference from the higher-priority tasks when constructing our (sufficient) schedulability test. Moreover, we derive an optimal priority assignment with respect to our schedulability test since it is compatible with Audsley's Optimal Priority Assignment (OPA). We show by means of comprehensive evaluations that our approach is highly effective concerning the number of schedulable task sets. Furthermore, one set of results reveals a rather non-intuitive observation, namely, that the worst-case suspension time of a computation segment should also be respected to improve the schedulability even if the suspension may finish earlier.

Over the years, many multiprocessor locking protocols have been designed and analyzed. However, the performance of these protocols highly depends on how the tasks are partitioned and prioritized, and how the resources are shared locally and globally. This paper answers a few fundamental questions when real-time tasks share resources in multiprocessor systems. We explore the fundamental difficulty of the multiprocessor synchronization problem and show that a very simplified version of this problem is NP-hard in the strong sense regardless of the number of processors and the underlying scheduling paradigm. Therefore, the allowance of preemption or migration does not reduce the computational complexity. On the positive side, we develop a dependency-graph approach that is specifically useful for frame-based real-time tasks, i.e., when all tasks have the same period and release their jobs always at the same time. We present a series of algorithms with speedup factors between 2 and 3 under semi-partitioned scheduling. We further explore methodologies for and tradeoffs between preemptive and non-preemptive scheduling algorithms, and partitioned and semi-partitioned scheduling algorithms. Our approach is extended to periodic tasks under certain conditions.

Real-time computing provides insightful ways to explore the optimization in resource usages, especially from the time point of view. Nevertheless, real-time task scheduling is recognized by its high complexity when there are non-preemptive shared resources and multiple processors. When more and more practical factors in system designs are considered, such as energy consumption and memory allocation, even some sub-problems in real-time task scheduling become intractable. Although people often criticize various artificial assumptions in real-time task scheduling, they have to admit that ideas in real-time computing and their extensions, such as tradeoff in cost, performance, energy, and even the quality of service, can be applied to multi-dimensional optimization in system designs. In this direction, we witness the rapid development of the embedded system industry and join the task force in system designs, especially mobile devices and non-volatile memory systems. Resource management on mobile devices, with a special emphasis on user experience, should not only consider the response time but also the visual perception of users. Non-volatile memory has also blurred the boundary between the memory and the storage. It enables certain unified considerations of the main memory and storage and also in-memory computing. It shows the ways to break the boundaries between hardware and software layers and have better integration of computing and memory/storage units. The advances in mobile systems and memory innovations inspire the evolution of embedded system designs and have also brought us insights to solutions regarding how systems should be restructured and how computing should be done. They might also provide their feedback to real-time computing and even shape the future direction of real-time computing in various innovative ways.

Multicore systems are increasingly utilized in real-time systems in order to address the high computational demands. To fully exploit the advantages of multicore processing, possible intra-task parallelism modeled as a directed acyclic graph (DAG) must be utilized efficiently. This paper considers the scheduling problem for parallel real-time tasks with constrained and arbitrary deadlines. In contrast to prior work in this area, it generalizes federated scheduling and proposes a novel reservation-based approach. Namely, we propose a reservation-based federated scheduling strategy that reduces the problem of scheduling arbitrary-deadline DAG task sets to the problem of scheduling arbitrary-deadline sequential task sets by allocating reservation servers. We provide the general reservation design for sporadic parallel tasks, such that any scheduling algorithm and analysis for sequential tasks with arbitrary deadlines can be used to execute the allocated reservation servers of parallel tasks. Moreover, the proposed reservation-based federated scheduling algorithms provide constant speedup factors with respect to any optimal scheduler for arbitrary-deadline DAG task sets. We demonstrate via numerical and empirical experiments that our algorithms are competitive with the state of the art.

Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive earliest deadline first (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, in other words, there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set.

Using Redundant Multithreading (RMT) for error detection and recovery is a prominent technique to mitigate soft-error effects in multi-core systems. Simultaneous Redundant Threading (SRT) on the same core or Chip-level Redundant Multithreading (CRT) on different cores can be adopted to implement RMT. However, only a few previously proposed approaches use adaptive CRT managements on the system level and none of them considers both SRT and CRT on the task level. In this paper, we propose to use a combination of SRT and CRT, called Mixed Redundant Threading (MRT), as an additional option on the task level. In our coarse-grained approach, we consider SRT, CRT, and MRT on the system level simultaneously, while the existing results only apply either SRT or CRT on the system level, but not simultaneously. In addition, we consider further fine-grained task level optimizations to improve the system reliability under hard real-time constraints. To optimize the system reliability, we develop several dynamic programming approaches to select the redundancy levels under Federated Scheduling. The simulation results illustrate that our approaches can significantly improve the system reliability compared to the state-of-the-art techniques.

In this paper, we take a careful look at speedup factors, utilization bounds, and capacity augmentation bounds. These three metrics have been widely adopted in real-time scheduling research as the de facto standard theoretical tools for assessing scheduling algorithms and schedulability tests. Despite that, it is not always clear how researchers and designers should interpret or use these metrics. In studying this area, we found a number of surprising results, and related to them, ways in which the metrics may be misinterpreted or misunderstood. In this paper, we provide a perspective on the use of these metrics, guiding researchers on their meaning and interpretation, and helping to avoid pitfalls in their use. Finally, we propose and demonstrate the use of parametric augmentation functions as a means of providing nuanced information that may be more relevant in practical settings.

Dynamic programming is an effective technique for the evaluation of the potential of optimal fuel consumption of drive trains, as it guarantees a globally optimal solution. This paper investigates two major problems associated with the application of dynamic programming. The first problem is the high computational complexity. Iterative dynamic programming is proposed as an alternative to dynamic programming in order to reduce the computational complexity, and issues with its implementation to discretized problems are addressed. The second problem is the loss of optimality due to the discretization of the continuous drive train model. The introduction of different errors and their propagation through the optimization process is investigated. The study of iterative dynamic programming and discretization errors is carried out for two test cases of hybrid marine drive trains models.

To tackle the unavoidable self-suspension behavior due to I/O-intensive interactions, multi-core processors, computation offloading systems with coprocessors, etc., the dynamic and the segmented self-suspension sporadic task models have been widely used in the literature. We propose new self-suspension models that are hybrids of the dynamic and the segmented models. Those hybrid models are capable of exploiting knowledge about execution paths, potentially reducing modelling pessimism. In addition, we provide the corresponding schedulability analysis under fixed-relative-deadline (FRD) scheduling and explain how the state-of-the-art FRD scheduling strategy can be applied. Empirically, these hybrid approaches are shown to be effective with regards to the number of schedulable task sets.

In computing systems, a job/process/task/thread may suspend itself when it has to wait for some other internal or external activities, such as computation offloading or memory accesses, to finish before it can continue its execution. In the literature, there are two commonly adopted self-suspending sporadic task models in real-time systems: 1) the dynamic self-suspension model and 2) the segmented self-suspension sporadic task model. A dynamic self-suspending sporadic task is specified with an upper bound on the maximum suspension time for a job (task instance), which allows a job to dynamically suspend itself arbitrary often as long as the suspension time upper bound is not violated. By contrast, a segmented self-suspending sporadic task has a predefined execution and suspension pattern in an interleaving manner. The dynamic self-suspension model is very flexible but inaccurate, whilst the segmented self-suspension model is very restrictive but very accurate. The gap between these two widely-adopted self-suspension task models can be potentially filled by the hybrid self-suspension task model. The investigation of the impact of self-suspension on timing predictability has been started in 1988. This survey paper provides a short summary of the state of the art in the design and analysis of scheduling algorithms and schedulability tests for self-suspending tasks in real-time systems.

1This paper answers several open questions of practical concerns to schedule soft real-time (SRT) tasks, to guarantee their bounded tardiness, under fixed-priority scheduling in homogeneous multiprocessor systems. We consider both cases with only SRT tasks and with mixed sets of SRT and hard real-time (HRT) tasks. For the case in which the system has only SRT tasks, we show that any fixed priority assignment policy yields a capacity augmentation factor of 2−1/M where M is the number of processors. We prove the optimality of the utilization-monotonic (UM) priority assignment (i.e., assigning higher priorities to high-utilization tasks) under our sufficient test for guaranteeing bounded tardiness. We show that UM priority assignment can yield a utilization bound of M+1/2M, which is shown asymptotically the best possible bound. For the case in which the system has mixed SRT and HRT tasks, we present two new fixed-priority assignment algorithms and their associated schedulability tests. One is a clustering-based greedy priority assignment policy and another is based on Audsley's optimal priority assignment (OPA) approach. We show that the utilization bounds, augmentation factors, and speedup factors are still maintained by the hard real-time cases. Therefore, introducing soft real-time tasks does not create additional problems (at least in those metrics) for scheduling if the priority assignments are properly done. As demonstrated by extensive experiments, these two policies yield reasonably good performance overall and much better performance than the deadline-monotonic priority assignment.

In a multi-core platform, resources, such as memory banks and buses, are mostly shared among all cores for power, performance, and cost reasons. The access interference on the shared resources poses a major challenge on the analysis of real-time properties, but can be alleviated if task data partition onto memory banks is applied with care. In this paper, we consider to schedule RAS (resource access sporadic) tasks onto a platform consisting of homogeneous cores and capacity-limited memory banks. According to our observation, we should avoid internal data spreading among the memory banks for a task while advocate external data spreading among memory banks for a given task set. We propose a two-phase algorithm with (4 + ρ + 3(2γ+1)/γ) speedup factor and (γ + 1) memory augmentation factor, where ρ γ 0 and ρ ≥ 1. The derived adjustable resource augmentation factors can be useful in terms of system synthesis and schedulability. Moreover, under the premise that a given task set is feasible, we devise a bi-section approach that can derive a schedulable solution requiring the least amount of memory augmentation. According to our experiment results, the proposed algorithm significantly outperformed the state-of-the-art algorithm [15] in terms of schedulability test even when memory augmentation is prohibited.

Chip manufacturers provide the Thermal Design Power (TDP) for a specific chip. The cooling solution is designed to dissipate this power level. But because TDP is not necessarily the maximum power that can be applied, chips are operated with Dynamic Thermal Management (DTM) techniques. To avoid excessive triggers of DTM, usually, system designers also use TDP as power constraint. However, using a single and constant value as power constraint, e.g., TDP, can result in significant performance losses in homogeneous and heterogeneous manycore systems. Having better power budgeting techniques is a major step towards dealing with the dark silicon problem. This paper presents a new power budget concept, called Thermal Safe Power (TSP), which is an abstraction that provides safe power and power density constraints as a function of the number of simultaneously active cores. Executing cores at any power consumption below TSP ensures that DTM is not triggered. TSP can be computed offline for the worst cases, or online for a particular mapping of cores. TSP can also serve as a fundamental tool for guiding task partitioning and core mapping decisions, specially when core heterogeneity or timing guarantees are involved. Moreover, TSP results in dark silicon estimations which are less pessimistic than estimations using constant power budgets.

Heterogeneous multicore systems clustered in multiple Voltage Frequency Islands (VFIs) are the next-generation solution for power and energy efficient computing systems. Due to the heterogeneity, the power consumption and execution time of a task changes not only with Dynamic Voltage and Frequency Scaling (DVFS), but also according to the task-to-island assignment, presenting major challenges for power management and energy minimization techniques. This paper focuses on energy minimization of periodic real-time tasks (or performance-constrained tasks) on such systems, in which the cores in an island are homogeneous and share the same voltage and frequency, but different islands have different types and numbers of cores and can be executed at other voltages and frequencies. We present an efficient algorithm to minimize the total energy consumption while satisfying the timing constraints of all tasks. Our technique consists of the coordinated selection of the voltage and frequency levels for each island, together with a task partitioning strategy that considers the energy consumption of the task executing on different islands and at different frequencies, as well as the impact of the frequency and the underlying core architecture to the resulting execution time. Every task is then mapped to the most energy efficient island for the selected voltage and frequency levels, and to a core inside the island such that the workloads of the cores in a VFI are balanced. We experimentally evaluate our technique and compare it to state-of-the-art solutions, resulting in average in 25 percent less energy consumption (and up to 87 percent for some cases), while guaranteeing that all tasks meet their deadlines.

Formal models used for representing recurrent real-time processes have traditionally been characterized by a collection of jobs that are released periodically. However, such a modeling may result in resource under-utilization in systems whose behaviors are not entirely periodic. For instance, tasks in cyber-physical system (CPS) may change their service levels, e.g., periods and/or execution times, to adapt to the changes of environments. In this work, we study a model that is a generalization of the periodic task model, called multi-mode task model: a task has several modes specified with different execution times and periods to switch during runtime, independent of other tasks. Moreover, we study the problem of allocating a set of multi-mode tasks on a homogeneous multiprocessor system. We present a scheduling algorithm using any reasonable allocation decreasing (RAD) algorithm for task allocations for scheduling multi-mode tasks on multiprocessor systems. We prove that this algorithm achieves 38% utilization for implicit-deadline rate-monotonic (RM) scheduled multi-mode tasks on multiprocessor systems.

The emergence of multicore and manycore platforms poses a big challenge for the design of real-time embedded systems, especially for timing analysis. We observe in this paper that response-time analysis for multicore platforms with shared resources can be symmetrically approached from two perspectives: a core-centric and a shared-resource-centric perspective. The common "core-centric" perspective is that a task executes on a core until it suspends the execution due to shared resource accesses. The potentially less intuitive "shared-resource-centric" perspective is that a task performs requests on shared resources until suspending itself back to perform computation on its respective core.

Partitioned multiprocessor scheduling has been widely accepted in academia and industry to statically assign and partition real-time tasks onto identical multiprocessor systems. This paper studies fixed-priority partitioned multiprocessor scheduling for sporadic real-time systems, in which deadline-monotonic scheduling is applied on each processor. Prior to this paper, the best known results are by Fisher, Baruah, and Baker with speedup factors 4-2/M and 3-1/M for arbitrary-deadline and constrained-deadline sporadic real-time task systems, respectively, where M is the number of processors. We show that a greedy mapping strategy has a speedup factor 3-1/M when considering task systems with arbitrary deadlines. Such a factor holds for polynomial-time schedulability tests and exponential-time (exact) schedulability tests. Moreover, we also improve the speedup factor to 2.84306 when considering constrained-deadline task systems. We also provide tight examples when the fitting strategy in the mapping stage is arbitrary and M is sufficiently large. For both constrained-and arbitrary-deadline task systems, the analytical result surprisingly shows that using exact tests does not gain theoretical benefits (with respect to speedup factors) if the speedup factor analysis is oblivious of the particular fitting strategy used.

For real-time embedded systems, self-suspending behaviors can cause substantial performance/schedulability degradations. In this paper, we focus on preemptive fixed-priority scheduling for the dynamic self-suspension task model on uniprocessor. This model assumes that a job of a task can dynamically suspend itself during its execution (for instance, to wait for shared resources or access co-processors or external devices). The total suspension time of a job is upper-bounded, but this dynamic behavior drastically influences the interference generated by this task on lower-priority tasks. The state-of-the-art results for this task model can be classified into three categories (i) modeling suspension as computation, (ii) modeling suspension as release jitter, and (iii) modeling suspension as a blocking term. However, several results associated to the release jitter approach have been recently proven to be erroneous, and the concept of modeling suspension as blocking was never formally proven correct. This paper presents a unifying response time analysis framework for the dynamic self-suspending task model. We provide a rigorous proof and show that the existing analyses pertaining to the three categories mentioned above are analytically dominated by our proposed solution. Therefore, all those techniques are in fact correct, but they are inferior to the proposed response time analysis in this paper. The evaluation results show that our analysis framework can generate huge improvements (an increase of up to 50% of the number of task sets deemed schedulable) over these state-of-the-art analyses.

To avoid catastrophic events like unrecoverable system failures on mobile and embedded systems caused by soft-errors, software-based error detection and compensation techniques have been proposed. Methods like error-correction codes or redundant execution can offer high flexibility and allow for application-specific fault-tolerance selection without the needs of special hardware supports. However, such software-based approaches may lead to system overload due to the execution time overhead. An adaptive deployment of such techniques to meet both application requirements and system constraints is desired. From our case study, we observe that a control task can tolerate limited errors with acceptable performance loss. Such tolerance can be modeled as a (m,k) constraint which requires at least m correct runs out of any k consecutive runs to be correct. In this paper, we discuss how a given (m,k) constraint can be satisfied by adopting patterns of task instances with individual error detection and compensation capabilities. We introduce static strategies and provide a formal feasibility analysis for validation. Furthermore, we develop an adaptive scheme that extends our initial approach with online awareness that increases efficiency while preserving analysis results. The effectiveness of our method is shown in a real-world case study as well as for synthesized task sets.

Embedded systems have limited resources, such as computation capabilities and battery life. The Dynamic Voltage and Frequency Scaling (DVFS) technique is used to save energy by running the processor of the embedded system at low voltage and frequency levels. However, this prolongs the execution time, which may cause potential deadline misses for real-time tasks. In this paper, we propose a general-purpose middleware to reduce the energy consumption in embedded systems without violating the real-time constraints. The algorithms in the middleware adopt the computation offloading concept to reduce the workload on the processor of the embedded system by sending the computation-intensive tasks to a powerful server. The algorithms are further combined with the DVFS technique to find the running frequency (or speed) such that the energy consumption is minimized and the real-time constraints are satisfied. The evaluation shows that our approach reduces the average energy consumption down to nearly 60%, compared to executing all the tasks locally at the maximum processor speed.

In many practical real-time systems, the physical environment and the system platform can impose uncertain execution behaviour to the system. For example, if transient faults are detected, the execution time of a task instance can be increased due to recovery operations. Such fault recovery routines make the system very vulnerable with respect to meeting hard real-time deadlines. In theory and in practical systems, this problem is often handled by aborting not so important tasks to guarantee the response time of the more important tasks. However, for most systems such faults occur rarely and the results of not so important tasks might still be useful, even if they are a bit late. This implicates to not abort these not so important tasks but keep them running even if faults occur, provided that the more important tasks still meet their hard real time properties. In this paper, we present Systems with Dynamic Real-Time Guarantees to model this behaviour and determine if the system can provide full timing guarantees or limited timing guarantees without any online adaptation after a fault occurred. We present a schedulability test, provide an algorithm for optimal priority assignment, determine the maximum interval length until the system will again provide full timing guarantees and explain how we can monitor the system state online. The approaches presented in this paper can also be applied to mixed criticality systems with dual criticality levels.

In computing systems, an execution entity (job/process/task) may suspend itself when it has to wait for some activities to continue/finish its execution. For real-time embedded systems, such self-suspending behavior has been shown to cause substantial performance/schedulability degradation in the literature. There are two commonly adopted self-suspending sporadic task models in real-time systems: 1) dynamic self-suspension and 2) segmented self-suspension sporadic task models. A dynamic self-suspending sporadic task is specified with an upper bound on the maximum suspension time for a job (task instance), which allows a job to dynamically suspend itself as long as the suspension upper bound is not violated. By contrast, a segmented self-suspending sporadic task has a predefined execution and suspension pattern in an interleaving manner.Even though some seemingly positive results have been reported for self-suspending task systems, the computational complexity and the theoretical quality (with respect to speedup factors) of fixed-priority preemptive scheduling have not been reported. This paper proves that the schedulability analysis for fixed-priority preemptive scheduling even with only one segmented self-suspending task as the lowest-priority task is coNP-hard in the strong sense. For dynamic self-suspending task systems, we show that the speedup factor for any fixed-priority preemptive scheduling, compared to the optimal schedules, is not bounded by a constant or by the number of tasks, if the suspension time cannot be reduced by speeding up. Such a statement of unbounded speedup factors can also be proved for earliest-deadline-first (EDF), least-laxity-first (LLF), and earliest-deadline-zero-laxity (EDZL) scheduling algorithms. However, if the suspension time can be reduced by speeding up coherently or the suspension time of each task is not comparable with (i.e., sufficiently smaller than) its relative deadline, then we successfully show that rate-monotonic scheduling has a constant speedup factor, with respect to the optimal schedules, for implicit-deadline task systems.

In this paper, we present a general response-time analysis and schedulability-test framework, called k2Q (k to Q). It provides automatic constructions of closed-form quadratic bounds or utilization bounds for a wide range of applications in real-time systems under fixed-priority scheduling. The key of the framework is a k-point schedulability test or a k-point response time analysis that is based on the utilizations and the execution times of k-1 higher-priority tasks. The natural condition of k2Q is a quadratic form for testing the schedulability or analyzing the response time. The response time analysis and the schedulability analysis provided by the framework can be viewed as a "blackbox'' interface that can result in sufficient utilization-based analysis. Since the framework is independent from the task and platform models, it can be applied to a wide range of applications.

When concurrent real-time tasks have to access shared resources, to prevent race conditions, the synchronization and resource access must ensure mutual exclusion, e.g., by using semaphores. That is, no two concurrent accesses to one shared resource are in their critical sections at the same time. For uniprocessor systems, the priority ceiling protocol (PCP) has been widely accepted and supported in real-time operating systems. However, it is still arguable whether there exists a preferable approach for resource sharing in multiprocessor systems. In this paper, we show that the proposed resource-oriented partitioned scheduling using PCP combined with a reasonable allocation algorithm can achieve a non-trivial speedup factor guarantee. Specifically, we prove that our task mapping and resource allocation algorithm has a speedup factor 11-6/(m+1) on a platform comprising m processors, where a task may request at most one shared resource and the number of requests on any resource by any single job is at most one. Our empirical investigations show that the proposed algorithm is highly effective in terms of task sets deemed schedulable.

Scheduling of real-time applications is an important research topic. We consider a large-scale application consisting of 100--1000 tasks with inter-task communications, which can be represented by a task graph. For scheduling these applications, previous research results have shown that the time-triggered scheduling approach is capable to effectively utilize real-time platforms. However, the time-triggered scheduling approach only supports periodically activated tasks. Sporadic (aperiodic) tasks, which are also common in industrial applications, require additional treatments in time-triggered approaches.

Due to the architectural design, process variations and aging, individual cores in many-core systems exhibit heterogeneous performance. In many-core systems, a commonly adopted soft error mitigation technique is Redundant Multithreading (RMT) that achieves error detection and recovery through redundant thread execution on different cores for an application. However,task mappingandthe task execution mode(i.e., whether a task executes in a reliable mode with RMT or unreliable mode without RMT) need to be considered for achieving resource-efficient reliability. This paper explores how to efficiently assign the tasks onto different cores with heterogeneous performance properties and determine the execution modes of tasks in order to achieve high reliability and satisfy the tolerance of timeliness. We demonstrate that the task mapping problem under heterogeneous performance can be solved by employing Hungarian Algorithm as subroutine to efficiently assign the tasks onto the cores to optimize the system reliability with polynomial time complexity. To obtain the efficient task execution modes, we also propose an iterative mode adaptation technique and guarantee the tolerable timing constraint. Our results illustrate that compared to state-of-the-art, the proposed approaches achieve up to$80$percent reliability improvement (on average$20$percent) under different scenarios of chip frequency variation maps.

Maintaining timeliness and data freshness for real-time data objects has long been recognized as an important problem in real-time database research. Despite years of active research, most of the past work focuses on uniprocessor systems. In this paper, we study the workload-aware temporal consistency maintenance problem upon multiprocessor platforms. We consider the problem of how to partition a set of update transactions to$m \ge 2$processors to maintain the temporal consistency of real-time data objects under both earliest deadline first (EDF) and deadline monotonic (DM) scheduling in each processor, while minimizing the total workload on$m$processors. Firstly, we only consider the feasibility aspect of the problem by proposing two polynomial time partitioning schemes, Temporal Consistency Partitioning under EDF ($\mathsf TCP_{\mathsf{EDF}}$) and Temporal Consistency Partitioning under DM ($\mathsf TCP_{\mathsf{DM}}$), and formally showing that the resource augmentation bounds of both$\mathsf TCP_{\mathsf{EDF}}$and$\mathsf TCP_{\mathsf{DM}}$are$({3 - \frac{1}{m}})$. Secondly, we address the partition problem globally by proposing a polynomial time heuristic, Density factor Balancing Fit ($\mathsf{DBF}$), where density factor balancing plays a major role in producing workload-efficient partitionings. Finally, we evaluate the feasibility and workload performances of$\mathsf{DBF}$versus other heuristics with comparable quality experimentally.

To enable reliable embedded systems, it is imperative to leverage the compiler and system software for joint optimization of functional correctness (i.e., vulnerability indexes) and timing correctness (i.e., deadline misses). This paper considers the optimization of the reliability-timing (RT) penalty, defined as a linear combination of the vulnerability and deadline misses. We propose a cross-layer approach to achieve reliable code generation and execution at compilation and system software layers for embedded systems. This is enabled by the concept of generating multiple versions for given application functions, with diverse performance and reliability tradeoffs, by exploiting different reliability-guided compilation options. As the execution time of a function is not fixed, the selection of the versions depends upon the execution behavior of the previous functions. Based on the reliability and execution time profiling of these versions, our reliability-driven system software decides the prioritization of the functions for determining their execution order and employs dynamic version selection to dynamically select a suitable version of a function. Specifically, our scheme builds a schedule table offline to optimize the RT penalty, and uses this table at run time to select suitable versions for the subsequent functions. A complex real-world application of “secure video and audio processing” composed of various functions is evaluated for reliable code generation and execution.

This work is motivated by the demand for scheduling tasks upon the increasingly popular island-based many-core architectures. On such an architecture, homogeneous cores are grouped into islands, each of which is equipped with a scratchpad memory module (referred to as local memory). We first show the NP-hardness and the inapproximability of the scheduling problem. Despite the inapproximability, positive results can still be found when different cases of the problem are investigated. A$(3-\frac{1}{F})$- approximation algorithm is proposed for the minimization of the maximum system utilization, where$F$is the number of cores in the platform. When the technique of resource augmentation is considered, this paper further develops a$(\gamma +1)$-memory$\frac{2\gamma -1}{\gamma -1}$-approximation algorithm, where$\gamma$represents the trade-off between CPU utilization and local memory space. On the other hand, a special case is also considered when the ratio of the worst-case execution time of a task without and with using the local memory is bounded by a constant. The capabilities of the proposed algorithms are then evaluated with benchmarks from MRTC, UTDSP, NetBench and DSPstone, where the maximum system utilization can be significantly reduced even when the local memory size is only 5 percent of the total footprint of all of the tasks.

Self-suspension is becoming an increasingly prominent characteristic in real-time systems such as: (i) I/O-intensive systems, where applications interact intensively with I/O devices, (ii) multi-core processors, where tasks running on different cores have to synchronize and communicate with each other, and (iii) computation offloading systems with coprocessors, like Graphics Processing Units (GPUs). In this paper, we show that rate-monotonic (RM), deadline-monotonic (DM) and laxity-monotonic (LM) scheduling will perform rather poor in dynamic self-suspending systems in terms of speed-up factors. On the other hand, the proposed PASS approach is guaranteed to find a feasible priority assignment on a speed-2 uniprocessor, if one exists on a unit-speed processor. We evaluate the feasibility of the proposed approach via a case study implementation. Furthermore, the effectiveness of the proposed approach is also shown via extensive simulation results.

For real time task sets, allowing preemption is often considered to be important to ensure the schedulability, as it allows high-priority tasks to be allocated to the processor nearly immediately. However, preemptive scheduling also introduces some additional overhead and may not be allowed for some hardware components, which motivates the needs of non-preemptive or limited-preemptive scheduling. We present a safe sufficient schedulability test for non-preemptive (NP) fixed priority scheduling that can verify the schedulability for Deadline Monotonic (DM-NP) and Rate Monotonic (RM-NP) scheduling in linear time, if task orders according to priority and period are given. This test leads to a better upper bound on the speedup factor for DM-NP and RM-NP in comparison to Earliest Deadline First (EDF-NP) than previously known, closing the gab between lower and upper bound. We improve our test, resulting in interesting properties of the blocking time that allow to determine schedulability by only considering the schedulability of the preemptive case if some conditions are met. Furthermore, we present a utilization bound for RM-NP, based on the ratio γ > 0 of the upper bound of the maximum blocking time to the execution time, significantly improving previous results.

In order to execute applications under real-time constraints on many-core processors with a Network-on-Chip (NoC), guaranteed service (GS) communication with guaranteed end-to-end latency and bandwidth is required. Several hardware-based solutions for GS communication have been proposed in literature. However, commercially available many-core processors, e.g., Tilera's Tile Pro64 or Adapt Eva's Epiphany, do not support such features. In this paper, we propose a software solution that allows GS communication on 2D-mesh packet-switching NoCs. Our investigation is based on a hardware model that is applicable to commercially available processors, which include multiple NoCs to separate request and response packets and support only best-effort communication. We prove that a common upper bound of the injection rate for all sources limits the congestion which leads to an upper bound of the worst-case transmission latency (WCTL) for any transmission, i.e., the combination of a request and a response packet. Furthermore, our approach supports arbitrary transmission streams that can be modified at runtime without violating the upper bound of the WCTL, as long as the injection rate is not violated. This enables adaptive features such as task migration or dynamic scheduling policies. Experiments evaluate our solution for different traffic patterns.

With the advent of cyber-physical systems, realtime tasks shall be run in different modes over time to react to the change of the physical environment. It is preferable to adopt high expressive models in real-time systems. In the light of simple implementation in kernels, fixed-priority scheduling has been widely adopted in commercial real-time systems. In this work we derive a technique for analyzing schedulability of the system where tasks can undergo mode change under fixed-priority scheduling. We study two types of fixed-priority scheduling in mode change systems: task-level and mode-level fixed-priority scheduling. The proposed tests run in polynomial time. We further show that a utilization of 2 - √2 ≈ 0.5857 can be guaranteed in implicit-deadline multi-mode systems if each mode is prioritized according to rate-monotonic policy. The effectiveness of the proposed tests is also shown via extensive simulation results.

To deal with a large variety of workloads in different application domains in real-time embedded systems, a number of expressive task models have been developed. For each individual task model, researchers tend to develop different types of techniques for deriving schedulability tests with different computation complexity and performance. In this paper, we present a general schedulability analysis framework, namely the k2U framework, that can be potentially applied to analyze a large set of real-time task models under any fixed-priority scheduling algorithm, on both uniprocessor and multiprocessor scheduling. The key to k2U is a k-point effective schedulability test, which can be viewed as a "blackbox" interface. For any task model, if a corresponding k-point effective schedulability test can be constructed, then a sufficient utilization-based test can be automatically derived. We show the generality of k2U by applying it to different task models, which results in new and improved tests compared to the state-of-the-art.

Energy efficiency is an important issue in computing systems and operating within a safe power budget is a necessary constraint. This paper presents a simple and practical solution both for energy minimization and peak power reduction, called Single Voltage Approximation (SVA) scheme, for periodic real-time tasks on multicore systems with a shared supply voltage in a voltage island. SVA is inspired by the Single Frequency Approximation (SFA) scheme, in which all the cores in the island run at a single voltage and frequency such that all tasks can meet their deadlines. In SVA, all the cores in the island are also executed at the same single voltage as in SFA. However, the frequency of each core is individually chosen, such that the tasks in each core can meet their deadlines, but without running at unnecessarily high frequencies. Thus, all the cores are executing tasks all the time and there is no need for any Dynamic Power Management (DPM) technique for reducing the energy consumption for idling. For task partitioning, SVA is combined with the Double Largest Task First (DLTF) partitioning scheme. Most importantly, this paper provides comprehensive analysis for combining DLTF and SVA, deriving its worst-case behavior both for energy minimization and peak power reduction, compared against the optimal solutions. Our analysis shows that, depending on the hardware, the energy consumption by combining DLTF and SVA is at most 1.95 (2.21, 2.42, and 2.59, respectively), compared to the optimal solutions, when the voltage island has up to 4 (8, 16, and 32, respectively) cores, which outperforms the worst-case factors of SFA when the cores fail to sleep efficiently. For peak power reduction, due to running at slower frequencies, combining DLTF and SVA always outperforms SFA, both in average and corner cases. Finally, we extend our analysis considering multicore systems with discrete voltage and frequency pairs and multiple voltage islands.

With the increasing number of cores in a computing system, how to coordinate the computing units and heterogeneous memory resources has soon become extremely critical for real-time systems. This paper explores the joint considerations of memory management and real-time task scheduling over island-based multi-core architecture, where the local memory module of an island offers shorter access time than the global memory module does. The objective of this work is to minimize the number of needed islands to successfully schedule real-time tasks. When the required amount of the local memory space is specified for each task, a scheduling algorithm is proposed to provide an asymptotic 299-approximation bound. When there is flexibility in determining the needed local memory space for each task, we propose an algorithm with an asymptotic 4-approximation bound to jointly manage memory resources and allocate computing cores. In addition to the worst-case approximation analysis, the proposed algorithms are also evaluated with 82 real-life benchmarks with the support of a worst-case execution time analyzer. Moreover, extensive evaluations are conducted to show the capability of the proposed approaches when being used with various computing cores and memory resources.

Efficient and effective system-level power management for multi-core systems with multiple voltage islands is necessary for next-generation computing systems. This paper considers energy efficiency for such systems, in which the cores in the same voltage island have to be operated at the same supply voltage level. We explore how to map given task sets onto cores, so that each task set is assigned and executed on one core and the energy consumption is minimized. Due to the restriction to operate at the same supply voltage in a voltage island, different mappings will result in different energy consumptions. By using the simple single frequency approximation scheme (SFA) to decide the voltages and frequencies of individual voltage islands, this paper presents the approximation factor analysis (in terms of energy consumption) for simple heuristic algorithms, and develops a dynamic programming algorithm, which derives optimal mapping solutions for energy minimization when using SFA. We experimentally evaluate the running time and energy consumption performance of these algorithms on Intel's single-chip cloud computer (SCC). Moreover, we conduct simulations for hypothetical platforms with different number of voltage islands and cores per island, also considering different task partitioning policies.

Manufacturers are constantly seeking to increase flash memory density in order to fulfill the ever growing demand for storage capacity. However, this trend significantly reduces the reliability and endurance of flash memory chips. The lifetime degradation worsens as the number of erase cycles grows, even with wear leveling technology being adopted to extend flash memory lifetime by evenly distributing erase cycles to every flash block. To address this issue, self-healing technology is proposed to recover a flash block before the flash block is worn out, but such a technology still has its limitation when recovering flash blocks. In contrast to the existing wear leveling designs, we adopt the self-healing technology to propose a heal-leveling design that evenly distributes healing cycles to flash blocks. Ultimately, heal-leveling aims to extend the lifetime of flash memory without introducing a large amount of live-data copying overheads. We conducted a series of experiments to evaluate the capability of the proposed design. The results show that our design can significantly improve the access performance and the effective lifetime of flash memory without the unnecessary overheads caused by wear leveling technology.

There are many timing unreliable computing components in modern computer systems, which are typically forbidden in hard real-time systems due to the timing uncertainty. In this paper, we propose a computation offloading mechanism to utilise these timing unreliable components in a hard real-time system, by providing local compensations. The key of the mechanism is to decide (1) how the unreliable components are utilized and (2) how to set the worst-case estimated response time. The local compensation has to start when the unreliable components do not deliver the results in the estimated response time. We propose a scheduling algorithm and its schedulability test to analyze the feasibility of the compensation mechanism. To validate the proposed mechanism, we perform a case study based on image-processing applications in a robot system and simulations. By adopting the timing unreliable components, the system can handle higher-quality images and with better performance.

This paper considers the scheduling of parallel real-time tasks with implicit deadlines. Each parallel task is characterized as a general directed acyclic graph (DAG). We analyze three different real-time scheduling strategies: two well known algorithms, namely global earliest-deadline-first and global rate-monotonic, and one new algorithm, namely federated scheduling. The federated scheduling algorithm proposed in this paper is a generalization of partitioned scheduling to parallel tasks. In this strategy, each high-utilization task (utilization ≥ 1) is assigned a set of dedicated cores and the remaining low-utilization tasks share the remaining cores. We prove capacity augmentation bounds for all three schedulers. In particular, we show that if on unit-speed cores, a task set has total utilization of at most m and the critical-path length of each task is smaller than its deadline, then federated scheduling can schedule that task set on m cores of speed 2, G-EDF can schedule it with speed 3 + v5/2 2.618, and G-RM can schedule it with speed 2 + v3 3.732. We also provide lower bounds on the speedup and show that the bounds are tight for federated scheduling and G-EDF when m is sufficiently large.

In many real-time systems, tasks may experience suspension delays when they block to access shared resources or interact with external devices such as I/O. It is known that such suspensions delays may negatively impact schedulability. Particularly in hard real-time systems, a few negative results exist on analyzing the schedulability of such systems, even for very restricted suspending task models on a uniprocessor. In this paper, we focus on the particular case of hard real-time suspending task systems with harmonic periods, which is a special case of practical relevance. We propose a new uniprocessor suspension-aware analysis technique for supporting such task systems under rate-monotonic scheduling. Our analysis technique is able to achieve only Theta(1) suspension-related utilization loss on a uniprocessor. Based upon this technique, we further propose a partitioning scheme that supports suspending task systems with harmonic periods on multiprocessors. The resulting schedulability test shows that compared to existing schedulability tests designed for ordinary non-suspending task systems, suspensions only results in Theta(m) additional suspension-related utilization loss, where m is the number of processors. Furthermore, experiments presented herein show that both our uniprocessor and multiprocessor schedulability tests improve upon prior approaches by a significant margin.

While advancements in chip manufacturing technology has accelerated the growth of embedded systems, it has revealed serious reliability and robustness challenges at various abstraction levels that threaten the applicability of scaled technologies [2, 3]. These reliability threats arise from multiple sources, and may result in faults in the hardware. Furthermore, these faults in the hardware may have catastrophic effects on the correctness of software execution [9, 11, 14]. This is particularly the case for real-time and timing-critical embedded systems involved in safety-, and mission-critical systems [13]. This occurs because traditional software abstraction layers make the fundamental assumption that the underlying hardware platform is error-free, and completely reliable. This is, however, no longer the case. In order to mitigate various reliability threats, besides hardware-level techniques, it is critical to develop and design resiliency at various layers of the embedded software stack [2, 3].

The number and diversity of cores in on-chip systems is increasing rapidly. However, due to the Thermal Design Power (TDP) constraint, it is not possible to continuously operate all cores at the same time. Exceeding the TDP constraint may activate the Dynamic Thermal Management (DTM) to ensure thermal stability. Such hardware based closed-loop safeguards pose a big challenge in using many-core chips for real-time tasks. Managing the worst-case peak power usage of a chip can help toward resolving this issue. We present a scheme to minimize the peak power usage for frame-based and periodic real-time tasks on many-core processors by scheduling the sleep cycles for each active core and introduce the concept of a sufficient test for peak power consumption for task feasibility. We consider both inter-task and inter-core diversity in terms of power usage and present computationally efficient algorithms for peak power minimization for these cases, i.e., a special case of “homogeneous tasks on homogeneous cores” to the general case of “heterogeneous tasks on heterogeneous cores”. We evaluate our solution through extensive simulations using the 48-core SCC platform and gem5 architecture simulator. Our simulation results show the efficacy of our scheme.

The applications of the mobile devices are increasingly being improved. They include computation-intensive tasks, such as video and audio processing. However, the mobile devices have limited resources, which may make it difficult to finish these tasks in time. Computation offloading can be used to boost the capabilities of these resource-constrained devices, where the computation-intensive tasks are moved to a powerful remote processing unit. This paper considers the computation offloading problem for sporadic real-time tasks. The total bandwidth server (TBS) is adopted on the remote processing unit (the server side) for resource reservation. On the client side, a dynamic programming algorithm is proposed to determine the offloading decision of the tasks such that their schedule is feasible (i.e., all the tasks meet their deadlines). The algorithm is evaluated using a case study of surveillance system and synthesized benchmarks.

In many real-time systems, tasks may experience self-suspension delays when accessing external devices. The problem of scheduling such self-suspending tasks to meet hard deadlines on a uniprocessor is known to be NP-hard in the strong sense. Current solutions including the common suspension-oblivious approach of treating all suspensions as computation can be quite pessimistic. This paper shows that another category of scheduling algorithms, namely fixed-relative-deadline (FRD) scheduling, may yield better performance than classical schedulers such as EDF and RM, for real-time tasks that may experience one self-suspension during the execution of a task instance. We analyze a simple FRD algorithm, namely EDA, and derive corresponding pseudo-polynomial-time and linear-time schedulability tests. To analyze the quality of EDA and its schedulability tests, we analyze their resource augmentation factors, with respect to the speed-up factor that is needed to ensure the schedulability and feasibility of the resulting schedule. Specifically, the speed-up factor of EDA is 2 and 3, when referring to the optimal FRD scheduling and any feasible arbitrary scheduling, respectively. Moreover, the speed-up factor of the proposed linear-time schedulability test is 2.787 and 4.875, when referring to the optimal FRD scheduling and any feasible arbitrary scheduling, respectively. Furthermore, extensive experiments presented herein show that our proposed linear-time schedulability test improves upon prior approaches by a significant margin. To our best knowledge, for the scheduling of self-suspending tasks, these are the first results of any sort that indicate it might be possible to design good approximation algorithms.

Due to the recent trend towards building complex real-time cyber-physical systems, system designers need to develop and choose expressive formal models for representing such systems, as the model should be adequately expressive such that it can accurately convey the relevant characteristics of the system being modeled. Compared to the classical sporadic task model, there exist a number of real-time task models that are more expressive. However, such models are often complex and thus are rather difficult to be analyzed efficiently. Due to this reason, prior analysis methods for dealing with such complex task models are pessimistic. In this paper, a novel analysis technique, namely the bur sty-interference analysis, is presented for analyzing two common expressive real-time task models, the general self-suspending task model and the deferrable server task model. This technique is used to derive new uniprocessor utilization-based schedulability tests and rate-monotonic utilization bounds for the two considered task models scheduled under rate-monotonic scheduling. Extensive experiments presented herein show that our proposed tests improve upon prior tests in all scenarios, in many cases by a wide margin. To the best of our knowledge, these are the first techniques that can efficiently analyze the general self-suspending and deferrable server task models on uniprocessors.

We consider the problem of online dynamic power management that provides hard real-time guarantees for multi-processor systems. In this problem, a set of jobs, each associated with an arrival time, a deadline, and an execution time, arrives to the system in an online fashion. The objective is to compute a non-migrative preemptive schedule of the jobs and a sequence of power on/off operations of the processors so as to minimize the total energy consumption while ensuring that all the deadlines of the jobs are met. We assume that we can use as many processors as necessary. In this paper we examine the complexity of this problem and provide online strategies that lead to practical energy-efficient solutions for real-time multi-processor systems. First, we consider the case for which we know in advance that the set of jobs can be scheduled feasibly on a single processor. We show that, even in this case, the competitive factor of any online algorithm is at least 2.06. On the other hand, we give a 4-competitive online algorithm that uses at most two processors. For jobs with unit execution times, the competitive factor of this algorithm improves to 3.59. Second, we relax our assumption by considering as input multiple streams of jobs, each of which can be scheduled feasibly on a single processor. We present a trade-off between the energy-efficiency of the schedule and the number of processors to be used. More specifically, for k given job streams and h processors with h>k, we give a scheduling strategy such that the energy usage is at most 4.k/(h-k) times that used by any schedule which schedules each of the k streams on a separate processor. Finally, we drop the assumptions on the input set of jobs. We show that the competitive factor of any online algorithm is at least 2.28, even for the case of unit job execution times for which we further derive an O(1)-competitive algorithm.

No abstract available.

No abstract available.

Energy-efficient designs are important issues in computing systems. This article studies the energy efficiency of a simple and linear-time strategy, called the Single Frequency Approximation (SFA) scheme, for periodic real-time tasks on multicore systems with a shared supply voltage in a voltage island. The strategy executes all the cores at a single frequency to just meet the timing constraints. SFA has been adopted in the literature after task partitioning, but the worst-case performance of SFA in terms of energy consumption incurred is an open problem. We provide comprehensive analysis for SFA to derive the cycle utilization distribution for its worst-case behaviour for energy minimization. Our analysis shows that the energy consumption incurred by using SFA for task execution is at most 1.53 (1.74, 2.10, 2.69, respectively), compared to the energy consumption of the optimal voltage/frequency scaling, when the dynamic power consumption is a cubic function of the frequency and the voltage island has up to 4 (8, 16, 32, respectively) cores. The analysis shows that SFA is indeed an effective scheme under practical settings, even though it is not optimal. Furthermore, since all the cores run at a single frequency and no frequency alignment for Dynamic Voltage and Frequency Scaling (DVFS) between cores is needed, any unicore dynamic power management technique for reducing the energy consumption for idling can be easily incorporated individually on each core in the voltage island. This article also provides an analysis of energy consumption for SFA combined with procrastination for Dynamic Power Management (DPM), resulting in an increment of 1 from the previous results for task execution. Furthermore, we also extend our analysis for deriving the approximation factor of SFA for a multicore system with multiple voltage islands.

Real-time task scheduling becomes even more challenging with the emerging of island-based multi-core architecture, where the local memory module of an island offers shorter access time than the global memory module does. With such a popular architecture design in mind, this paper exploits real-time task scheduling over island-based homogeneous cores with local and global memory pools. Joint considerations of real-time scheduling and memory allocation are presented to efficiently use the computing and memory resources. A polynomial-time algorithm with an asymptotic 4-approximation bound is proposed to minimize the number of needed islands to successfully schedule tasks. To evaluate the performance of the proposed algorithm, 82 benchmarks from the MRTC, MediaBench, UTDSP, NetBench, and DSPstone benchmark suites were profiled by a worst-case-execution-time analyzer aiT and included in the experiments.

Efficiently utilizing the computational resources of many core systems is one of the most prominent challenges. The problem worsens when resource requirements vary unpredictably and applications may be started/stopped at any time. To address this challenge, we propose two schemes that calculate and adapt task mappings at runtime: a centralized, optimal mapping scheme and a distributed, hierarchical mapping scheme that trades optimality for a high degree of scalability. Experiments on Intel's 48-core Single-Chip Cloud Computer and in a many core simulator show that a significant improvement in system performance can be achieved over current state-of-the-art.

State-of-the-art reliability optimizing schemes deploy spatial or temporal redundancy for the complete functionality. This introduces significant performance/area overhead which is often prohibitive within the stringent design constraints of embedded systems. This paper presents a novel scheme for selective software reliability optimization constraint under user-provided tolerable performance overhead constraint. To enable this scheme, statistical models for quantifying software resilience and error masking properties at function and instruction level are proposed. These models leverage a whole new range of reliability optimization. Given a tolerable performance overhead, our scheme selectively protects the reliability-wise most important instructions based on their masking probability, vulnerability, and redundancy overhead. Compared to state-of-the-art [7], our scheme provides a 4.84X improved reliability at 50% tolerable performance overhead constraint.

Computation offloading concept has been recently adopted to improve the performance of embedded systems by moving some computation-intensive tasks (partially or wholly) to a powerful remote server. In this paper, we consider a computation offloading problem for frame-based real-time tasks, in which all the tasks have the same arrival time and the same relative deadline/period, by adopting the total bandwidth server (TBS) as resource reservations in the server side (remote execution unit). We prove that the problem is N P-complete and propose two algorithms in this paper. The first algorithm is a greedy algorithm with low complexity and provides a quick heuristic approach to decide which tasks to be offloaded and how the tasks are scheduled. The maximum finishing time of the solution derived from the greedy algorithm is at most twice of the finishing time (make span, maximal on the client and on the server) of any schedule. The second algorithm is a dynamic programming approach, which builds a three-dimensional table and requires pseudo-polynomial time complexity, to make an optimal decision for computation offloading. The algorithms are evaluated with a case study of a surveillance system and synthesized benchmarks.

In many-core systems, the efficient deployment of computational and other resources is key in order to achieve a high throughput. Current state-of-the-art task mapping schemes balance the computational load among cores while avoiding congestions within the communication links. The problem is that a large number of cores running many memory-intensive tasks may congest memory controllers because their number and bandwidth is constrained. To avoid a high throughput degradation that could result from congested memory controllers, the mapping of tasks must be sensitized to the limited bandwidth of off-chip memory. Designing efficient and effective algorithms to optimize the throughput by jointly considering the load of memory controllers, computation, and communication is very challenging. In this paper, we address this problem by distributing cores among applications and then heuristically map tasks such that the load of the memory controllers is sufficiently balanced. Our heuristic also minimizes the effect of decreased throughput resulting from mapping communicating tasks to cores that belong to different controllers. Our experiments encourage us in that we can reduce the saturation of memory controllers and significantly increase the system throughput compared to employing several state-of-the-art task mapping schemes.

To enable reliable embedded systems, it is imperative to leverage the compiler and system software for joint optimization of functional correctness, i.e., vulnerability indexes, and timing correctness, i.e., the deadline misses. This paper considers the optimization of the Reliability-Timing (RT) penalty, defined as a linear combination of the vulnerability indexes (reliability penalties) and the deadline misses. We propose a multi-layer approach to achieve reliable code generation and execution at compilation and system software layers for embedded systems. This is enabled by the concept of generating multiple versions, for given application functions, with diverse performance and reliability tradeoffs, by exploiting different reliability-guided compilation options. Based on the reliability and execution time profiling of these versions, our reliability-driven system software employs dynamic version selections to dynamically select a suitable version of a function according to the execution behavior of the previous functions. Specifically, our scheme builds a schedule table offline to optimize the RT penalty, and uses this table at run time to select suitable versions for the subsequent functions properly. A complex real-world application of “secure video and audio processing” composed of various functions is evaluated for reliable code generation and execution. The reliability analysis and evaluation is performed on a reliability-aware processor simulator.

Energy-efficient designs are important issues in computing systems. This paper studies the energy efficiency of a simple and linear-time strategy, called Single Frequency Approximation (SFA) scheme, for periodic real-time tasks on multi-core systems with a shared supply voltage in a voltage island. The strategy executes all the cores at a single frequency to just meet the timing constraints. SFA has been adopted in the literature after task partitioning, but the worst-case performance of SFA, in terms of energy consumption, is an open problem. We provide comprehensive analysis for SFA to derive the cycle utilization distribution for its worst-case behaviour for energy minimization. Our analysis shows that the energy consumption by using SFA for task execution is at most 1.53 (1.74, 2.10, 2.69, respectively), compared to the energy consumption of the optimal voltage/frequency scaling, when the dynamic power consumption is a cubic function of the frequency and the voltage island has up to 4 (8, 16, 32, respectively) cores. The analysis shows that SFA is indeed an effective scheme under practical settings, even though it is not optimal. Furthermore, since all the cores run at a single frequency and no frequency alignment for Dynamic Voltage and Frequency Scaling (DVFS) between cores is needed, any uni-core dynamic power management technique for reducing the energy consumption for idling can be easily incorporated individually on each core in the voltage island. This paper also provides the analysis of energy consumption for SFA, combined with the procrastination for Dynamic Power Management (DPM). Furthermore, we also extend our analysis for deriving the approximation factor of SFA for a multi-core system with multiple voltage islands.

By allowing users to specify multiple execution versions of a task with different amounts of worst-case execution time and costs, this paper explores how to minimize of the overall system cost under the timing constraints for sporadic real-time tasks. One specific application is to minimize the requirement scratchpad memory size (system cost) to meet the timing constraint, while the worst-case execution time of a task depends on its allocated scratchpad memory size. This paper shows that the problem is NP-hard for approximation, if speed augmentation is not allowed. The algorithms proposed in this paper are analyzed based on (α, β)-approximation, in which a β speed augmentation factor is allowed and the system cost is at most α times of the optimal solution. For tasks with constrained deadlines, an efficient (1, 2/1-η)-approximation algorithm based on dynamic programming is proposed for deadline-monotonic (DM) scheduling, where 0 <; η <; 1 is a user-defined parameter for the rounding precision in dynamic programming. This is further extended to a (1, 1.6322/1-η )-approximation algorithm for earliest-deadline-first (EDF) scheduling. A polynomialtime (1 + ε, 1 + η)-approximation scheme is also developed for EDF scheduling by considering 0 <; ε, 0 <; η <; 1 when the ratio of the maximum relative deadline to the minimum relative deadline of tasks is a constant. This paper is concluded by considering the dual problem to maximize of the system profit by selecting execution versions with different amounts of worst-case execution time.

Energy-efficiency is a major concern in modern computing systems. For such systems, the presence of multiple voltage islands, where the voltage of each island can change independently and all cores in an island share the same supply voltage at any given time, is an expected compromise between global and per-core Dynamic Voltage and Frequency Scaling (DVFS). This paper focuses on energy minimization for a set of periodic tasks assigned on a voltage island. We present a simple and practical solution, that assigns the tasks onto cores in the island and then applies a DVFS schedule, particularly the Single Frequency Approximation (SFA) scheme. Furthermore, we provide thorough theoretical analysis of our solution, in terms of energy efficiency, against the optimal task partitioning and optimal DVFS schedule, especially for the state-of-the-art designs, that have a few number of cores per voltage island. The analysis shows that, our task partitioning scheme combined with SFA is a good and practical solution for energy efficiency. Particularly, when the number of cores in each voltage island is limited, the approximation factor is at most 2.01 (2.29, 2.55, 2.80, respectively) when the dynamic power consumption is a cubic function of the frequency and the islands have up to 4 (8, 16, 32, respectively) cores. Moreover, with non-negligible overhead for sleeping, further combination with any uni-core procrastination algorithm that consumes no more energy than keeping a core idle when it has no workload in its ready queue, increases the approximation factor by at most 1.

No abstract available.

No abstract available.

The papers in this special section present state-of-the-art power aware design for embedded systems. The articles examine recent developments used to address such topics as power consumption, power design, power requirements, energy management, and system performance.

In the past decade, the development of mobile and embedded systems has demanded energy efficiency for improving the lifetime of embedded devices. To avoid preemption overhead or ease timing verification, nonpreemptive scheduling has been deemed useful or necessary in meeting system timing requirements for certain applications built on embedded devices. In this paper, our aim is to design nonpreemptive scheduling algorithms that ensure timing correctness and optimize energy consumption on a processor with variable speeds. We propose a representative algorithm, ISA, which can produce lower speeds for a variety of nonpreemptive task sets than other comparable methods, and hence resulting in significant energy savings. When combined with a selective frequency-inheritance policy we design to efficiently determine if processor speedup can be disabled without jeopardizing any task deadlines, ISA can achieve even larger gains, up to 30% reduction in energy consumption. Finally, we propose a dynamic slack reclamation policy built on ISA, namely ISA-DR, which can result in additional energy savings when a task consumes less than its worst-case execution time.

Many cyber-physical systems consist of a collection of control loops implemented on multiple electronic control units (ECUs) communicating via buses such as FlexRay. Such buses support hybrid communication protocols consisting of a mix of time- and event-triggered slots. The time-triggered slots may be perfectly synchronized to the ECUs and hence result in zero communication delay, while the event-triggered slots are arbitrated using a priority-based policy and hence messages mapped onto them can suffer non-negligible delays. In this paper, we study a switching scheme where control messages are dynamically scheduled between the time-triggered and the event-triggered slots. This allows more efficient use of time-triggered slots which are often scarce and therefore should be used sparingly. Our focus is to perform a schedulability analysis for this setup, i.e., in the event of an external disturbance, can a message be switched from an event-triggered to a time-triggered slot within a specified deadline? We show that this analysis can check whether desired control performance objectives may be satisfied, with a limited number of time-triggered slots being used.

Multiprocessor platforms have been widely adopted to accommodate the increasing computation requirement of modern applications. Partitioned scheduling (or packing) has been widely exploited by partitioning real-time tasks onto processors to meet the timing constraints, which has been shown to be NP-complete in the strong sense. This paper studies the approximation of partitioned scheduling by exploiting resource augmentation with (1) speeding up or (2) allocating more processors. When adopting speeding up to meet timing constraints, we provide a polynomial-time approximation scheme (PTAS) to derive near-optimal solutions only with the assumption that the ratio of the maximum relative deadline to the minimum relative deadline is a constant. The previously known PTAS for this problem imposes additional restrictions on the periods and the execution times of tasks. By removing these additional constraints, our scheme can be adopted for wider task sets. When considering the resource augmentation by allocating more processors, we show that there does not exist any asymptotic polynomial-time approximation scheme (APTAS) unless P=NP.

This work is motivated by the advance of multiprocessor system architecture, in which the allocation of tasks over heterogeneous memory modules has a significant impact on the task execution. By considering two different types of memory modules with different access latencies, this paper explores joint considerations of memory allocation and real-time task scheduling to minimize the maximum utilization of processors of the system. For implicit-deadline sporadic tasks, a two-phase algorithm is developed, where the first phase determines memory allocation to derive a lower bound of the maximum utilization, and the second phase adopts worst-fit partitioning to assign tasks. It is shown that the proposed algorithm leads to a tight (2-⁄2M+1)-approximation bound where M is the number of processors. The proposed algorithm is then evaluated with 82 realistic benchmarks from MRTC, MediaBench, UTDSP, NetBench and DSPstone, and extensive simulations are further conducted to analyze the proposed algorithm.

Stacking DRAMs on processing cores by Through-Silicon Vias (TSVs) provides abundant bandwidth and enables a distributed memory interface design. To achieve the best balance in performance and cost in an application-specific system, the distributed memory interface should be tailored for the target applications. In this paper, we propose the first distributed memory interface synthesis framework for application-specific Network-on-Chips (NoCs) with 3D-stacked DRAMs. To maximize the performance of a selected hardware configuration, the proposed framework co-synthesizes the hardware configuration of the distributed memory interface, and the software configuration, e.g. task mapping and data assignment. Since TSVs have adverse impact on chip costs and yields, the goal of the framework is minimizing the number of TSVs provided that the user-defined performance constraint is met.

The expense of power cost in server farms has driven the recent power-aware development in both industry and academia. At the same time, a Service Level Agreement (SLA) of service performance between a customer and a service provider is demanded to meet the customer satisfaction. This paper investigates the queueing-theoretical power-saving design strategy for server farms under a given SLA, which in particular is measured in a certain level percentile of the job response time. We consider server farms with servers that are equipped with the capabilities of Dynamic Voltage Scaling (DVFS) and Dynamic Power Management (DPM). We adopt an M/G/1/PS server model, where the job service time distribution is assumed heavy-tailed, as discovered and validated by previous research. We propose a design strategy called Power Tail to minimize the power consumption under the given SLA. Our data confirms that the proposed Power Tail strategy indeed provides statistical guarantee in comparison with existing dynamic DVFS approaches and significantly outperforms the intuitive load-balancing strategy.

With the evolution of today's semiconductor technology, chip temperature increases rapidly mainly due to the growth in power density. For modern embedded real-time systems, it is crucial to estimate maximal temperatures in order to take mapping or other design decisions to avoid burnout, and still be able to guarantee meeting real-time constraints. This paper provides answers to the question: When work-conserving scheduling algorithms, such as earliest-deadline-first (EDF), rate-monotonie (RM), deadline-monotonic (DM), are applied, what is the worst-case peak temperature of a real-time embedded system under all possible scenarios of task executions? We propose an analytic framework, which considers a general event model based on network and real-time calculus. This analysis framework has the capability to handle a broad range of uncertainties in terms of task execution times, task invocation periods, and jitter in task arrivals. Simulations show that our framework is a cornerstone to design real-time systems that have guarantees on both schedulability and maximal temperatures.

Servers have been proposed to implement resource reservations on shared resources. Such reservations isolate the temporal behavior of tasks sharing the shared resources, thereby providing performance guarantees to tasks independent of other tasks. In existing work, resource reservation has been synonymous to utilization (also called bandwidth) on the resource, i.e., we can reserve only a constant fraction of the resource utilization via a server. Such reservation schemes are not suited to serve interrupt-like tasks: tasks that occur seldom but require quick service or tasks with jitter. With this motivation, we present a generalized server algorithm, called Demand Bound Server (DBS), whose offered service is characterized by the demand bound function (dbf) of the task it serves. We show that schedulability of DBS tightly follows that of EDF, and if schedulable a DBS provides a performance guarantee as requested by the dbf of the task. We present an implementation of DBS when the dbf is a shifted-periodic curve and characterize its overhead. We also present efficient composition operations on DBS that widen the class of implemented servers to tightly serve tasks arising in most practical settings.

Modern multiprocessor and multicore architectures adopt shared resources to meet increased performance requirements. Adaptive arbiters, such as FlexRay, have been adopted to grant access to shared resources. While increasing the performance, timing analysis is more challenging with this kind of arbiter. This paper considers real-time tasks that are composed of super blocks, while super blocks themselves are composed of phases. Phases are characterized by their worst-case computation time on their processing element and their worst-case number of access requests to a shared resource. Resource accesses, such as access to caches or scratchpad memory, are synchronous and cause the processing element to stall until the access is served. Based on dynamic programming, we develop an algorithm that safely derives an upper-bound of the worst-case response time of a phase. The worst-case response time of a task can then be determined for both sequential or time-triggered execution of super blocks. Experimental results are conducted for a real-world application.

As modern VLSI technology is scaling to the deep sub-micron domain, embedded systems face a power-efficiency problem, i.e., static power consumption caused by the leakage current. This paper explores how to use dynamic power management to reduce static power consumption while guaranteeing hard real-time properties. To tackle event arrivals with non-deterministic patterns, the arrival curve model is adopted to describe event arrivals in the interval domain. To reduce runtime overhead, periodic power management is investigated, which turns on and off a system with a fixed period. To reduce the timing complexity of computing such a periodic scheme, two algorithms, which are based on a linear-segmented representation of the arrival curve model, are proposed to trade the complexity with accuracy for energy reduction. We also present simulation results to demonstrate the effectiveness of our algorithms.

Several servers have been proposed to schedule streams of a periodic jobs in the presence of other periodic tasks. Standard schedulability analysis has been extended to consider such servers. However, not much attention has been laid on computing the worst-case delay suffered by a given stream of jobs when scheduled via a server. Such analysis is essential for using servers to schedule hard real-time tasks. We illustrate, with examples, that well established resource models, such as supply bound function and models from Real-Time Calculus, do not tightly characterize servers. In this work, we analyze the server algorithm of the Constant Bandwidth Server and compute a provably tight resource model of the server. The approach used enables us to differentiate between the soft and hard variants of the server. A similar approach can be used to characterize other servers, the final results for which are presented.

In recent work, approximation of the demand bound function for a sporadic task uses a linear approximation when the interval length of interest is larger than the relative deadline of the task. Such an approximation leads to a factor 2 for resource augmentation under a naive analysis, i.e., if the schedulability test using this approximate demand bound function fails, the task set is not schedulable by slowing down the system to 50% of the original speed. In this paper we provide a tighter analysis of such an approach on uniprocessor systems and on identical multiprocessor systems with partitioned scheduling under the earliest-deadline-first strategy. For uniprocessor systems, we prove that the resource augmentation factor is at most 2e-1/e ≈ 1.6322, where e is the Euler number. For identical multiprocessor systems with M processors, with respect to resource augmentation, we show that deadline-monotonic partitioning with approximate demand bound functions leads to a factor 3e-1/e-1/M ≈ 2.6322-1/M for constrained-deadline task sets and a factor 3-1/M for arbitrary-deadline task sets, in which the best results known so far are 3-1/M for constrained-deadline ones and 4-2/M for arbitrary-deadline ones. Moreover, we also provide concrete input instances to show that the lower bound of resource augmentation factors for uniprocessor systems (identical multiprocessor systems under an arbitrary order of fitting and a large number of processors, respectively) under such approaches is 1.5 (2.5, respectively).

Deriving deadlines and periods of update transactions for maintaining timeliness and data freshness has long been recognized as an important problem in real-time database research. Despite years of active research, the state of the art only focuses on uniprocessor systems. In this paper, we take a first step of studying the workload-aware temporal consistency maintenance problem upon multiprocessor platforms. We consider the problem of how to partition a set of update transactions to m ≥ 2 processors to maintain the temporal consistency of real-time data objects under earliest deadline first (EDF) scheduling, while minimizing the total workload on m processors. Firstly, we only consider the feasibility aspect of the problem by proposing a polynomial time partitioning scheme, Temporal Consistency Partitioning (TCP), and formally showing that the resource augmentation bound of TCP is (3 - 1/m). Secondly, we address the partition problem globally by proposing a polynomial time heuristic, Density factor Balancing Fit (DBF), where density factor balancing plays a major role in producing workload-efficient partitionings. Finally, we evaluate the feasibility and workload performances of DBF versus other heuristics with comparable quality experimentally.

Leakage energy consumption is an increasingly important issue as the technology continues to shrink. Existing leakage reduction techniques for hard real-time systems utilize slack to turn off a CPU completely. However, turning on/off a processor involves high performance and energy overheads. Hence, a hard real-time system is very likely to have unutilized slack if only the CPU shutdown technique is used to reduce leakage. Architectural-level shutdown techniques in all instances have a much lower overheads than turning off a CPU; therefore, they can be utilized in a hard real-time system to further reduce CPU leakage. However, existing architecture-level shutdown techniques cause unpredictable performance degradation thereby unsuitable for a hard real-time system that must meet the timing constraint in all cases. This paper is the first attempt to bridge this gap. This paper focuses on cache leakage reduction and proposes the first Timing-Aware Cache Leakage Control (TACLC) mechanism. TACLC exploits system slack to turn cache lines into low-leakage states provided that the timing constraint is met. The experimental results demonstrate that TACLC effectively utilizes system slack to reduce cache leakage. For systems with low CPU utilization, TACLC achieves comparable leakage reduction to the leakage control policy that aggressively turns cache lines into low-leakage modes while neglecting the timing constraint.

Dynamic power management has become essential for battery-driven embedded systems. This paper explores how to efficiently and effectively reduce the energy consumption of a device (system) for serving multiple event streams. Considering two different preemptive scheduling, i.e., earliest deadline first and fixed priority, we propose new method to adaptively control the power mode of the device according to historical arrivals of events. Our method can not only tackle arbitrary event arrivals but also provide hard real-time guarantees with respect to both timing and backlog constraints. Simulation results are presented as well to demonstrate the effectiveness of our approach.

In this paper a framework for energy management in energy harvesting embedded systems is presented. As a possible example scenario, we focus on wireless sensor nodes which are powered by solar cells. We demonstrate that classical power management solutions have to be reconceived and/or new problems arise if perpetual operation of the system is required. In particular, we provide a set of algorithms and methods for different application scenarios, including real-time scheduling, application rate control as well as reward maximization. The goal is to optimize the performance of the application subject to given energy constraints. Our methods optimize the system performance which allows the usage of, e.g., smaller solar cells and smaller batteries. Our theoretical results are supported by simulations using long-term measurements of solar energy in an outdoor environment. Furthermore, to demonstrate the practical relevance of our approaches, we measured the implementation overhead of our algorithms on real sensor nodes.

Multi-Processor Systems-on-Chip (MPSoC) are an increasingly important design paradigm not only for mobile embedded systems but also for industrial applications such as automotive and avionic systems. Such systems typically execute multiple concurrent applications, with different execution modes. Modes define differences in functionality and computational resource demands and are assigned with an execution probability. We propose a dynamic mapping approach to maintain low power consumption over the system lifetime. Mapping templates for different application modes and execution probabilities are computed offline and stored on the system. At runtime a manager monitors the system and chooses an appropriate pre-computed template. Experiments show that our approach outperforms global static mapping approaches up to 45%.

Multi-processor and multi-core systems are becoming increasingly important in time critical systems. Shared resources, such as shared memory or communication buses are used to share data and read sensors. We consider real-time tasks constituted by superblocks, which can be executed sequentially or by a time triggered static schedule. Three models to access shared resources are explored: (1) the dedicated access model, in which accesses happen only in dedicated phases, (2) the general access model, in which accesses could happen at anytime, and (3) the hybrid access model, combining the dedicated and general access model. For resource access based on a Time Division Multiple Access (TDMA) protocol, we analyze the worst-case completion time for a superblock, derive worst-case response times for tasks and obtain the relation of schedulability between different models. We conclude with proposing the dedicated sequential model as the model of choice for time critical resource sharing multi-processor/multi-core systems.

Employing COTS components in real-time embedded systems leads to timing challenges. When multiple CPU cores and DMA peripherals run simultaneously, contention for access to main memory can greatly increase a task's WCET. In this paper, we introduce an analysis methodology that computes upper bounds to task delay due to memory contention. First, an arrival curve is derived for each core representing the maximum memory traffic produced by all tasks executed on it. Arrival curves are then combined with a representation of the cache behavior for the task under analysis to generate a delay bound. Based on the computed delay, we show how tasks can be feasibly scheduled according to assigned time slots on each core.

Leakage power consumption contributes significantly to the overall power dissipation for systems that are manufactured in advanced deep sub-micron technology. Different from many previous results, this paper explores leakage-aware energy-efficient scheduling if leakage power consumption depends on temperature. We propose a pattern-based approach which divides a given time horizon into several time segments with the same length, where the processor is in the active (dormant, respectively) mode for a fixed amount of time at the beginning (end, respectively) of each time segment. Computation is advanced in the active mode, whereas the dormant mode helps reduce the temperature via cooling as well as the leakage power consumption. Since the pattern-based approach leads to a steady state with an equilibrium temperature, we develop a procedure to find the optimal pattern whose energy consumption in steady state is the minimum. Compared to existing work, our approach is more effective, has less run-time scheduling overhead, and requires only a simple scheduler to control the system mode periodically. The paper contains extensive simulation results which validate the new models and methods.

Reducing the power consumption while maintaining the response time constraint has been an important goal in server system design. One of the techniques widely explored in the literature to achieve this goal is Dynamic Voltage Scaling (DVS). However, DVS is not efficient in modern systems where the overall power consumption includes a large portion of static power consumption. In this paper, we aim to reduce the static power consumption by Dynamic Power Management (DPM) with sleep model in addition to DVS. We propose a smart PowerSleep power-saving scheme, where a procrastination technique is adopted to carefully aggregate jobs to reduce the overhead of transitions in and out of the sleep mode. We also observe that PowerSleep might not always be a good choice due to the mode transition overhead when the server utilization is high, where instead we use PowerIdle power-saving scheme with DVS only. By modeling the system with M/G/1/PS queuing model and further extensions, we present how to minimize the mean power consumption of the server under the given mean response time constraint for both power-saving schemes. Simulation results show that our smart PowerSleep scheme significantly outperforms the simple power saving scheme which adopts sleep mode.

Performance boosting of modern computing systems is constrained by the chip/circuit power dissipation. Dynamic voltage scaling (DVS) has been applied for reducing the energy consumption by dynamically changing the supply voltage. One can optimistically apply greedy online DVS scheduling algorithms by considering only the events that have arrived in the system. However, this might require a speed that is beyond a system's capability. Alternatively, one can pessimistically use a conservative speed to ensure timing guarantees, which might consume an excessive amount of energy as events might be processed faster than necessary. This paper presents an adaptive scheme that combines these two strategies for the scheduling of arbitrary event streams. The proposed adaptive DVS scheduler chooses the execution speed dynamically as long as it is below a certain threshold. Once the speed exceeds this threshold, the proposed scheduler operates at a constant (pessimistic) speed for guaranteeing the feasibility. The computation of the threshold speed is, however, not straight-forward. For deriving it, we make use of a framework based on timed model checking because the scheduler is strongly state-dependent. The resulting analysis framework allows to obtain the threshold speed for the proposed adaptive DVS scheduling algorithm such that both timing and speed constraints are guaranteed to be met and at the same time an energy-efficient execution is ensured.

Modern vehicle electronics control units (ECUs) are getting rapidly complicated because of active safety and semi-autonomous driving controls, such as electric stability program (ESP) and adaptive cruise control (ACC). Furthermore, the operational environment of ECUs is extremely harsh, especially in terms of an ambient temperature well exceeding 100°C, which causes a very small temperature headroom. Thus, ECUs require a careful temperature management and high performance at the same time.

Modern computing systems have adopted multicore architectures and multiprocessor systems on chip (MPSoCs) for accommodating the increasing demand on computation power. However, performance boosting is constrained by shared resources, such as buses, main memory, DMA, etc.This paper analyzes the worst-case completion (response) time for real-time tasks when time division multiple access (TDMA) policies are applied for resource arbitration.Real-time tasks execute periodically on a processing element and are constituted by sequential superblocks. A superblock is characterized by its accesses to a shared resource and its computation time. We explore three models of accessing shared resources: (1)dedicated access model, in which accesses happen only at the beginning and the end of a superblock, (2) general access model, in which accesses could happen anytime during the execution of a superblock, and (3) hybrid access model, which combines the dedicated and general access models. We present a framework to analyze the worst-case completion time of real-time tasks (superblocks) under these three access models, for a given TDMA arbiter. We compare the timing analysis of the three proposed models for a real-world application.

Dynamic Voltage Scaling (DVS) has been widely used for decreasing the dynamic power dissipation of processors. For real-time systems, DVS techniques have been developed that permit to meet the timing constraints of multiple real-time tasks and at the same time reduce the overall dynamic energy consumption. Known methods for static priority DVS scheduling are, however, either restricted to simple periodic/sporadic task release patterns or presume full a priori knowledge of task release times. Moreover, none of the present approaches considers the optimization of task priorities for reducing the energy consumption. In this paper we explore how to determine the static priorities and individual execution speeds (supply voltages) of multiple tasks with non-deterministic release times bounded by arrival curves such that the energy consumption is reduced and the real-time constraints are met. The result are different heuristics for the design of DVS-based real-time systems with static priorities. We show that the proposed methodology leads to energy-efficient system designs and demonstrate the applicability of the approach by means of experiments.

Energy harvesting (also known as energy scavenging) is the process of generating electrical energy from environmental energy sources. There exists a variety of different energy sources such as solar energy, kinetic energy, or thermal energy. In recent years, this term has been frequently applied in the context of small autonomous devices such as wireless sensor nodes. In this article, a framework for energy management in energy harvesting embedded systems is presented. As a possible scenario, we focus on wireless sensor nodes that are powered by solar cells. We demonstrate that classical power management solutions have to be reconceived and/or new problems arise if perpetual operation of the system is required. In particular, we provide a set of algorithms and methods for various application scenarios, including real-time scheduling, application rate control, as well as reward maximization. The goal is to optimize the performance of the application subject to given energy constraints. Our methods optimize the system performance which, for example, allows the usage of smaller solar cells and smaller batteries. Furthermore, we show how to dimension important system parameters like the minimum battery capacity or a sufficient prediction horizon. Our theoretical results are supported by simulations using long-term measurements of solar energy in an outdoor environment. In contrast to previous works, we present a formal framework which is able to capture the performance, the parameters, and the energy model of various energy harvesting systems. We combine different viewpoints, include corresponding simulation results, and provide a thorough discussion of implementation aspects.

Multiprocessor SOC platforms have been adopted for a wide range of high-performance applications, like automotive and avionic systems. Task assignment and processing unit allocation are key steps in the design of predictable and efficient embedded systems. Given the execution modes of applications, we propose a methodology to compute a task to processing element mapping, such that the expected average power consumption is minimized. Changing usage scenarios are represented by varying execution probabilities of modes. Statically precomputed template mappings for each execution probability are stored on the system and applied at runtime, allowing the system to adapt to changing environmental conditions. The underlying model considers static (leakage) and dynamic power. This study shows that deriving approximative solutions with a constant worst-case approximation factor in polynomial time is not achievable unless P = NP, even if a feasible task mapping is provided as an input. A polynomial-time heuristic algorithm is proposed that applies a multiple-step heuristic to derive template mappings. At runtime a manager monitors the system and chooses an appropriate precomputed template, hence low power-consumption is maintained over the systems lifetime. Experimental results reveal the effectiveness of the proposed algorithm by comparing the derived solutions to the optimal ones, obtained via an integer linear program (ILP).

As application complexity increases, modern embedded systems have adopted heterogeneous processing elements to enhance the computing capability or to reduce the power consumption. The heterogeneity has introduced challenges for energy efficiency in hardware and software implementations. This paper studies how to partition real-time tasks on a platform with heterogeneous processing elements (processors) so that the energy consumption can be minimized. The power consumption models considered in this paper are very general by assuming that the energy consumption with higher workload is larger than that with lower workload, which is true for many systems. We propose an approximation scheme to derive near-optimal solutions for different hardware configurations in energy/power consumption. When the number of processors is a constant, the scheme is a fully polynomial time approximation scheme (FPTAS) to derive a solution with energy consumption very close to the optimal energy consumption in polynomial-time/space complexity. Experimental results reveal that the proposed scheme is very effective in energy efficiency with comparison to the state-of-the-art algorithm.

Dynamic voltage scaling (DVS) has been widely adopted to reduce the energy consumption resulting from the dynamic power of modern processors. However, while the leakage power resulting from the leakage current becomes significant, how to aggregate the idle time to turn processors to the sleep or dormant modes is crucial in reducing the overall energy consumption. Moreover, for systems with non-DVS components, the execution order of tasks also affects the system-wide energy consumption. With the consideration of the dynamic and leakage power of processors as well as the power consumption resulting from non-DVS components, this paper summarizes our work on energy-efficient real-time task scheduling for both uniprocessor and multiprocessor platforms through procrastination of task executions, preemption control, and proper task assignment.

Adopting multiple processing units to enhance the computing capability or reduce the power consumption has been widely accepted for designing modern computing systems. Such configurations impose challenges on energy efficiency in hardware and software implementations. This work targets power-aware and energy-efficient task partitioning and processing unit allocation for periodic real-time tasks on a platform with a library of applicable processing unit types. Each processing unit type has its own power consumption characteristics for maintaining its activeness and executing jobs. This paper proposes polynomial-time algorithms for energy-aware task partitioning and processing unit allocation. The proposed algorithms first decide how to assign tasks onto processing unit types to minimize the energy consumption, and then allocate processing units to fit the demands. The proposed algorithms for systems without limitation on the allocated processing units are shown with an (m + 1)-approximation factor, where mis the number of the available processing unit types. For systems with limitation on the number of the allocated processing units, the proposed algorithm is shown with bounded resource augmentation on the limited number of allocated units. Experimental results show that the proposed algorithms are effective for the minimization of the overall energy consumption.

Power management has been a critical issue in the design of embedded systems due to the limited power supply. To prolong the lifetime, energy minimization has been studied under performance constraints in the past decade. The emerging embedded systems with the capability to harvest energy from the environment have recently triggered the revision of power management to improve the quality of service dynamically. As the available power/energy of an electronic device changes over time and is limited by many environmental factors, the system has to decide when to change to which service level to provide better quality of service without wasting the harvested energy. In this paper, we explore how to maximize the quality of service, in terms of system rewards, of a periodic application with discrete levels in an energy harvesting system. To decide service levels in a time horizon, this paper presents algorithms to derive optimal solutions if the future harvested energy is known. In addition, we present efficient algorithms to derive near-optimal solutions approximately. Our work is supported by simulation results which are based on long-term measurements of the power generated by real solar cells.

Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job must be executed within one of its feasible intervals. In this paper, we are interested in maximizing the sum of the weights of the multiple feasible interval jobs that complete in time when jobs are associated with weights for its in-time completion. We develop heuristic algorithms that apply the least-earliest-completion-time-first (LECF) strategy as a schedulability test or apply variations of the LECF strategy with job evictions. The capability of our proposed algorithms is verified by a series of simulations.

It is suggested that emotion plays a significant role in rational and intelligent behaviors. People behave emotions in different ways, and may not be noticeable through outside appearances. However, physiological information may reveal the clue for emotions. We proposed a mobile personal emotion monitoring system design, and proposed an adaptive algorithm that can help recognize user's emotion stateby using physiological sensors. We applied the dimensional analysis approach and adopted IAPS (International Affective Picture System) to manipulate psychological experiments. We also proposed an emotion recognition learning algorithm. It would extract each pattern of emotions from cross validation training and can further learn adaptively by feeding personalized testing data. We measured the learning rate of each subject which reveals incremental enhancement. Furthermore, we adopted a dimensional to discrete emotion transforming concept for validating the subjective rating. Compared to the experiment results of related works, our system outperforms both in dimensional and discrete analyses. Most importantly, the system is implemented based on wireless physiological sensors for mobile usage. This system can reflect the image of emotion states in order to provide on-line smart services.

Thermal management becomes a prominent issue in system design for both server systems and embedded systems. A system could fail if the peak temperature exceeds its thermal constraint. This research studies thermal-constrained scheduling for frame-based real-time tasks on a dynamic voltage/speed scaling system. Our objective is to design speed schedulers for real-time tasks by utilizing dynamic voltage/speed scaling to meet both timing and thermal constraints. Two approaches are proposed: One is based on the minimization of the response time under the thermal constraint, and the other is based on the minimization of the temperature under the timing constraint. We present detailed schedulability analysis for both proposed approaches. Our data show that our proposed proactive approaches outperform existing reactive ones.

As the power density of modern electronic circuits increases dramatically, systems are prone to overheating. Thermal management has become a prominent issue in system design. This paper explores thermal-aware scheduling for sporadic real-time tasks to minimize the peak temperature in a homogeneous multicore system, in which heat might transfer among some cores. By deriving an ideally preferred speed for each core, we propose global scheduling algorithms which can exploit the flexibility of multicore platforms at low temperature. Compared with load-balancing strategies, the proposed algorithms can significantly reduce the peak temperature by up to 30degC to 70degC for simulated platforms.

Multiprocessor SoC platforms have been adopted for a wide range of high performance applications. Task assignment and processing unit allocation are key steps in the design of predictable and efficient embedded systems. Provided that the probability distributions and mutual exclusion conditions for executing applications are known a priori, this paper explores the mapping of tasks onto processing units while minimizing the expected average power consumption. The underlying model considers static (leakage) and dynamic power. This study shows that deriving approximative solutions with a constant worst-case approximation factor in polynomial time is not achievable unless P=NP, even if a feasible task mapping is provided as an input. A polynomial-time heuristic algorithm is proposed that applies a multiple-step heuristic. Experimental results reveal the effectiveness of the proposed algorithm by comparing the derived solutions to the optimal ones, obtained via an integer linear program (ILP) specification.

Energy-efficient and power-aware designs have played important roles in modern computing systems to reduce the power bills for server systems or prolong the lifetime of embedded devices. Moreover, systems with multiple heterogeneous processing units have been widely adopted to enhance the computing capability or reduce the power consumption. This work explores how to synthesize a heterogeneous multiprocessor platform or select processing units with the partitioning of real-time tasks so that the energy consumption is minimized. Given a set of processing unit types, characterized by the power consumption for maintaining activeness and executing jobs, this paper proposes an efficient and effective algorithm to allocate processing units with energy-efficient task partitioning. We show that the algorithm is with a (1+ ln n)-approximation factor, in worst cases, for processing unit types with a variety of power consumption models, where n is the number of tasks. The approximation factor is asymptotically optimal for polynomial-time approximation algorithms unless P = NP. Experimental results show that the proposed algorithm is effective for energy consumption minimization.

Thermal constraints have limited the performance improvement of modern computing systems in recent years. As a system could fail if the peak temperature exceeds its thermal constraint, overheating should be avoided while designing a system. Moreover, higher temperature also leads to higher leakage power consumption. This paper explores dynamic thermal management to minimize the energy consumption for a specified computing demand under the thermal constraint. We develop energy-efficient speed scheduling schemes for frame-based real-time tasks under thermal constraints. Experimental results reveal the effectiveness of the proposed scheme in terms of energy consumption in comparison with the reactive schemes in the literature.

Performance boosting of modern computing systems has been constrained by the significant chip/circuit power dissipation. Dynamic voltage scaling (DVS) has been applied in the past decade for reducing the energy consumption by dynamically changing the supply voltage. On-line scheduling algorithms for DVS systems usually guarantee the real-time constraints of the system based on the condition that they can select any system speed that is sufficiently high to allow processing of all events within their deadlines. However, practical systems have a maximum available system speed and the feasibility of using on-line DVS algorithms needs to be verified during design time, i.e., they will never require during runtime a speed higher than the maximum available. This paper presents feasibility analysis of two on-line DVS algorithms that can compute in advance an upper bound on the system speed that these algorithms may require given that there is a single input event stream described by the worst-case event arrivals in interval domain. Moreover, we also present new results on the competitive ratios of the resulting schedules for energy consumption minimization with comparison to the off-line optimal solutions to show the effectiveness of the two algorithms. At the end, the performance of the different algorithms is evaluated.

Power dissipation has constrained the performance boosting of modern computer systems in the past decade. Dynamic power management has been widely applied to change the system (or device) state dynamically to reduce the power consumption. This paper explores how to effectively reduce the energy consumption to handle event streams with hard real-time guarantees. We adopt Real-Time Calculus to describe the event arrival and resource service by arrival curves and service curves in the interval domain, respectively. We develop online algorithms to adaptively control the power mode of the device, postponing the processing of arrival events as late as possible. Profited from the worst-case interval-based abstraction, our algorithms can on one hand tackle arbitrary event arrivals (even with burstiness) and on the other hand guarantee hard real-time requirements in terms of both timing and backlog constraints. We also present simulation results to demonstrate the effectiveness of our algorithms.

Modern computing systems often adopt multiple processing elements to enhance the computing capability or reduce the power consumption, especially for embedded systems. Such configurations impose challenges on energy efficiency in hardware and software implementations. This paper targets energy-efficient task partitioning for real-time tasks on a platform with two heterogeneous processing elements (processors), in which each one has its own characteristics on power consumption and job execution. This paper proposes a general framework for different hardware configurations in energy/power consumption. The framework provides a fully polynomial-time approximation scheme (FPTAS) to derive a solution with energy consumption very close to the optimal energy consumption in tolerable time/space complexity. Experimental results reveal that the proposed framework is effective in energy efficiency.

The pursuit of energy efficiency is becoming more and more important in hardware and software designs. This research explores energy-efficient scheduling for a periodic real-time task with uncertain execution time in dynamic voltage scaling (DVS) systems with non-negligible leakage/static power consumption. Distinct from the assumption of non-reducible static power consumption in the literature, this paper considers the possibility to reduce it by turning a processor to a dormant mode. We propose an algorithm to derive an optimal frequency assignment to minimize the expected energy consumption without procrastination, while another extended algorithm is developed to apply procrastination scheduling for further energy reduction. Experimental results show that the proposed algorithms can effectively minimize the expected energy consumption.

Energy-efficiency has been an important system issue in hardware and software designs for both real-time embedded systems and server systems. This research explores systems with probabilistic distribution on the execution time of realtime tasks on homogeneous multiprocessor platforms with the capability of dynamic voltage scaling (DVS). The objective is to derive a task partition which minimizes the expected energy consumption for completing all the given tasks in time. We give an efficient 1.13-approximation algorithm and a polynomial-time approximation scheme (PTAS) to provide worst-case guarantees for the strongly NP-hard problem. Experimental results show that the algorithms can effectively minimize the expected energy consumption.

Renewable energies can enable embedded systems to be functional indefinitely. In particular for small autonomous sensors, energy harvesting techniques have attracted much interest. This paper considers systems which provide services periodically with adjustable quality evaluated in terms of rewards. The reward garnered for one service is monotonically increasing and strictly concave with respect to the energy consumption of the service. There exist two major constraints which arise due to the burstiness of common energy sources: (1) The harvested energy is temporarily low and the service must be lowered or suspended. (2) During bursts, the harvested energy exceeds the battery capacity. To resolve these issues, we propose algorithms to derive optimal solutions which maximize the overall reward. Furthermore, we determine the minimum battery capacity necessary to optimally exploit a given power source. By applying real data recorded for photovoltaic cells as the harvested energy, simulations illuminate the merits of our algorithms.

Reliability-aware power management (RAPM) schemes have been recently studied to save energy while preserving system reliability. The existing RAPM schemes, however, provision for worst-case execution scenarios and are rather conservative. In this paper, by exploiting the probabilistic execution time information of real-time tasks, we develop an optimistic RAPM scheme. Instead of scheduling a full recovery for tasks whose executions are scaled down, the new scheme puts aside just enough slack to guarantee the required reliability leave while leaving more slack for energy management to achieve better energy savings. The problem is shown to be NP-hard and a novel heuristic algorithm is proposed and evaluated. The simulation results show that the optimistic RAPM scheme performs very well. It achieves energy savings comparable to that of the ordinary (but reliability-ignorant) power management scheme, while maintaining the system reliability as successfully as the conservative RAPM schemes.

Power-aware and energy-efficient designs play important roles for modern hardware and software designs, especially for embedded systems. This paper targets a scheduling problem on a processor with the capability of dynamic voltage scaling (DVS), which could reduce the power consumption by slowing down the processor speed. The objective of the targeting problem is to minimize the average flow time of a set of jobs under a given energy constraint, where the flow time of a job is defined as the interval length between the arrival and the completion of the job. We consider two types of processors, which have a continuous spectrum of the available speeds or have only a finite number of discrete speeds. Two algorithms are given: (1) An algorithm is proposed to derive optimal solutions for processors with a continuous spectrum of the available speeds. (2) A greedy algorithm is designed for the derivation of optimal solutions for processors with a finite number of discrete speeds. The proposed algorithms are extended to cope with jobs with different weights for the minimization of the average weighted flow time. The proposed algorithms are also evaluated with comparisons to schedules which execute jobs at a common effective speed.

Dynamic voltage scaling (DVS) circuits have been widely adopted in many computing systems to provide tradeoff between performance and power consumption. The effective use of energy could not only extend operation duration for hand-held devices but also cut down power bills of server systems. Moreover, while many chip makers are releasing multi-core chips and multiprocessor system-on-a-chips (SoCs), multiprocessor platforms for different applications become even more popular. Multiprocessor platforms could improve the system performance and accommodate the growing demand of computing power and the variety of application functionality. This paper summarizes our work on several important issues in energy-efficient scheduling for real-time tasks in multiprocessor DVS systems. Distinct from most previous work based on heuristics, we aim at the provision of approximated solutions with worst-case guarantees. The proposed algorithms are evaluated by a series of experiments to provide insights in system designs.

Leakage energy consumption is an increasingly important issue as the technology continues to shrink. Since on-chip caches constitute a major portion of the processor’s transistor budget, several leakage control policies have been proposed to reduce cache leakage. However, these policies introduce performance unpredictability thereby not suitable for hard real-time applications that require the timing constraint is met in all cases. In this paper, we propose the first approach to apply existing low leakage circuit techniques on hard real-time applications. The proposed timing-aware cache leakage control mechanism exploits task slack time to turn cache lines into the low-leakage state provided that the timing constraint is met. The experimental results show that the proposed cache leakage control policy achieves comparable leakage reduction to the leakage control policy that aggressively turns cache lines into low-leakage modes without considering the timing constraint.

Many computing systems have adopted the dynamic voltage scaling (DVS) technique to reduce energy consumption by slowing down ope- ration speed. However, the longer a job executes, the more energy in leakage current the processor consumes for the job. To reduce the power/energy consumption from the leakage current, a processor can enter the dormant mode. Existing research results for leakage-aware DVS scheduling perform procrastination of real-time jobs greedily so that the idle time can be aggregated as long as possible to turn off the processor. This paper proposes algorithms for the procrastination deter- mination of periodic real-time tasks in uniprocessor systems. Instead of greedy procrastination, the procrastination procedures are applied only when the evaluated energy consumption is less than not procras- tination. Evaluation results show that our proposed algorithms could derive energy-efficient solutions and outperform existing algorithms.

Dynamic voltage scaling (DVS) has been adopted in many computing systems to reduce the energy consumption of the processor by slowing down the processor speed. However, for system devices without DVS capability, the longer a task executes, the more energy the task consumes in the required system devices. This paper explores energy-efficient scheduling for periodic hard real-time tasks in a system consisted of a DVS processor and multiple non-DVS system devices. We propose an algorithm for static scheduling which minimizes the system energy consumption of a given set of real-time tasks, provided that each task executes in its worst case. For systems in which some tasks might complete earlier than its estimated worst-case execution time, we develop on-line algorithms to reclaim the slack time to reduce the energy consumption. Compared to existing algorithms, our proposed algorithm can reduce the energy consumption both in the CPU and system devices

While there is a tradeoff between the energy consumption and the satisfaction of task deadlines, the management of the processor temperature is of paramount important to the survival of the processor and the reduction of packing cost. This paper explores the scheduling of periodic real-time tasks with temperature-aware considerations in a uniprocessor or homogeneous multiprocessor environment. By modeling the cooling process approximately according to Fourier's law, a 2.719-approximation algorithm is shown for the minimization of the maximum temperature for processors with continuous processor speeds. When the processor is with discrete speeds only, we extend the 2.719 approximation algorithm to manage the voltage/speed transition so that the maximum temperature can be minimized. For homogeneous multiprocessor systems, we show that the largest-task first strategy has a 3.072-approximation bound in the minimization of the maximum temperature when all of the processors are on a chip. When each processor is on a chip, the approximation bound in the minimization of the maximum temperature is 6.444. When jobs might complete earlier than their worst-case estimation, dynamic scheduling is further explored to reduce the maximum temperature

Multiprocessor platforms have been widely adopted in both embedded and server systems. In addition to the performance improvement, multiprocessor systems could have the flexibility in tolerating processor failures via task replication. This paper considers the replication of periodic hard real-time tasks in identical multiprocessor environments. Each task is replicated on K distinct processors, where K is a user-determined integer for fault tolerance to improve system reliability. When the objective is to minimize the maximum utilization in a system with a specified number of processors, we present a greedy algorithm with a 2-approximation ratio, and a polynomial-time approximation scheme is developed. For the minimization of the number of processors required to derive feasible schedules with task replication, we develop greedy algorithms with a 2-approximation ratio and an asymptotic polynomial-time approximation scheme

Energy-efficient designs have played import roles for hardware and software implementations for a decade. With the advanced technology of VLSI circuit designs, energy-efficiency can be achieved by adopting the dynamic voltage scaling (DVS) technique. In this paper, we survey the studies for energy-efficient scheduling in real-time systems on DVS platforms to cover both theoretical and practical issues.

In reality, peripheral devices often make a significant contribution to the power consumption of the entire system. An effective energy-efficient scheduling algorithm should consider not only the energy consumption of the processor but also the usages of devices. In this paper, we explore energy-efficient scheduling of periodic real-time tasks in a system with a dynamic-voltage-scaling (DVS) processor and multiple non-DVS system devices. We consider systems that any device used by a task remains operating while the task is active. We propose scheduling algorithms in the management of task preemption to reduce the energy consumption of devices. Simulation results show that our proposed algorithms could not only reduce the number of task preemption significantly but also minimize the energy consumption, compared to earliest-deadline-first scheduling.

The energy-aware design for electronic systems has been an important issue in hardware and/or software implementations, especially for embedded systems. This paper targets a synthesis problem for heterogeneous multiprocessor systems to schedule a set of periodic real-time tasks under a given energy consumption constraint. Each task is required to execute on a processor without migration, where tasks might have different execution times on different processor types. Our objective is to minimize the processor cost of the entire system under the given timing and energy consumption constraints. The problem is first shown being NP - hard and having no polynomial-time algorithm with a constant approximation ratio unless NP = P . We propose polynomial-time approximation algorithms with (m + 2) - approximation ratios for this challenging problem, where m is the number of the available processor types. Experimental results show that the proposed algorithms could always derive solutions with system costs close to those of optimal solutions.

Energy-efficiency and power-awareness for electronic systems have been important design issues in hardware and software implementations. We consider the scheduling of periodic hard real-time tasks along with the allocation of processors under a given energy constraint. Each processor type could be associated with its allocation cost. The objective of this work is to minimize the entire allocation cost of processors so that the timing and energy constraints are both satisfied. We develop approximation algorithms for processor types with continuous processor speeds or discrete processor speeds. The capability of the proposed algorithms was evaluated by a series of experiments, and it was shown that the proposed algorithms always derived solutions with system costs close to those of optimal solutions in the experiments.

This work is motivated by the needs of energy-efficient designs for multi-context FPGAs. Dynamic-voltage-scaling-based algorithms are proposed to schedule loading and executing of tasks in a multi-context FPGA. When a task partition over contexts is given, two optimal scheduling algorithms are proposed in minimizing the energy consumption and the maximum time span of task executions. When no task partition is given, two approximation algorithms with approximation ratios 2.371 and 1.540 are presented in the energy-consumption minimization and the maximum-time-span minimization, respectively.

As the dynamic voltage scaling (DVS) technique provides system engineers the flexibility to trade-off the performance and the energy consumption, DVS has been adopted in many computing systems. However, the longer a job executes, the more energy in the leakage current the device/processor consumes for the job. To reduce the energy consumption resulting from the leakage current, a system might enter the dormant mode. This paper targets energy-efficient rate-monotonic scheduling for periodic real-time tasks on a uniprocessor DVS system with non-negligible leakage power consumption. An on-line simulated scheduling strategy and a virtually blocking time strategy are developed for procrastination scheduling to reduce energy consumption. The proposed algorithms derive a feasible schedule for real-time tasks with worst-case guarantees for any input instance. Experimental results show that our proposed algorithms could derive energy-efficient solutions.

Multiple processing elements are often adopted in the current designs of embedded systems. Such configurations impose challenges on hardware/software co-designs with energy-efficient considerations. This paper targets energy-efficient real-time task scheduling of such popular configurations, in which systems are equipped with a DVS processor and a non-DVS processing element (PE). We consider task scheduling under different power consumption models of the non-DVS PE. When the power consumption of the non-DVS PE is independent on the assigned workload, a fully polynomial-time approximation scheme is developed for energy-efficient scheduling. When the energy consumption of the non-DVS PE depends on the assigned workload, a 0.5-approximation algorithm is developed to maximize the energy saving, compared to the execution of tasks on a DVS processor. Extensive simulations were performed to evaluate the capability of our proposed algorithms. The results show that our algorithms are very effective in energy-efficiency

In the recent decade, voltage scaling has become an attractive feature for many system component designs. In this paper we consider energy-efficient real-time task scheduling over a chip multiprocessor architecture. The objective is to schedule a set of frame-based tasks with the minimum energy consumption, where all tasks are ready at time 0 and share a common deadline. We show that such a minimization problem is NP-hard and then propose a 2.371-approximation algorithm. The strength of the proposed algorithm was demonstrated by a series of simulations, for which near optimal results were obtained.

Energy-efficient scheduling is an effective way to balance the system performance and the energy consumption. We design a polynomial-time (1+ε)-approximation algorithm to minimize the energy consumption for periodic real-time tasks over such processors, where ε is the tolerable error given by users (1 ≥ ε > 0). It provides trade-offs between the user's tolerable error and the runtime complexity including the time complexity and the memory space complexity. System engineers could trade performance with implementation constraints.

Strong connectivity has been an important feature explored in many network applications, such as sensor networks. This research focuses on a dual power assignment problem, where each sensor node has two transmission power levels. The objective is to minimize the number of wireless sensor nodes assigned to transmit messages at the high transmission power level, while the resulting sensor network is strongly connected. We propose an efficient 1.75-approximation algorithm for this challenging problem. We not only show that the approximation ratio of the proposed algorithm is tight but also demonstrate the capability of the proposed algorithm in terms of simulation experiments.

In the past decades, a number of research results have been reported for energy-efficient scheduling over uniprocessor and multiprocessor environments. Different from many of the past results on the assumption for task power characteristics, we consider real-time scheduling of tasks with different power characteristics. The objective is to minimize the energy consumption of task executions under the given deadline constraint. When tasks have a common deadline and are ready at time 0, we propose an optimal real-time task scheduling algorithm for multiprocessor environments with the allowance of task migration. When no task migration is allowed, a 1.412-approximation algorithm for task scheduling is proposed for different settings of power characteristics. The performance of the approximation algorithm was evaluated by an extensive set of experiments, where excellent results were reported.

Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is NP-hard for both nonpreemptible and preemptible jobs. This paper develops two approximation algorithms for nonpreemptible and preemptible jobs. When jobs are nonpreemptible, algorithm LECF is with a 2-approximation factor; when jobs are preemptible, algorithm LEF is proved being a 3-approximation algorithm. We also show that our analysis on the two algorithms is tight by providing a set of input instances. Simulation results demonstrate that algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms.

This paper is interested in reward maximization of periodic real-time tasks under a given energy constraint, where the reward received depends on how much computation a task runs before its deadline. When voltage scaling could be done at any time, and tasks share the same power consumption function, we propose a greedy algorithm which derives a solution with at least a half of the optimal reward for any input instance. A fully polynomial-time approximation scheme is also proposed by applying the dynamic programming approach so that the ratio of the reward of the derived solution to that of an optimal solution is at least 1 - /spl epsiv/ under polynomial-time complexity in 1//spl epsiv/ for any 0 < /spl epsiv/ < 1, where /spl epsiv/ denotes a user-specified tolerable error to the derived solutions. When voltage scaling could be done only when a task instance arrives or terminates, or tasks might have different power consumption functions, we develop an approximation algorithm based on linear programming, which guarantees to derive a solution with at least 1/3 optimal reward for any input instance. A series of experiments was conducted to show the capability of the proposed algorithms in reward maximization.

Summary form only given. While excellent research results have been proposed for query optimization, little work has been done for the scheduling of query execution plans. We target the optimization problem of the schedule lengths of query execution plans in a symmetric multiprocessor (SMP) database system. We show the NP-hardness of the optimization problem. A critical-path-based algorithm is proposed to minimize the schedule length of a collection of query execution plans. When each query execution plan has a tree or a directed acyclic graph structure, we show that the approximation ratios of our proposed algorithm are 2 and (3 - 2/M), respectively, where M is the number of processors in the system. When the proposed algorithm is adopted for online usages, the competitive ratio of the algorithm is proven being (3 $2/M). The proposed algorithm is optimal when there is a sufficient number of processors. The performance of the proposed algorithm is evaluated based on the TPC-C benchmark.