Optimal bounds on the gain of permitting dynamic allocation of communication channels in distributed computing

Consider a distributed system consisting of n computers connected by a number of identical broadcast channels. All computers may receive messages from all channels. We distinguish between two kinds of systems: systems in which the computers may send on any channel (dynamic allocation) and system where the send port of each computer is statically allocated to a particular channel. A distributed task (application) is executed on the distributed system. A task performs execution as well as communication between its subtasks. We compare the completion time of the communication for such a task using dynamic allocation and channels with the completion time using static allocation and channels. Some distributed tasks will benefit very much from allowing dynamic allocation, whereas others will work fine with static allocation. In this paper we define optimal upper and lower bounds on the gain (or loss) of using dynamic allocation and channels compared to static allocation and channels. Our results show that, for some tasks, the gain of permitting dynamic allocation is substantial, e.g. when , there are tasks which will complete 1.89 times faster using dynamic allocation compared to using the best possible static allocation, but there are no tasks with a higher such ratio. Received: 26 February 1998 / 26 July 1999     

Computation of Determinants, Adjoint Matrices, and Characteristic Polynomials without Division

Algorithms are proposed for computing the characteristic polynomial, determinant, and adjoint matrix for a n × n matrix and for solving a system of n-1 linear homogeneous equations in n variables by Cramer's rule using O(n ⁴ ) ring operations (without the division operation) over an arbitrary commutative ring. The exponent in the estimate of the computation time can be additionally reduced if an algorithm of asymptotically fast matrix multiplication is used.     

Efficient Detection of Channel Predicates in Distributed Systems

This paper discusses efficient detection of global predicates in a distributed program. Previous work in this area required predicates to be specified as a conjunction of predicates defined on individual processes. Many properties in distributed systems, however, use the state of channels, such as “the channel is empty,” or “there is a token in the channel.” In this paper, we introduce the concept of alinearchannel predicate and provide efficient centralized and distributed algorithms to detect any conjunction of local and linear channel predicates. The class of linear predicates is fairly broad. For example, classic problems such as detection of termination and computation of global virtual time are instances of conjunctions of linear channel predicates. Linear predicates can be functions of the number of messages in the channel, or can be based upon the actual contents of the messages. The main application of our results are in debugging and testing of distributed programs. For these applications it is important to detect thefirststate where some predicate is true. We show that this first state is uniquely defined if and only if linear predicates are used.     

Tracking the condition number for RLS in signal processing

We apply a fast adaptive condition estimation scheme, calledACE, to recursive least squares (RLS) computations in signal processing.ACE is fast in the sense that onlyO(n) operations are required forn parameter problems, and is adaptive over time, i.e., estimates at timet are used to produce estimates at timet + 1. RLS algorithms for linear prediction of time series are applied in various fields of signal processing: identification, estimation, and control. However, RLS algorithms are known to suffer from numerical instability problems under finite word-length conditions, due to ill-conditioning. We apply adaptive procedures, linear in the order of the problem, for accurately tracking relevant extreme eigen-values or singular values and the associated condition numbers over timet. In this paper exponentially weighted data windows are considered. The sliding data window case, which involves downdating as well as updating, is considered else-where. Numerical experiments indicate thatACE yields an accurate, yet inexpensive, RLS condition estimator for signal processing applications.Research supported by the Air Force under Grant No. AFOSR-88-0285 and by the National Science Foundation under Grant No. DMS-89-02121.     

A Parallel Algorithm for Linear Programs with an Additional Reverse Convex Constraint

A parallel method for globally minimizing a linear program with an additional reverse convex constraint is proposed which combines the outer approximation technique and the cutting plane method. Basicallyp(≤n) processors are used for a problem withnvariables and a globally optimal solution is found effectively in a finite number of steps. Computational results are presented for test problems with a number of variables up to 80 and 63 linear constraints (plus nonnegativity constraints). These results were obtained on a distributed-memory MIMD parallel computer, DELTA, by running both serial and parallel algorithms with double precision. Also, based on 40 randomly generated problems of the same size, with 16 variables and 32 linear constraints (plusx≥ 0), the numerical results from different number processors are reported, including the serial algorithm's.     

