Energy-harvesting (EH) Internet of Things (IoT) devices operate under intermittent energy availability, which disrupts task execution and makes energy-intensive over-the-air (OTA) updates particularly challenging. Conventional OTA update mechanisms rely on reboots and incur significant overhead, rendering them unsuitable for intermittently powered systems. Recent live OTA update techniques reduce reboot overhead but still lack mechanisms to ensure consistency when updates interact with runtime execution. This paper presents AERO, an Adaptive and Efficient Runtime-Aware OTA update mechanism that integrates update tasks into the device’s Directed Acyclic Graph (DAG) and schedules them alongside routine tasks under energy and timing constraints. By identifying update-affected execution regions and dynamically adjusting dependencies, AERO ensures consistent update integration while adapting to intermittent energy availability. Experiments on representative workloads demonstrate improved update reliability and efficiency compared to existing live update approaches.

Fault tolerance, energy management, and quality of service (QoS) are essential aspects for the design of real-time embedded systems. In this work, we focus on exploring methods that can simultaneously address the above three critical issues under standby-sparing. The standby-sparing mechanism adopts a dual-processor architecture in which each processor plays the role of the backup for the other one dynamically. In this way, it can provide fault tolerance subject to both permanent and transient faults. Due to its duplicate executions of the real-time jobs/tasks, the energy consumption of a standby-sparing system could be quite high. With the purpose of reducing energy under standby-sparing, we proposed three novel scheduling schemes: The first one is for (1, 1)-constrained tasks, and the second one and the third one (which can be combined into an integrated approach to maximize the overall energy reduction) are for general ( m,k )-constrained tasks that require that among any k consecutive jobs of a task no more than ( k - m ) out of them could miss their deadlines. Through extensive evaluations and performance analysis, our results demonstrate that compared with the existing research, the proposed techniques can reduce energy by up to 11% for (1, 1)-constrained tasks and 25% for general ( m,k )-constrained tasks while assuring ( m,k )-constraints and fault tolerance as well as providing better user perceived QoS levels under standby-sparing.

Computer vision has been greatly advanced with Convolutional Neural Networks (CNN or ConvNet), which generally have high demand on computational resources during training and/or inference. In this work, we focus on techniques to reduce resource needs of a CNN without largely affecting its accuracy. In particular, for the widely utilized ResNets that contain ConvNet layers organized in groups, we propose the Structured Coarse Block Rescaling (SCBR) to remove whole CNN channels from a group of ConvNet layers by adjusting their width together to circumvent the prohibitive costs in training of fine-grained model compression approaches. For a set of selected width modifiers, we experimentally evaluated the SCBR-pruned ResNets with the CIFAR dataset where the model size can be reduced to below 20% with less than 2% accuracy reduction when comparing to their baseline models. Furthermore, an efficient Gaussian Process (GP) guided search scheme is proposed to systematically explore impacts of SCBR across all width modifiers. Based on the derived ResNets from the set of selected width modifiers, the resulting GP model can predict performance of a SCBR-pruned ResNet with any width modifier, which has been experimentally verified with accuracy errors mostly below 0.5%.

Clouds have been adopted widely by many organizations for their supports of flexible resource demands and low cost, which is normally achieved through sharing the underlying hardware among multiple cloud tenants. However, such sharing with the changes in resource contentions in virtual machines (VMs) can result in large variations for the performance of cloud applications, which makes it difficult for ordinary cloud users to estimate the run-time performance of their applications. In this article, we propose online learning methodologies for performance modeling and prediction of applications that run repetitively on multi-tenant clouds (such as on-line data analytic tasks). Here, a few micro-benchmarks are utilized to probe the in-situ perceivable performance of CPU, memory and I/O components of the target VM. Then, based on such profiling information and in-place measured application’s performance, the predictive models can be derived with either Regression or Neural-Network techniques. In particular, to address the changes in the intensity of resource contentions of a VM over time and its effects on the target application, we proposedperiodic model retrainingwhere the sliding-window technique was exploited to control the frequency and historical data used for model retraining. Moreover, aprogressive modelingapproach has been devised where the Regression and Neural-Network models are gradually updated for better adaptation to recent changes in resource contention. With 17 representative applications from PARSEC, NAS Parallel and CloudSuite benchmarks being considered, we have extensively evaluated the proposed online schemes for the prediction accuracy of the resulting models and associated overheads on both a private and public clouds. The evaluation results show that, even on the private cloud with high and radically changed resource contention, the average prediction errors of the considered models can be less than 20 percent with periodic retraining. The prediction errors generally decrease with higher retraining frequencies and more historical data points but incurring higher run-time overheads. Furthermore, with the neural-network progressive models, the average prediction errors can be reduced by about 7 percent with much reduced run-time overheads (up to 265X) on the private cloud. For public clouds with less resource contentions, the average prediction errors can be less than 4 percent for the considered models with our proposed online schemes.

With ever-increasing attacks against learning-enabled components (LECs) in safety-critical systems, it has become more challenging to ensure robust operations. By focusing on anterior and posterior attacks on LECs, where malicious tasks need to run before and after a victim task, respectively, to launch attacks, we study in this work the victim-aware fixed-priority scheduling in single processor systems. Specifically, by exploiting the preference-oriented fixed-priority (POFP) scheduler, we devise a Victim-Aware Priority Assignment (VAPA) scheme to assign different priorities for victim tasks that are subject to anterior and posterior attacks, respectively. VAPA aims at reducing both anterior and posterior attacking occasions in the resultant schedule and thus enhancing the robust operations of the victim tasks. Online adaptation is also considered by exploiting idle time slots to further remove such attacking occasions whenever possible. The main ideas of the victim-aware scheduling are illustrated via a concrete example and future work is discussed.

For real-time computing systems, energy efficiency, quality of service (QoS), and fault tolerance are among the major design concerns. In this work, we study the problem of reliable and energy-aware$(m,k)$-deadlines enforcement using standby sparing under the fixed-priority assignment. The standby-sparing systems adopt a primary processor and a spare processor to provide fault tolerance for both permanent and transient faults. In order to reduce energy consumption for such kinds of systems, we proposed two novel scheduling schemes under the QoS constraint of$(m,k)$-deadlines: one for task sets partitioned with deeply red pattern and one for task sets partitioned with evenly distributed pattern. The evaluation results demonstrate that our proposed approaches significantly outperformed the previous research in energy conservation while assuring$(m,k)$-deadlines and fault tolerance for real-time systems.

Deep learning neural networks are of critical importance to enable next-generation IoT devices. However, due to the limited computation power, memory space, and energy, it remains a grand challenge to deploy those algorithms on IoT devices efficiently as they demand high computation, energy, and memory footprint. Numerous pruning methods of deep learning algorithms have been proposed to minimize the latency, energy, and weights. However, few consider the running time memory footprint and the overhead caused by data movement between the volatile memory and non-volatile memory. This paper proposes four novel memory-ware mechanisms for implementing CNN models on self-restrained embedded systems. The proposed techniques maximize the use of high-speed volatile memory and provide three implementation choices to achieve the minimum energy cost, SRAM space usage, and inference latency, as well as a hybrid trade-off choice of the three features. The experimental evaluation compares their energy cost, time latency, and required run-time memory footprint and demonstrates high implementation efficiency.

