A CAD environment for Real-time DSP implementations on multiprocessors

A software environment designed to support the real-time implementation of Digital Signal Processing (DSP) applications onto multiple programmable processors is described. The system, called McDAS, allows a designer to program his application as he would on a single processor, using a high level signal-flow DSP language. The program is then automatically scheduled and compiled onto a target multiprocessor. The environment allows the scheduler to be invoked with different numbers of processors and multiprocessor topology to explore various implementations. McDAS maximizes the computational throughput by exploiting pipelining, retiming, and parallel execution under the architectural constraints. The code generator is retargetable to different multiprocessor architectures as well as core processors. Data buffers and synchronizations are automatically inserted to ensure correct execution. The final implementation can be used for simulation speedup or real-time processing.     

Software Reliability Model for Modular Program Structure

The paper treats a modular program in which transfers of control between modules follow a semi-Markov process. Each module is failure-prone, and the different failure processes are assumed to be Poisson. The transfers of control between modules (interfaces) are themselves subject to failure. The overall failure process of the program is described, and an asymptotic Poisson process approximation is given for the case when the individual modules and interfaces are very reliable. A simple formula gives the failure rate of the overall program (and hence mean time between failures) under this limiting condition. The remainder of the paper treats the consequences of failures. Each failure results in a cost, represented by a random variable with a distribution typical of the type of failure. The quantity of interest is the total cost of running the program for a time t, and a simple approximating distribution is given for large t. The parameters of this limiting distribution are functions only of the means and variances of the underlying distributions, and are thus readily estimable. A calculation of program availability is given as an example of the cost process. There follows a brief discussion of methods of estimating the parameters of the model, with suggestions of areas in which it might be used.     

Redundant task-allocation in multicomputer systems

A simple yet effective method for improving multicomputer multiprocessor system reliability via redundant allocation of tasks to computers (processors) is described. Given any known (nonredundant) scheduling strategy, tasks are allocated to processors statically and redundantly using a k-circular shifting (KCS) algorithm. so that if some processors fail during the execution. all tasks can be completed on the remaining processors (but at a longer time). Redundant allocation of independent tasks to identical processors (computers), subject to real-time constraints on total execution time, is discussed in detail, and analytic reliability estimates are derived. The longest processing time scheduling is given as an example of nonredundant deterministic scheduling of independent tasks. Processor utilization for redundant task-allocation is discussed and compared with standby redundancy: the authors' KCS algorithm achieves much higher processor utilization than standby redundancy     

基于Amdahl定律扩展的多核处理器性能模型研究

通过引入应用程序并行特征、通信开销、资源限制等因素,建立了基于Amdahl定律扩展的多核处理器性能模型.通过模型参数仿真,搜索面向特定应用的多核处理器设计空间,得出如下规律:增大计算核心规模可实现超线性加速比;结构应优先选择异构结构;设计多进程、大容量的共享通信区可降低核间通信开销;计算核心数目和规模由应用程序并行度和各并行部分比例及设计规模决定.     

DSP处理器单粒子翻转率测试系统的研制

航天器及其内部元器件在太空中会受到单粒子效应(SEE)带来的威胁,因此航天用电子器件在装备前必须进行抗SEE能力的测试评估。针对传统测试方法存在的测试系统程序容易在辐照过程崩溃、统计翻转数不准确、单粒子闩锁(SEL)辨别不清晰和忽略内核翻转统计等问题,设计了一种测试系统,通过片外加载与运行程序从而减少因辐照导致片内程序异常的现象;通过片外主控电路统计被测电路翻转数使统计翻转结果准确;通过主控电路控制被测电路时钟供给排除因频率增加导致电流过大而误判发生SEL的情况;通过内核指令集统计内核翻转数。实验结果表明,该测试系统可以实时全面地监测数字信号处理器(DSP)的SEE,并有效防止辐照实验器件(DUT)因SEL而失效。     

On the transient analysis of a maintained system subject to random stresses

This paper deals with the probablistic analysis of a system subject to stresses. The system consists of a basic unit and a standby and is provided with a service facility to carry out maintenance, inspection prior to repair and repair of the units in the system. The operating unit is sent for maintenance as soon as its strength, after being hit by a stress, falls below a specified critical value, the strength being assumed to be deterministic. The operating unit may also fail on any stress by virtue of the stress exceeding the strength. The failed unit is subject to inspection prior to repair to ascertain the type of repair the unit has to undergo. The stress experienced by a unit is assumed to be a random variable governed by a probability law. The time between successive stresses and the time for maintenance, inspection and repair are random variables governed by probability laws. Explicit expressions for various system characteristics have been obtained using the state-space method and the regeneration point technique.     

