An Efficient Real-Time Fault-Tolerant Scheduling Algorithm Based on Multiprocessor Systems

In the context of real-time fault-tolerant scheduling in multiprocessor systems, Primary-backup scheme plays an important role. A backup copy is always preferred to be executed as passive backup copy whenever possible because it can take the advantages of backup copy de-allocation technique and overloading technique to improve schedulability. In this paper, we propose a novel efficient fault-tolerant ratemonotonic best-fit algorithm efficient fault-tolerant rate-monotonic best-fit （ERMBF） based on multiprocessors systems to enhance the schedulability. Unlike existing scheduling algorithms that start scheduling tasks with only one processor. ERMBF pre-allocates a certain amount of processors before starting scheduling tasks, which enlarge the searching spaces for tasks. Besides, when a new processor is allocated, we reassign the task copies that have already been assigned to the existing processors in order to find a superior tasks assignment configuration. These two strategies are all aiming at making as many backup copies as possible to be executed as passive status. As a result, ERMBF can use fewer processors to schedule a set of tasks without losing real-time and fault-tolerant capabilities of the system. Simulation results reveal that ERMBF significantly improves the schedulability over existing, comparable algorithms in literature.

Dynamic Load Balancing Based on Restricted Multicast Tree in Homogeneous Multiprocessor Systems

To decrease the cost of exchanging load information among processors, a dynamic load-balancing （DLB） algorithm which adopts multieast tree technology is proposed. The muhieast tree construction rules are also proposed to avoid wrongly transferred or redundant DLB messages due to the overlapping of multicast trees. The proposed DLB algorithm is distributed controlled, sender initiated and can help heavily loaded processors with complete distribution of redundant loads with minimum number of executions. Experiments were executed to compare the effects of the proposed DLB algorithm and other three ones, the results prove the effectivity and practicability of the proposed algorithm in dealing with great scale compute-intensive tasks.

Study and Analysis of Bus Arbitration Mechanism in PI-MPS Multiprocessor System

This paper presents the mechanism of the bus arbitration in PI-MPS multiprocessor sys-tem,describes encode approach,arbiter timing states and uniqueness of master modular ininterconnection bus,and measures and analyses latency of bus arbitration as well.

Error Recovery in a Real-Time Multiprocessor System

In this paper,a new scheme for recovering errors due to transient faults in a real-time multiprocessor system is presented.The scheme,called dynamic redundancy at the task level,is implemented in a real-time multitasking environment.Utilizing the facilities in the operating system,the scheme makes backup tasks for the primary tasks as redundancy.The paper introduces an algorithm to gene- rate a fault tolerant schedule for the tasks so that they recover errors as retry or checkpointing does.A reliability model is proposed to evahaste the effectiveness of the scheme.

Dynamic I/O-Aware Scheduling for Batch-Mode Applications on Chip Multiprocessor Systems of Cluster Platforms

Efficiency of batch processing is becoming increasingly important for many modern commercial service centers, e.g., clusters and cloud computing datacenters. However, periodical resource contentions have become the major performance obstacles for concurrently running applications on mainstream CMP servers. I/O contention is such a kind of obstacle, which may impede both the co-running performance of batch jobs and the system throughput seriously. In this paper, a dynamic I/O-aware scheduling algorithm is proposed to lower the impacts of I/O contention and to enhance the co-running performance in batch processing. We set up our environment on an 8-socket, 64-core server in Dawning Linux Cluster. Fifteen workloads ranging from 8 jobs to 256 jobs are evaluated. Our experimental results show significant improvements on the throughputs of the workloads, which range from 7% to 431%. Meanwhile, noticeable improvements on the slowdown of workloads and the average runtime for each job can be achieved. These results show that a well-tuned dynamic I/O-aware scheduler is beneficial for batch-mode services. It can also enhance the resource utilization via throughput improvement on modern service platforms.

Low-cost fault tolerance in evolvable multiprocessor systems:a graceful degradation approach

The evolvable multiprocessor (EvoMP), as a novel multiprocessor system-on-chip (MPSoC) machine with evolvable task decomposition and scheduling, claims a major feature of low-cost and efficient fault tolerance. Non-centralized control and adaptive distribution of the program among the available processors are two major capabilities of this platform, which remarkably help to achieve an efficient fault tolerance scheme. This letter presents the operational as well as architectural details of this fault tolerance scheme. In this method, when a processor becomes faulty, it will be eliminated of contribution in program execution in remaining run-time. This method also utilizes dynamic rescheduling capability of the system to achieve the maximum possible efficiency after processor reduction. The results confirm the efficiency and remarkable advantages of the proposed approach over common redundancy based techniques in similar systems.

