Search

We consider a real-time system where a single processor with variable speed executes an infinite sequence of sporadic and independent jobs. We assume that job sizes and relative deadlines are bounded by C and Δ respectively. Furthermore, S max denotes the maximal speed of the processor. In such a real-time system, a speed selection policy dynamically chooses (i.e., on-line) the speed of the processor to execute the current, not yet finished, jobs. We say that an on-line speed policy is feasible if it is able to execute any sequence of jobs while meeting two constraints: the processor speed is always below S max and no job misses its deadline. In this paper, we compare the feasibility region of four on-line speed selection policies in single-processor real-time systems, namely Optimal Available (OA) (Yao et al. in IEEE annual foundations of computer science, 1995), Average Rate (AVR) (Yao et al. 1995), (BKP) (Bansal in J ACM 54:1, 2007), and a Markovian Policy based on dynamic programming (MP) (Gaujal in Technical Report hal-01615835, Inria, 2017). We prove the following results: (OA) is feasible if and only if S max ≥ C (h Δ - 1 + 1) , where h n is the n-th harmonic number ( h n = ∑ i = 1 n 1 / i ≈ log n ). (AVR) is feasible if and only if S max ≥ C h Δ . (BKP) is feasible if and only if S max ≥ e C (where e = exp (1) ). (MP) is feasible if and only if S max ≥ C . This is an optimal feasibility condition because when S max < C no policy can be feasible. This reinforces the interest of (MP) that is not only optimal for energy consumption (on average) but is also optimal regarding feasibility. [ABSTRACT FROM AUTHOR]

The power overhead of Networks-on-Chip (NoCs) becomes tremendous in high density Multiprocessor Systems-on-Chip (MPSoCs). Especially in hard real-time and safety-critical systems, power management mechanisms must be developed and efficiently adhered to real-time requirements. However, state-of-the-art solution typically induces a high timing overhead, thus challenging safety, or has limited power saving capabilities. Additionally, current power-gating mechanisms do not provide an upper bound of the latency overhead, and thus no timing guarantees. We propose a safe and enhanced approach for power-gating that allows a global and dynamic power management under timing guarantees, i.e., all deadlines of critical tasks are met. It introduces a control-layer to save power on the NoC data layer using multiple Power-Aware Traffic-Monitor (PATM) units, which apply knowledge of the global state of the system to efficiently save power on NoC routers even at high NoCs utilizations. To safely apply the PATMs in hard real-time systems while meeting the deadlines, we provide a formal worst-case timing analysis to derive PATMs upper bound latency overhead. Experimental results show that our approach efficiently reduces static power consumption, and provides scalability inducing very small area overhead. • The power overhead of Networks-on-Chip (NoCs) becomes tremendous in high density Multiprocessor Systems-on-Chip (MPSoCs). • A safe and enhanced approach for power-gating has been proposed, which allows a global and dynamic power management. • To safely apply our approach in hard real-time systems, we provide a formal worst-case timing analysis. • Experimental results, with a realistic application, indicate the efficiency of our approach compared with basic NoCs. • Our approach saves up to 81,4% and 79,13% of the static power of 4 × 4 and 8 × 8 NoCs, respectively. • Using synthetic workloads, our approach considerably saves power even at high NoCs utilizations, inducing small area penalty. [ABSTRACT FROM AUTHOR]

Advances in semiconductor technology have made integration of multiple processing cores into one single die a promising trend towards increasing processing performance, lowering power consumption, and increasing reliability for embedded systems. Multicore processors, due to their intrinsic redundancies, are good choices for critical embedded systems for which the reliability is a crucial component. In this paper, an aging-aware adaptive fault tolerance method for DVFS-enabled multicore processors is presented. The analytical results show 3 to 6 order of magnitude increase in reliability of the system without addition of cores or redundant software. By using an aging-aware approach, the proposed method contributes to less than 0.05% negative shift of the maximum frequency of every core in the processor. Experimental results also show that the method has less than 7% energy overhead as compared to the original mode of operation. [ABSTRACT FROM AUTHOR]

