Multicycle Polling Scheduling Algorithms for FieldBus Networks

The paper deals with the scheduling of periodic information flow in a FieldBus environment. The scheduling problem is defined from an analytical point of view, giving a brief survey of the most well-known solutions. One of these is called multicycle polling scheduling, which is based on the hypothesis that all the production periods of the periodic processes to be scheduled are harmonic. Although in some process control or manufacturing scenarios, this hypothesis may be acceptable, there are many real industrial processes to which it cannot be applied. The aim of the paper is to make a contribution towards solving the scheduling problem. It essentially concerns extension of the theory on which multicycle polling scheduling is based to a much more realistic and general scenario, where the periods of all the processes to be scheduled have arbitrary values. The authors present a new formulation of multicycle polling scheduling, called extended multicycle polling scheduling, and demonstrate that it comprises the scenario currently considered in the literature. Two algorithmic solutions for extended multicycle polling scheduling are then proposed, giving a computational complexity analysis which will highlight the capability of the algorithmic scheduling solutions to be performed on-line. The paper concludes by comparing the multicycle polling scheduling approach known in literature and the one presented in the paper. Comparison is performed by evaluating the use of available bandwidth to serve both periodic and asynchronous traffic in the two approaches.     

Temporal isolation in real-time systems: the VBS approach

Temporal isolation in real-time systems allows the execution of software processes isolated from one another in the temporal domain. Intuitively, the execution of a process is temporally isolated if the real-time behavior of the process is independent of the execution of the other concurrently scheduled processes in the system. The article provides a comprehensive discussion of temporal isolation through variable-bandwidth servers (VBSs). VBS consists of an EDF-based uniprocessor scheduling algorithm and a utilization-based schedulability test. The scheduling algorithm runs in constant time modulo the time complexity of queue management. The schedulability test runs in time linear in the number of processes and enables admission of an individual process in constant time. The test is a sufficient condition for VBS to provide temporal isolation through lower and upper response-time bounds on processes. We present the VBS design, implementation, proofs, and experiments, followed by condensed versions of results on scheduler overhead accounting with VBS and on reducing power consumption in VBS systems.     

A solution to the end-effector position optimisation problem in robotics using neural networks

The paper presents an original application of the Hopfield-type neural network to a robotics optimisation problem. The robot considered features an arm composed of three revolute joints, the last of which is the end-effector. The robot is planar as the movement of the end-effector is limited to one plane. The mechanical characteristics of the actuators in the joints, the accuracy of the angle position sensors, and dimensional errors in the mechanical elements which make up the end-effector all contribute towards an end-effector positioning error along an assigned trajectory. The computational complexity of the algorithmic solution to the minimisation of this error is at times incompatible with certain particularly critical industrial applications. To reduce the calculation time, the author presents a neural approach based on a Hopfield-type model. A detailed definition of the neural approach is given, its capacity for solving the problem is demonstrated, and the computational complexity is analysed. This analysis shows the drastic computational reduction provided by the neural approach as compared with an algorithmic solution to the problem of end-effector position optimisation.     

An improved constraint satisfaction adaptive neural network for job-shop scheduling

This paper presents an improved constraint satisfaction adaptive neural network for job-shop scheduling problems. The neural network is constructed based on the constraint conditions of a job-shop scheduling problem. Its structure and neuron connections can change adaptively according to the real-time constraint satisfaction situations that arise during the solving process. Several heuristics are also integrated within the neural network to enhance its convergence, accelerate its convergence, and improve the quality of the solutions produced. An experimental study based on a set of benchmark job-shop scheduling problems shows that the improved constraint satisfaction adaptive neural network outperforms the original constraint satisfaction adaptive neural network in terms of computational time and the quality of schedules it produces. The neural network approach is also experimentally validated to outperform three classical heuristic algorithms that are widely used as the basis of many state-of-the-art scheduling systems. Hence, it may also be used to construct advanced job-shop scheduling systems.     

A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling

Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling.     

