Fault-Tolerant Scheduling for Real-Time Embedded Control Systems

With the increasing complexity of industrial application, an embedded control system (ECS) requires processing a number of hard real-time tasks and needs fault-tolerance to assure high reliability. Considering the characteristics of real-time tasks in ECS, an integrated algorithm is proposed to schedule real-time tasks and to guarantee that all real-time tasks are completed before their deadlines even in the presence of faults. Based on the nonpreemptive critical-section protocol (NCSP), this paper analyzes the blocking time introduced by resource conflicts of relevancy tasks in fault-tolerant multiprocessor systems. An extended schedulability condition is presented to check the assignment feasibility of a given task to a processor. A primary/backup approach and on-line replacement of failed processors are used to tolerate processor failures. The analysis reveals that the integrated algorithm bounds the blocking time, requires limited overhead on the number of processors, and still assures good processor utilization. This is also demonstrated by simulation results. Both analysis and simulation show the effectiveness of the proposed algorithm in ECS.     

具有优先链约束的网格作业多资源调度问题

网格计算是网络并行计算的发展新趋势,网格系统中的分布式资源管理和调度一直是研究的热点和难点。对于网格应用作业的多资源调度问题,一个网格作业往往要分成多步骤进行,每个步骤都需要占用多个资源。首先将该问题抽象为典型的多处理机任务调度模型P_m|fix,p=1,chain|C_max,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行,而且每个任务都需要一个单位的处理时间,并根据优先关系形成链约束。该问题被证明为NP难问题。利用宽度优先技术和首次满足方法,构建了几个多项式时间近似算法,并通过模拟实验分析算法性能,实验结果显示算法是实用的。     

Energy efficient scheduling of parallel tasks on multiprocessor computers

In this paper, scheduling parallel tasks on multiprocessor computers with dynamically variable voltage and speed are addressed as combinatorial optimization problems. Two problems are defined, namely, minimizing schedule length with energy consumption constraint and minimizing energy consumption with schedule length constraint. The first problem has applications in general multiprocessor and multicore processor computing systems where energy consumption is an important concern and in mobile computers where energy conservation is a main concern. The second problem has applications in real-time multiprocessing systems and environments where timing constraint is a major requirement. Our scheduling problems are defined such that the energy-delay product is optimized by fixing one factor and minimizing the other. It is noticed that power-aware scheduling of parallel tasks has rarely been discussed before. Our investigation in this paper makes some initial attempt to energy-efficient scheduling of parallel tasks on multiprocessor computers with dynamic voltage and speed. Our scheduling problems contain three nontrivial subproblems, namely, system partitioning, task scheduling, and power supplying. Each subproblem should be solved efficiently, so that heuristic algorithms with overall good performance can be developed. The above decomposition of our optimization problems into three subproblems makes design and analysis of heuristic algorithms tractable. A unique feature of our work is to compare the performance of our algorithms with optimal solutions analytically and validate our results experimentally, not to compare the performance of heuristic algorithms among themselves only experimentally. The harmonic system partitioning and processor allocation scheme is used, which divides a multiprocessor computer into clusters of equal sizes and schedules tasks of similar sizes together to increase processor utilization. A three-level energy/time/power allocation scheme is adopted for a given schedule, such that the schedule length is minimized by consuming given amount of energy or the energy consumed is minimized without missing a given deadline. The performance of our heuristic algorithms is analyzed, and accurate performance bounds are derived. Simulation data which validate our analytical results are also presented. It is found that our analytical results provide very accurate estimation of the expected normalized schedule length and the expected normalized energy consumption and that our heuristic algorithms are able to produce solutions very close to optimum.     

基于多核处理器的关联任务并行感知调度算法

关联任务在多核处理器上并行调度所产生的通信时延,会对任务调度长度和处理器利用率造成负面影响,为了改善多核系统对关联任务的处理性能,针对关联任务在多核处理器上的调度特点,提出一种并行感知调度算法。计算各任务与终点间的最长路径值,按照该值的降序来分配任务调度次序,在分配处理器内核时兼顾关联度和任务最早可执行时间,设置最佳匹配评价函数。实验结果表明,与busHEFT和DTSV算法相比,该算法具有更短的任务调度时延、更少的通信量以及更高的处理器利用率。     

非完全互连同构系统上的静态任务调度

