On the Accelerated Scan Finite Markov Chain Imbedding Approach

As an excellent tool for reliability system research, the finite Markov chain imbedding (FMCI) approach can be used not only to evaluate the system reliability, but also to do other research in reliability systems such as generating functions, waiting time, and optimal arrangement problems. But the computation for system reliability based on the FMCI approach becomes difficult if the number of components in the system is comparatively large, because there would be more matrices that need to be multiplied. To overcome this drawback, the accelerated scan finite Markov chain imbedding (AS-FMCI) approaches with fixed step length, and alterable step, are introduced in this paper to decrease the complexity of computation for system reliability through decreasing the number of the matrixes that need to be multiplied. A numerical example is presented, and the results show that the new method can save computational time.      

Optimal design of fault-tolerant distributed systems based on arecursive algorithm

The authors address the issue of optimal design (in terms of the number of processors) of a distributed system which is based on a recursive algorithm for fault tolerance (RAFT). The reliability and performance of the system using RAFT are determined as a function of reliability of individual processors and the number of fault modes in a processor. Also discussed are how to determine the design policies when the objective is to minimize the average system failure. Several numerical examples illustrate the results     

A Heuristic Method for Determining Optimal Reliability Allocation

The paper presents a method for obtaining an optimal reliability allocation of an n-stage series system. In each stage, redundant comnponents can be added (in parallel, stand-by, or k-out-of-n:G, etc.), or a more reliable component can be used in order to improve the system reliability. The solution is obtained by repeatedly using a more reliable candidate at each stage that has the greatest value of a `weighted sensitivity function'. The balance between the objective unction and the constraints is controlled by a `balancing coefficient'. The overall computational procedure is given and an example is presented. The computations are given for a set of randomly generated test problems in which the optimal parallel redundancy under linear onstraints is determined. The proposed method is then compared with other methods.     

Gossip-Based Load Balance Strategy in Big Data Systems with Hierarchical Processors

In big data systems, data are assigned to different processors by the system manager, which has a large amount of work to perform, such as achieving load balances and allocating data to the system processors in a centralized way. To alleviate its load, we claim that load balancing can be conducted in a decentralized way, and thus, the system manager need not be in charge of this task anymore. Two decentralized approaches are proposed for load balancing schemes, namely, a utilization scheme based on a load balance algorithm (UBLB) and a number of layers scheme based on a load balance algorithm (NLBLB). In the UBLB scheme, considering the hierarchy of the processor’s processing abilities, a gossip-based algorithm is proposed to achieve load balance using the jobs’ utilizations as load balance indicators in addition to the number of jobs. The reason for this action is that the processor’s process abilities are different from one another. Thus, the utilization indicator is more reasonable. In the NLBLB scheme, the processors are classified into different layers according to their processing abilities. In each layer, a sub-load balance is conducted, which means that the UBLB is achieved in a sub-region. The efficiencies of the two proposed schemes are validated by simulation, which proves their positive effect.     

DSP与FPGA的SRIO互连设计

在DSP+FPGA的高速图像处理系统中,针对系统数据量大、运算复杂的特点,提出了一种基于SRIO协议的DSP与FPGA处理器互连,并进一步使用FPGA中的MPMC控制器连接DDR2SDRAM,实现了图像处理系统内部处理器的共享存储。该方法通过在DSP和FPGA上编程,实现了SRIO协议中的存储器映射I/O事务(LSU)方式的传输,处理器之间通过SRIO接口传输的数据速率达到3.125Gb/s。实验结果表明,该方法有效地实现了处理器之间数据稳定可靠的传输,使系统内的数据交换灵活快捷,提高了DSP的协处理能力,很好地满足了处理系统实时性的需求。     

An efficient motion vector composition algorithm for fast-forward playback in a video streaming system

Fast-forward playback enables viewers to scan through the video scene of interest efficiently. One approach to realize fast-forward playback is to employ a frame-skipping transcoder which transcodes only the frames required for playback at the desired fast speed. Various motion vector composition algorithms are used to compose the new motion vectors with reduced complexity. These algorithms do not work well for dropping a large number of frames, which is very common in fast-forward playback. In this paper, a new multiple-candidate vector selection algorithm (MCVS) is proposed to select a composed motion vector from a set of candidate motion vectors, which utilizes relevant areas in the target macroblock to ensure a reliable tracking process for motion vector composition. Experimental results show that the proposed MCVS can provide fast-forward playback through video transcoding with significant gain, in terms of rate-distortion performance, especially when a large speed-up factor is required.     