User-defined schedulers for real-time concurrent objects

Scheduling concerns the allocation of processors to processes, and is traditionally associated with low-level tasks in operating systems and embedded devices. However, modern software applications with soft real-time requirements need to control application-level performance. High-level scheduling control at the application level may complement general purpose OS level scheduling to fine-tune performance of a specific application, by allowing the application to adapt to changes in client traffic on the one hand and to low-level scheduling on the other hand. This paper presents an approach to express and analyze application-specific scheduling decisions during the software design stage. For this purpose, we integrate support for application-level scheduling control in a high-level object-oriented modeling language, Real-Time ABS, in which executable specifications of method calls are given deadlines and real-time computational constraints. In Real-Time ABS, flexible application-specific schedulers may be specified by the user, i.e., developer, at the abstraction level of the high-level modeling language itself and associated with concurrent objects at creation time. Tool support for Real-Time ABS is based on an abstract interpreter that supports simulations and measurements of systems at the design stage.     

强实时环境下调度非周期任务的时限寻优方法

文章提出了强实时环境下调度弱时限非周期任务的时限寻优方法（ＤＯＡ）,该方法在保证周期任务和偶发性任务满足时限要求的前提下,使非周期任务的响应时间达到最优。它还可根据实时应用的需要对算法的执行性能和计算复杂度进行折衷调整。仿真实验表明,ＤＯＡ与现有的动态调度算法相比,使非周期任务响应时间更短,同时它收敛快,额外开销小,计算复杂度低,实现方便,因此是强实时环境下对周期任务与非周期任务进行混合调度的一种较好的方法。     

混合事务的ERtTDF调度算法及可调度性分析

在实时数据库及数据处理系统中,针对周期性实时事务,应用经典的EDF等调度算法对其可以得到可行的调度;而对于混合实时事务-事务的时间性质是混合的,经典EDF不太适用。文中扩展EDF为最早实时事务截止期优先-ERtTDF(EarliestReal-timeTransactionDeadlineFirst),它可以有效地调度混合事务。文中给出了其可调度条件和时间需求条件,并把时间需求条件扩展到时限小于周期以及引入资源共享控制等方面,最后给出了集成调度实时、非实时以及混合事务的系统框架。通过性能比较,可以得到ERtTDF算法处理上面事务模型时性能较经典EDF更优。     

Scheduling of computational processes in real-time distributed systems with uncertain task execution times

An approach to scheduling computational processes in real-time distributed computing systems is considered. It is assumed that the task execution time is inexactly; more precisely, it is assumed to belog to a certain time interval. The problem is formulated as the scheduling of jobs of which each is characterized by its priority and consists of a set of tasks (with respect to the number of processors) executing on different processors and associated by a hierarchical precedence relationship. The proposed approach is based on algorithms with low computational complexity for suboptimal scheduling of equal-priority tasks.     

Pre-run-time scheduling to reduce schedule length in the FieldBusenvironment

The paper deals with the problem of scheduling the transmission of periodic processes in a distributed FieldBus system, defining the conditions guaranteeing correct transmission. The scheduling of periodic processes fixes the transmission times for each process in a table, whose length is equal to the Least Common Multiple (LCM) of all the periods. This involves great memorization problems when some periods are relatively prime. The authors identify the theoretical conditions which allow the length of the scheduling table to be drastically reduced, but still guarantee correct transmission. On the basis of the theoretical conditions given, the authors present a pre-run-time scheduling algorithm which determines a transmission sequence for each producing process within the desired scheduling interval. An online scheduling algorithm is also proposed to schedule new transmission requests which are made while the system is functioning. The reduction in the schedule length may increase the number of transmissions, thus reducing the effective bandwidth and increasing the communication overload. In order to make as complete an analysis as possible of the scheduling solution, the authors also present an analysis of both the computational complexity of the algorithms proposed and the communication overload introduced     

非精确计算中基于反馈的CPU在线调度算法

