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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Network invariants for real-time systems

We extend the approach of model checking parameterized networks of processes by means of network invariants to the setting of real-time systems. We introduce timed transition structures (which are similar in spirit to timed automata) and define a notion of abstraction that is safe with respect to linear temporal properties. We strengthen the notion of abstraction to allow a finite system, then called network invariant, to be an abstraction of networks of real-time systems. In general the problem of checking abstraction of real-time systems is undecidable. Hence, we provide sufficient criteria, which can be checked automatically, to conclude that one system is an abstraction of a concrete one. Our method is based on timed superposition and discretization of timed systems. We exemplify our approach by proving mutual exclusion of a simple protocol inspired by Fischer’s protocol, using the model checker TLV. Part of this work was done during O. Grinchtein’s stay at Weizmann Institute. This author was supported by the European Research Training Network “Games”.     

An optimal boundary fair scheduling algorithm for multiprocessor real-time systems

With the emergence of multicore processors, the research on multiprocessor real-time scheduling has caught more researchers’ attention recently. Although the topic has been studied for decades, it is still an evolving research field with many open problems. In this work, focusing on periodic real-time tasks with quantum-based computation requirements and implicit deadlines, we propose a novel optimal scheduling algorithm, namely boundary fair (Bfair), which can achieve full system utilization as the well-known Pfair scheduling algorithms. However, different from Pfair algorithms that make scheduling decisions and enforce proportional progress (i.e., fairness) for all tasks at each and every time unit, Bfair makes scheduling decisions and enforces fairness to tasks only at tasks’ period boundaries (i.e., deadlines of periodic tasks). The correctness of the Bfair algorithm to meet the deadlines of all tasks’ instances is formally proved and its performance is evaluated through extensive simulations. The results show that, compared to that of Pfair algorithms, Bfair can significantly reduce the number of scheduling points (by up to 94%) and the overhead of Bfair at each scheduling point is comparable to that of the most efficient Pfair algorithm (i.e., PD²). Moreover, by aggregating the time allocation of tasks for the time interval between consecutive period boundaries, the resulting Bfair schedule can dramatically reduce the number of required context switches and task migrations (as much as 82% and 85%, respectively) when compared to those of Pfair schedules, which in turn reduces the run-time overhead of the system.     

A hierarchical optimization neural network for large-scale dynamic systems

A recurrent neural network for dynamical hierarchical optimization of nonlinear discrete large-scale systems is presented. The proposed neural network consists of hierarchically structured sub-networks: one coordination sub-network at the upper level and several local optimization sub-networks at the lower level. In particular, the coordination sub-network and the local optimization sub-networks work simultaneously. This feature makes the proposed method outperform in computational efficiency the conventional iterative algorithms where there usually exists an alternately waiting time during the coordination and local optimization processes. Moreover, the state equations of the subsystems of the large-scale system are imbedded into their corresponding local optimization sub-networks. This imbedding technique not only overcomes the difficulty in treating the constraints imposed by the state equations, but also leads to significant reduction in the network size. We present stability analysis to prove that the neural network is asymptotically stable and this stable state corresponds to the optimal solution to the original optimal control problem. Finally, we illustrate the performance of the proposed method by an example.