A maintenance inspection model for a single machine with general failure distribution

In this paper we develop a mathematical model for determining a periodic inspection schedule in a preventive maintenance program for a single machine subject to random failure. We formulate the problem as a profit maximization model with general failure time distribution. We show that under certain conditions on the probability density function of failure, a unique optimal inspection interval can be obtained. When the failure times are exponentially distributed, we propose alternative optimal and heuristic procedures to find exact and approximate inspection intervals. Our heuristic solution method is shown numerically to be more efficient than an earlier published heuristic procedure. We also investigated the sensitivity of the optimal inspection interval and expected profit per unit of time with respect to the changes in the two parameters of the Weibull time to failure distribution.     

Study on adaptive job assignment for multiprocessor implementationof MPEG2 video encoding

The high demand on computation performance by multimedia information processing such as digital video compression and decompression has made multiprocessor computation more and more popular. In this paper, we present our study on adaptive job assignment for multiprocessor implementation of a Motion Picture Expert Group 2 (MPEG2) video encoding algorithm. Data partitioning technique is used for job assignment to the processors in the multiprocessor environment to exploit the data structure adopted by the MPEG standard that divides a frame of a picture into macro blocks (MBs) which are processed independently during encoding. An adaptive data partitioning scheme is developed to cope with the inherent nonuniform spatial distribution of motion activities, such that the computation load distribution over processors is as uniform as possible, which helps improve the speedup of the whole multiprocessor system. Simulations with several video sequences have shown that, in comparison to its nonadaptive counterpart, the adaptive scheme can effectively improve the speedup of the multiprocessor system. In addition, the speedup scales well with the increase of the number of processors used in the computation     

Optimum scheduling of a new maintenance program under stochastic degradation

In this paper we consider an intermittently operating system which is under periodic review and which is subject to random aging or degradation. The optimal schedule when initiating a new maintenance program is analyzed so as to minimize the long term discounted cost. The scheduled maintenance is based on the level of system degradation rather than time. The functional equation approach enables one to incorporate such factors as the fixed cost of maintenance, the recurring costs, the discount factor and the probability distribution of aging in a given period. The analysis is illustrated with an example.     

Stochastic behavior of a two-unit cold standby redundant system subject to random failure

The present paper deals with a stochastic model of a two-unit cold standby redundant system subject to random failure. The random failure occurs at random times which follow an exponential distribution. Using a regenerative point technique in the Markov-renewal process, several reliability characteristics are obtained. The mean time to system failure function is studied graphically.     

Image processing using one-dimensional processor arrays

The first half of this paper presents the design rationale for CNAPS, a specialized one-dimensional (1-D) processor array developed by Adaptive Solutions Inc. In this context, we discuss the problem of Amdahl's law which severely constrains special-purpose architectures. We also discuss specific architectural decisions such as the kind of parallelism, the computational precision of the processors, on-chip versus off-chip processor memory, and-most importantly-the interprocessor communication architecture. We argue that, for our particular set of applications, a 1-D architecture gives the best “bang for the buck”, even when compared to the more traditional two-dimensional (2-D) architecture. The second half of this paper describes how several simple algorithms map to the CNAPS array. Our results show that the CNAPS 1-D array offers excellent performance over a range of IP algorithms. We also briefly look at the performance of CNAPS as a pattern recognition engine because many image processing and pattern recognition problems are intimately related     

Failure Time for a Redundant Repairable System of Two Dissimilar Elements

The distribution of time to failure for a system consisting of two dissimilar elements or subsystems operating redundantly and susceptible to repair is discussed. It is assumed that the times to failure for the two system elements are independent random variables from possibly different exponential distributions, and that the repair times peculiar to each element are independently distributed in an arbitrary fashion. For this basic model a derivation is given of the Laplace-Stieltjes transform of the distribution function of time to system failure, i.e, the time until both elements are simultaneously down for repair, measured from an instant at which both are operating. An explicit formula is given for the mean or expected time to system failure, a natural approximation to the latter is exhibited, and numerical comparisons indicate the quality of this approximation for various repair time distributions. In a second model the possibility of system failures due to overloading the remaining element after a single element failure is explicitly recognized. The assumptions made for the basic model are augmented by a stochastic process describing the random occurrence of overloads. Numerical examples are given. Finally, it is shown how the above models may be easily modified to account for delays in initiating repairs resulting from only occasional system surveillance, and to account for random catastrophic failures.     

A Standby Redundant Model with Noninstantaneous Switchover