随着家庭网络中的多媒体服务器和实时数据库服务器这类应用对实时的灵活性的要求不断增加,传统实时基于最长执行时间(WCET)的调度算法已经不能满足它们对性能优化的要求.因此,产生了一些软实时的调度算法来解决这些问题.提出了一种由反馈环节控制的实时调度算法,该算法用于调度能使用不精确计算模型描述的进程.算法可以在各种负载条件下,通过在调度过程中引入的反馈控制,在计算精度和计算时间上直接取得折衷,将进程错过时限的比例控制在预定范围内.     

面向云端FPGA的卷积神经网络加速器的设计及其调度

卷积神经网络的高计算复杂性阻碍其广泛用于实时和低功耗应用,现有软件实现方案难以满足其对运算性能与功耗的要求,传统面向FPGA的卷积神经网络构造方式具有流程复杂、周期较长和优化空间较小等问题。针对该问题,根据卷积神经网络计算模式的特点,提出一种面向云端FPGA的卷积神经网络加速器的设计及其调度机制。通过借鉴基于HLS技术、引入循环切割参数和对卷积层循环重排的设计,采用模块化方式构造网络,并进行参数拓展以进一步优化加速器处理过程;通过分析系统任务和资源的特性总结调度方案,且从控制流和数据流两方面对其进行优化设计。与其他已有工作相比,提出的设计提供了一种同时具有灵活性、低能耗、高能效和高性能的解决方案,并且探讨了加速器的高效通用调度方案。实验结果表明,该加速器可在有效提高运算整速度的同时减少功耗。     

RealNet: a neural network architecture for real-time systems scheduling

Real-time embedded systems are spreading to more and more new fields and their scope and complexity have grown dramatically in the last few years. Nowadays, real-time embedded computers or controllers can be found everywhere, both in very simple devices used in everyday life and in professional environments. Real-time embedded systems have to take into account robustness, safety and timeliness. The most-used schedulability analysis is the worst-case response time proposed by Joseph and Pandya (Comput J 29:390–395,1986). This test provides a bivaluated response (yes/no) indicating whether the processes will meet their corresponding deadlines or not. Nevertheless, sometimes the real-time designer might want to know, more exactly, the probability of the processes meeting their deadlines, in order to assess the risk of a failed scheduling depending on critical requirements of the processes. This paper presents RealNet, a neural network architecture that will generate schedules from timing requirements of a real-time system. The RealNet simulator will provide the designer, after iterating and averaging over some trials, an estimation of the probability that the system will not meet the deadlines. Moreover, the knowledge of the critical processes in these schedules will allow the designer to decide whether changes in the implementation are required.This revised version was published online in November 2004 with a correction to the accepted date.     

Scheduling image processing tasks in a multilayer system

Multilayer multiprocessor systems are generally employed in real-time applications such as robotics and computer vision. This paper introduces three heuristic algorithms for multiprocessor task scheduling in such systems. In our model, tasks with arbitrary processing times and arbitrary processor requirements are considered. The scheduling aims at minimising completion time of processes in a two-layer system. We employed an effective lower bound (LB) for the problem. Then, we analysed the average performance of the heuristic algorithms by computing the average percentage deviation of each heuristic solution from the LB on a set of randomly generated problems. We have also applied these algorithms for scheduling computer vision tasks running on prototype multilayer architecture. Our computational and empirical results showed that the proposed heuristic algorithms perform well.     

开销敏感的多处理器最优节能实时调度算法

嵌入式多处理器系统的能耗问题变得日益重要,如何减少能耗同时满足实时约束成为多处理器系统节能实时调度中的一个重要问题.目前绝大多数研究基于关键速度降低处理器的频率以减少动态能耗,采用关闭处理器的方法减少静态能耗.虽然这种方法可以实现节能,但是不能保证最小化能耗.而现有最优的节能实时调度未考虑处理器状态切换的时间和能量开销,因此在切换开销不可忽视的实际平台中不再是最优的.文中针对具有独立动态电压频率调节和动态功耗管理功能的多处理器系统,考虑处理器切换开销,提出一种基于帧任务模型的最优节能实时调度算法.该算法根据关键速度来判断系统负载情况,确定具有最低能耗值的活跃处理器个数,然后根据状态切换开销来确定最优调度序列.该算法允许实时任务在处理器之间任意迁移,计算复杂度小,易于实现.数学分析证明了该算法的最优性.     

