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     

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     

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     

Equal allocation scheduling for data intensive applications

A new analytical model for equal allocation of divisible computation and communication load is developed. Equal allocation of load is attractive in multiple processor systems when real time information on processor and link capacity that is necessary for optimal scheduling is not available. The model includes a detailed accounting of solution reporting time. Equal allocation scheduling is compared with sequential scheduling and a new type of multi-installment scheduling. Aerospace applications include the processing of satellite imagery, radar, and sensor networks.     

Fast Algorithms for Time Domain Broadband Adaptive Array Processing

Recursive algorithms are presented for time domain, broadband, adaptive beamforming. The algorithms are rapidly converging and can be computationally efficient for a certain range of array processor parameters. The algorithms are presented for two forms of array processor. One form is a Frost-type structure in which explicit constraints are required for defining the array-look direction and also to control the sensitivity of the array processor to implementation errors. The other form is a partitioned array processor in which constraints are built into the processor and the adaptive weight control algorithm is therefore unconstrained. The two processors presented are both element-space processors but the algorithms can be applied also to beam-space processors.     

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.     

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 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     

Some Effects of Hard Limiting in Adaptive Antenna Systems

Adaptive antennas are often implemented with the Applebaum-Howells-type adaptive processor usually include a hard limiter between each antenna port and its correlation mixer, primarily for dynamic range compression. Brennan and Reed [3] analyzed the effects of hard limiting, and their conclusions suggest that it does not degrade the steady-state performance of the adaptive processor. Standard and hard-limited processors are compared and it is shown that when the two types of processor have the same sensitivity threshold, the hard-limited one can fail to provide sufficient interference cancellation when the correlation matrix of input signals has two or more eigenvalues of differing magnitudes. The consequence of hard limiting is that (depending on the processor design parameters) the larger of two or more signals can capture the hard limiter, allowing the smaller signals to pass through the processor essentially unattenuated. It is also shown that when a hard-limited processor is designed to provide the same cancellation as a standard one, it must have essentially as large a dynamic range as the standard, processor; therefore, it offers no advantage of dynamic range compression. Moreover, the hard-limited processor lacks a constant sensitivity threshold, which can be a desirable feature of a standard processor. Specific examples are presented for identical-element array antennas and for multiple-beam antennas.     

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     

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     

Paral lel VLSI Implementation of the Kalrman Filter

The problem of parallel implementation of the square-root Kalman filters is addressed. At the system level, our approach is to apply systolic-type VLSI processor arrays as basic building blocks to accelerate the matrix operations required in each iteration. To maximize the parallelism, we also exploit an inter-array pipelining scheme through the overlapping of execution between successive processor arrays. We estimate that with (5n2 + r2 + 8nr + n + 3r)/2 processors, it would take max[(4n + 2r, 2n + 4r-2)] time units to complete one Kalman filter iteration, where n is the dimension of the underlying state space model and r is the dimension of the input vector.     

基于多分区操作系统的多核确定性调度方法设计

为提高多分区操作系统环境下多核处理器的应用带来的操作系统任务调度的确定性,研究了多分环境下多核操作系统结构,从处理器核心和分区的资源分配和分区调度表的时间同步角度出发,采用了静态配置、处理器绑定和时间窗口调度方法,实现了处理器资源的确定性分配,解决了调度表之间的时间同步问题。测试结果表明,方法有效提高了分区环境下多核操作系统任务调度的确定性。     

软件无线电的可重构流处理器体系结构

 针对软件无线电中存在通用数字信号处理器（DSP）计算能力不足以及专用基带处理器缺乏扩展性的问题,提出了一种新的处理器：面向软件无线电的可重构流处理器及相应的专用指令集。仿真证明,该处理器的可重构设计具备指令集扩展能力,可以对多种无线通信标准甚至是新的通信标准提供支持;面向软件无线电的流体系结构和专用指令集保证了对多种高速无线基带信号的实时处理,运算能力是通用DSP的5~13倍。该处理器为软件无线电中的硬件设计难题提供了一种新的解决途径。     

Analysis and design optimization of monopulse receivers forsecondary surveillance radar

