This paper presents a unified formal framework, called ReTA, that allows users to definescheduling problemsusing a user-friendly domain-specific language (DSL) and automatically obtain response times of jobs in return. ReTA supports user-defined online scheduling policies (beyond work-conserving or priority-based scheduling) for heterogeneous computing resource types with multiple instances per type (e.g., multiple CPU cores, GPUs, DSPs, and FPGAs on one single chip), thus supporting global, partitioned, and clustered scheduling. In the current version of ReTA, we focus on non-preemptive periodic tasks as these are susceptible to scheduling anomalies and hence harder to analyze. ReTA performs response-time analysis by constructing atimed labeled transition system(TLTS) from the domain model as a basis for performing a reachability analysis enriched with efficient state-space reduction techniques. Our empirical evaluations show that ReTA identifies up to50 times more schedulable task setsthan fixed-point iteration-based analyses. With a runtime on the order of a few minutes, ReTA produces highly accurate resultstwo-orders of magnitude fasterthan an exact Timed Automata-based analysis in UPPAAL (e.g., for systems with 16 cores and 32 tasks).

A major requirement of safety-critical systems is high reliability at low power consumption. Dynamic voltage and frequency (v/f) scaling (DVFS) techniques are widely exploited to reduce power consumption. However, DVFS through downscaling v/f levels has a negative impact on the reliability of the tasks running on the cores, and through upscaling v/f levels has circuitlevel aging effects. To achieve high reliability in multicore safetycritical systems, task replication as a fault-tolerant technique is an established way to deal with the negative effect of downscaling v/f levels, but it may accelerate aging effects due to elevating the on-chip temperatures. In this paper, we propose an aging-aware task replication (called ATLAS) method that solves the problem of satisfying the desired reliability target for a set of periodic hard real-time tasks which are executed on a multicore system. The proposed method satisfies the reliability target of the tasks through updating the required number of replicas for each task at different years. We replicate the tasks through our proposed formulas such that the reliability target is satisfied. However, task replication increases the temperature of the system and accelerates aging. To decelerate aging, we attempt to reduce the temperature while mapping and scheduling the tasks. We have also developed a modified demand bound function (DBF) for our aging-aware task replication method to verify scheduling the realtime tasks. Compared to the existing state-of-the-art techniques, experimental results for safety-critical applications on different configurations of multicore systems demonstrate the efficiency and effectiveness of our proposed method. Experiments show that our proposed method improves schedulability on average by 16.1% and reduces the temperature on average by 7.4°C compared to state-of-the-art methods while meeting the system reliability target.

Real-time systems are commonly used in safety-critical applications which require tasks to be completed before their deadlines, even in the presence of faults. Thus, fault tolerance becomes essential to ensure a certain level of reliability in safety-critical real-time systems [1]. To achieve fault tolerance in computer systems, redundancy can be implemented either in space (spatial redundancy) or time (time redundancy) [2]. Unlike spatial redundancy which involves increasing hardware resources, time redundancy focuses on re-execution or multiple executions of software on the same hardware resources [3] and therefore is better suited for embedded systems with limited cost and size constraints that are subject to transient faults more often than permanent faults [2], [4].

While multicore real-time systems are extensively employed in the industry, research gaps still exist in developing a scalable analysis to find tight bounds on the worst-case response time (WCRT) of tasks scheduled by global preemptive scheduling policies. Additionally, the presence of release jitter poses a challenge where examining the earliest and latest release times may not derive WCRT. The existing analyses either provide very conservative bounds or face challenges in scaling to systems with numerous cores and tasks. This work provides preliminary foundations to derive tight WCRT bounds for tasks scheduled by global preemptive job-level fixed-priority scheduling policies (e.g., EDF and FP) on homogeneous multicore platforms by performing a reachability analysis using time-label-transition systems. Our solution uses 2 orders of magnitude less memory than UPPAAL and identifies on average 12% (up to 39%) more schedulable task sets than sufficient schedulability analyses (e.g., for systems with 4 cores and 10 tasks).

Abstract Response-time analysis (RTA) has been a means to evaluate the temporal correctness of real-time systems since the 1970 s. While early analyses were successful in capturing the exact upper bound on the worst-case response-time (WCRT) of systems with relatively simple computing platforms and task activation models, nowadays we see that most existing RTAs either become pessimistic or do not scale well as systems become more complex (e.g., parallel tasks running on a multicore platform). To make a trade-off between accuracy and scalability, recently, a new reachability-based RTA, called schedule-abstraction graph (SAG), has been proposed. The analysis is at least three orders of magnitude faster than other exact RTAs based on UPPAAL. However, it still has a fundamental limitation in scalability as it suffers from state-space explosion when there are large uncertainties in the timing parameters of the input jobs (e.g., large release jitters or execution-time variations). This could impede its applicability to large industrial use cases, or to be integrated with automated tools that explore alternative design choices. In this paper, we improve the scalability of the SAG analysis by introducing partial-order reduction rules that avoid combinatorial exploration of all possible scheduling decisions. We include systems with dependent and independent task execution models (i.e., with and without precedence constraint). Our empirical evaluations show that the proposed solution is able to reduce the runtime by five orders of magnitude and the number of explored states by 98% in comparison to the original SAG analysis. These achievements come only at a negligible cost of an over-estimation of 0.1% on the actual WCRT. We applied our solution on an automotive case study showing that it is able to scale to realistic systems made of hundreds of tasks for which the original analysis fails to finish.