This special issue aims to provide a platform for the researchers, academia, and industry to present their novel solutions, applications, tools, software, hardware, and algorithms designed for addressing various sustainability challenges in CPS.The response from the CPS community was enthusiastic: the special issue received 34 manuscripts submitted by the authors from China, United States, India, Korea, Lebanon, and so on.According to the Journal of Software: Practice and Experience (SPE) review standards, this special issue accepted 14 high-quality research articles that cover a wide range of topics.These articles provide the software and hardware co-design solutions to improve dependability, energy efficiency, quality of service (QoS) of CPS, and also to introduce the methodologies for specific CPS applications.

For real-time computing systems, energy efficiency, Quality of Service, and fault tolerance are among the major design concerns. In this work, we study the problem of reliable and energy-aware fixed-priority (m,k)-deadlines enforcement with standby-sparing. The standby-sparing systems adopt a primary processor and a spare processor to provide fault tolerance for both permanent and transient faults. In order to reduce energy consumption for such kind of systems, we proposed a novel scheduling scheme under the QoS constraint of (m,k)deadlines. The evaluation results demonstrate that our proposed approach significantly outperformed the previous research in energy conservation while assuring (m,k)-deadlines and fault tolerance for real-time systems.

Accurate performance prediction for cloud applications is an essential component to support many cloud resource management and auto-scaling policies. However, most existing studies on performance prediction for cloud applications in multitenant clouds are at the system level and may require access to performance counters in hypervisors. In this work, we propose uPredict, a user-level profiler-based performance predictive framework for single-VM (virtual machine) applications in multitenant clouds. We designed three micro-benchmarks to assess the contention of CPUs, memory and disks in a VM, respectively. Based on the measured performance of an application and micro-benchmarks, the application and VM-specific predictive models are derived by exploiting various regression and neural network based techniques. These models can then be used to predict the application's performance using the in-situ profiled resource contention with the micro-benchmarks. We evaluated uPredict extensively with representative benchmarks from PARSEC, NAS Parallel Benchmarks and CloudSuite, on a private cloud and two public clouds. The results show that the average prediction errors are between 10.4% to 17% for various predictive models on the private cloud with high resource contention, while the errors are within 4% on public clouds. A smart load-balancing scheme powered by uPredict is presented and can effectively reduce the execution and turnaround times of the considered application by 19% and 10%, respectively.

Cybersickness is one of the primary challenges to the usability and acceptability of virtual reality (VR). Cybersickness can cause motion sickness-like discomforts, including disorientation, headache, nausea, and fatigue, both during and after the VR immersion. Prior research suggested a significant correlation between physiological signals and cybersickness severity, as measured by the simulator sickness questionnaire (SSQ). However, SSQ may not be suitable for automatic detection of cybersickness severity during immersion, as it is usually reported before and after the immersion. In this study, we introduced an automated approach for the detection and prediction of cybersickness severity from the user's physiological signals. We collected heart rate, breathing rate, heart rate variability, and galvanic skin response data from 31 healthy participants while immersed in a VR roller coaster simulation. We found a significant difference in the participants' physiological signals during their cybersickness state compared to their resting baseline. We compared a support vector machine classifier and three deep neural classifiers for cybersickness severity detection and prediction in two minutes' future, given the previous two minutes of physiological signals. Our proposed simplified convolutional long short-term memory classifier achieved an accuracy of 97.44% for detecting current cybersickness severity and 87.38% for predicting future cybersickness severity from the physiological signals.

Resource management is a vital factor for better performance in cloud systems and many resource allocation algorithms have been studied. In this work, focusing on applications with timing constraints (i.e., deadlines) running on resource-constrained clouds that have multiple heterogeneous nodes of computing resources (e.g., CPU cores and memory), we propose TIMER-Cloud, a time-sensitive resource allocation and virtual machine (VM) provisioning framework. As a key component of the framework, user requests (of running certain applications) are prioritized according to their deadlines and resource demands (in the form of VM and its operation time). Specifically, in addition to the intuitive Earliest Deadline First (EDF) ordering of requests, we propose three prioritization heuristics: a) one based on the Time-Sensitive Resource Factor (TSRF) that incorporates a request's deadline and usage efficiency of all its resources; b) the Dominant Share (DS) extension of TSRF that emphasizes the most demanded resource of a request aiming at obtaining balanced resource usage among the nodes; and c) a unified k-EDFscheme that integrates the ideas of EDF and TSRF/DS to balance the needs of meeting imminent deadlines of requests and improving resource usage efficiency. Then, for the mapping of the prioritized user requests to the heterogeneous nodes, we propose a novel request-to-node mapping algorithm based on the idea of euclidean Distance that finds the node with the best match of its resource requirements for each request. TIMER-Cloud has been implemented and validated on a cloud testbed powered by OpenStack with a few heterogeneous nodes. The proposed VM provisioning schemes are further evaluated through extensive simulations using the execution data of benchmark applications. The results show that the proposed schemes can outperform the state-of-the-art deadline oblivious scheme by serving up to 12 percent more user requests and achieving up to 8 percent more system rewards for the over-loaded scenario with 140 percent system load.

Heterogeneous multicore processors have recently become de facto computing engines for state-of-the-art embedded applications. Nonetheless, very little research focuses on the scheduling of periodic (implicit-deadline) real-time tasks upon heterogeneous multicores under the requirements of task synchronization, which is stemmed from resource access conflicts and can greatly affect the schedulability of tasks. In view of partitioned Earliest Deadline First and Multiprocessor Stack Resource Policy, we first discuss the blocking-aware utilization bound for uniform heterogeneous multicores and then illustrate its non-monotonicity, where the bound may decrease with more deployed cores. Following the insights obtained from the bound analysis, taking the system heterogeneity into consideration, we propose a Synchronization-Aware Task Partitioning Algorithm for Heterogeneous Multicores (SA-TPA-HM)). Several resource-guided and heterogeneity-oriented mapping heuristics are incorporated to reduce the negative impacts of blocking interferences for better schedulability performance of tasks and balanced workload distribution across cores. The extensive simulation results show that SA-TPA-HM can obtain the schedulability ratios approximate to an Integer Non-Linear Programming--based solution, and much higher (e.g., 60% more) in contrast to the existing partitioning algorithms targeted at homogeneous multicores. The measurement results in Linux kernel further reveal the practical viability of SA-TPA-HM that can experience lower runtime overhead (e.g., 15% less) when compared to other mapping schemes.

Several recent studies have investigated the virtual machine (VM) provisioning problem for requests with time constraints (deadlines) in cloud systems. These studies typically assumed that a request is associated with a single execution time when running on VMs with a given resource demand. In this paper, we consider modern applications that are normally implemented with generic frameworks that allow them to execute with various numbers of threads on VMs with different resource demands. For such applications, it is possible for the users to specify multiple execution options (MEOs) for a request where each execution option is represented by a certain number of VMs with some resources to run the application and its corresponding execution time. We investigate the problem of virtual machine provisioning for such time-sensitive requests with MEOs in resource-constrained clouds. By incorporating the MEOs of requests, we propose several novel and flexible VM provisioning schemes that carefully balance resource usage efficiency, input workloads and request deadlines with the objective of achieving higher resource utilization and system benefits. We evaluated the proposed MEO-aware schemes on various workloads with both benchmark requests and synthetic requests. The results show that our MEO-aware algorithms outperform the state-of-the-art schemes that consider only a single execution option of requests by serving up to 38% more requests and achieving up to 27% more benefits.