时滞多变量过程信息融合解耦控制

针对工业过程中时滞多变量线性系统各回路问存在的强耦合问题,提出一种基于信息融合估计的解耦控制方法.通过融合主通道和相应耦合通道的期望输出软约束信息和控制能量软约束信息,估计出二次性能指标下的最优自适应解耦控制律.进一步对无限预见期望输出信息进行一步预见等效处理,获得计算更简单的近似最优解耦控制律.实例仿真结果表明了该解耦控制器具有计算量小、解耦程度可调以及控制品质好等优点.     

基于矩阵和求逆及MRC的低复杂度MIMO检测器

信道编码MIMO系统需要检测器具有软输入软输出特性,而常规的检测算法通常具有很高的计算复杂度,阻碍了其在实际中的应用.提出一种低复杂度MIMO检测方案.首次迭代中,利用低复杂度快速矩阵和分解方案来获得MMSE检测输出,避免了常规矩阵和求逆中的Jordan标准型化简;其余迭代中,利用信道解码器提供的软信息将MIMO系统转...     

Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links

Summary.  We consider agreement and leader election on asynchronous complete networks when the processors are reliable, but some of the channels are subject to failure. Fischer, Lynch, and Paterson have already shown that no deterministic algorithm can solve the agreement problem on asynchronous networks if any processor fails during the execution of the algorithm. Therefore, we consider only channel failures. The type of channel failure we consider in this paper is Byzantine failure, that is, channels fail by altering messages, sending false information, forging messages, losing messages at will, and so on. There are no restrictions on the behavior of a faulty channel. Therefore, a faulty channel may act as an adversary who forges messages on purpose to prevent the successful completion of the algorithm. Because we assume an asynchronous network, the channel delays are arbitrary. Thus, the faulty channels may not be detectable unless, for example, the faulty channels cause garbage to be sent. We present the first known agreement and leader election algorithm for asynchronous complete networks in which the processors are reliable but some channels may be Byzantine faulty. The algorithm can tolerate up to [n−22] faulty channels, where n is the number of processors in the network. We show that the bound on the number of faulty channels is optimal. When the processors terminate their corresponding algorithms, all the processors in the network will have the same correct vector, where the vector contains the private values of all the processors. Received: May 1994/Accepted: July 1995     

Linear algebra for tensor problems

By a tensor problem in general, we mean one where all the data on input and output are given (exactly or approximately) in tensor formats, the number of data representation parameters being much smaller than the total amount of data. For such problems, it is natural to seek for algorithms working with data only in tensor formats maintaining the same small number of representation parameters—by the price of all results of computation to be contaminated by approximation (recompression) to occur in each operation. Since approximation time is crucial and depends on tensor formats in use, in this paper we discuss which are best suitable to make recompression inexpensive and reliable. We present fast recompression procedures with sublinear complexity with respect to the size of data and propose methods for basic linear algebra operations with all matrix operands in the Tucker format, mostly through calls to highly optimized level-3 BLAS/LAPACK routines. We show that for three-dimensional tensors the canonical format can be avoided without any loss of efficiency. Numerical illustrations are given for approximate matrix inversion via proposed recompression techniques.      

Review Article A review of multi-channel indices of class separability

Abstract

