Temperature-aware task scheduling algorithm for soft real-time multi-core systems

High temperature will affect the stability and performance of multi-core processors. A temperature-aware scheduling algorithm for soft real-time multi-core systems is proposed in this paper, namely LTCEDF (Low Thermal Contribution Early Deadline First). According to the core temperature and thread thermal contribution, LTCEDF performs thread migration and exchange to avoid thermal saturation and to keep temperature equilibrium among all the cores. The core temperature calculation method and the thread thermal contribution prediction method are presented. LTCEDF is simulated on ATMI simulator platform. Simulation results show that LTCEDF can not only minimize the thermal penalty, but also meet real-time guarantee. Moreover, it can create a more uniform power density map than other thermal-aware algorithms, and significantly reduce thread migration frequency.     

Utility accrual real-time scheduling for multiprocessor embedded systems

We present the first Utility Accrual (or UA) real-time scheduling algorithm for multiprocessors, called the global Multiprocessor Utility Accrual scheduling algorithm (or gMUA). The algorithm considers an application model where real-time activities are subject to time/utility function time constraints, variable execution time demands, and resource overloads where the total activity utilization demand exceeds the total capacity of all processors. We consider the scheduling objective of (1) probabilistically satisfying lower bounds on each activity’s maximum utility, and (2) maximizing the system-wide, total accrued utility. We establish several properties of gMUA including optimal total utility (for a special case), conditions under which individual activity utility lower bounds are satisfied, a lower bound on system-wide total accrued utility, and bounded sensitivity for assurances to variations in execution time demand estimates. Finally, our simulation experiments validate our analytical results and confirm the algorithm’s effectiveness.     

Integrating job parallelism in real-time scheduling theory

We investigate the global scheduling of sporadic, implicit deadline, real-time task systems on multiprocessor platforms. We provide a task model which integrates job parallelism. We prove that the time-complexity of the feasibility problem of these systems is linear relatively to the number of (sporadic) tasks for a fixed number of processors. We propose a scheduling algorithm theoretically optimal (i.e., preemptions and migrations neglected). Moreover, we provide an exact feasibility utilization bound. Lastly, we propose a technique to limit the number of migrations and preemptions.     

T-CREST: Time-predictable multi-core architecture for embedded systems

Real-time systems need time-predictable platforms to allow static analysis of the worst-case execution time (WCET). Standard multi-core processors are optimized for the average case and are hardly analyzable. Within the T-CREST project we propose novel solutions for time-predictable multi-core architectures that are optimized for the WCET instead of the average-case execution time. The resulting time-predictable resources (processors, interconnect, memory arbiter, and memory controller) and tools (compiler, WCET analysis) are designed to ease WCET analysis and to optimize WCET performance. Compared to other processors the WCET performance is outstanding.The T-CREST platform is evaluated with two industrial use cases. An application from the avionic domain demonstrates that tasks executing on different cores do not interfere with respect to their WCET. A signal processing application from the railway domain shows that the WCET can be reduced for computation-intensive tasks when distributing the tasks on several cores and using the network-on-chip for communication. With three cores the WCET is improved by a factor of 1.8 and with 15 cores by a factor of 5.7.The T-CREST project is the result of a collaborative research and development project executed by eight partners from academia and industry. The European Commission funded T-CREST.     

Genetic design of real-time neural network controllers

The use of genetic algorithms to design neural networks for real-time control of flows in sewerage networks is discussed. In many control applications, standard supervised learning techniques (such as back-propagation) cannot be used through lack of training data. Reinforcement learning techniques, such as genetic algorithms, are a computationally-expensive but viable alternative if a simulator is available for the system in question. The paper briefly describes why genetic algorithms and neural networks were selected, then reports the results of a feasibility study. This demonstrates that the approach does indeed have merits. The implications of high computational cost are discussed, in terms of scaling up to significantly complex problems.     

Schedulability issues for EDZL scheduling on real-time multiprocessor systems

EDZL (Earliest Deadline first until Zero Laxity) is an efficient and practical scheduling algorithm on multiprocessor systems. It has a comparable number of context switch to EDF (Earliest Deadline First) and its schedulable utilization seems to be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3m/4=0.75m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m(1−1/e)≈0.6321m, where e≈2.718 is the Euler's number.     