Heterogeneous multicore processors have become popular computing engines for modern embedded real-time systems recently. However, there is rather limited research on the scheduling of real-time tasks running on heterogeneous multicore systems with shared resources. Note that, different partitionings of tasks upon heterogeneous cores can affect the synchronization overheads of tasks (and thus the system schedulability). Focusing on the partitioned-EDF scheduling and resource access protocol MSRP (Multiprocessor Stack Resource Policy), this paper proposes an effective synchronization aware task partitioning algorithm for heterogeneous multicores (SATPA-HM). Several resource-oriented heuristics are exploited to tighten the bound on the synchronization costs of tasks through dynamic task prioritization and to find an appropriate core for each task that can minimize the system utilization increment. The simulation results show that our proposed SA-TPA-HM scheme can achieve higher acceptance ratio (e.g., 60% more), when compared to the existing schemes designed for homogeneous multicores.

For a set of real-time tasks that have mixed preference of being executed at early or late times before their deadlines, we have recently studied both earliest-deadline based and fixed-priority preference-oriented (PO) scheduling algorithms for uniprocessor systems. In this work, focusing on multiprocessor real-time systems, we study the foundational guidelines to design partition-based PO scheduling algorithms for tasks with mixed preference requirements. In particular, through a concrete example, we illustrate that the harmonicity of tasks' periods should be incorporated when making scheduling decisions in addition to their execution preferences to obtain favorable schedules that better fulfill tasks' preference requirements. Based on such guidelines, we design a period-aware preference-oriented (PAPO) partitioned scheduling algorithm and discuss several variations by considering harmonicity as well as utilization of tasks.

This paper presents the design and evaluation of a novel project designed to facilitate the learning of memory management concepts and interactions between different components. This project removes the complexity of a full or specific operating system by implementing memory management inside the user space. Evaluation results show that the mean exam scores improved by about 29% to 34%. On average, the total code size is less than 300 lines and time spent working on this project is under 17 hours. Therefore, this project is beneficial in helping students learn memory management while maintaining a reasonable project workload.

In mixed-criticality (MC) systems, multiple activities with various certification requirements (thus with different criticality levels) can co-exist on shared hardware platforms, where multicore processors have emerged as the de facto computing engines. In this paper, by using the partitioned earliest-deadline-first with virtual deadlines (EDF-VDs) scheduler for a set of periodic MC tasks running on multicore systems, we derive a criticality-aware utilization bound for efficient feasibility tests and then identify its characteristics. Our analysis shows that the bound increases with increasing number of cores and decreasing system criticality level. We show that, since the utilizations of MC tasks at different criticality levels can vary considerably, the utilization contribution of a task on different cores may have large variations and thus can significantly affect the system schedulability under the EDF-VD scheduler. Based on these observations, we propose a novel and efficient criticality-aware task partitioning algorithm (CA-TPA) to compensate for the inherent pessimism of the utilization bound. In order to improve the system schedulability, the task priorities are determined according to their utilization contributions to the system in CA-TPA. Moreover, by analyzing the utilization variations of tasks at different levels, we develop several heuristics to minimize the utilization increment and balance the workload on cores. The simulation results show that the CA-TPA scheme is very effective in achieving higher schedulability ratio and yielding balanced workloads. The actual implementation in Linux operating system further demonstrates the applicability of CA-TPA with lower run-time overhead, compared to the existing partitioning schemes.

The papers in this special section focus on low power dependable computing systems (LPDC). Faults (especially transient faults that lead to soft errors) have become more common due to the miniaturization of computing systems with continuously scaled technology sizes. Thus, it is imperative for most modern computing systems to deploy one or more types of fault-tolerance techniques. Traditionally, fault tolerance has been achieved through various error reduction, detection, and recovery techniques at different levels of the hardware/software stacks (e.g., circuit, architecture, operating systems, compiler, and application software), which generally incur power and energy overheads. Given the fact that energy has become a first-class system resource (especially for batterypowered mobile and IoT devices), it is important to understand the interdependencies between system reliability and power/energy consumption, and further investigate techniques that can address their tradeoffs. This special issue on Low-Power Dependable Computing (LPDC) seeks to tackle these challenges by exploring novel and bold ideas to achieve energy-efficient reliable computations in modern computing systems.

Standby-sparing systems where one processor is used as primary while another one is deployed as spare have been used to provide high reliability to real-time embedded systems. To reduce the energy consumption, the primary uses DVFS while the spare employs DPM to postpone the backup tasks. In this paper, we re-visit the problem for heterogeneous multicore systems that include both high-performance and low-power cores. We identify and address the two main dimensions of the problem, namely, what type of core to use as the primary or backup, and how to make frequency assignments on the primary to maximize energy savings.

Cost savings are very critical in modern heterogeneous computing systems, especially in embedded systems. Task scheduling plays an important role in cost savings. In this article, we tackle the problem of scheduling tasks on heterogeneous multicore embedded systems with the constraints of time and resources for minimizing the total cost, while considering the communication overhead. This problem is NP-hard and we propose several heuristic techniques— ISGG , RLD , and RLDG —to address the problem. Experimental results show that the proposed algorithms significantly outperform the existing approaches in terms of cost savings.

Cyber-physical-social systems (CPSS), an emerging computing paradigm, have attracted intensive attentions from the research community and industry. We are facing various challenges in designing secure, reliable, and user-satisfied CPSS. In this article, we consider these design issues as a whole and propose a system-level design optimization framework for CPSS design where energy consumption, security-level, and user satisfaction requirements can be fulfilled while satisfying constraints for system reliability. Specifically, we model the constraints (energy efficiency, security, and reliability) as the penalty functions to be incorporated into the corresponding objective functions for the optimization problem. A smart office application is presented to demonstrate the feasibility and effectiveness of our proposed design optimization approach.

Many algorithms have recently been studied for scheduling mixed-criticality (MC) tasks. However, most existing MC scheduling algorithms guarantee the timely executions of high-criticality (HC) tasks at the expense of discarding low-criticality (LC) tasks, which can cause serious service interruption for such tasks. In this work, aiming at providing guaranteed services for LC tasks, we study an elastic mixed-criticality (E-MC) task model for dual-criticality systems. Specifically, the model allows each LC task to specify its maximum period (i.e., minimum service level) and a set of early-release points. We propose an early-release (ER) mechanism that enables LC tasks to be released more frequently and thus improve their service levels at runtime, with both conservative and aggressive approaches to exploiting system slack being considered, which is applied to both earliest deadline first (EDF) and preference-oriented earliest-deadline schedulers. We formally prove the correctness of the proposed early-release--earliest deadline first scheduler on guaranteeing the timeliness of all tasks through judicious management of the early releases of LC tasks. The proposed model and schedulers are evaluated through extensive simulations. The results show that by moderately relaxing the service requirements of LC tasks in MC task sets (i.e., by having LC tasks’ maximum periods in the E-MC model be two to three times their desired MC periods), most transformed E-MC task sets can be successfully scheduled without sacrificing the timeliness of HC tasks. Moreover, with the proposed ER mechanism, the runtime performance of tasks (e.g., execution frequencies of LC tasks, response times, and jitters of HC tasks) can be significantly improved under the ER schedulers when compared to that of the state-of-the-art earliest deadline first—virtual deadline scheduler.

