Distributed computation with communication delay [distributedintelligent sensor networks]

A linear network of communicating processors is examined. The objective is to solve a computational problem in a minimal amount of time. The processors in the networks may be equipped either with or without front-end processors for communication off-loading. The cases of equal division of processing load and optimal division of processing load are discussed for both the network with front-end processors and the network without front end processors. An example of the inclusion of solution time, the time taken for processors to report the solution back to the problem originator, is also presented     

Distributed computation in linear networks: closed-form solutions

A linear network of communicating processors is analyzed. The processors in the network may or may not be equipped with front-end processors. The processing load originates either at the boundary or at the interior of the network. Closed-form solutions and computational techniques are presented for the above situations, to obtain time optimal distribution of processing loads on the processors. Some important results are proved analytically using the closed-form expressions     

Distributed computation for a tree network with communicationdelays

Tree networks of communicating processors are examined with the objective of solving a computational problem in a minimal amount of time. The processors in the networks may be equipped either with or without front-end processors for communicating of loading. The determination of the optimal division of processing load is discussed for the network with and the network without front-end processors. The inclusion of solution time, the time taken for sensors to report the solution back to originator, is discussed     

Wireless sensor networks: scheduling for measurement and data reporting

An optimal load allocation approach is presented for measurement and data reporting in wireless sensor networks with a single level tree network topology. The measurement problem investigated involves a measurement space, part of which can be sampled by each sensor. We seek to optimally assign sensors part of the measurement space to minimize reporting time and energy usage. Three representative measurement and reporting strategies are studied. This work is novel as it considers, for the first time, the measurement capacity of processors and assumes negligible computation time which is radically different from the traditional divisible load scheduling research to date. Aerospace applications include satellite remote sensing and monitoring and sensor networks deployed and monitored from the air.     

Optimal load distribution for tree network processors

A tree network consisting of communicating processors is considered. The objective is to minimize the processing time by distributing the processing load to other nodes. The effect of the order of load distribution on the processing time is addressed. An algorithm which optimally determines the order of load distribution is developed. It is shown that the order depends only on the channel capacity between nodes but not on the computing capability of each node     

Optimal time-varying load sharing for divisible loads

A load sharing problem involving the optimal load allocation of divisible loads in a distributed computing system consisting of N processors interconnected through a bus-oriented network is investigated. For a divisible lend, the workload is infinitely divisible so that each fraction of the workload can be distributed and independently computed on each processor. For the first time in divisible load theory, an analysis is provided in the case when the processor speed and the channel speed are time varying due to background jobs submitted to the distributed system with nonnegligible communication delays. A numerical method to calculate the average of the time-varying processor speed and the channel speed and an algorithm to find the optimal allocation of the workload to minimize the total processing finish time are proposed via a deterministic analysis. A stochastic analysis which makes use of Markovian queueing theory is introduced for the case when arrival and departure times of the background jobs are not known     

Processor equivalence for daisy chain load sharing processors

A linear daisy chain of processors in which processor load is divisible and shared among the processors is examined. It is shown that two or more processors can be collapsed into a single equivalent processor. This equivalence allows a characterization of the nature of the minimal time solution, a simple method to determine when to distribute load for linear daisy chain networks of processors without front end communication subprocessors and closed form expressions for the equivalent processing speed of infinitely large daisy chains of processors     

Divisible load scheduling on single-level tree networks with buffer constraints

Scheduling a divisible load on a heterogeneous single-level tree network with processors having finite-size buffers is addressed. We first present the closed-form solutions for the case when the available buffer size at each site is assumed to be infinite. Then we analyze the case when these buffer sizes are of finite size. For the first time in the domain of DLT (divisible load theory) literature, the problem of scheduling with finite-size buffers is addressed. For this case, we present a novel algorithm, referred to as incremental balancing strategy, to obtain an optimal load distribution. Algorithm IBS adopts a strategy to feed the divisible load in a step-by-step incremental balancing fashion by taking advantage of the available closed-form solutions of the optimal scheduling for the case without buffer size constraints. Based on the rigorous mathematical analysis, a number of interesting and useful properties exhibited by the algorithm are proven. We present a very useful discussion on the implications of this problem on the effect of sequencing discussed in the literature. Also, the impact of Rule A, a rule that obtains a reduced optimal network to achieve optimal processing time by eliminating a redundant set of processor-link pairs, is also discussed. Numerical examples are presented.     

面向机载应用的领域专用加速器研究