Hard real-time tasks' scheduling considering voltage scaling, precedence and exclusion relations

Several scheduling approaches have been developed to address DVS in time-critical systems, however, overheads, precedence and exclusion relations have been neglected. This paper presents a pre-runtime scheduling method for hard real-time systems considering DVS, overheads as well as inter-task relations. The proposed method adopts a formal model based on time Petri nets in order to find a feasible schedule that satisfies timing and energy constraints.     

Resource access control for dynamic priority distributed real-time systems

Many of today’s complex computer applications are being modeled and constructed using the principles inherent to real-time distributed object systems. In response to this demand, the Object Management Group’s (OMG) Real-Time Special Interest Group (RT SIG) has worked to extend the Common Object Request Broker Architecture (CORBA) standard to include real-time specifications. This group’s most recent efforts focus on the requirements of dynamic distributed real-time systems. One open problem in this area is resource access synchronization for tasks employing dynamic priority scheduling. This paper presents two resource synchronization protocols that meet the requirements of dynamic distributed real-time systems as specified by Dynamic Scheduling Real-Time CORBA 2.0 (DSRT CORBA). The proposed protocols can be applied to both Earliest Deadline First (EDF) and Least Laxity First (LLF) dynamic scheduling algorithms, allow distributed nested critical sections, and avoid unnecessary runtime overhead. These protocols are based on (i) distributed resource preclaiming that allocates resources in the message-based distributed system for deadlock prevention, (ii) distributed priority inheritance that bounds local and remote priority inversion, and (iii) distributed preemption ceilings that delimit the priority inversion time further. Chen Zhang is an Assistant Professor of Computer Information Systems at Bryant University. He received his M.S. and Ph.D. in Computer Science from the University of Alabama in 2000 and 2002, a B.S. from Tsinghua University, Beijing, China. Dr. Zhang’s primary research interests fall into the areas of distributed systems and telecommunications. He is a member of ACM, IEEE and DSI. David Cordes is a Professor of Computer Science at the University of Alabama; he has also served as Department Head since 1997. He received his Ph.D. in Computer Science from Louisiana State University in 1988, an M.S. in Computer Science from Purdue University in 1984, and a B.S. in Computer Science from the University of Arkansas in 1982. Dr. Cordes’s primary research interests fall into the areas of software engineering and systems. He is a member of ACM and a Senior Member of IEEE.     

FASA: A software architecture and runtime framework for flexible distributed automation systems

Modern automation systems have to cope with large amounts of sensor data to be processed, stricter security requirements, heterogeneous hardware, and an increasing need for flexibility. The challenges for tomorrow’s automation systems need software architectures of today’s real-time controllers to evolve.This article presents FASA, a modern software architecture for next-generation automation systems. FASA provides concepts for scalable, flexible, and platform-independent real-time execution frameworks, which also provide advanced features such as software-based fault tolerance and high degrees of isolation and security. We show that FASA caters for robust execution of time-critical applications even in parallel execution environments such as multi-core processors.We present a reference implementation of FASA that controls a magnetic levitation device. This device is sensitive to any disturbance in its real-time control and thus, provides a suitable validation scenario. Our results show that FASA can sustain its advanced features even in high-speed control scenarios at 1 kHz.     

Language constructs for real-time distributed systems

The paper observes syntactic and semantic requirements for a language for programming real-time distributed systems. A proposal for language features that meet these requirements is offered, and the features are applied to an example.     

Demand-based schedulability analysis for real-time multi-core scheduling