In mixed-criticality (MC) system, diverse application activities with various certification requirements (different criticality) can share a computing platform, where multicore processors have emerged as the prevailing computing engines. Focusing on the problem of resource access contention in multicore MC systems, we analyze the synchronization issues and blocking characteristics of the Multiprocessor Stack Resource Policy (MSRP) with both priority and criticality inversions among MC tasks being considered. We develop the first criticality-aware utilization bound under partitioned Earliest Deadline First (EDF) and MSRP by taking the worst case synchronization overheads of tasks into account. The non-monotonicityof the bound where it may decrease when more cores are deployed is identified, which can cause anomalies in the feasibility tests. With the objective to improve system schedulability, a novel criticality-cognizant and resource-oriented analysis approach is further studied to tighten the bound on the synchronization overheads for MC tasks scheduled under partitioned EDF and MSRP. The simulation results show that the new analysis approach can effectively reduce the blocking times for tasks (up to 30 percent) and thus improve the schedulability ratio (e.g., 10 percent more). The actual implementation in Linux kernel further shows the practicability of partitioned-EDF with MSRP (with run-time overhead being about 3 to 7 percent of the overall execution time) for MC tasks running on multicores with shared resources.

On emerging multicore systems, task replication is a powerful way to achieve high reliability targets. In this paper, we consider the problem of achieving a given reliability target for a set of periodic real-time tasks running on a multicore system with minimum energy consumption. Our framework explicitly takes into account the coverage factor of the fault detection techniques and the negative impact of Dynamic Voltage Scaling (DVS) on the rate of transient faults leading to soft errors. We characterize the subtle interplay between the processing frequency, replication level, reliability, fault coverage, and energy consumption on DVS-enabled multicore systems. We first develop static solutions and then propose dynamic adaptation schemes in order to reduce the concurrent execution of the replicas of a given task and to take advantage of early completions. Our simulation results indicate that through our algorithms, a very broad spectrum of reliability targets can be achieved with minimum energy consumption thanks to the judicious task replication and frequency assignment.

The scheduling for mixed-criticality (MC) systems, where multiple activities have different certification requirements and thus different criticality on a shared hardware platform, has recently become an important research focus. In this work, considering that multicore processors have emerged as the de-facto platform for modern embedded systems, we propose a novel and efficient criticality-aware task partitioning algorithm (CA-TPA) for a set of periodic MC tasks running on multicore systems. We employ the state-of-the art EDF-VD scheduler on each core. Our work is based on the observation that the utilizations of MC tasks at different criticality levels can have quite large variations, hence when a task is allocated, its utilization contribution on different processors may vary by large margins and this can significantly affect the schedulability of tasks. During partitioning, CA-TPA sorts the tasks according to their utilization contributions on individual processors. Several heuristics are investigated to balance the workload on processors with the objective of improving the schedulability of tasks under CA-TPA. The simulation results show that our proposed CA-TPA scheme is effective, giving much higher schedulability ratios when compared to the classical partitioning schemes.

For mixed-criticality (MC) systems, recent studies show that it can be important to provide continuous (albeit degraded) services for low-critical (LC) tasks even in the high running mode. In this paper, focusing on dual-criticality systems, we study a mode-switch fixed-priority (MS-FP) scheduler for a set of dual-rate mixed-criticality (DR-MC) tasks, where each LC task can have a pair of small and large periods to represent its service requirements in the low (LO) and high (HI) running modes, respectively. Moreover, DR-MC tasks may adjust their priorities at the mode-switch point for better system schedulability. By extending the response time analysis (RTA) technique for MC systems, we first derive the schedulability conditions for a set of DR-MC tasks under the MS-FP scheduler with mode transition being considered. Then, we investigate how to select periods and priorities of DR-MC tasks to optimize their control performance and formulate it as a Non-Linear Optimization problem. We propose an efficient heuristic for a simplified optimization problem based on Branch & Bound Search Tree (BBST) technique. The effectiveness of the proposed heuristic and the MS-FP scheduler with DR-MC task model is illustrated through one case study with four tasks and compared against the Ipopt solutions.

Clouds are becoming an important platform for scientific workflow applications. However, with many nodes being deployed in clouds, managing reliability of resources becomes a critical issue, especially for the real-time scientific workflow execution where deadlines should be satisfied. Therefore, fault tolerance in clouds is extremely essential. The PB (primary backup) based scheduling is a popular technique for fault tolerance and has effectively been used in the cluster and grid computing. However, applying this technique for real-time workflows in a virtualized cloud is much more complicated and has rarely been studied. In this paper, we address this problem. We first establish a real-time workflow fault-tolerant model that extends the traditional PB model by incorporating the cloud characteristics. Based on this model, we develop approaches for task allocation and message transmission to ensure faults can be tolerated during the workflow execution. Finally, we propose a dynamic fault-tolerant scheduling algorithm, FASTER, for realtime workflows in the virtualized cloud. FASTER has three key features: 1) it employs a backward shifting method to make full use of the idle resources and incorporates task overlapping and VM migration for high resource utilization, 2) it applies the vertical/horizontal scaling-up technique to quickly provision resources for a burst of workflows, and 3) it uses the vertical scaling-down scheme to avoid unnecessary and ineffective resource changes due to fluctuated workflow requests. We evaluate our FASTER algorithm with synthetic workflows and workflows collected from the real scientific and business applications and compare it with six baseline algorithms. The experimental results demonstrate that FASTER can effectively improve the resource utilization and schedulability even in the presence of node failures in virtualized clouds.

Network-on-Chip (NoC) has emerged as interconnect paradigm in state-of-the-art multi/many core architectures. Voltage and frequency island (VFI) was recently adopted as an effective energy management technique for large scale multicore chip designs. Focusing on NoCand VFI-based multi/many core real-time systems with Dynamic Voltage and Frequency Scaling (DVFS) capability, we study both static and dynamic contention-aware energy management schemes for task set with precedence relationships and a common deadline. First, our static schemes utilize two approaches with contention awareness to obtain the mapping of tasks to cores together with scheduling of communications on NoC for minimizing makespan, and thus can potentially lower uniform scaled frequency for cores and links while meeting the timeliness. Next, different from other existing schemes, by incorporating the latency due to network congestions into the analysis, our dynamic contention-aware energy management schemes perform the allocation of feasible slack to tasks and communications simultaneously for further energy savings, subject to common voltage and frequency limitations of VFI and timing constraints of task set. The results through extensive simulations and case studies show that, compared to heuristicbased and INLP-based task mapping solutions (with pessimistic estimation of communication contention), our static scheme can obtain better energy savings (e.g., 25 percent more). The results also show that our dynamic scheme can save up to 45 percent more energy compared to our static scheme under deadline guarantee, while the online scheme ignoring the traffic congestions in NoC can result in serious deadline violation and usually more energy consumption (e.g., 15 percent more).