The sensitivity to calibration and component errors of the receiver configurations used for monopulse processing of secondary surveillance radar (SSR) replies is analyzed. The effects of video gain error in amplitude processors and large Gaussian perturbations in phase processors are discussed. Phase processors are shown to be robust to variations in antenna difference pattern null depth. A half-angle phase processor that yields the benefits of phase processing without the sensitivity to system errors associated with conventional implementations is described     

Constrained Improvement MTI Radar Processors

A new class of staggered PRF MTI radar processors is developed in this paper. These processors are constrained to achieve a specified value of MTI improvement and, subject to this constraint, minimize variations in processor response as a function of target Doppler frequency. The selection of both filter weights and PRF stagger sequences is discussed and a number of representative designs are presented.     

多线程控制技术在面向对象实时仿真中的应用

随着实时仿真复杂性的提高,单个的处理器不足以完成所有的必需仿真计算任务。希望能在不同的处理器上完成实时仿真的不同任务,对称多处理器的机制需要软件支持,以使每个处理器通过共享内存进行信息交换。利用多线程控制技术,可以在非全进程开销或不使用共享内存的条件下,使用多处理器。其理由在于线程本身就蕴涵有共享地址的概念。一个多线程的实时程序,利用其中的主线程控制其它的辅助线程,每个处理器用于完成一个辅助的实时计算线程,主线程负责实时时钟的监控,当时钟到达时,启动相应的辅助线程,辅助线程利用图形用户界面(GUI)来监控仿真的进行。     

An efficient large-scale mesh deformation method based on MPI/OpenMP hybrid parallel radial basis function interpolation

An efficient MPI/OpenMP hybrid parallel Radial Basis Function (RBF) strategy for both continuous and discontinuous large-scale mesh deformation is proposed to reduce the computational cost and memory consumption. Unlike the conventional parallel methods in which all processors use the same surface displacement and implement the same operation, the present method employs different surface points sets and influence radius for each volume point movement, accompanied with efficient geometry searching strategy. The deformed surface points, also called Control Points (CPs), are stored in each processor. The displacement of spatial points is interpolated by using only 20–50 nearest control points, and the local influence radius is set to 5–20 times the maximum displacement of control points. To shorten the searching time for the nearest control point clouds, an Alternating Digital Tree (ADT) algorithm for 3D complex geometry is designed based on an iterative bisection technique. Besides, an MPI/OpenMP hybrid parallel approach is developed to reduce the memory cost in each High-Performance Computing (HPC) node for large-scale applications. Three 3D cases, including the ONERA-M6 wing and a commercial transport airplane standard model with up to 2.5 billion hybrid elements, are used to test the present mesh deformation method. The robustness and high parallel efficiency are demonstrated by a wing deflection case with a maximum bending angle of 45° and more than 80% parallel efficiency with 1024 MPI processors. In addition, the availability for both continuous and discontinuous surface deformation is verified by interpolating the projecting displacement with opposite directions surface points to the spatial points.     

网络连接机群上CFD计算的一种负载平衡方法

讨论在网络连接的分布式存储并行机群上进行CFD计算的一种负载平衡方法和相关问题。当数值计算的方法是区域分解法时,各节点机上的负载与其处理的子区域的网格节点数成正比,所以同样大小的子区域可保证负载平衡。采用负载再分配即区域再剖分的方法来达到动态负载平衡,构造了一种对多块网格(每块内为结构网格但各块间的连接关系可以是非结构的)进行近似平均分划的方法,并用一种数据结构和算法保证了剖分出的多个子区之间正确的互联和边界信息传递关系。给出了用这种剖分算法对常见多块网格进行分划的例子,并对三维流场进行了实际计算。结果证明本文方法是正确的,能有效地均衡计算负载,达到较理想的并行效率。     

Signature search time evaluation in flat file databases

For the first time, divisible load scheduling theory is used to solve for the expected time for searching for both single and multiple signatures in certain multiple processor database architectures. The target architectures examined for illustrative purposes are linear daisy chains and single level tree networks with single and multiple installment load distribution. The use of divisible load modeling and analysis yields elegant expressions for expected search time.