In real-time systems, schedulability analysis has been widely studied to provide offline guarantees on temporal correctness, producing many analysis methods. The demand-based schedulability analysis method has a great potential for high schedulability performance and broad applicability. However, such a potential is not yet fully realized for real-time multi-core scheduling mainly due to (i) the difficulty of calculating the resource demand under dynamic priority scheduling algorithms that are favorable to multi-cores, and (ii) the lack of understanding how to combine the analysis framework with deadline-miss conditions specialized for those scheduling algorithms. Addressing those two issues, to the best of our knowledge, this paper presents the first demand-based schedulability analysis for dynamic job-priority scheduling algorithms: EDZL (Earliest Deadline first until Zero-Laxity) and LLF (Least Laxity First), which are known to be effective for real-time multi-core scheduling. To this end, we first derive demand bound functions that compute the maximum possible amount of resource demand of jobs of each task while the priority of each job can change dynamically under EDZL and LLF. Then, we develop demand-based schedulability analyses for EDZL and LLF, by incorporating those new demand bound functions into the existing demand-based analysis framework. Finally, we combine the framework with additional deadline-miss conditions specialized for those two laxity-based dynamic job-priority scheduling algorithms, yielding tighter schedulability analyses. Via simulations, we demonstrate that the proposed schedulability analyses outperform the existing schedulability analyses for EDZL and LLF.     

Preference-oriented real-time scheduling and its application in fault-tolerant systems

In this paper, we consider a set of real-time periodic tasks where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP) while still meeting their deadlines. After introducing the idea of preference-oriented (PO) execution, we formally define the concept of PO-optimality. For fully-loaded systems (with 100% utilization), we first propose a PO-optimal scheduler, namely ASAP-Ensured Earliest Deadline (SEED), by focusing on ASAP tasks where the optimality of ALAP tasks’ preference is achieved implicitly due to the harmonicity of the PO-optimal schedules for such systems. Then, for under-utilized systems (with less than 100% utilization), we show the discrepancies between different PO-optimal schedules. By extending SEED, we propose a generalized Preference-Oriented Earliest Deadline (POED) scheduler that can obtain a PO-optimal schedule for any schedulable task set. The application of the POED scheduler in a dual-processor fault-tolerant system is further illustrated. We evaluate the proposed PO-optimal schedulers through extensive simulations. The results show that, comparing to that of the well-known EDF scheduler, the scheduling overheads of SEED and POED are higher (but still manageable) due to the additional consideration of tasks’ preferences. However, SEED and POED can achieve the preference-oriented execution objectives in a more successful way than EDF.     

Static priority scheduling of event-triggered real-time embedded systems

Real-time embedded systems are often specified as a collection of independent tasks, each generating a sequence of event-triggered code blocks. The goal of scheduling tasks in this domain is to find an execution order which satisfies all real-time constraints. Within the context of recurring real-time tasks, all previous work either allowed preemptions, or only considered dynamic scheduling, and generally had exponential complexity. However, for many embedded systems running on limited resources, preemptive scheduling may be very costly due to high context switching and memory overheads, and dynamic scheduling can be less desirable due to high CPU overhead. In this paper, we study static priority scheduling of recurring real-time tasks. We focus on and obtain schedule-theoretic results for the non-preemptive uniprocessor case. To achieve this, we derive a sufficient (albeit not necessary) condition for schedulability under static priority scheduling and show that this condition can be efficiently tested in practice. The latter technique is demonstrated with examples, where in each case, an optimal solution for a given problem specification is obtained within reasonable time, by first detecting good candidates using meta-heuristics, and then by testing them for schedulability.

L-p Fuzzy ARTMAP neural network architecture

In this paper, an L-p based Fuzzy ARTMAP neural network is presented. The category choice of this network is based on the L-p norm. Geometrical properties of this architecture are presented. Comparisons between this category choice and the category choice of the Fuzzy ARTMAP are illustrated. And simulation results on the databases taken from the UCI repository are performed. It will be shown that using the L-p norm is geometrically more attractive. It will operate directly on the input patterns without the need for doing any preprocessing. It should be noted that the Fuzzy ARTMAP architecture requires two preprocessing steps: normalization and complement coding. Simulation results on different databases show the good generalization performance of the L-p Fuzzy ARTMAP compared to the performance of Fuzzy ARTMAP.     

Adaptive finite-time neural network control for nonlinear stochastic systems with state constraints