Most real-time scheduling algorithms prioritize tasks solely based on their timing parameters and cannot effectively handle them when they have different execution preferences. In this paper, for a set of periodic tasks, where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP), we investigate preference-oriented fixed-priority scheduling algorithms. Specifically, following the idea in dual-priority scheduling, we derive promotion times for ALAP tasks (only). Then, we devise a dual-queue based fixed-priority scheduling algorithm that retains ALAP tasks in the waiting queue until their promotion times to delay their executions while putting ASAP tasks into the ready queue immediately once they arrive for early execution. We also investigate online techniques to further expedite (delay) the executions of ASAP (ALAP) tasks, respectively. Our evaluation results show that the dual-queue technique with ALAP tasks' promotion times can effectively address the execution preferences of both ASAP and ALAP tasks, which can be further improved at runtime with wrapper-task based slack management. Our technique is shown to yield clear advantages over a simple technique that periodically inserts idle intervals to the schedule before ALAP tasks are executed.

In this paper, we consider the feasibility problem of a set of real-time jobs which may be subject to a fault burst during execution. A fault burst represents a time interval during which multiple jobs may incur faults; hence multiple recoveries may be needed. We show that determining the feasibility of a real-time system, which may be subject to a fault burst that may last at most Δ time units, is an NP-Hard problem even when the exact position of the fault burst is known a priori. However, in a practical system, the fault burst may occur at any arbitrary and unpredictable time. We develop feasibility analysis by assuming multiple recovery strategy where, in addition to the job at the end of which the fault is detected, all preempted tasks are also re-executed. We formally characterize the overhead that a scheduler incurs due to a fault burst and present a generic recovery strategy, called Δ-idling, that is shown to minimize the worst-case overhead for any priority-driven scheduling algorithm. Next, we analyze periodic task systems. We show that the preemptive EDF policy, when coupled with Δ-idling, provides the highest possible utilization bound ½ (1 - Δ over Pmin), where Pminis the smallest task period. We also present an empirical evaluation of the EDF policy with Δ-idling over synthetically generated task sets, and show that it offers a clear improvement over the naive EDF policy that triggers the recovery tasks as soon as an error is detected.

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

In real-time systems, both scheduling theory and resource access protocols have been studied extensively. However, there is very limited research on scheduling algorithms for real-time systems with shared resources, where the problem becomes more prominent with the emergence of multicore processors. In this paper, focusing on partitioned-EDF scheduling and MSRP resource access protocol, we study the utilization bound and efficient task mapping schemes for a set of periodic real-time tasks that access shared resources in multiprocessor/multicore systems. Specifically, with synchronization overhead being considered, we illustrate the schedulability anomaly for such systems. We develop the first synchronization-cognizant utilization bound and further analyze its non-monotonicity where the bound can decrease when more processors are deployed. Then, we show that finding the optimal mapping for tasks with shared resources is NP-hard. Based on a novel approach that iteratively tightens the synchronization overhead, we propose two efficient synchronization-cognizant task mapping algorithms (SC-TMA) with the goal of achieving better schedulability and balanced workload on deployed processors. Finally, the proposed SC-TMA schemes are evaluated through extensive simulations with synthetic tasks. The results show that, the schedulability ratio and (average) system load under SC-TMA are close to that of an INLP (Integer Non-Linear Programming) based solution for small task systems. When compared to the existing task mapping algorithms, SC-TMA obtain much better schedulability ratio and lower/balanced workload on all processors.

To address the service abrupt problem for low-criticality tasks in existing mixed-criticality scheduling algorithms, we study an Elastic Mixed-Criticality (E-MC) task model, where the key idea is to have variable periods (i.e., service intervals) for low-criticality tasks. The minimum service requirement of a low-criticality task is ensured by its largest period. However, at runtime low-criticality tasks can be released early by exploiting the slack time generated from the over-provisioned execution time for high-criticality tasks to reduce their service intervals and thus improve their service levels. We propose an Early-Release EDF (ER-EDF) scheduling algorithm, which can judiciously manage the early release of low-criticality tasks without affecting the timeliness of high-criticality tasks. Compared to the state-of-the-art EDF-VD scheduling algorithm, our simulation results show that the ER-EDF can successfully schedule much more task sets. Moreover, the achieved execution frequencies of low-criticality tasks can also be significantly improved under ER-EDF.

The Standby-Sparing (SS) technique has been previously explored to improve energy efficiency while providing fault tolerance in dual-processor real-time systems. In this paper, by considering both transient and permanent faults, we develop energy-efficient fault tolerance techniques for real-time systems deploying an arbitrary number of identical processors. First, we study the Paired-SS technique, where processors are organized as groups of two (i.e., pairs) and SS is applied within each pair of processors directly after partitioning tasks to the pairs. Then, we propose a Generalized-SS technique that partitions processors into two groups containing primary and secondary processors, respectively. The main and backup copies of tasks are executed on the primary and secondary processors under the partitioned-EDF and partitioned-EDL scheduling policies, respectively. The objective is to reduce the overlapped executions of the main and backup copies in order to improve energy savings. Our experimental evaluations show that, for a given system with fixed number of processors, typically there exists a configuration of primary and secondary processors under the Generalized-SS technique that can lead to better energy savings when compared to the Paired-SS technique.

The Elastic Mixed-Criticality (E-MC) task model and an Early-Release EDF (ER-EDF) scheduling algorithm have been studied to address the service interruption problem for low-criticality tasks in uniprocessor systems. In this paper, focusing on multicore systems, we first investigate the schedulability of E-MC tasks under partitioned-EDF (P-EDF) by considering various task-to-core mapping heuristics. Then, with and without task migrations being considered, we study both global and local early-release schemes. Compared to the state-of-the-art Global EDF-VD scheduler, the superior performance of the proposed schemes in terms of improving the service levels of low-criticality tasks is confirmed through extensive simulations.

The traffic pattern has significant impact on the performance of network-on-chip. Many recent studies have shown that multimedia applications can be supported in on-chip interconnects. Driven by the motivation of evaluating on-chip interconnects in multimedia embedded systems, a new analytical model is proposed to investigate the performance of the fat-tree based on-chip interconnection network under bursty multimedia traffic and nonuniform message destinations. Extensive simulation experiments are conducted to validate the accuracy of the model, which is then adopted as a cost-efficient tool to investigate the effects of bursty multimedia traffic with nonuniform destinations on the network performance.