An increasingly common question arising in processing digital multi-channel data from spacecraft and aircraft scanner systems is “which channels contain the best information to separate the classes of interest to the user?”. This may be to identify the best single channel for separating classes in a black and white photographic or line printer output product, or the best three channels for a colour photographic presentation of the data, or the best ‘n’ channels to enter into a classification (being mindful of the ‘trade off’ between improved sub-class separability and increasing usage of computer space and time resources). The only valid way to approach separability using more than one channel is to consider it in multi-channel space utilizing the inter-channel relationship terms. Having defined the classes using some form of hierarchical ordering approach, such as that proposed by Anderson et al. (1972), the user may compile the statistical profiles of the classes of interest from the sensor multi-channel data. Based on these statistics a number of multi-channel separability indices may be derived. Each of these indices quantifies, on the basis of the user-defined multi-channel statistics, the degree of inter-class separability the user can expect as a function of subsets of channels drawn from the overall sensor channel set. This review considers some of the more common multi-channel indices of separability and presents the links between them. Their various properties, and some limitations, are also presented as is an operational approach to their use.     

渐进图像传输的码率分配快速算法

针对带限时变信道上的渐进图像传输,提出了一种信源信道联合编码码率分配快速算法,首先参考一组速率兼容信道码字的误码性能划分信道分区,在各分区内缩小可用信 道码率集后,通过前后向码率搜索求解最佳码率分配。该算法运算复杂度低,计算次数比启发式码率搜索算法降低了一个数量级,缩短了运算时间。因此,将其应用于自适应传输 系统,可根据信道状况快速调整码率分配。仿真结果表明,接收端重建图像的PSNR值始终在29.5 dB以上,同时波动范围小于4 dB,具有优良稳定的传输质量。     

Fast linear systolic matrix vector multiplication

The systolic concept in the parallel architecture design proposed by the H. T. Kung [1,2] obtains high throughput and speedups. The linear array for the matrix vector multiplication executes the algorithm in 2n ? 1 time steps using 2n ? 1 processors. Although the speedup obtained is very high, the efficiency is very poor (typical values of 25% efficiency for problem size greater than 10). H. T. Kung proposed an idea for a linear systolic array using two data streams flowing in opposite directions. However, the processors in the array perform operations in every second time moment.

Attempts to improve this design have been made by many researchers. Nonlinear and folding transformations techniques [3,4,5] only decrease the number of processors used to half the size, but do not affect the time.

We propose the use of a fast linear systolic computation procedure to obtain a solution that uses 3n/2 processors and executes the algorithm in 3n/2 time steps for the same cells, the same communication and the same regular data flow as the H. T. Kung linear array. Only the algorithm is restructured and more efficiently organized. Now the processors are utilized in every time step and no idle steps are required.     

Performance bounds on the splitting algorithm for binary testing

Summary In machine fault-location, medical diagnosis, species identification, and computer decisionmaking, one is often required to identify some unknown object or condition, belonging to a known set of M possibilities, by applying a sequence of binary-valued tests, which are selected from a given set of available tests. One would usually prefer such a testing procedure which minimizes or nearly minimizes the expected testing cost for identification. Existing methods for determining a minimal expected cost testing procedure, however, require a number of operations which increases exponentially with M and become infeasible for solving problems of even moderate size. Thus, in practice, one instead uses fast, heuristic methods which hopefully obtain low cost testing procedures, but which do not guarantee a minimal cost solution. Examining the important case in which all M possibilities are equally likely, we derive a number of cost-bounding results for the most common heuristic procedure, which always applies next that test yielding maximum information gain per unit cost. In particular, we show that solutions obtained using this method can have expected cost greater than an arbitrary multiple of the optimal expected cost.The authors are indebted to R. L. Rivest for simplying the original proof of Theorem 1 and to P. J. Burke for his many valuable comments.     

Processor-time optimal parallel algorithms for digitized images on mesh-connected processor arrays