在分布式内存多处理机DMM(distributed memory multiprocessor)系统中,不同处理机上运行的任务之间的通信开销仍然很大,有时甚至抵消了多处理机并行所带来的好处.为了使并行程序在DMM系统上能得以高效的执行,必须采用合理的调度技术将任务分配给处理机.文章首先分别给出了任务调度系统中的任务模型、处理机模型以及调度问题的形式化描述,然后在此基础上研究了任务调度中3个最重要的问题,即(1) 如何顺序选择参与调度的任务,(2) 如何选择路由,(3) 如何分配任务给处理机.其中,路由选择     

Analysis of processor allocation in multiprogrammed,distributed-memory parallel processing systems

A main objective of scheduling independent jobs composed of multiple sequential tasks in shared-memory and distributed-memory multiprocessor computer systems is the assignment of these tasks to processors in a manner that ensures efficient operation of the system. Achieving this objective requires the analysis of a fundamental tradeoff between maximizing parallel execution, suggesting that the tasks of a job be spread across all system processors, and minimizing synchronization and communication overheads, suggesting that the job's tasks be executed on a single processor. The authors consider a class of scheduling policies that represent the essential aspects of this processor allocation tradeoff, and model the system as a distributed fork-join queueing system. They derive an approximation for the expected job response time, which includes the important effects of various parallel processing overheads (such as task synchronization and communication) induced by the processor allocation policy     

嵌入式并行系统中基于任务优化的调度算法

在嵌入式并行计算系统中,任务调度是决定系统性能的关键。多任务调度中,启发式调度法是一种设计简单且性能良好的调度方法。目前的调度算法大多是基于任务复制的,没有充分考虑前驱任务与其后继任务间的相关性。该文提出了一种基于相关任务优化(DTO)的调度算法,通过分析已用处理机的负载和空闲时间,尽量减少系统的调度长度和处理机数目。算法分析结果表明,DTO算法在性能上优于其他算法,对嵌入式并行计算系统中的多任务调度是一个较好的选择。     

多处理器调度算法实现及其Petri网建模与仿真

多处理器调度算法在嵌入式实时系统领域中起着关键的作用。根据多处理器的特点,提出一种实时多处理器动态分割并行调度算法SPara。该算法解决了此前多处理器算法,如Myopic、EDPF等仅依据截止期对任务调度产生的问题,实现了增加任务紧迫度限制的调度策略,以及针对执行时间长、截止期紧迫任务的有效调度方法。同时算法结合高级颜色时间Petri网理论进行建模并仿真。测试结果表明,SPara算法在处理器利用率以及调度成功率方面较Myopic等算法有较大提高。     

Performance of local search heuristics on scheduling a class of pipelined multiprocessor tasks

This paper presents the evaluation of the solution quality of heuristic algorithms developed for scheduling multiprocessor tasks for a class of multiprocessor architectures designed to exploit temporal and spatial parallelism simultaneously. More specifically, we deal with multi-level or partitionable architectures where MIMD parallelism and multiprogramming support are the two main characteristics of the system. We investigate scheduling a number of pipelined multiprocessor tasks with arbitrary processing times and arbitrary processor requirements in this system. The scheduling problem consists of two interrelated sub-problems, which are finding a sequence of pipelined multiprocessor tasks on a processor and finding a proper mapping of tasks to the processors that are already being sequenced. For the solution of the second problem, various techniques are available. However, the problem remains of generating a feasible sequence for the pipelined operations. We employed three well-known local search heuristic algorithms that are known to be robust methods applicable to various optimization problems. These are Simulated Annealing, Tabu Search, and Genetic Algorithms. We then conduct computational experiments and evaluate the reduction achieved in completion time by each heuristic. We have also compared the results with well-known simple list-based heuristics.     

Orthogonal multiprocessor sharing memory with an enhanced mesh for integrated image understanding

This paper proposes a new parallel architecture, which has the potential to support low-level image processing as well as intermediate and high-level vision analysis tasks efficiently. The integrated architecture consists of an SIMD mesh of processors enhanced with multiple broadcast buses, and MIMD multiprocessor with orthogonal access buses, and a two-dimensional shared memory array. Low-level image processing is performed on the mesh processor, while intermediate and high-level vision analysis is performed on the orthogonal multiprocessor. The interaction between the two levels is supported by a common shared memory. Concurrent computations and I/O are made possible by partitioning the memory into disjoint spaces so that each processor system can access a different memory space. To illustrate the power of such a two-level system, we present efficient parallel algorithms for a variety of problems from low-level image processing to high-level vision. Representative problems include matrix based computations, histogramming and key counting operations, image component labeling, pyramid computations, Hough transform, pattern clustering, and scene labeling. Through computational complexity analysis, we show that the integrated architecture meets the processing requirements of most image understanding tasks.     