Stochastic gradient optimization of importance sampling for theefficient simulation of digital communication systems

Importance sampling (IS) techniques offer the potential for large speed-up factors for bit error rate (BER) estimation using Monte Carlo (MC) simulation. To obtain these speed-up factors, the IS parameters specifying the simulation probability density function (PDF) must be carefully chosen. With the increased complexity in communication systems, analytical optimization of the IS parameters can be virtually impossible. We present a new IS optimization algorithm based on stochastic gradient techniques. The formulation of the stochastic gradient descent (SGD) algorithm is more general and system-independent than other existing IS methodologies, and its applicability is not restricted to a specific PDF or biasing scheme. The effectiveness of the SGD algorithm is demonstrated by two examples of communication systems where the IS techniques have not been applied before. The first example is a communication system with diversity combining, slow nonselective Rayleigh fading channel, and noncoherent envelope detection. The second example is a binary baseband communication system with a static linear channel and a recursive least square (RLS) linear equalizer in the presence of additive white Gaussian noise (AWGN)     

An Algorithm to Determine the Reliability of a Complex System

The method most often suggested for determining the reliability of a system is to construct a reliability network, enumerate from the network all mutually exclusive working states of the system, calculate the probability of occurrence of each working state, and sum these probabilities. For a complex system this is not a practical method for there is a very large number of working states. Esary and Proschan suggest a lower bound approximation to reliability that requires the enumeration of a much smaller set of system states. These states are called minimal cuts. An algorithm is presented to determine the set of minimal cuts and thus calculate a lower bound to system reliability. The algorithm is intended for digital-computer implementation and computational times are provided.     

A distributed algorithm for fault simulation of combinatorial and asynchronous sequential digital designs, utilizing circuit partitioning, on loosely-coupled parallel processors

Fault simulation constitutes an indispensable tool in ensuring the correctness and quality of manufactured digital designs. Traditional uniprocessor based algorithms for fault simulation have been observed to be agonizingly slow for today's large and complex digital designs. More recently, a few researchers introduce an approach, as evident in the literature, wherein the fault set is partitioned and the digital design fault simulated for each of the fault subset on separate processors of a parallel processor system. The approach is limited in that it continues to utilize the traditional uniprocessor-based algorithm and the performance results are not encouraging. This paper introduces, perhaps for the first time, a distributed algorithm that is capable of fault simulating both combinational and asynchronous sequential digital designs on parallel processors. An underlying assumption of the algorithm is that the digital design, under fault simulation, is partitioned by the user. In this approach, referred to as NODIFS in this paper, every component in the circuit is modeled as an asynchronous, concurrent, entity that is fault simulated as soon as appropriate signal transitions and fault lists are asserted at its input ports. The circuit partitioning is such that components of every partition are allocated to a unique processor of the parallel processor system. Consequently, a number of components may be concurrently fault simulated on multiple processors in NODIFS implying significant increase in throughput. This approach promises (i) very high throughput because of its ability, in principle, to utilize the maximal inherent parallelism, and (ii) scalability. The algorithm is novel in that the overall task of decision-making i.e., fault simulation of the circuit, is distributed into a number of natural, independent, and concurrent entities that execute asynchronously to utilize maximal parallelism. NODIFS's success is the result of the asynchronous distributed discrete-event simulation algorithm, YADDES, and a new approach to fault simulation. The notion of scalability implies that where the problem size increases, the algorithm continues to apply and, by increasing the number of computational engines proportionately, the performance of the algorithm will continue to increase. Furthermore, NODIFS is a natural choice for fault simulation of digital designs at the behavior-level — an eventual reality, wherein the ratio of the computational to communication load for the behavior models may approach a significantly large value. This paper also reports on an implementation of NODIFS on both the ARMSTRONG parallel processor system at Brown University and the performance results indicate significant increase in the speedup for a few representative example digital designs. It is stressed that the representative digital designs serve to support the mathematical validity of the algorithm along with the proof of correctness and not to demonstrate a high-performance, commercial, industrial-quality fault simulator.     