This paper focuses on the adaptive finite-time neural network control problem for nonlinear stochastic systems with full state constraints. Adaptive controller and adaptive law are designed by backstepping design with log-type barrier Lyapunov function. Radial basis function neural networks are employed to approximate unknown system parameters. It is proved that the tracking error can achieve finite-time convergence to a small region of the origin in probability and the state constraints are confirmed in probability. Different from deterministic nonlinear systems, here the stochastic system is affected by two random terms including continuous Brownian motion and discontinuous Poisson jump process. Therefore, it will bring difficulties to the controller design and the estimations of unknown parameters. A simulation example is given to illustrate the effectiveness of the designed control method.     

Modular architecture for custom-built systems oriented to real-time computer vision: Application to color recognition

This paper presents a modular architecture called DIPSA, which is intended to be used for building custom-made real-time Computer-Vision systems. It consists of four module types and each of them represents a family of circuits that perform specific visual tasks. Our architectural model proposes an algorithm-dependent methodology and makes good results possible using problem oriented solutions. The desired performance is achieved choosing the appropriate modules and connecting them by means of heterogeneous pipeline and concurrence. Additionally, two DIPSA-based hardware systems for real-time Color Recognition are described here.     

An anomaly prevention approach for real-time task scheduling

This research responds to practical requirements in the porting of embedded software over platforms and the well-known multiprocessor anomaly. In particular, we consider the task scheduling problem when the system configuration changes. With mutual-exclusive resource accessing, we show that new violations of the timing constraints of tasks might occur even when a more powerful processor or device is adopted. The concept of scheduler stability and rules are then proposed to prevent scheduling anomaly from occurring in task executions that might be involved with task synchronization or I/O access. Finally, we explore policies for bounding the duration of scheduling anomalies.     

Efficient real-time divisible load scheduling

Providing QoS and performance guarantees to arbitrarily divisible loads has become a significant problem for many cluster-based research computing facilities. While progress is being made in scheduling arbitrarily divisible loads, current approaches are not efficient and do not scale well. In this paper, we propose a linear algorithm for real-time divisible load scheduling. Unlike existing approaches, the new algorithm relaxes the tight coupling between the task admission controller and the task dispatcher. By eliminating the need to generate exact schedules in the admission controller, the algorithm avoids high overheads. We also proposed a hybrid algorithm that combines the best of our efficient algorithm and a previously best-known approach. We experimentally evaluate the new algorithm. Simulation results demonstrate that the algorithm scales well, can schedule large numbers of tasks efficiently, and performs similarly to existing approaches in terms of providing real-time guarantees.     

Pre-run-time scheduling in real-time systems: Current researches and Artificial Intelligence perspectives

This paper presents the taxonomy of real-time systems with special emphasize on pre-run-time scheduling problem. Firstly, we present real-time systems, real-time tasks, timing, precedence and exclusion constraints. Then, we describe the problem of pre-run-time scheduling of tasks under constraints. After that, we present the most existing efficient techniques to deal with the latter problem. We summarize the discussion of existing techniques and possible research perspectives after surveying the Artificial Intelligence’s point of view about the problem of pre-run-time scheduling of real-time tasks. The Artificial Intelligence survey includes Constraint Satisfaction Problems class since pre-run-time scheduling belongs to the latter class. The Artificial Intelligence survey includes also Path-finding Problems from which intelligent algorithms could be observed such as Learning-Real-Time-A1(LRTA1) thanks to its important properties (optimality, linear space complexity and determinism). The development of an algorithm like LRTA1 to solve Constraints Satisfaction Problems and particularly the pre-run-time scheduling of real-time tasks problem is one clear research direction to deal with large-scale real-time systems. The overall objective of this paper is to show what are the perspectives to Artificial Intelligence literature that could be beneficial firstly to Artificial Intelligence community itself and secondly to real-time systems community.     

An object-oriented architecture for knowledge-based production scheduling systems

This paper describes an object-oriented architecture to support decision making in production scheduling environments. An object-oriented world view is used to integrate concepts from discrete event simulation, conventional scheduling logic and artificial intelligence to produce capacity-feasible schedules. The architecture was implemented as a collection of loosely coupled reusable software objects by extending the functionality of software objects from BLOCS/M (Berkeley Library of Objects for Control and Simulation of Manufacturing). Our experience with an industrial prototype is presented.