机载环境下数据处理规模的剧增以及人机混合智能的应用使得传统的以CPU 为核心计算单元的架构 已不能满足计算需求。在满足延时、精度等指标的情况下,选用高能效的处理器或处理器组合来快速准确地处 理这些数据成为机载计算领域面临的重要问题。按照常规处理器、领域专用加速器两大类型对各自主要代表性 处理器的架构特点进行了分析和总结,得出了各类处理器在机载情况下的主要适用场景和应用情况。根据领域 专用的设计思想开发了面向数据关联应用的专用加速器,对数据关联算法中的统计距离计算和分簇处理这两个 计算瓶颈进行了定制化的加速设计,并在基于FPGA 的平台上进行了测试验证,结果表明,加速器对于统计距 离计算的加速效果约为FT2000/4 单核性能的10 倍,对于分簇处理的加速效果约为FT2000/4 单核性能的3 倍, 整体运算速度相比FT2000/4 处理器的单核提升了5 倍。     

A parallel computer architecture for continuous simulation

A parallel computer specifically designed for the solution of ordinary differential equations is described. The first version of the machine contains thirty-two processors, running in an asynchronous multiple-instruction/multiple-data mode, communicating with high-speed parallel busses. Synchronization is accomplished by a microprogrammable communication controller. A number of processors have been designed and built for the machine. The processor types offer a wide variation in solution speed and accuracy. To permit easy comparisons with analog and hybrid systems, performance is measured by finding the highest frequency sine wave which can be integrated in real time with an accuracy of 0.1% or higher. Using this performance measure the performance limit of the current machine is 2000 Hz. The structure is capable of solving systems described by differential equations up to order sixty-four at these performance limits     

Optimal divisible job load sharing for bus networks

Optimal load allocation for load sharing a divisible job over N processors interconnected in bus-oriented network is considered. The processors are equipped with front-end processors. It is analytically proved, for the first time, that a minimal solution time is achieved when the computation by each processor finishes at the same time. Closed form solutions for the minimum finish time and the optimal data allocation for each processor are also obtained     

Task allocation and reallocation for fault tolerance inmulticomputer systems

The goal of task allocation in a set of interconnected processors (computers) is to maximize the efficient use of resources and thus reduce the job turnaround time. Proposed is a simple yet effective method to allocate the tasks in multicomputer systems for minimizing the interprocessor communication cost subject to resource limitations defined by the system and designer. The limitations can be viewed as results from the load balancing since the execution time of each task, the number of available processors, processor speed, and memory capacity are known to the system or designer. As the number of processors increases, the probability of a failure existing somewhere in the systems at any time also increases. Very few established task allocation models have considered the reliability property. In multicomputer systems, we define system reliability as the probability that the system can run the tasks successfully. After the (nonredundant) task scheduling strategy is defined, tasks are then reallocated to processors statically and redundantly. This is a form of time redundancy, in which if some processors fail during the execution, all tasks can be completed on the remaining processors (but at a longer time). Due to static preallocation of tasks this method is simpler and thus more practical than well-known dynamic reconfiguration and rollback recovery techniques in multicomputer systems. We demonstrate the effectiveness of the task allocation and reallocation for hardware fault tolerance by illustrations of applying the methods to different examples and practical communications network multiprocessor system     

AS4074 与宝石柱 HSDB 协议性能分析及比较

对高速线性令牌传递数据总线的性能进行了分析,建立了排队系统模型,并导出了节点消息延时、等待队列长度等网络特性与网络吞吐量之间的关系表达式,着重讨论了AS4074和宝石柱HSDB两种协议的性能差异,得出AS4074在中、低负载情况下性能优于宝石柱HSDB,因而更适合于新一代航空电子综合系统的结论。     

三种系统可靠性评估方法的比较与分析

故障树、故障Petri网和贝叶斯网络是评估系统可靠性、安全性的三种重要模型。其中,故障树在工程中应用最广,而后两种模型其各自具有不可替代的优点,可以弥补故障树在实际应用中的不足。在介绍三种模型的基础上,通过对故障树向故障Petri网转化方法、故障树向贝叶斯网络转化方法的研究,给出描述三种模型的典型逻辑关系等价结构图的表格,揭示三种模型的内在联系。结合该表,提出故障Petri网向贝叶斯网络的转化方法。同时,利用上述三种模型对导弹发动机故障进行对比分析,结果表明故障Petri网使故障传播过程一目了然,而通过故障Petri网络或故障树转化而来的等价贝叶斯网络可计算出更多定量结果。     

Flowgraph Techniques for Closed Systems