While Dynamic Voltage Scaling (DVS) remains as a popular energy management technique for modern computing systems, recent research has identified significant and negative impacts of voltage scaling on system reliability. To preserve system reliability under DVS settings, a number of reliability-aware power management (RA-PM) schemes have been recently studied. However, the existing RA-PM schemes normally schedule a separate recovery for each task whose execution is scaled down and are rather conservative. To overcome such conservativeness, we study in this article novel RA-PM schemes based on the shared recovery (SHR) technique. Specifically, we consider a set of frame-based real-time tasks with individual deadlines and a common period where the precedence constraints are represented by a directed acyclic graph (DAG). We first show that the earliest deadline first (EDF) algorithm can always yield a schedule where all timing and precedence constraints are met by considering the effective deadlines of tasks derived from as late as possible (ALAP) policy, provided that the task set is feasible. Then, we propose a shared recovery based frequency assignment technique (namely SHR-DAG) and prove its optimality to minimize energy consumption while preserving the system reliability. To exploit additional slack that arises from early completion of tasks, we also study a dynamic extension for SHR-DAG to improve energy efficiency and system reliability at runtime. The results from our extensive simulations show that, compared to the existing RA-PM schemes, SHR-DAG can achieve up to 35% energy savings, which is very close to the maximum achievable energy savings. More interestingly, our extensive evaluation also indicates that the new schemes offer non-trivial improvements on system reliability over the existing RA-PM schemes as well.

The negative impact of the popular energy management technique Dynamic Voltage and Frequency Scaling (DVFS) on the reliability of real-time embedded systems, in terms of increased transient fault rates, has been recently identified. As a result, recent research literature includes a number of solutions within the so-called Reliability-Aware Power Management (RA-PM) framework, where the aim is to preserve the system's original reliability. In this research effort, we propose a more general framework where the aim is to achieve arbitrary reliability levels that may vary for each periodic task. A critical component of our solution is the use of dynamically allocated recoveries: we show that providing a relatively modest recovery allowance to a given periodic task helps to achieve surprisingly high reliability levels as long as these allowances can be reclaimed on-demand during the hyper period. We propose a pseudo-polynomial time feasibility test, as well as static and dynamic algorithms to determine the recovery allowance and frequency assignments to minimize energy consumption while satisfying timing and reliability constraints. Our experimental evaluation points to the significant gain potential of the new framework in terms of both energy and reliability figures.

Voltage and frequency island (VFI) was recently adopted as an effective energy management technique for multicore processors. For a set of periodic real-time tasks that access shared resources running on a VFI-based multicore system with dynamic voltage and frequency scaling (DVFS) capability, we study both static and dynamic synchronization-aware energy management schemes. First, based on the enhanced MSRP resource access protocol with a suspension mechanism, we devise a synchronization-aware task mapping heuristic for partitioned-EDF scheduling, which assigns tasks that access similar set of resources to the same core to reduce the synchronization overhead and thus improve schedulability. Then, static schemes that assign uniform and different scaled frequencies for tasks on different VFIs are studied. To further exploit dynamic slack, we propose an integrated synchronization-aware slack management framework to appropriately reclaim, preserve, release and steal slack at runtime to slow down the execution of tasks subject to the common voltage/frequency limitation of VFIs and timing/synchronization constraints of tasks. Taking the additional delay due to task synchronization into consideration, the new scheme allocates slack in a fair manner and scales down the execution of both noncritical and critical sections of tasks for more energy savings. Simulation results show that, the synchronization-aware mapping can significantly improve the schedulability of tasks. The energy savings obtained by the static scheme with different frequencies for tasks on different VFIs is close to that of an optimal Integer Nonlinear Programming (INLP) solution. Moreover, compared to the simple extension of existing solutions for uniprocessor systems, our schemes can obtain much better energy savings (up to 40 percent) with comparable DVFS overhead.

DVFS remains an important energy management technique for embedded systems. However, its negative impact on transient fault rates has been recently shown. In this paper, we propose the Generalized Shared Recovery (GSHR) technique to optimally use the DVFS technique in order to achieve a given reliability goal for real-time embedded applications. Our technique determines the optimal number of recoveries to deploy as well as task-level processing frequencies to minimize the energy consumption while achieving the reliability goal and meeting the timing constraints. The recoveries may be shared among tasks, improving the prospects of DVFS compared to existing reliability-aware power management frameworks. The experimental evaluation points to the close-to-optimal energy savings of our proposed technique.

In this paper, we present an energy-aware standby-sparing technique for periodic real-time applications. A standby-sparing system consists of a primary processor where the application tasks are executed using Dynamic Voltage Scaling (DVS) to save energy, and a spare processor where the backup tasks are executed at maximum voltage/frequency, should there be a need. In our framework, we employ Earliest-Deadline-First (EDF) and Earliest-Deadline-Late (EDL) scheduling policies on the primary and spare CPUs, respectively. The use of EDL on the spare CPU allows delaying the backup tasks on the spare CPU as much as possible, enabling energy savings. We develop static and dynamic algorithms based on these principles, and evaluate their performance experimentally. Our simulation results show significant energy savings compared to existing reliability-aware power management (RAPM) techniques for most execution scenarios.

Cluster scheduling, where processors are grouped into clusters and the tasks that are allocated to one cluster are scheduled by a global scheduler, has attracted attention in multiprocessor real-time systems research recently. In this paper, by adopting optimal global schedulers within each cluster, first we investigate the worstcase utilization bound for cluster scheduling. Specifically, for a system with m homogeneous clusters where each cluster has k processors, we show that the worstcase achievable system utilization is (⌊k/α⌋·m+1)/(⌊k/α⌋+1) · k, where a is the maximum utilization for the periodic tasks considered. By focusing on an efficient optimal global scheduler, namely the boundary-fair (Bfair) algorithm, we propose a period-aware partitioning heuristic aiming at reducing the scheduling overhead. Simulation results show that the percentage of task sets that can be scheduled is significantly improved under cluster scheduling even for small-size clusters (e.g., k = 2). Moreover, the proposed period-aware partitioning heuristic markedly reduces the scheduling overhead of cluster scheduling with Bfair.

Recently, the negative effect of the popular power management technique Dynamic Voltage and Frequency Scaling (DVFS) on the system reliability has been identified. As a result, various reliability-aware power management (RAPM) schemes have been studied for uniprocessor real-time systems. In this paper, we investigate global scheduling-based RAPM (G-RAPM) schemes for a set of frame-based real-time tasks running on a homogeneous multiprocessor system. An important dimension of the problem is how to select the appropriate subset of tasks for energy and reliability management (i.e., schedule a recovery for each selected task and scale down their executions). We show that making this decision optimally (i.e., the static G-RAPM problem) is NP-hard. Then we propose two efficient G-RAPM heuristics, which rely on local and global task selections, respectively. Moreover, to reclaim dynamic slack generated at runtime, we extend the slack-sharing based global dynamic power management scheme to the reliability-aware settings. The proposed schemes are evaluated through extensive simulations. The results show that our static G-RAPM heuristics can preserve system reliability while achieving significant energy savings (within 3% of an upper bound for most cases). Moreover, G-RAPM with global task selection provides better opportunities for dynamic slack reclamation and up to 15% more energy savings can be obtained at runtime compared to that of local task selection.

Recent studies show that voltage scaling, which is an efficient energy management technique, has a direct and negative effect on system reliability because of the increased rate of transient faults (e.g., those induced by cosmic particles). In this article, we propose energy management schemes that explicitly take system reliability into consideration. The proposed reliability-aware energy management schemes dynamically schedule recoveries for tasks to be scaled down to recuperate the reliability loss due to energy management. Based on the amount of available slack, the application size, and the fault rate changes, we analyze when it is profitable to reclaim the slack for energy savings without sacrificing system reliability. Checkpoint technique is further explored to efficiently use the slack. Analytical and simulation results show that the proposed schemes can achieve comparable energy savings as ordinary energy management schemes (which are reliability-ignorant) while preserving system reliability. The ordinary energy management schemes that ignore the effects of voltage scaling on fault rate changes could lead to drastically decreased system reliability.