In this paper, a novel resource allocation approach dedicated to hard real-time systems with distinctive operational modes is proposed. The aim of this approach is to reduce the energy dissipation of the computing cores by either powering them off or switching them into energy-saving states while still guaranteeing to meet all timing constraints. The approach is illustrated with two industrial applications, an engine control management and an engine control unit. Moreover, the amount of data to be migrated during the mode change is minimised. Since the number of processing cores and their energy dissipation are often negatively correlated with the amount of data to be migrated during the mode change, there is some trade-off between these values, which is also analysed in this paper. [ABSTRACT FROM AUTHOR]

Scratchpad memory (SPM) is a promising on-chip memory choice in real-time and cyber-physical systems where timing is of the utmost importance. SPM has time-predictable characteristics since its data movement between the SPM and the main memory is entirely managed by software. One way of such management is dynamic management. In dynamic management of instruction SPMs, code blocks are dynamically copied from the main memory to the SPM at runtime by executing direct memory access (DMA) instructions. Code management techniques try to minimize the overhead of DMA operations by finding an allocation scheme that leads to efficient utilization. In this article, we present three function-level code management techniques. These techniques perform allocation at the granularity of functions, with the objective of minimizing the impact of DMA overhead to the worst-case execution time (WCET) of a given program. The first technique finds an optimal mapping of each function to a region using integer linear programming (ILP), whereas the second technique is a polynomial-time heuristic that is suboptimal. The third technique maps functions directly to SPM addresses, not using regions, which can further reduce the WCET. Based on ILP, it can also find an optimal mapping. We evaluate our techniques using the Mälardalen WCET suite, MiBench suite, and proprietary automotive applications from industry. The results show that our techniques can significantly reduce the WCET estimates compared to caches with the state-of-the-art cache analysis. [ABSTRACT FROM AUTHOR]

Over time, more and more systems are becoming mixed-criticality systems. As the complexity and size of these systems grow, computation/communication resources should be more efficient than with traditional systems. Time-triggered (TT) Ethernet is a communication infrastructure that enables the use of a single physical communication infrastructure for distributed mixed-criticality applications while providing timely determinism. TTEthernet distinguishes between two traffic categories: The standard event-triggered (ET) traffic and the TT traffic. The latter, for which higher priority is granted, is subject to strong timing guarantees because of strict-periodicity constraint which fixes start-time cycles of TT messages. In addition, messages in an ET Ethernet traffic, which are of lower priority, have a minimum time interval between their transmission. The focus of this paper is on the timing analysis of a TTEthernet traffic by proposing: (i) A feasibility condition allowing to assess the timing requirements of TT messages. (ii) A schedulability condition allowing to check the schedulability of ET messages by taking into account of TT messages scheduling and idle times. [ABSTRACT FROM AUTHOR]

Resource reservation is a technique that allows isolating applications from interfering among each other. In the most classic setting, this method requires the periodic allocation of a given budget of resource over time. However, in reality, the actual budget allocation may deviate from its ideal value. Examples of causes of this deviation are: the presence of a system tick, the usage of shared resources, the self-blocking on I/O operations, etc. Since control techniques are an effective mean to deal with uncertainties and disturbances, unknown at design time but bounded, in this paper we propose to use feedback to achieve the target budget allocation, which may have deviated due to on-line events. The proposed scheme, called Self-Adaptive Server (SAS), is described and analyzed. We prove that the controller gain, which maximizes the resource delivered to the application, is $$\frac{3-\sqrt{5}}{2}$$ . We also implemented the scheduler on a lightweight operating system for a microcontroller. Thanks to the extremely simple implementation, SAS servers are well suited for low-overhead resource isolation mechanisms with proved real-time guarantees. [ABSTRACT FROM AUTHOR]