Dispatching rule selection using artificial neural networks for dynamic planning and scheduling

To schedule a job shop, the first task is to select an appropriate scheduling algorithm or rule. Because of the complexity of scheduling problems, no general algorithm sufficient for solving all scheduling problems has yet been developed. Most job-shop scheduling systems offer alternative algorithms for different situations, and experienced human schedulers are needed to select the best dispatching rule in these systems. This paper proposes a new algorithm for job-shop scheduling problems. This algorithm consists of three stages. First, computer simulation techniques are used to evaluate the efficiency of heuristic rules in different scheduling situations. Second, the simulation results are used to train a neural network in order to capture the knowledge which can be used to select the most efficient heuristic rule for each scheduling situation. Finally, the trained neural network is used as a dispatching rule selector in the real-time scheduling process. Research results have shown great potential in using a neural network to replace human schedulers in selecting an appropriate approach for real-time scheduling. This research is part of an ongoing project of developing a real-time planning and scheduling system.     

基于对象分布式实时系统约束的一致性研究

在分布式实时系统中,时间约束规格的一致性是解决任务分配和调度等关键问题的必要前提。该文给出了一种基于对象分布式实时系统调度的通用模型,并对该模型进行了形式化描述。该模型克服了以往模型不能在应用系统的逻辑和功能部件上描述系统实时约束的不足,允许从方法和活动上描述所需的约束,降低了单一约束描述的繁杂程度。为了解决使用该模型进行约束规格的一致性问题,该文给出了绝对时间约束、相对时间约束、一致性约束以及相对时间约束和一致性约束之间的一致性判定的必要条件。     

Artificial neural networks for flexible manufacturing systems scheduling

Artificial neural networks (ANNs) are information processing systems motivated by the goals of reproducing the cognitive processes and organizational models of neurobiological systems. By virtue of their computational structure, ANN's feature attractive characteristics such as graceful degradation, robust recall with noisy and fragmented data, parallel distributed processing, generalization to patterns outside of the training set, nonlinear modeling capabilities, and learning. These computational features could provide enhanced inferencing functionality and real-time capabilities to develop approaches for traditional difficult problems such as flexible manufacturing system (FMS) scheduling. In this paper three different schemes of ANN's are applied to the FMS scheduling problem. These include a) relaxation-based networks, b) competitive-based schemes, and c) adaptive pattern recognition scheduling.     

Scheduler Modeling Based on the Controller Synthesis Paradigm

The controller synthesis paradigm provides a general framework for scheduling real-time applications. Schedulers can be considered as controllers of the applications; they restrict their behavior so that given scheduling requirements are met. We study a modeling methodology based on the controller synthesis paradigm. The methodology allows to get a correctly scheduled system from timed models of its processes in an incremental manner, by application of composability results which simplify schedulability analysis. It consists in restricting successively the system to be scheduled by application of constraints defined from scheduling requirements. The latter are a conjunction of schedulability requirements that express timing properties of the processes and policy requirements about resource management. The presented methodology allows a unified view of scheduling theory and approaches based on timing analysis of models of real-time applications.     

一种基于PID的实时控制与调度协同设计方法

针对实时控制领域中由于资源共享引起的控制系统性能下降问题，提出一种对延迟和抖动进行补偿的协同设计方法．讨论了协同设计中的周期分配问题，对一些变结构任务或混杂任务，采用任务周期动态调整的方法以适应其最坏执行时间的变化，并通过查询宏周期实例表，改进PID算法对延迟和抖动进行补偿．