YH-MCS Reconstructable Fault-tolerant Multiprocessor Control System

FMS is the basic and frontier technology of advanced manufacturing.Its critical compo-nent is FMS control system.Reconstructable fault-tolerant multiprocessor control system,YH-MCS,is the result of the research on the high-performance and high-reliable FMS con-trol system.This paper describes its architecture,technology characteristics,academic valueand application potentiality.

Development of FPGA Based NURBS Interpolator and Motion Controller with Multiprocessor Technique

The high-speed computational performance is gained at the cost of huge hardware resource,which restricts the application of high-accuracy algorithms because of the limited hardware cost in practical use.To solve the problem,a novel method for designing the field programmable gate array(FPGA)-based non-uniform rational B-spline(NURBS) interpolator and motion controller,which adopts the embedded multiprocessor technique,is proposed in this study.The hardware and software design for the multiprocessor,one of which is for NURBS interpolation and the other for position servo control,is presented.Performance analysis and experiments on an X-Y table are carried out,hardware cost as well as consuming time for interpolation and motion control is compared with the existing methods.The experimental and comparing results indicate that,compared with the existing methods,the proposed method can reduce the hardware cost by 97.5% using higher-accuracy interpolation algorithm within the period of 0.5 ms.A method which ensures the real-time performance and interpolation accuracy,and reduces the hardware cost significantly is proposed,and it’s practical in the use of industrial application.

Approximation algorithm for multiprocessor parallel job scheduling

P k |fix| C max problem is a new scheduling problem based on the multiprocessor parallel job, and it is proved to be NP hard problem when k ≥3. This paper focuses on the case of k =3. Some new observations and new techniques for P 3 |fix| C max problem are offered. The concept of semi normal schedulings is introduced, and a very simple linear time algorithm Semi normal Algorithm for constructing semi normal schedulings is developed. With the method of the classical Graham List Scheduling, a thorough analysis of the optimal scheduling on a special instance is provided, which shows that the algorithm is an approximation algorithm of ratio of 9/8 for any instance of P 3|fix| C max problem, and improves the previous best ratio of 7/6 by M.X.Goemans.

Timed Petri Net Models of Shared-Memory Bus-Based Multiprocessors

In shared-memory bus-based multiprocessors, when the number of processors grows, the processors spend an increasing amount of time waiting for access to the bus (and shared memory). This contention reduces the performance of processors and imposes a limitation of the number of processors that can be used efficiently in bus-based systems. Since the multi-processor’s performance depends upon many parameters which affect the performance in different ways, timed Petri nets are used to model shared-memory bus-based multiprocessors at the instruction execution level, and the developed models are used to study how the performance of processors changes with the number of processors in the system. The results illustrate very well the restriction on the number of processors imposed by the shared bus. All performance characteristics presented in this paper are obtained by discrete-event simulation of Petri net models.

A Class of Parallel Runge-Kutta Methods for Differential-Algebraic Systems of Index 2

A class of parallel Runge-Kutta Methods for differential-algebraic equations of index 2are constructed for multiprocessor system. This paper gives the order conditions and investigatesthe convergence theory for such methods.

Design of efficient parallel algorithms on shared memory multiprocessors

The design of parallel algorithms is studied in this paper. These algorithms are applicable to shared memory MIMD machines In this paper, the emphasis is put on the methods for design of the efficient parallel algorithms. The design of efficient parallel algorithms should be based on the following considerationst algorithm parallelism and the hardware-parallelism; granularity of the parallel algorithm, algorithm optimization according to the underling parallel machine. In this paper , these principles are applied to solve a model problem of the PDE. The speedup of the new method is high. The results were tested and evaluated on a shared memory MIMD machine. The practical results were agree with the predicted performance.

A Particle Swarm Optimization to Minimize Makespan for a Four-Stage Multiprocessor Open Shop with Dynamic Job Release Time