This paper considers the case of a standby redundant system where the switchover is not instantaneous. The duration of time between the instant at which action is initiated on the standby subsystem in order to bring it to the active state and the instant at which it becomes operating standby is called switchover time, and is considered to be a random variable. A policy specifying the instant at which action is initiated on the standby subsystem in order to bring it to the operating standby state is proposed and under this proposed policy, the Laplace transform of the probability density function of time to system failure and the expression for expected time to system failure are derived.     

Single-unit system with corrective maintenance at random checks governed by probabilities in a geometric progression

A system which comprises only one unit and a single server is considered. While the unit is in operation, at random intervals it is subjected to checks for corrective maintenance (CM). While the unit is under CM, it is also working and thus may fail. The probabilities that the unit will not undergo CM at random checks are in geometric progression (p, p², p³,…), whereas the probabilities that the unit will undergo CM are (1 − p, 1 − p²,…). We consider three models, and obtain the mean time to system failure and steady-state availability of the system for these models.     

Reliability of checkpointed real-time systems using time redundancy

Real-time computers are often used in embedded, life-critical applications where high reliability is important. A common approach to making such systems dependable is to vote on redundant processors executing multiple copies of the same task is described. The processors which make up such voted systems are subjected not only to independently occurring permanent and transient failure, but also to correlated transients brought about by electromagnetic interference from the operating environment. To counteract these transients, checkpointing and time redundancy are required, in addition to processor redundancy. This work analyzes the use of time and device redundancy in systems subject to correlated failure. The tradeoffs in checkpoint placement in such a system are found to be considerably different from those for non-redundant systems without real-time constraints. The authors compare fault-tolerant designs and without a rollback capability, accounting for the increased hardware-failure rate due to processor duplication when faults are detected in hardware, and the doubled execution times when detection is implemented in software     

Failure-Aware Task Scheduling of Synchronous Data Flow Graphs Under Real-Time Constraints

As more processors are integrated into Multiprocessor System-on-Chips (MPSoCs) via relentless technology scaling, the mean-time-to-failure (MTTF) is reduced to the extent that unexpected processor failures are considered during design time. A popular approach to tolerate processor failures is to migrate tasks on the faulty processor to live processors. This approach, however, is not suitable for real-time digital signal processing (DSP) applications since it may not guarantee real-time constraints. In this paper, we propose the re-scheduling of the entire application to minimize throughput degradation under a latency constraint, given that the application is specified by a Synchronous Data Flow (SDF) graph. We obtain sub-optimal re-scheduling results using a genetic algorithm for each scenario of processor failures at compile-time. If a failure is detected at run-time, the live processors obtain the saved schedule, perform task transfer, and execute the remaining tasks of the current iteration. We compare preemptive and non-preemptive migration policies and propose a hybrid policy to obtain better performance. We demonstrate the viability of the proposed technique through experiments with real-life DSP applications as well as randomly generated graphs under timing constraints and random fault scenarios.     

Cost analysis of a two-unit standby system with delayed replacement and better utilization of units

This paper develops the model for a system, having two identical units—one operative and the other cold standby. Each unit of the system has three modes—normal, partial failure and total failure. The replacement time of a failed unit by a standby unit is not negligible but is a random variable. System fails when both the units fail totally. Failure time distributions of units are exponential, whereas repair time distributions are arbitrary. Several reliability characteristics of interest to system designers and operations managers have been evaluated using the theory of regeneration point technique.     

Availability Allocation Using a Family of Hyperbolic Cost Functions

This paper develops a technique for allocating the parameters, repair time and failure rate, to each component of a system at the lowest possible cost. The allocations are subject to the constraint of a required availability. To make an analytic solution possible, the assumptions of constant failure rates, s-independent components, series system, and no multiple failures were made. Each component is assumed to have a hyperbolic cost function associated with changing its failure rate and its repair time. A Lagrange Multiplier method was used to solve the problem.     

The Effect of Partial Failure Modes on Reliability Analysis

An analysis is presented of the effect of partial failure modes on the calculation of an optimum amount of redundancy. (Partial failure modes are modes that are catastrophic to the part but not to the system.) The analysis is limited to systems that are not repaired, whose performance can be measured with a one-dimensional capacity index, and that are composed of parts that fail in only one mode. The problem is formulated in terms of loss coefficients and state probabilities and a model is given to organize computation of the state probabilities. The analysis is incorporated into a redundancy optimization program so that, for the first time, optimal redundancy can be calculated for systems with partial failure modes. This program is applied to an example system and the results are explained. It is shown that the partial failure mode analysis will always yield a lower expected loss, will thus require less redundancy, and hence will yield a lower initial system cost than the equivalent total failure-mode analysis.