This paper presents an optimal scheduling solution for a case of agents sharing a resource. The amount of resource can not satisfy all agents at once and in case of runout there is a penalty. Each agent randomly toggle its state between requiring and not requiring the resource. Using the knowledge of previous state and probability of change, the scheduling algorithm is able to calculate optimal number of concuring agents for one turn, that minimizes possibility of collision yet provides as much throughput as possible. Several different scheduling strategies are tested. The optimal solution adapts automatically to the value of probability of change. Further experiments show that optimality is retained if only the average probability of a set of agents is known. A case of practical application is provided. [ABSTRACT FROM AUTHOR]

This letter designs the performance enhancement guaranteed cache (PEG-C) for hard real-time systems. The PEG-C uses two counters to monitor the number of hits and misses at runtime to improve the average-case performance, while guaranteeing the worst-case execution time (WCET). Our experiments indicate that with a few preloaded instructions, a PEG instruction cache can achieve the same average-case performance as a regular instruction cache while ensuring performance enhancement even in the worst case. [ABSTRACT FROM PUBLISHER]

For advanced features of next generation vehicles, the real-time programs in automotive embedded systems are dramatically increasing. For such large volume program codes, this paper proposes a novel framework to use high-density and low-cost nonvolatile memory, i.e., NAND flash memory, as a low-cost means of storing and executing hard real-time programs. Regarding this, one challenge is that NAND flash memory allows only 2 KB page-based read operations not per-byte random accesses, which requires RAM as working storage for code executions. This paper proposes two solutions, i.e., partitioned RAM solution and shared RAM solution, that minimize the RAM size required to deterministically guarantee the deadlines of all the hard real-time tasks. The proposed solutions are verified with the actual real-time programs for unmanned autonomous driving. To the best of our knowledge, this is the first work that allows us to use NAND flash memory for hard real-time program executions with the minimal usage of RAM. [ABSTRACT FROM PUBLISHER]

Standby-sparing is one of the common techniques in order to design fault-tolerant safety-critical systems where the high level of reliability is needed. Recently, the minimization of energy consumption in embedded systems has attracted a lot of concerns. Simultaneous considering of high reliability and low energy consumption by DVS is a challenging problem in designing such a system, since using DVS has been shown to reduce the reliability profoundly. In this article, we have studied different schemes of standby-sparing systems from the energy consumption and reliability point of view. Moreover, we propose a new standby-sparing scheme which addresses both reliability and energy consumption jointly together. This scheme uses a simple energy management coupled with an online task scheduler which tries to dispatch those ready tasks which are expected to lead to high reliability and low energy consumption in the system. The effectiveness of the proposed scheme has been shown on TGFF under stochastic workloads. The results show 52% improvement on energy saving compared to the conventional hot standby-sparing system. Moreover, two orders of magnitude higher reliability is obtained on average, while preserving the same level of energy saving as compared to the state-of-the-art low-energy standby-sparing system (LESS). [ABSTRACT FROM AUTHOR]

Abstract: Due to the rapidly growing requirements of low power consumption and long battery life, the energy efficiency is becoming one of the most important concerns in the electronic system design. At the system level, the Dynamic Power Management (DPM) and Dynamic Voltage (and Frequency) Scaling (DVS) are two widely applied run-time techniques to adjust the trade-off between the system performance and power dissipation. In addition, the chip multi-core processor platforms have become the de-facto solution to cope with the continuous increase of the system complexity. In this article, we study the problem of combined application of DPM and DVS in the context of hard real-time systems on cluster-based multi-core processor platforms. We propose a heuristic algorithm based on the simulated annealing approach and introduce its online execution making the system adaptive to the run-time changes. Our approach considers multiple low power states with non-negligible state switching overhead. The experimental results show that our algorithm can significantly reduce the power consumption in comparison with existing algorithms. [Copyright &y& Elsevier]