This paper considers the scheduling problem observed in chip sorting operation of LED manufacturing, where each lot (job) with release time have four operations to be processed on a set of processing stages without pre-determined necessary route. Each stage has one and more identical sorting machines. The sorting machines scheduling problem can be treated as a four-stage multiprocessor open shop problem with dynamic job release, and the objective is minimizing the makespan in the paper. This problem is formulated into a mixed integer programming (MIP) model and empirically shows its computational intractability. Due to the computational intractability, a particle swarm optimization (PSO) algorithm is proposed. A series of computational experiments are conducted to evaluate the performance of the proposed PSO in comparison with exact solution on various small-size problem instances. The results show that the PSO algorithm could finds most optimal or better solutions in one second.

Energy-Efficient Scheduling Based on Task Migration Policy Using DPM for Homogeneous MPSoCs

Increasing the life span and efficiency of Multiprocessor System on Chip(MPSoC)by reducing power and energy utilization has become a critical chip design challenge for multiprocessor systems.With the advancement of technology,the performance management of central processing unit(CPU)is changing.Power densities and thermal effects are quickly increasing in multi-core embedded technologies due to shrinking of chip size.When energy consumption reaches a threshold that creates a delay in complementary metal oxide semiconductor(CMOS)circuits and reduces the speed by 10%–15%because excessive on-chip temperature shortens the chip’s life cycle.In this paper,we address the scheduling&energy utilization problem by introducing and evaluating an optimal energy-aware earliest deadline first scheduling(EA-EDF)based technique formultiprocessor environments with task migration that enhances the performance and efficiency in multiprocessor systemon-chip while lowering energy and power consumption.The selection of core andmigration of tasks prevents the system from reaching itsmaximumenergy utilization while effectively using the dynamic power management(DPM)policy.Increase in the execution of tasks the temperature and utilization factor(u_(i))on-chip increases that dissipate more power.The proposed approach migrates such tasks to the core that produces less heat and consumes less power by distributing the load on other cores to lower the temperature and optimizes the duration of idle and sleep times across multiple CPUs.The performance of the EA-EDF algorithm was evaluated by an extensive set of experiments,where excellent results were reported when compared to other current techniques,the efficacy of the proposed methodology reduces the power and energy consumption by 4.3%–4.7%on a utilization of 6%,36%&46%at 520&624 MHz operating frequency when particularly in comparison to other energy-aware methods for MPSoCs.Tasks are running and accurately scheduled to make an energy-efficient processor by controlling and managing the thermal effects on-chip and optimizing the energy consumption of MPSoCs.

概率故障条件下k元(n-m)方体子网络的可靠性

k元n方体具有许多优良特性,已成为多处理器系统最常用的互连网络拓扑结构之一。当系统互连网络中发生故障时,系统子网络的保持能力对系统实际应用至关重要。为了精确度量k元n方体中任意规模子网络的容错能力,研究了有故障发生时k元n方体中k元(n-m)方体子网络的可靠性。当k(k≥3)为奇整数时,在概率故障条件下得出了k元n方体中存在无故障k元(n-m)方体子网络的概率的上界和下界,并给出了该可靠性的一种近似评估方法。实验结果表明,随着顶点可靠性的降低,k元(n-m)方体子网络可靠性的上下界趋于一致;当顶点可靠性较高时,利用近似评估方法得出的结果更为准确。

An Optimal DPM Based Energy-Aware Task Scheduling for Performance Enhancement in Embedded MPSoC

Minimizing the energy consumption to increase the life span and performance of multiprocessor system on chip(MPSoC)has become an integral chip design issue for multiprocessor systems.The performance measurement of computational systems is changing with the advancement in technology.Due to shrinking and smaller chip size power densities onchip are increasing rapidly that increasing chip temperature in multi-core embedded technologies.The operating speed of the device decreases when power consumption reaches a threshold that causes a delay in complementary metal oxide semiconductor(CMOS)circuits because high on-chip temperature adversely affects the life span of the chip.In this paper an energy-aware dynamic power management technique based on energy aware earliest deadline first(EA-EDF)scheduling is proposed for improving the performance and reliability by reducing energy and power consumption in the system on chip(SOC).Dynamic power management(DPM)enables MPSOC to reduce power and energy consumption by adopting a suitable core configuration for task migration.Task migration avoids peak temperature values in the multicore system.High utilization factor(ui)on central processing unit(CPU)core consumes more energy and increases the temperature on-chip.Our technique switches the core bymigrating such task to a core that has less temperature and is in a low power state.The proposed EA-EDF scheduling technique migrates load on different cores to attain stability in temperature among multiple cores of the CPU and optimized the duration of the idle and sleep periods to enable the low-temperature core.The effectiveness of the EA-EDF approach reduces the utilization and energy consumption compared to other existing methods and works.The simulation results show the improvement in performance by optimizing 4.8%on u_(i) 9%,16%,23%and 25%at 520 MHz operating frequency as compared to other energy-aware techniques for MPSoCs when the least number of tasks is in running state and can schedule more tasks to make an energy-efficient processor by controlling and managing the energy consumption of MPSoC.