The dynamic voltage and frequency scaling (DVFS) technique is the basis of numerous state-of-the-art energy management schemes proposed for real-time embedded systems. However, recent research has illustrated the alarmingly negative impact of DVFS on task and system reliability. In this paper, we consider the problem of assigning processing frequencies to a set of real-time tasks in order to maximize the overall reliability, under given time and energy constraints. First, under the frame-based task model, we formulate the problem as a nonlinear optimization problem and show how to obtain the static optimal solution. Then, we propose online (dynamic) algorithms that detect early completions and adjust the task frequencies at runtime, to improve overall reliability. Furthermore, we extend these solutions to the periodic task model, with both static and dynamic solutions. All our solutions ensure that all timing constraints are met while the cumulative energy consumption of tasks does not exceed the given energy budget. Our simulation results indicate that our algorithms perform comparably to a clairvoyant optimal scheduler that knows the exact workload in advance.

While Dynamic Voltage Scaling (DVS) remains as a popular energy management technique for real-time embedded applications, recent research has identified significant and negative impact of voltage scaling on system reliability. For this reason, a number of reliability-aware power management (RA-PM) schemes were recently proposed to preserve the system reliability when DVS is used. In this paper, we propose a new approach, called the shared recovery (SHR) technique, to minimize the system-level energy consumption while still preserving the system’s original reliability. The main idea of the SHR technique is to avoid the offline allocation of separate recovery tasks to the scaled tasks by assigning a global/shared recovery block that can be used by any task at run-time. Our simulation results show that, compared to the existing RA-PM schemes, our scheme can achieve up to 35 % energy savings. Further, this performance is shown to be comparable to the maximum energy savings thatcanbeachievedbyanyalgorithm. Interestingly,ourextensive evaluation indicates that SHR offers also non-trivial gains over the previous algorithms on the reliability side. Further, a dynamic extension is proposed to improve energy and reliability management at run-time by reducing the size of the recovery block and re-using the slack that arises from early completions.

Mobile elements, which can traverse the deployment area and convey the observed data from static sensor nodes to a base station, have been introduced for energy efficient data collection in wireless sensor networks (WSNs). However, most existing solutions only plan a single path for the mobile element, which may lead to quick energy depletion for the sensor nodes that are far away from the path. In this paper, for data collection in WSNs, we study the multi-path planning (MPP) problem for the mobile element to prolong the lifetime of WSNs. Observing the intractability of the problem, two MPP heuristic schemes, namely fixed-K and adaptive-K, are proposed. The central idea of these schemes is to plan multiple paths and have the mobile element follow them in turn to balance the energy consumption on individual sensor nodes, thus extending the lifetime of WSNs. The proposed schemes are evaluated through extensive simulations. The results show that, compared to that of the single path solution, the multi-path approaches can extend the lifetime of WSNs by up to four times. Moreover, the adaptive-K scheme treats the sensor nodes more fairly with less variation on their energy consumptions.

Dynamic voltage and frequency scaling (DVFS) has been widely used to manage energy in real-time embedded systems. However, it was recently shown that DVFS has direct and adverse effects on system reliability. In this work, we investigate static and dynamic reliability-aware energy management schemes to minimize energy consumption for periodic real-time systems while preserving system reliability. Focusing on earliest deadline first (EDF) scheduling, we first show that the static version of the problem is NP-hard and propose two task-level utilization-based heuristics. Then, we develop a job-level online scheme by building on the idea of wrapper-tasks, to monitor and manage dynamic slack efficiently in reliability-aware settings. The feasibility of the dynamic scheme is formally proved. Finally, we present two integrated approaches to reclaim both static and dynamic slack at runtime. To preserve system reliability, the proposed schemes incorporate recovery tasks/jobs into the schedule as needed, while still using the remaining slack for energy savings. The proposed schemes are evaluated through extensive simulations. The results confirm that all the proposed schemes can preserve the system reliability, while the ordinary (but reliability-ignorant) energy management schemes result in drastically decreased system reliability. For the static heuristics, the energy savings are close to what can be achieved by an optimal solution by a margin of 5 percent. By effectively exploiting the runtime slack, the dynamic schemes can achieve additional energy savings while preserving system reliability.

The dynamic voltage scaling (DVS) technique is the basis of numerous state-of-the-art energy management schemes proposed for real-time embedded systems. However, recent research has illustrated the alarmingly negative impact of DVS on task and system reliability. In this paper, we consider the problem of processing frequency assignment to a set of real-time tasks in order to maximize the overall reliability, under given time and energy constraints. First, we formulate the problem as a non-linear optimization problem and show how to obtain the static optimal solution. Then, we propose on-line (dynamic) algorithms that detect early completions and adjust the task frequencies at run-time, to improve overall reliability. Our simulation results indicate that our algorithms perform comparably to a clairvoyant optimal scheduler that knows the exact workload in advance.

Reliability-aware power management (RAPM) schemes, which consider the negative effects of voltage scaling on system reliability, were recently studied to save energy while preserving system reliability. The existing RAPM schemes for periodic tasks may be, however, inherently unfair in that they can manage only some tasks at the expense of the other remaining tasks. In this work, we propose the flexible reliability-aware power management framework, which allows the management of all the tasks in the system, according to their assurance requirements. Optimally solving this problem is shown to be NP-hard in the strong sense and upper bounds on energy savings are derived. Then, by extending the processor demand analysis, a pseudo-polynomial-time static scheme is proposed for the "deeply red" recovery patterns. On-line schemes that manage dynamic slack for better energy savings and reliability enhancement are also discussed. The schemes are evaluated extensively through simulations. The results show that, compared to the previous RAPM schemes, the new flexible RAPM schemes can guarantee the assurance requirements for all the tasks, but at the cost of slightly decreased energy savings. However, when combined with dynamic reclaiming, the new schemes become as competitive as the previous ones on the energy dimension, while improving overall reliability.

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.

Considering the impact of the popular energy management technique Dynamic Voltage and Frequency Scaling (DVFS) on system reliability, the Reliability-Aware Power Management (RA-PM) problem has been recently explored to save energy while maintaining system reliability. In this work, focusing on Rate Monotonic Scheduling (RMS) policy, we study static RA-PM schemes for periodic realtime tasks. After showing the intractability of the problem, we focus on two widely-known feasibility tests for RMS (namely, the Liu-Layland bound and Time Demand Analysis) and propose a number of heuristics based on the priority-monotonic speed assignment. The heuristics are evaluated through extensive simulations.