In this paper, we focus on the pinwheel task model with a variable voltage processor with d discrete voltage/speed levels. We propose an intra-task DVS algorithm, which constructs a minimum energy schedule for k tasks in O(d+k log k) time. We also give an inter-task DVS algorithm with O(d+n log n) time, where n denotes th e number of jobs. Previous approaches solve this problem by generating a canonical schedule beforehand and adjusting the tasks' speed in O(dn log n) or O(n3) time. However, the length of a canonical schedule depends on the hyper period of those task periods and is of exponential length in general. In our approach, the tasks with arbitrary periods are first transformed into harmonic periods and then profile their key features. Afterward, an optimal discrete voltage schedule can be computed directly from those features. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a systematic methodology for designing a hard real-time multi-core testbed to validate and benchmark various rate monotonic scheduling (RMS)-based task allocation and scheduling schemes in energy consumption. The hard real-time multi-core testbed comprises Intel Core Duo T2500 processor with dynamic voltage scaling (DVS) capability and runs the Linux Fedora 8 operating system supporting soft real-time scheduling. POSIX threads API and Linux FIFO scheduling policy are utilized to facilitate the design and Dhrystone-based tasks are generated to verify the design. A LabView-based DAQ system is designed to measure the energy consumption of CPU and system board of the testbed. A case study of task allocation and scheduling algorithms is also presented that aim to optimize the schedule feasibility and energy consumed by the processor and memory module in the multi-core platform. The experience from the implementation is summarized to serve as potential guidelines for other researchers and practitioners. [Copyright &y& Elsevier]

Increasing integrated circuit (IC) power densities and temperatures may hamper multiprocessor system-on-chip (MPSoC) use in hard real-time systems. This paper formalizes the temperature-aware real-time MPSoC assignment and scheduling problem and presents an optimal phased steady-state mixed integer linear programming-based solution that considers the impact of scheduling and assignment decisions on MPSoC thermal profiles to directly minimize the chip peak temperature. We also introduce a flexible heuristic framework for task assignment and scheduling that permits system designers to trade off accuracy for running time when solving large problem instances. Finally, for task sets with sufficient slack, we show that inserting idle times between task executions can further reduce the peak temperature of the MPSoC quite significantly. [ABSTRACT FROM AUTHOR]

Abstract: Tasks in an embedded system are scheduled either preemptively or non-preemptively. In case of preemptive scheduling, interferences on the cache of the preempted and preempting task may extend the execution times. The corresponding delay is referred to as cache-related preemption delay (CRPD). Lee et al. presented a CRPD analysis using the concept of useful cache block (UCB): a cache block is useful if it may be in the cache before a program point and may be reused after this point. If a preemption occurs at that point, the number of additional cache misses is bounded by the number of UCBs. An upper bound on the CRPD of the whole task is thus given by the program point with the largest set of UCBs. In this article, we provide a survey of the state of the art techniques to bound the CRPD, based on, but not limited to UCBs. Based on this survey we present an alternative definition of UCBs to improve the CRPD bounds substantially. [Copyright &y& Elsevier]

This article presents a detailed discussion of LRE-TL (Local Remaining Execution-TL-plane), an algorithm that schedules hard real-time periodic and sporadic task sets with unconstrained deadlines on identical multiprocessors. The algorithm builds upon important concepts such as the TL-plane construct used in the development of the LLREF algorithm (Largest Local Remaining Execution First). This article identifies the fundamental TL-plane scheduling principles used in the construction of LLREF . These simple principles are examined, identifying methods of simplifying the algorithm and allowing it to handle a more general task model. For example, we identify the principle that total local utilization can never increase within any TL-plane as long as a minimal number of tasks are executing. This observation leads to a straightforward approach for scheduling task arrivals within a TL-plane. In this manner LRE-TL can schedule sporadic tasks and tasks with unconstrained deadlines. Like LLREF, the LRE-TL scheduling algorithm is optimal for task sets with implicit deadlines. In addition, LRE-TL can schedule task sets with unconstrained deadlines provided they satisfy the density test for multiprocessor systems. While LLREF has a O( n) runtime per TL-plane, LRE-TL's runtime is O( nlog n) per TL-plane. [ABSTRACT FROM AUTHOR]