A methodology for digital real time simulation of dynamic systems using modern DSPs

The speedup factor in real time simulation of dynamic systems using multiprocessor resources depends on: the architecture of the multiprocessor system, type of interconnection between parallel processors, numerical methods and techniques used for discretization and task assignment and scheduling policy. The minimization of the number of processors needed for real time simulation requires the minimization of processors times for interprocessor communications and efficient scheduling policy. Therefore, this article presents a methodology for the real time simulation of dynamic systems including a new pre-emptive static assignment and scheduling policy. The advantages of applying digital signal processor with parallel architecture, for example TMS320C40, in real time simulation have been described. Some important issues in real time architectures necessary for efficient multiprocessor real time simulations, such as multiple I/O channels, concurrent I/O and CPU processing, direct high speed interprocessor communications, fast context switching, multiple busses, multiple memories, and powerful arithmetic units are inherent to this processor. These features minimize interprocessor communication time and maximize sustained CPU performance.     

Optimal Compile-Time Multiprocessor Scheduling Based on the O–1 Linear Programming Algorithm with the Branch and Bound Technique

The problem of exploiting the effective utilization of a multiprocessor system essentially depends on optimal scheduling of parallel tasks onto the processors in the system. A recently proposed compile-time scheduling algorithm based on the 0–1 linear programming algorithm with the branch and bound technique, to produce optimal schedules, has the problems of communication link contention, nonoptimality, and modeling incompletely connected processor systems. In this paper, we present a modified version of this algorithm for producing contention-free optimal schedules for any arbitrary multiprocessor topology. To alleviate the impediments of large requirements of CPU time for the optimal scheduling algorithm, we have developed three new effective techniques, namely,processor isomorphism, look ahead pruning, andlower bound on the completion time of tasks. The performance of our algorithm is analyzed using DFT and LU decomposition methods as benchmarks.     

Observations on using genetic algorithms for dynamic load-balancing

Load-balancing problems arise in many applications, but, most importantly, they play a special role in the operation of parallel and distributed computing systems. Load-balancing deals with partitioning a program into smaller tasks that can be executed concurrently and mapping each of these tasks to a computational resource such as a processor (e.g., in a multiprocessor system) or a computer (e.g., in a computer network). By developing strategies that can map these tasks to processors in a way that balances out the load, the total processing time will be reduced with improved processor utilization. Most of the research on load-balancing focused on static scenarios that, in most of the cases, employ heuristic methods. However, genetic algorithms have gained immense popularity over the last few years as a robust and easily adaptable search technique. The work proposed here investigates how a genetic algorithm can be employed to solve the dynamic load-balancing problem. A dynamic load-balancing algorithm is developed whereby optimal or near-optimal task allocations can “evolve” during the operation of the parallel computing system. The algorithm considers other load-balancing issues such as threshold policies, information exchange criteria, and interprocessor communication. The effects of these and other issues on the success of the genetic-based load-balancing algorithm as compared with the first-fit heuristic are outlined     

基于MPI高性能计算的方法研究

并行处理在计算能力方面与单处理器的串行处理相比有着无可比拟的优势。个人计算机和网络成本的下降使得使用分布式系统进行并行处理的现象越来越普遍,而分布式网络系统中多采用MPI作为并行编程标准。为了减少程序运行时间,改善MPI计算的性能,负载均衡方法尤为重要,本文提出一种在MPI并行处理中负载均衡的方法,可以按照节点的计算能力和负载情况,在节点之间分配和迁移任务。实验表明,本文提出的方法可有效提高MPI并行处理的性能。     

A distributed self-scheduler for partially ordered tasks

Large scale scientific applications such as weather modelling and continuous simulation require the orders of magnitude performance improvement available with the new generation of parallel vector supercomputers such as the Floating Point Systems T Series. Many of these applications exhibit a high degree of parallelism, much of which can be expressed as computational tasks which are of varying size and degrees of dependence on one another, and can be partially ordered for execution. DeSPOT (A Distributed Self-Scheduler for Partially Ordered Tasks) is an algorithm for the dynamic distribution of such non-uniform tasks to achieve automatic load balancing on a distributed memory hypercube multiprocessor. This paper describes the DeSPOt algorithm and presents its performance characteristics of various test cases using result timings on the FPS T 20.     

