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.

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.

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.

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.

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.

Development of single-chip fuzzy controller based on FFSI in binary

Length and concise structure of fuzzy logic reasoning program and its real-time reasoning characteris-tic have their effect on the performance of a digital single-chip fuzzy controller. The control effect of a digitalfuzzy controller based on looking up fuzzy control responding table is only relative to the table and not relative tothe fuzzy control rules in the practical control process. Aiming at above problem and having combined fuzzy log-ic reasoning with digital operational characteristics of a single-chip microcomputer, functioning-fuzzy-subset in-ference (FFSI) in binary, in which triangle membership functions of error and error-in-change are all represen-ted in binary and singleton membership functions of control variable is binary too, has been introduced. The cir-cuit principle plans of a single-chip fuzzy controller have been introduced for development of its hardware, andthe primary program structure, fuzzy logic reasoning subroutine, serial communication subroutine with PC andreliability design of the fuzzy controller are all discussed in detail. The control of indoor temperature by a fuzzycontroller has been conducted using a testing-room thermodynamic system. Research results show that the FFSIin binary can exercise a concise fuzzy control in a single-chip fuzzy controller, and the fuzzy controller is there-fore reliable and possesses a high performance-price ratio.

Fork-Join program response time on multiprocessors with exchangeable join

The Fork-Join program consisting of K parallel tasks is a useful model for a large number of computing applications. When the parallel processor has multi-channels, later tasks may finish execution earlier than their earlier tasks and may join with tasks from other programs. This phenomenon is called exchangeable join (EJ), which introduces correlation to the task’s service time. In this work, we investigate the response time of multiprocessor systems with EJ with a new approach. We analyze two aspects of this kind of systems: exchangeable join (EJ) and the capacity constraint (CC). We prove that the system response time can be effectively reduced by EJ, while the reduced amount is constrained by the capacity of the multiprocessor. An upper bound model is constructed based on this analysis and a quick estimation algorithm is proposed. The approximation formula is verified by extensive simulation results, which show that the relative error of approximation is less than 5%.

Gas concentration monitoring system for small and medium-sized coal mines based on gas-sensing detection and single-chip control

This paper is aimed at the actual conditions of disaster caused by gas in small and medium-sized coal mines. A new gas concentration monitoring system for coal mines is developed on the basis of gas-sensing detection and single-chip control. The monitoring system uses the tin oxide as the main material of N-type semiconductor gas sensors, be- cause it has good sensitive characteristics for the flammable and explosive gas （ such as methane, carbon monoxide）. The QM-N5-semiconductor gas sensor is adopted to detect the output values of the resistance under the different gas con- centrations. The system, designedly, takes the AT89C51 digital chip as the core of the circuit processing hardware structure to analyze and judge the input values of the resistance, and then achieve the control and alarm for going beyond the limit of gas concentration. The gas concentration monitoring system has man）, advantages including simple in struc- ture, fast response time, stable performance and low cost. Thus, it can be widely used to monitor gas concentration and provide early wamings in small and medium-sized coal mines.

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.

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.

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.

Temporal consistency maintenance on multiprocessor platforms with instance skipping

Maintaining temporal consistency of real-time data is important for cyber-physical systems.Most of the previous studies focus on uniprocessor systems.In this paper,the problem of temporal consistency maintenance on multiprocessor platforms with instance skipping was formulated based on the(m,k)-constrained model.A partitioned scheduling method SC-AD was proposed to solve the problem.SC-AD uses a derived sufficient schedulability condition to calculate the initial value of m for each sensor transaction.It then partitions the transactions among the processors in a balanced way.To further reduce the average relative invalid time of real-time data,SC-AD judiciously increases the values of m for transactions assigned to each processor.Experiment results show that SC-AD outperforms the baseline methods in terms of the average relative invalid time and the average valid ratio under different system workloads.

A Single-Chip UHF RFID Reader Transceiver IC