Image processing on a memory array architecture

In this paper we examine the usefulness of a simple memory array architecture to several image processing tasks. This architecture, called theAccess Constrained Memory Array Architecture (ACMAA) has a linear array of processors which concurrently access distinct rows or columns of an array of memory modules. We have developed several parallel image processing algorithms for this architecture. All the algorithms presented in this paper achieve a linear speed-up over the corresponding fast sequential algorithms. This was made possible by exploiting the efficient local as well as global communication capabilities of the ACMAA.     

Instruction Set Extensions for MPEG-4 Video

This paper describes instruction set extensions for the acceleration of MPEG-4 algorithms on programmable (RISC-) CPUs. MPEG-4 standardizes audio and video compression schemes for a variety of bit rates and scenarios. As MPEG-4 targets a much broader range of different applications than previously defined hybrid video coding standards like H.263 or MPEG-2, it employs a much higher number of different algorithms and coding modes. Therefore, MPEG-4 implementations will require a more software-oriented approach to be efficient. However, the total computational load for an optimized implementation of an MPEG-4 video codec is expected to exceed the performance levels of today's multimedia signal processors, making further hardware acceleration a necessity. For that purpose, we propose a number of instruction set extensions that add function-specific blocks to the data path of a CPU. These dedicated modules are highly adapted to the most computation-intensive processing schemes of MPEG-4, such as DCT, motion compensation, padding, shape coding, or bitstream parsing. The increased functionality of basic instructions results in a significant speed-up over standard RISC instruction sets, thus making MPEG-4 implementations feasible on programmable processor platforms. Possible target architectures include VLIW multimedia processors, MIMD-style multiprocessors, or coprocessor architectures     

Amdahl's law: a generalization under processor failures

Recent advances in VLSI technology make it possible to manufacture computer systems with thousands of processors that can work concurrently on the same problem and improve the running time of programs. Amdahl's law measures the speedup (the ratio of the running time of a program on a 1-processor system to the running time of the same program on a multi-processor system) under the assumptions that processors are fault free and do not fail. This paper generalizes Amdahl's law under the assumption that processors are subject to failures. If the failure of processors is modeled as random, the actual number of processors available to a program becomes a random variable as well. This stochastic process is represented by a closed queuing network, and it is completely analyzed under certain assumptions. Numerical results show that value of the degradation factor (the ratio of failure rate of processors to their repair rate) is crucial to the system performance. Amdahl's law implicitly uses the fact that all of the processors are used by the parallel portion of a program. However, for a real system, processors are subject to failure, and consequently, the number of available processors becomes random. This paper assumes that processors may fail and re-evaluates the expression for the speedup factor in Amdahl's law. It obtains closed-form expressions for the speedup factor and the PLF (performance loss factor)     

Redundancy Allocation for Series-Parallel Systems Using Integer Linear Programming

We consider the problem of maximizing the reliability of a series-parallel system given cost and weight constraints on the system. The number of components in each subsystem, and the choice of components are the decision variables. In this paper, we propose an integer linear programming approach that gives an approximate feasible solution, close to the optimal solution, together with an upper bound on the optimal reliability. We show that integer linear programming is a useful approach for solving this reliability problem. The mathematical programming model is relatively simple. Its implementation is immediate by using a mathematical programming language, and integer linear programming software. And the computational experiments show that the performance of this approach is excellent based on a comparison with previous results.      

PCB外观检查机形态学运算多核并行加速的实现

为了解决PCB外观检查机中存在的速度问题,对其中用到的形态学运算采用多核并行的方式进行加速。给出了腐蚀运算的普通算法和一种优化算法的多核并行实现过程。实验表明,无论是形态学运算的普通串行算法还是优化算法,通过多核并行处理的方式都可使其运算速度大幅提高。当运算规模较大时,并行加速比可趋近参于运算的处理器数量。     

相关竞争失效场合雷达功率放大系统可靠性评估