A new load distribution strategy for linear network with communication delays

In this paper, we propose a new load distribution strategy called ‘send-and-receive’ for scheduling divisible loads, in a linear network of processors with communication delay. This strategy is designed to optimally utilize the network resources and thereby minimizes the processing time of entire processing load. A closed-form expression for optimal size of load fractions and processing time are derived when the processing load originates at processor located in boundary and interior of the network. A condition on processor and link speed is also derived to ensure that the processors are continuously engaged in load distributions. This paper also presents a parallel implementation of ‘digital watermarking problem’ on a personal computer-based Pentium Linear Network (PLN) topology. Experiments are carried out to study the performance of the proposed strategy and results are compared with other strategies found in literature.     

On-line scheduling of scalable real-time tasks on multiprocessor systems

The computation time of scalable tasks depends on the number of processors allocated to them in multiprocessor systems. As more processors are allocated to a scalable task, the overall computation time of the task decreases but the total amount of processors’ time devoted to the execution of the task, called workload, increases due to parallel execution overhead. In this paper, we propose a task scheduling algorithm that utilizes the property of scalable tasks for on-line and real-time scheduling. In the proposed algorithm, the total workload of all scheduled tasks is reduced by managing processors allocated to the tasks as few as possible without missing their deadlines. As a result, the processors in the system have less load to execute the scheduled tasks and can execute more newly arriving tasks before their deadlines. Simulation results show that the proposed algorithm performs significantly better than the conventional algorithm based on a fixed number of processors to execute each task.     

Simulation of multiple digital signal processor systems

The high speed needed in solving digital signal processing problems in real time has often given rise to multiple processor hardware designs. Devices such as the TMS32020 digital signal processor possess features designed to support concurrent processing. Progress in this area is currently hampered by the lack of suitable multiprocessor development tools. It is suggested that an incremental approach to multiprocessor development, using several methods of simulating the signal processor, may be used. Two simulation environments specifically for the development and testing of multiple digital signal processor designs are described. Firstly a single processor simulation system where the algorithms which will be performed by other concurrent processors may be executed in a high level language but without any need to simulate the instructions of the other processors. Secondly a multiple TMS32020 digital signal processor system where processors are simulated as several communicating tasks on a host computer using the IBM AIX (UNIX derived) multitasking operating system.     

同构计算环境中一种快速有效的静态任务调度算法

快速有效的调度任务是多处理器计算环境中的一个关键问题．目前任务调度算法中刻画任务依赖关系最流行的模型是DAG,在以前的文献中,提出了一种新的更实际、更普遍的TTIG模型及其相应的MATE算法(基于同构计算环境)．延伸了TTIG模型,并提出基于同构系统的新的算法及两种启发式方法(GBHA1和GBHA2)．GBHA以组的形式尽量消除图中回路,因而能获得任务图的全局信息,具有更好的调度性能．在模拟实验中,将此算法与MATE和其他同构环境中基于DAG的有效调度算法,在不同测试条件下进行了比较,结果显示GBHA在性能上明显优于MATE,与基于DAG模型的调度算法比较而言,在性能方面各有千秋,但在算法时间复杂度方面具有显著的优势．     

How useful is old information?

We consider the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information. For example, consider a multiprocessor system where incoming tasks with exponentially distributed service requirements arrive as a Poisson process, the tasks must choose a processor for service, and a task knows when making this choice the processor queue lengths from T seconds ago. What is a good strategy for choosing a processor in order for tasks to minimize their expected time in the system? Such models can also be used to describe settings where there is a transfer delay between the time a task enters a system and the time it reaches a processor for service. Our models are based on considering the behavior of limiting systems where the number of processors goes to infinity. The limiting systems can be shown to accurately describe the behavior of sufficiently large systems and simulations demonstrate that they are reasonably accurate even for systems with a small number of processors. Our studies of specific models demonstrate the importance of using randomness to break symmetry in these systems and yield important rules of thumb for system design. The most significant result is that only small amounts of queue length information can be extremely useful in these settings; for example, having incoming tasks choose the least loaded of two randomly chosen processors is extremely effective over a large range of possible system parameters. In contrast, using global information can actually degrade performance unless used carefully; for example, unlike most settings where the load information is current, having tasks go to the apparently least loaded server can significantly hurt performance