The prominent energy management technique, dynamic voltage and frequency scaling (DVFS), was recently shown to have direct and adverse effects on system reliability. In this work, we investigate static and dynamic reliability-aware energy management schemes for a set of periodic real-time tasks to minimize energy consumption while preserving system reliability. Focusing on EDF scheduling, we first show that the static problem is NP-hard and propose two task-level utilization-based heuristics. Then, we develop a job-level dynamic (on-line) scheme by building on the idea of wrappertasks, to monitor and manage dynamic slack efficiently in reliability-aware settings. Our schemes incorporate recovery tasks/jobs into the schedule as needed for reliability preservation, while still using the remaining slack for energy savings. Simulation results show that all the proposed schemes can achieve significant energy savings while preserving the system reliability. Moreover, the energy savings of the static heuristics are close to those of the static optimal solution by a margin of 5%

With the continued scaling of CMOS technologies and reduced design margins, the reliability concerns induced by transient faults have become prominent. Moreover, the popular energy management technique dynamic voltage and frequency scaling (DVFS) has been shown to have direct and negative effects on reliability. In this work, for a set of real-time tasks, we focus on the slack allocation problem to minimize their energy consumption while preserving the overall system reliability. Building on our previous findings for a single real-time application where a recovery task was used to preserve reliability, we identify the problem of reliability-aware energy management for multiple tasks as NP-hard and propose two polynomial-time heuristic schemes. We also investigate the effects of on-chip/off-chip workload decomposition on energy management, by considering a generalized power model. Simulation results show that ordinary energy management schemes could lead to drastically decreased system reliability, while the proposed reliability-aware heuristic schemes are able to preserve the system reliability and obtain significant energy savings at the same time.

In this paper, we consider the system-wide energy management problem for a set of periodic real-time tasks running on a DVS-enabled processor. Our solution uses a generalized power model, in which frequency-dependent and frequency-independent power components are explicitly considered. Further, variations in power dissipations and on-chip/off-chip access patterns of different tasks are encoded in the problem formulation. Using this generalized power model, we show that it is possible to obtain analytically the task-level energy-efficient speed below which DVS starts to affect overall energy consumption negatively. Then, we formulate the system-wide energy management problem as a non-linear optimization problem and provide a polynomial-time solution. We also provide a dynamic slack reclaiming extension which considers the effects of slow-down on the system-wide energy consumption. Our experimental evaluation shows that the optimal solution provides significant (up to 50%) gains over the previous solutions that focused on dynamic CPU power at the expense of ignoring other power components

Abstract Power conservation has become a key design issue for many sys-tems, including clusters deployed for embedded systems, where

The slack time in real-time systems can be used by recovery schemes to increase system reliability as well as by frequency and voltage scaling techniques to save energy. Moreover, the rate of transient faults (i.e., soft errors caused, for example, by cosmic ray radiations) also depends on system operating frequency and supply voltage. Thus, there is an interesting trade-off between system reliability and energy consumption. This work first investigates the effects of frequency and voltage scaling on the fault rate and proposes two fault rate models based on previously published data. Then, the effects of energy management on reliability are studied. Our analysis results show that, energy management through frequency and voltage scaling could dramatically reduce system reliability, and ignoring the effects of energy management on the fault rate is too optimistic and may lead to unsatisfied system reliability.

Power aware computing has become popular, recently and many techniques have been proposed to manage processor energy consumption for traditional real-time applications. In this paper, we are concerned mainly with the AND/OR model of real-time applications that have different execution paths consisting of different tasks. The contribution of this paper is twofold. First, we propose a greedy slack stealing algorithm to deal with applications represented by AND/OR graphs and prove its correctness in terms of meeting the timing constraints. Then, using statistical information about the applications, we propose a few variations of speculative scheduling algorithms that intend to save energy by reducing the number of speed changes (and, thus, the overhead) while ensuring that the application meets its timing constraints. Some practical issues are also considered, such as shared memory access contention and idle energy consumption. The performance of the algorithms is analyzed with respect to processor energy savings. The results surprisingly show that the greedy slack stealing scheme is better than some speculative schemes and that the greedy scheme is good enough when a reasonable minimal speed exists in the system or when there are only a few (four to six) voltage/speed levels.

The Pfair algorithms are optimal for independent periodic real-time tasks executing on a multiple-resource system. However, they incur a high scheduling overhead by making scheduling decisions in every time unit to enforce proportional progress for each task. In this paper, we will propose a novel scheduling algorithm, boundary fair (BF), which makes scheduling decisions and enforces fairness to tasks only at period boundaries. The BF algorithm is also optimal in the sense that it achieves 100% system utilization. Moreover, by making scheduling decisions at period boundaries, BF effectively reduces the number of scheduling points. Theoretically, the BF algorithm has the same complexity as that of the Pfair algorithms. But, in practice, it could reduce the number of scheduling points dramatically (e.g., up to 75% in our experiments) and thus reduce the overall scheduling overhead, which is especially important for online scheduling.

The high power consumption of modern processors becomes a major concern because it leads to decreased mission duration (for battery-operated systems), increased heat dissipation, and decreased reliability. While many techniques have been proposed to reduce power consumption for uniprocessor systems, there has been considerably less work on multiprocessor systems. In this paper, based on the concept of slack sharing among processors, we propose two novel power-aware scheduling algorithms for task sets with and without precedence constraints executing on multiprocessor systems. These scheduling techniques reclaim the time unused by a task to reduce the execution speed of future tasks and, thus, reduce the total energy consumption of the system. We also study the effect of discrete voltage/speed levels on the energy savings for multiprocessor systems and propose a new scheme of slack reservation to incorporate voltage/speed adjustment overhead in the scheduling algorithms. Simulation and trace-based results indicate that our algorithms achieve substantial energy savings on systems with variable voltage processors. Moreover, processors with a few discrete voltage/speed levels obtain nearly the same energy savings as processors with continuous voltage/speed, and the effect of voltage/speed adjustment overhead on the energy savings is relatively small.

Power aware computing has become popular recently and many techniques have been proposed to manage the energy consumption for traditional real-time applications. We have previously proposed (2001) two greedy slack sharing scheduling algorithms for such applications on multi-processor systems. In this paper, we are concerned mainly with real-time applications that have different execution paths consisting of different number of tasks. The AND/OR graph model is used to represent the application data dependence and control flow. The contribution of this paper is twofold. First, we extend our greedy slack sharing algorithm for traditional applications to deal with applications represented by AND/OR graphs. Then, using the statistical information about the applications, we propose a few variations of speculative scheduling algorithms that intend to save energy by reducing the number of speed changes (and thus the overhead) while ensuring that the applications meet the timing constraints. The performance of the algorithms is analyzed with respect to energy savings. The results obtained show that the greedy scheme is better than some speculative schemes and that the greedy scheme is good enough when a reasonable minimal speed exists in the system.

The power consumption of modern high-performance processors is becoming a major concern because it leads to increased heat dissipation and decreased reliability. While many techniques have been proposed to reduce power consumption for uni-processors, there has been considerably less work on multi-processor systems. In this paper we focus on power-aware scheduling for multi-processor real-time systems. Based on the idea of slack sharing among processors, we propose two novel scheduling algorithms for task sets with and without precedence constraints. These scheduling techniques reclaim the time unused by a task to reduce the execution speed of future tasks, and thus reduce the total energy consumption of the system. Simulation results indicate that our algorithms achieve up to 60% energy savings on multi-processor systems with variable voltage processors.