针对相关竞争失效场合难以获取高可靠部件的性能分布信息,无法对系统可靠性进行准确估计的问题.提出了相关竞争失效场合下考虑认知不确定性的多态系统可靠性评估方法.该方法首先通过假定部件突发失效阈值为递减型随机过程来表征累积退化与突发失效的相关性,同时为降低对部件认知不确定性的影响,假定冲击引起的部件性能损伤分布参数和突发失效参数均为区间变量,建立基于区间变量的部件性能分布模型;而后对传统的通用生成函数方法进行改进,给出了区间通用生成函数的定义及其运算法则;最后对某型雷达功率放大系统的可靠性进行分析.该方法不仅克服了部件的失效模式复杂、状态信息少的不足,且方法简单、思路清晰,具有很强的通用性和工程应用价值.     

Efficient algorithms for k-out-of-n andconsecutive-weighted-k-out-of-n:F system

A new reliability model, consecutive-weighted-k-out-of-n:F system, is proposed and an O(n) algorithm is provided to evaluate its reliability. An O(n·min(n,k)) algorithm is also presented for the circular case of this model. The authors design an O(n) parallel algorithm using k processors to compute the reliability of k-out-of-n systems, that achieves linear speedup     

Digital Circuit Redundancy

While some original work is presented, this paper is mainly of the nature of a survey of redundancy techniques to date. Several redundancy techniques are described in detail with mathematical models for estimating reliability improvement. The methods are compared on the basis of reliability improvement and general comments are made about applications. The reliability equations for Moore-Shannon, majority, gate connector, and other redundancies, show that Moore-Shannon type of redundancy provides the best reliability improvement An example of a Moore-Shannon redundant flip-flop shows that large reliability improvements are obtained applying redundancy to only the less reliable components, thus keeping the amount of redundancy to a minimum.     

An architectural co-synthesis algorithm for distributed, embeddedcomputing systems

Many embedded computers are distributed systems, composed of several heterogeneous processors and communication links of varying speeds and topologies. This paper describes a new, heuristic algorithm which simultaneously synthesizes the hardware and software architectures of a distributed system to meet a performance goal and minimize cost. The hardware architecture of the synthesized system consists of a network of processors of multiple types and arbitrary communication topology; the software architecture consists of an allocation of processes to processors and a schedule for the processes. Most previous work in co-synthesis targets an architectural template, whereas this algorithm can synthesize a distributed system of arbitrary topology. The algorithm works from a technology database which describes the available processors, communication links, I/O devices, and implementations of processes on processors. Previous work had proposed solving this problem by integer linear programming (ILP); our algorithm is much faster than ILP and produces high-quality results     

基于CPCI架构的大数据量红外图像实时处理系统

针对大规模、高帧频的红外探测器所具有的红外图像数据量大,对图像的传输速度和处理能力要求高的特点,提出了一种高性能的红外图像实时处理系统。该系统依托CPCI体系架构具有的传输速度快、扩展能力强、可靠、稳定等特点,通过利用FPGA+DSP的高速信号处理平台,实现大数据量红外图像的高速传输、实时处理、信息融合、目标检测和目标跟踪功能。该系统架构设计简单,使用灵活,扩展性好,充分结合了不同处理器件的优点,具有图像处理能力强、数据传输速度快、接口可靠方便和编程灵活等特点。该系统已经在具体项目中得以应用,能够满足大数据量红外图像实时处理的要求。     

Optimal algorithms for synthesis of reliable application-specificheterogeneous multiprocessors

Fast and optimally-reliable application-specific multiprocessor-synthesis is critical in system-level design, especially in medical, automotive, space, and military applications. Previous work in multiprocessor-synthesis and task-allocation for performance and reliability requires exponential time, and therefore, is useful only for small examples. We present the first deterministic and provably-optimal algorithm (RELSYN-OPT) to synthesize real-time, reliable multiprocessors using a heterogeneous library of N processors and L link types. We prove that for a series-parallel graph with M subtasks and nested-depth d, the worst-case computational complexity of RELSYN-OPT Is O(M·(L+N)·N^d). For tree-structured task graphs, RELSYN-OMT runs in O(M·(L+N)), and is asymptotically optimum, RELSYN-OPT, because of its speed, applies to static and dynamic task allocation for an ultra-reliable distributed processing environment for which, until now, research has produced only suboptimal heuristic solutions