A two-port with both generator and load constitutes a closed system; it can be defined as a system with only interdependent variables or as a system containing no independent variables. The flowgraph describes the relationships between variables in a closed system as determined by the topology of its components. The corresponding closed flowgraph represents a zero-port network from which N-port networks can be generated as subsets by truncation of the closed system. A constraint governing any closed system expressing the properties of its cut-sets and tie-sets is referred to as the topology equation. The topology equation can be computed from the sum of loops in the closed flowgraph, and forms the key for the derivation of properties of closed systems and derived N-port subsets. Oscillators analyzed as zero-ports are discussed in detail to illustrate the rationale for the flowgraph approach to closed systems. To exploit the closed system model conceptually and computationally for N-ports, an approach is suggested and illustrated for N = 1 by an analysis of transfer functions and for N = 2 by a sensitivity analysis of stochastic networks.     

光纤通道在航电设备中的应用和设计

随着信息技术的不断发展,现代战争对信息的传输和处理速度有了更高的要求。光纤通道作为新一代航电系统网络和总线新技术,它具有兼容性好、延迟低、可靠性高、传输速度快和传输距离远等优点,本文介绍了光纤通道的协议结构、拓扑结构、分类服务;并结合航空电子设备的具体需求,提出了应用光纤通道的方案。     

Automated inspection of through hole solder joints utilizing X-rayimaging

Solder joint inspection has traditionally been done by manual inspection. The disadvantage of manual inspection is the large amount of time required and the decrease in efficiency as operator fatigue occurs. This has prompted the development of automated inspection systems to speed up the inspection process and increase efficiency. Automated inspection systems typically use visible light, infrared light or X-rays to illuminate the board. These systems require solder joint position information that is provided either by CAD data or by human entry of the position information. This paper describes a preliminary, automated inspection system that finds the solder joints in an X-ray image and inspects them using an artificial neural network (ANN). The identification of solder joints in the gray-scale image is done using image processing techniques; CAD data or manual registration of the solder joints is not required. The image processing techniques also yield binary maps (i.e., black and white images) showing the locations of ICs and other components, which is useful for other diagnostics     

Graph-tree-based software control flow checking for COTS processors on pico-satellites

 This paper proposes a generic high-performance and low-time-overhead software control flow checking solution, graph-tree-based control flow checking (GTCFC) for space-borne commercial- off-the-shelf (COTS) processors. A graph tree data structure with a topology similar to common trees is introduced to transform the control flow graphs of target programs. This together with design of IDs and signatures of its vertices and edges allows for an easy check of legality of actual branching during target program execution. As a result, the algorithm not only is capable of detecting all single and multiple branching errors with low latency and time overheads along with a linear-complexity space overhead, but also remains generic among arbitrary instruction sets and independent of any specific hardware. Tests of the algorithm using a COTS-processor-based onboard computer (OBC) of in-service ZDPS-1A pico-satellite products show that GTCFC can detect over 90% of the randomly injected and all-pattern-covering branching errors for different types of target programs, with performance and overheads consistent with the theoretical analysis; and beats well-established preeminent control flow checking algorithms in these dimensions. Furthermore, it is validated that GTCGC not only can be accommodated in pico-satellites conveniently with still sufficient system margins left, but also has the ability to minimize the risk of control flow errors being undetected in their space missions. Therefore, due to its effectiveness, efficiency, and compatibility, the GTCFC solution is ready for applications on COTS processors on pico-satellites in their real space missions.     

Classification of radar targets using synthetic neural networks

Radar target classification performance of neural networks is evaluated. Time-domain and frequency-domain target features are considered. The sensitivity of the neural network algorithm to changes in network topology and training noise level is examined. The problem of classifying radar targets at unknown aspect angles is considered. The performance of the neural network algorithms is compared with that of decision-theoretic classifiers. Neural networks can be effectively used as radar target classification algorithms with an expected performance within 10 dB (worst case) of the optimum classifier     

Statistically Optimum Optical Data Processing with Automatic Focus Estimation

The problem of optimally processing data with unknown focus is investigated. Optimum data processors are found by the method of maximum likelihood under a variety of assumptions that apply to most of the situations arising in practice. The unknown focus may be either an unknown parameter or an unknown random variable; the signal may be of known form or a random function; it is further assumed that the signal is received in additive, white, Gaussian noise. The problems of jointly estimating other unknown parameters and, in the case of a random signal, jointly estimating the signal, are also treated. The asymptotic variance and correlation of the estimators is discussed. Electrooptical realizations of the maximum likelihood computers are given. An iterative method of solution of the likelihood equation is also discussed. The discussion and results are directly applicable to the processing of synthetic aperture radar data.