k元(n-1)方体子网络可靠性的近似评估方法

多处理器系统互连网络的拓扑性质对系统功能的实现起着重要的作用。k元n方体网络的子网络可靠性是以k元n方体为拓扑结构构建的多处理器系统处理计算任务时需要考虑的一个重要因素。为了精确高效地度量概率故障条件下k元n方体中k元(n-1)方体子网络的可靠性,提出基于反向传播(BP)神经网络的k元(n-1)方体子网络可靠性的近似评估方法。首先,利用蒙特卡洛仿真方法和k元(n-1)方体子网络可靠性的已有上下界给出用于训练BP神经网络的数据集的生成方法;其次,基于生成的训练数据集构造用于评估k元(n-1)方体子网络可靠性的BP神经网络模型;最后,对BP神经网络模型得出的k元(n-1)方体子网络可靠性的近似评估结果进行了分析,并与近似计算公式和基于蒙特卡洛的评估方法的结果进行了对比。与近似计算公式相比,所提方法得出的结果更为精确;与基于蒙特卡洛的评估方法相比,所提方法的评估耗时平均减少了约59%。实验结果表明,所提方法在兼顾精度和效率方面具有一定优势。

互连网络连通度与诊断度的关联关系研究综述

连通度与诊断度不仅在定义上存在着紧密的关联关系,而且一些诊断度理论也是受到了相关连通度的启发而提出的.本文首先系统综述了连通度与诊断度的研究进展,重点梳理了连通度与诊断度的关联关系,得出了在多处理器计算机系统中,多种诊断度会随着相关连通度的提高而增强,同时呈现出明显线性关系的重要结论.进而通过研究,确定了诊断度与相关连通度之间的具体关联关系可以大大简化诊断度的度量过程,快速计算出多处理器计算机系统的各类诊断度.最后,提出了以互连网络为研究对象,未来开展连通度与诊断度的关联关系研究的方向.研究成果对于推进互连网络的可靠性研究、促进互连网络的应用推广有着非常重要的参考价值.

Design of ANN Based Non-Linear Network Using Interconnection of Parallel Processor

Suspicious mass traffic constantly evolves,making network behaviour tracing and structure more complex.Neural networks yield promising results by considering a sufficient number of processing elements with strong interconnections between them.They offer efficient computational Hopfield neural networks models and optimization constraints used by undergoing a good amount of parallelism to yield optimal results.Artificial neural network(ANN)offers optimal solutions in classifying and clustering the various reels of data,and the results obtained purely depend on identifying a problem.In this research work,the design of optimized applications is presented in an organized manner.In addition,this research work examines theoretical approaches to achieving optimized results using ANN.It mainly focuses on designing rules.The optimizing design approach of neural networks analyzes the internal process of the neural networks.Practices in developing the network are based on the interconnections among the hidden nodes and their learning parameters.The methodology is proven best for nonlinear resource allocation problems with a suitable design and complex issues.The ANN proposed here considers more or less 46k nodes hidden inside 49 million connections employed on full-fledged parallel processors.The proposed ANN offered optimal results in real-world application problems,and the results were obtained using MATLAB.

基于MrsP协议的任务划分优化算法

多处理器实时系统中,调度和资源共享是核心问题,与之相对应的调度算法和共享资源访问协议将直接影响系统的性能,这就要求调度算法和资源访问协议在保证实时性的基础上尽量发挥硬件平台的计算能力。然而,现有的调度算法多假设任务相互独立,没有考虑任务之间的资源共享,共享资源访问协议也多侧重于规则和最坏响应时间分析。对此,将P-RM算法和MrsP协议相结合,得出了多处理器实时系统的整体可调度性条件。文中根据MrsP协议的特性,提出了一种减小阻塞时间的任务划分算法,通过改进任务利用率的计算方式解决了关键区重复计算的问题,与之前的任务划分算法相比,也解决了关键区重复计算以及任务分类后拆分再分配的问题。实验表明,该算法所需要的处理器数目减少了15%~20%。