We present processor-time optimal parallel algorithms for several problems onn ×n digitized image arrays, on a mesh-connected array havingp processors and a memory of sizeO(n ²) words. The number of processorsp can vary over the range [1,n ^3/2] while providing optimal speedup for these problems. The class of image problems considered here includes labeling the connected components of an image; computing the convex hull, the diameter, and a smallest enclosing box of each component; and computing all closest neighbors. Such problems arise in medium-level vision and require global operations on image pixels. To achieve optimal performance, several efficient data-movement and reduction techniques are developed for the proposed organization.This research was supported in part by the National Science Foundation under Grant IRI-8710836 and in part by DARPA under Contract F33615-87-C-1436 monitored by the Wright Patterson Airforce Base.     

Effective diagonalization strategies for the solution of a class ofoptimal design problems

It is shown that it is possible to obtain optimal diagonalization strategies for the discretization of semiinfinite minimax optimal design problems. Both exact and approximate methods for the computation of these optimal diagonalization strategies are proposed. The algorithms for computing approximate diagonalization strategies yield very good approximations in much less computing time than needed to compute an optimal diagonalization strategy exactly. The proposed diagonalization strategies can be implemented by using estimation schemes to obtain approximations to the various quantities which determine an optimal strategy. Experimental results, involving the solution of optimal loop-shaping problems for multivariable linear feedback systems, show that the use of these implementable strategies leads to considerable savings in computer time over alternative approaches     

Min-max functions

A variety of problems in operations research, control theory, computer science, etc., can be modeled as discrete event systems with maximum and minimum constraints. When these systems require only maximum constraints (or, dually, only minimum constraints) they can be studied by linear methods based on max-plus algebra. Systems with mixed constraints, however, are nonlinar from this perspective and relatively little is known about their behaviour. The paper lays the foundations of the theory of discrete event systems with mixed constraints. We introduce min-max functions,F:R ⁿ R ⁿ , which are constructed using finitely many operations of min, max and +, and study them as dynamical systems. Among other results, we give a complete account of the periodic behavior of functions of dimension 2; we introduce and characterize the concept of balance which generalizes irreducibility in the linear theory; and we give a formula for the cycle time (eigenvalue) of a min-max function which generalizes the maximum cycle mean formula.     

On Kalman filtering over fading wireless channels with controlled transmission powers

We study stochastic stability of centralized Kalman filtering for linear time-varying systems equipped with wireless sensors. Transmission is over fading channels where variable channel gains are counteracted by power control to alleviate the effects of packet drops. We establish sufficient conditions for the expected value of the Kalman filter covariance matrix to be exponentially bounded in norm. The conditions obtained are then used to formulate stabilizing power control policies which minimize the total sensor power budget. In deriving the optimal power control laws, both statistical channel information and full channel information are considered. The effect of system instability on the power budget is also investigated for both these cases.     

On a new class of binary group codes

A new class of binary group error-correcting codes is formalized and defined. The codes are generated by irreducible and primitive polynomials over the binary field by an iterative procedure. A general formula for the number of corregible errors related to the lengthn of the code vectors is given. A method to obtain from a given code a class of subcodes is described. The encoding and decoding (error-detecting, error-correcting) procedures are extremely simple and use linear shift registers. A general formula describing the number of operations involved is given. This work has been supported by the National Science Fundation under grant numberGP-2122 and represents part of the doctoral dissertation.     

Fast QR factorization of low-rank changes of Vandermonde-like matrices

This paper is concerned with the solution of linear systems with coefficient matrices which are Vandermonde-like matrices modified by adding low-rank corrections. Hereafter we refer to these matrices as modified Vandermonde-like matrices. The solution of modified Vandermonde-like linear systems arises in approximation theory both when we use Remez algorithms for finding minimax approximations and when we consider least squares problems with constraints. Our approach relies on the computation of an inverse QR factorization. More specifically, we show that some classical orthogonalization schemes for m×n, m≥n, Vandermonde-like matrices can be extended to compute efficiently an inverse QR factorization of modified Vandermonde-like matrices. The resulting algorithm has a cost of O(mn) arithmetical operations. Moreover it requires O(m) storage since the matrices Q and R are not stored. Received: January 1997 / Accepted: November 1997