Model-driven methods have been quite effective for reducing the intricacies of embedded software development, since they provide effective means for property verification as well as automatic code generation. Nevertheless, regarding energy-constrained hard real-time systems, few model-driven methods are available and, usually, most methods (model-driven or not) consider simplified system specifications, such as absence of intertask relations. This paper presents a model-driven method for software synthesis of hard real-time embedded applications with energy constraints. A formal model based on time Petri nets is adopted in order to provide a basis for pre-runtime schedule generation and property analysis/verification. [ABSTRACT FROM AUTHOR]

This paper presents a compositional and hybrid approach for the performance analysis of distributed real-time systems. The developed methodology abstracts system components by either flow-oriented and purely analytic descriptions or by state-based models in the form of timed automata. The interaction among the heterogeneous components is modeled by streams of discrete events. In total this yields a hybrid framework for the compositional analysis of embedded systems. It supplements contemporary techniques for the following reasons: (a) state space explosion as intrinsic to formal verification is limited to the level of isolated components; (b) computed performance metrics such as buffer sizes, delays and utilization rates are not overly pessimistic, because coarse-grained analytic models are used only for components that conform to the stateless model of computation. For demonstrating the usefulness of the presented ideas, a corresponding tool-chain has been implemented. It is used to investigate the performance of a two-staged computing system, where one stage exhibits state-dependent behavior that is only coarsely coverable by a purely analytic and stateless component abstraction. Finally, experiments are performed to ascertain the scalability and the accuracy of the proposed approach. [ABSTRACT FROM AUTHOR]

In this paper, we consider offline validation of hard real-time systems composed of both periodic and sporadic tasks, embedded on centralized multi-processor architectures. To model hard real-time systems, we use untimed finite automata: each accepted word is a valid operational behavior of the periodic component of the system. Then, by associating generating functions with edges of the automaton, we give a modular decisional technique to decide the feasibility of sporadic tasks. [Copyright &y& Elsevier]

A modeling notation is introduced which extends Time Petri Nets with an additional mechanism of resource assignment making the progress of timed transitions be dependent on the availability of a set of preemptable resources. The resulting notation, which we call Preemptive Time Petri Nets, permits natural description of complex real-time systems running under preemptive scheduling, with periodic, sporadic, and one-shot processes, nondeterministic execution times, semaphore synchronizations, and precedence relations deriving from internal task sequentialization and from interprocess communication running on multiple processors. A state space analysis technique is presented which supports the validation of Preemptive Time Petri Net models, combining tight schedulability analysis with exhaustive verification of the correctness of logical sequencing. The analysis technique partitions the state space in equivalence classes in which timing constraints are represented in the form of Difference Bounds Matrixes. This permits it to maintain a polynomial complexity in the representation and derivation of state classes, but it does not tightly encompass the constraints deriving from preemptive behavior, thus producing an enlarged representation of the state space. False behaviors deriving from the approximation can be cleaned-up through an algorithm which provides a necessary and sufficient condition for the feasibility of a behavior along with a tight estimation of its timing profile. [ABSTRACT FROM AUTHOR]

An enumerative technique is presented which supports reachability and timeliness analysis of time-dependent models. The technique assumes a dense model of time and uses equivalence classes to enable discrete and compact enumeration of the state space. Properties of timed reachability among states are recovered through the analysis of timing constraints embedded within equivalence classes. In particular, algorithms are given to evaluate a tight profile for the set of feasible timings of any untimed run. Runtime refinement of static profiles supports a mixed static/dynamic strategy in the development of a failure avoidance mechanism for dynamic acceptance and a guarantee of hard real-time processes. [ABSTRACT FROM AUTHOR]