A single-chip UHF RFID reader transceiver IC has been implemented in 0.18 μm SiGe BiCMOS technology. The chip includes all transceiver blocks as RX/TX RF front-end, RX/TX analog baseband, frequency synthesizer and I2C with fully-compliant China 800/900 MHz RFID draft, ISO/IEC 18000-6C protocol and ETSI 302 208-1 local regulation. The normal mode receiver in the presence of -3 dBm self-jammer achieves -75 dBm 1% PER sensitivity. The linear class-A PA integrated in transmitter has 25 dBm OP1 dB output power for CW. The fully-integrated fractional-N fre-quency synthesizer is designed based on MASH 1-1-1 sigma-delta modulator and 1.8 GHz fundamental frequency LC-VCO for lower in-band and out-of-band phase noise. The measured phase noise is up to -106 dBc/Hz@200 kHz and -131 dBc/Hz@1 MHz offset from center frequency and the integrated RMS jitter from 10 kHz to 10 MHz is less than 1.6 pS. The chip dissipates 330 mA from 3.3 V power supply when transmitting 22.4 dBm CW signal and the PAE of linear PA is up to 26%. The chip die area is 16.8 mm2.

具有缺弧和失效点的单定向超立方体的诊断度

对于大规模多处理器系统,为了保证其可靠性,需要将发生故障的处理器及时诊断出来并进行更换。诊断度是系统能够自我识别的故障处理器的最大数目。n维单定向超立方体UQ_(n)是通过对超立方体Q_(n)所有的边进行定向得到的一个有向网络。研究了PMC模型下具有缺弧和失效点的单定向超立方体的诊断度。设S是UQ_(n)中缺弧和失效点的集合且S≤n/2」-1.通过对其缺弧和失效点的分布模式进行讨论,得到了UQ_(n)-S在PMC模型下的诊断度为UQ_(n)-S的最小入度,其中n≥3.

一种分片式多核处理器的用户级模拟器

随着片上晶体管资源的增多和互连线延迟的加大,分片式多核微处理器已成为多核处理器设计的新方向.为了对这种新型处理器进行体系结构的深入研究和设计空间的探索,设计并实现了针对分片式多核处理器的用户级多核性能模拟器.该多核模拟器在龙芯2号单处理器核的基础上,完整地模拟了基于目录的Cache一致性协议和存储转发式片上互联网络的结构模型,详细地刻画了由于系统乱序处理各种请求应答和请求之间的冲突而造成的时序特性,可以通过运行各种串行或并行的工作负载对多核处理器的各种重要性能指标加以评估,为多核处理器的结构设计提供了快速、灵活、高效的研究平台.

多处理器实时系统可调度性分析的UPPAAL模型

随着多处理器实时系统在安全性攸关系统中的广泛应用,保证这类系统的正确性成为一项重要的工作.可调度性是实时系统正确性的一项关键性质.它表示系统必须满足的一些时间要求.传统的可调度性分析方法结论保守或者不完备,为了避免这些方法的缺陷,提出使用模型检测的方法来实现可调度性分析.提出了一个用于多处理器实时系统可调度性分析的模板,将与系统可调度性相关的部分包括实时任务、运行平台和调度管理模块都用时间自动机建模,并使用UPPAAL验证可调度的性质是否总被满足.符号化模型检测方法被用于推断可调度性,但是由于秒表触发的近似机制,符号化模型检测方法不能用于证明系统不可调度.作为补充,统计模型检测方法被用于估算系统不可调度的概率,并在系统不可调度时生成反例.此外,在系统可调度时,通过统计模型检测方法获取一些性能相关的信息.

多机多任务实时系统云调度策略

采用云方法对多机实时系统任务的重要性和任务处理的适时性进行分析 ,实时计算被激活任务的价值及其在不同资源条件下的作业执行时间 ,提出一种兼顾任务价值和作业执行时间两方面因素的新的调度策略——云调度策略 ,有效地解决了任务优先级的判定和任务处理适时性问题 ,提高了系统资源利用效率、运行质量和系统整体效能 .仿真证明 ,此策略优于现在广泛采用的固定优先级和先到先处理调度策略 .