Increasing the number of cores integrated on a single chip offers a great potential for the implementation of fault-tolerant techniques to achieve high reliability in real-time embedded systems. Checkpointing with rollback-recovery is a well-established technique to tolerate transient faults in multicore platforms. To consider the worst-case fault occurrence scenario, checkpointing technique requires to re-execute some parts of the tasks, and that might lead to simultaneous execution of task parts with high power consumptions, which eventually might result in a peak power increase beyond the thermal design power (TDP). Exceeding TDP can elevate on-chip temperatures beyond safe limits, and thereby triggering countermeasures that throttle down the voltage and frequency levels or power gate the cores. Such countermeasures might lead to violating task deadlines and degrading the system's reliability. To avoid such severe scenarios, it is inevitable to consider the impact of applying fault-tolerant techniques on the power consumption and prevent violating the power constraint of the chip, i.e., TDP. This paper presents for the first time, a peak-power-aware checkpointing (PPAC) technique that tolerates a given number of faults,k, while at the same time meets the power constraint in hard real-time embedded systems. To do this, our proposed technique (PPAC) adjusts the timing of the checkpoints, which have lower power consumption than the tasks to the execution time points that have power spikes beyond TDP. Moreover, PPAC exploits the available slack times on the cores to delay the execution of some tasks to avoid the remaining power spikes beyond TDP, which could not be mitigated by solely adjusting checkpoints. To evaluate our technique, we extend the state-of-the-art system-level simulator, gem5, with the state-of-the-art checkpointing module in Linux. Our experimental results show that our proposed technique is able to tolerate a given number of faults without exceeding the timing and power constraints in hard real-time embedded systems. The resulting peak power reduction achieved by our technique compared to state-of-the-art techniques is an average of 23%. Moreover, our technique employs the Dynamic Power Management (DPM) during the slack times resulting at runtime in the case of fault-free scenarios, which provides energy savings with an average of 17.28% and up to 61.1%.

Multicore platforms are becoming the dominant trend in designing Mixed-Criticality Systems (MCSs), which integrate applications of different levels of criticality into the same platform. A well-known MCS is the dual-criticality system that is composed of low-criticality and high-criticality tasks. The availability of multiple cores on a single chip provides opportunities to employ fault-tolerant techniques, such as N-Modular Redundancy (NMR), to ensure the reliability of MCSs. However, applying fault-tolerant techniques will increase the power consumption on the chip, and thereby on-chip temperatures might increase beyond safe limits. To prevent thermal emergencies, urgent countermeasures, like Dynamic Voltage and Frequency Scaling (DVFS) or Dynamic Power Management (DPM) will be triggered to cool down the chip. Such countermeasures, however, might not only lead to suspending low-criticality tasks, but also it might lead to violating timing constraints of high-criticality tasks. In order to prevent such severe scenarios, it is indispensable to consider a temperature constraint within the scheduling process of fault-tolerant MCSs. Therefore, this paper presents, for the first time, a thermal-aware scheduling scheme for fault-tolerant MCSs, named TherMa-MiCs. In particular, TherMa-MiCs, satisfies the temperature constraint jointly with the timing constraints of the high-criticality tasks, while attempting to maximize the QoS of low-criticality tasks under the predefined constraints. At the same time, a reliability target is satisfied by employing the well-known N-Modular Redundancy (NMR) fault-tolerant technique. Experimental results show that our proposed scheme meets the temperature and timing constraints, while at the same time, improving the QoS of low-criticality tasks, with an average of 44%.

Tackling the dark silicon problem in a heterogeneous multicore system, the temperature constraints across the system should be addressed carefully by assigning a proper set of tasks to a pool of the heterogeneous cores during the run-time. When such a system is utilized in a reliable/real-time application, the reliability/timing constraints of the application should also be augmented to the temperature constraints and make the tasks mapping problem more and more complex. To solve the mapping problem in such a situation, we propose READY; an online reliability- and deadline-aware mapping and scheduling algorithm for heterogeneous multicore systems. READY utilizes an adaptive power constraint (as a metric for temperature measurement) that is updated according to the number and position of the active cores on the chip. READY, first, attempts to meet the reliability target of the system by improving the reliability of each task. Then, it performs the mapping and scheduling of the tasks on cores of different islands, so that the peak power and timing constraints are met. The simulation results illustrate that while READY guarantees the timing constraints and meets reliability targets, it improves the peak-power-aware system schedulability (chip performance) by 23.77% (up to 40.69%).