Fault-tolerant embedding of complete binary trees in hypercubes

The focus is on the following graph-theoretic question associated with the simulation of complete binary trees by faulty hypercubes: if a certain number of nodes or links are removed from an n-cube, will an (n-1)-tree still exists as a subgraph? While the general problem of determining whether a k-tree, k< n, still exists when an arbitrary number of nodes/links are removed from the n-cube is found to be NP-complete, an upper bound is found on how many nodes/links can be removed and an (n-1)-tree still be guaranteed to exist. In fact, as a corollary of this, it is found that if no more than n-3 nodes/links are removed from an (n-1)-subcube of the n-cube, an (n-1)-tree is also guaranteed to exist     

On time mapping of uniform dependence algorithms into lowerdimensional processor arrays

Most existing methods of mapping algorithms into processor arrays are restricted to the case where n-dimensional algorithms, or algorithms with n nested loops, are mapped into (n-1)-dimensional arrays. However, in practice, it is interesting to map n-dimensional algorithms into (k-1)-dimensional arrays where k<n. A computational conflict occurs if two or more computations of an algorithm are mapped into the same execution time. Based on the Hermite normal form of the mapping matrix, necessary and sufficient conditions are derived to identify mapping without computational conflicts. These conditions are used to find time mappings of n-dimensional algorithms into (k-1)-dimensional arrays, k<n , without computational conflicts. For some applications, the mapping is time-optimal     

The minimal dimension of stable faces required to guaranteestability of a matrix polytope: D-stability

The problem of determining whether a polytope P of n ×n matrices is D-stable-i.e. whether each point in P has all its eigenvalues in a given nonempty, open, convex, conjugate-symmetric subset D of the complex plane-is discussed. An approach which checks the D-stability of certain faces of P is used. In particular, for each D and n the smallest integer m such that D-stability of every m-dimensional face guarantees D-stability of P is determined. It is shown that, without further information describing the particular structure of a polytope, either (2n-4)-dimensional or (2n-2)-dimensional faces need to be checked for D-stability, depending on the structure of D. Thus more work needs to be done before a computationally tractable algorithm for checking D-stability can be devised     

On the gap between the structural controllability of time-varyingand time-invariant systems

Structural controllability of time-invariant and time-varying systems when the input control sequences have a restricted length k is compared. The dimensions of controllable space coincide in the following three special cases: the input sequences have length k=2; the input sequences have k=n, where n is the size of the system (i.e., the ultimate controllability is the same in both cases); and for every length of input sequences provided that the system has a single input only. It is proved that there may appear a gap for every input length k such that 2< k⩽n/2. The case when n/2<k<n is left open     

Balanced parallel sort on hypercube multiprocessors

A parallel sorting algorithm for sorting n elements evenly distributed over 2^d p nodes of a d-dimensional hypercube is presented. The average running time of the algorithm is O((n log n)/p+p log 2n). The algorithm maintains a perfect load balance in the nodes by determining the (kn/p)th elements (k1,. . ., (p-1)) of the final sorted list in advance. These p-1 keys are used to partition the sorted sublists in each node to redistribute data to the nodes to be merged in parallel. The nodes finish the sort with an equal number of elements (n/ p) regardless of the data distribution. A parallel selection algorithm for determining the balanced partition keys in O(p log2n) time is presented. The speed of the sorting algorithm is further enhanced by the distance-d communication capability of the iPSC/2 hypercube computer and a novel conflict-free routing algorithm. Experimental results on a 16-node hypercube computer show that the sorting algorithm is competitive with the previous algorithms and faster for skewed data distributions     

Stabilization by reduced-order controllers

A recent result by A. Linnemann (Syst. Contr. Lett., vol.11, p.27-32, 1988) gives conditions under which a continuous-time single-loop plant of order n can be stabilized by a reduced-order controller. Specifically, if the Euclidean algorithm is applied to the numerator and denominator polynomials of the transfer function and one of the remainders is a kth-order Hurwitz polynomial, then a stabilizing controller of order n-k-1 exists. The author provides an alternative proof of this result     

Two-dimensional convolution on a pyramid computer

An algorithm for convolving a k×k window of weighting coefficients with an n×n image matrix on a pyramid computer of O(n²) processors in time O(logn+k²), excluding the time to load the image matrix, is presented. If k=Ω (√log n), which is typical in practice, the algorithm has a processor-time product O(n ² k²) which is optimal with respect to the usual sequential algorithm. A feature of the algorithm is that the mechanism for controlling the transmission and distribution of data in each processor is finite state, independent of the values of n and k. Thus, for convolving two {0, 1}-valued matrices using Boolean operations rather than the typical sum and product operations, the processors of the pyramid computer are finite-state     

Robust Schur stability of a polytope of polynomials

The main objective of the authors is to provide a necessary and sufficient condition for a polytope of polynomials to have all its zeros inside the unit circle. The criterion obtained serves as a discrete-time counterpart for results in S. Bialas (1985) and F. Fu and B.R. Barmish (1987) for the continuous case. Also, the results are reduced to operations on (n-1)×(n-1) matrices. It is concluded that, by the edge result of A.C. Bartlett et al. (1987), it suffices to check the exposed edges in order to determine whether a polytope of polynomials has all its zeros in a simply connected region D     

Rotator graphs: an efficient topology for point-to-pointmultiprocessor networks

Rotator graphs, a set of directed permutation graphs, are proposed as an alternative to star and pancake graphs. Rotator graphs are defined in a way similar to the recently proposed Faber-Moore graphs. They have smaller diameter, n-1 in a graph with n factorial vertices, than either the star or pancake graphs or the k-ary n-cubes. A simple optimal routing algorithm is presented for rotator graphs. The n-rotator graphs are defined as a subset of all rotator graphs. The distribution of distances of vertices in the n-rotator graphs is presented, and the average distance between vertices is found. The n-rotator graphs are shown to be optimally fault tolerant and maximally one-step fault diagnosable. The n-rotator graphs are shown to be Hamiltonian, and an algorithm for finding a Hamiltonian circuit in the graphs is given     

Network communication in edge-colored graphs: gossiping

A mechanism for scheduling communications in a network in which individuals exchange information periodically according to a fixed schedule is presented. A proper k edge-coloring of the network is considered to be a schedule of allowed communications such that an edge of color i can be used only at times i modulo k. Within this communication scheduling mechanism, the information exchange problem known as gossiping is considered. It is proved that there is a proper k edge-coloring such that gossip can be completed in a path of n edges in a certain time for n⩾k⩾1. Gossip can not be completed in such a path any earlier under any proper k edge-coloring. In any tree of bounded degree Δ and diameter d, gossip can be completed under a proper Δ edge-coloring in time (Δ-1)d +1. In a k edge-colored cycle of n vertices, other time requirements of gossip are determined     

The stability of a family of polynomials can be deduced from afinite number 0(k3) of frequency checks

Let φ(s,a)=φ₀(s,a)+ a₁φ₁(s)+a₂ φ₂(s)+ . . .+a_kφ _k(s)=φ₀(s)-q(s, a) be a family of real polynomials in s, with coefficients that depend linearly on parameters a_i which are confined in a k-dimensional hypercube Ω_a . Let φ₀(s) be stable of degree n and the φ_i(s) polynomials (i⩾1) of degree less than n. A Nyquist argument shows that the family φ(s) is stable if and only if the complex number φ₀(jω) lies outside the set of complex points -q(jω,Ω_a) for every real ω. In a previous paper (Automat. Contr. Conf., Atlanta, GA, 1988) the authors have shown that -q(jω,Ω_a ), the so-called `-q locus', is a 2k convex parpolygon. The regularity of this figure simplifies the stability test. In the present paper they again exploit this shape and show that to test for stability only a finite number of frequency checks need to be done; this number is polynomial in k, 0(k³), and these critical frequencies correspond to the real nonnegative roots of some polynomials     

Optimal resilient distributed algorithms for ring election

The problem of electing a leader in a dynamic ring in which processors are permitted to fail and recover during election is discussed. It is shown that &thetas;(n log n+k_r) messages, counting only messages sent by functional processors, are necessary and sufficient for dynamic ring election, where k_r is the number of processor recoveries experienced     

A processor-time-minimal systolic array for transitive closure

Using a directed acyclic graph (DAG) model of algorithms, the authors focus on processor-time-minimal multiprocessor schedules: time-minimal multiprocessor schedules that use as few processors as possible. The Kung, Lo, and Lewis (KLL) algorithm for computing the transitive closure of a relation over a set of n elements requires at least 5n-4 parallel steps. As originally reported. their systolic array comprises n² processing elements. It is shown that any time-minimal multiprocessor schedule of the KLL algorithm's dag needs at least n²/3 processing elements. Then a processor-time-minimal systolic array realizing the KLL dag is constructed. Its processing elements are organized as a cylindrically connected 2-D mesh, when n=0 mod 3. When n≠0 mod 3, the 2-D mesh is connected as a torus     

An efficient digital search algorithm by using a double-arraystructure

An efficient digital search algorithm that is based on an internal array structure called a double array, which combines the fast access of a matrix form with the compactness of a list form, is presented. Each arc of a digital search tree, called a DS-tree, can be computed from the double array in 0(1) time; that is to say, the worst-case time complexity for retrieving a key becomes 0(k) for the length k of that key. The double array is modified to make the size compact while maintaining fast access, and algorithms for retrieval, insertion, and deletion are presented. If the size of the double array is n+cm, where n is the number of nodes of the DS-tree, m is the number of input symbols, and c is a constant particular to each double array, then it is theoretically proved that the worst-case times of deletion and insertion are proportional to cm and cm², respectively, and are independent of n. Experimental results of building the double array incrementally for various sets of keys show that c has an extremely small value, ranging from 0.17 to 1.13     

Fast image labeling using local operators on mesh-connectedcomputers

A new parallel algorithm is proposed for fat image labeling using local operators on image pixels. The algorithm can be implemented on an n×n mesh-connected computer such that, for any integer k in the range [1, log (2n)], the algorithm requires Θ(kn¹k/) bits of local memory per processor and takes Θ(kn) time. Bit-serial processors and communication links can be used without affecting the asymptotic time complexity of the algorithm. The time complexity of the algorithm has very small leading constant factors, which makes it superior to previous mesh computer labeling algorithms for most practical image sizes (e.g. up to 4096×4096 images). Furthermore, the algorithm is based on using stacks that can be realized using very fast shift registers within each processing element     

Out-of-roundness problem revisited

The properties and computation of the minimum radial separation (MRS) standard for out-of-roundness are discussed. Another standard out-of-roundness measurement called the minimum area difference (MAD) center is introduced. Although the two centers have different characteristics, the approach to finding both centers shares many commonalities. An O(n log n+k) time algorithm which is used to compute the MRS center is presented. It also computes the MAD center of a simple polygon G, where n is the number of vertices of G, and k is the number of intersection points of the medial axis and the farthest-neighbor Voronoi diagram of G. The relationship between MRS and MAD is discussed     

Complete instability of a box of polynomials

The authors study the converse of V.L. Kharitonov's polynomial problem (1978) by asking whether the complete instability of a box of polynomials can be determined from extreme sets. They show that it is not enough to check the (n-4)-dimensional boundary, but prove that the complete instability of the (n-1)-dimensional boundary is sufficient     

A processor-time-minimal systolic array for cubical mesh algorithms

Using a directed acyclic graph (DAG) model of algorithms, the paper focuses on time-minimal multiprocessor schedules that use as few processors as possible. Such a processor-time-minimal scheduling of an algorithm's DAG first is illustrated using a triangular shaped 2-D directed mesh (representing, for example, an algorithm for solving a triangular system of linear equations). Then, algorithms represented by an n×n×n directed mesh are investigated. This cubical directed mesh is fundamental; it represents the standard algorithm for computing matrix product as well as many other algorithms. Completion of the cubical mesh required 3n-2 steps. It is shown that the number of processing elements needed to achieve this time bound is at least [3n^2/4]. A systolic array for the cubical directed mesh is then presented. It completes the mesh using the minimum number of steps and exactly [3n ^2/4] processing elements it is processor-time-minimal. The systolic array's topology is that of a hexagonally shaped, cylindrically connected, 2-D directed mesh     

n-D polynomial matrix equations

Linear matrix equations in the ring of polynomials in n indeterminates (n-D) are studied. General- and minimum-degree solutions are discussed. Simple and constructive, necessary and sufficient solvability conditions are derived. An algorithm to solve the equations with general n-D polynomial matrices is presented. It is based on elementary reductions in a greater ring of polynomials in one indeterminate, having as coefficients polynomial fractions in the other n-1 indeterminates, which makes the use of Euclidean division possible     

Minimal parameter solution of the orthogonal matrix differentialequation

The straightforward solution of the first-order differential equation satisfied by all nth-order orthogonal matrices requires n² integrations to obtain the matrix elements. There are, however, only n(n-1)/2 independent parameters which determine an orthogonal matrix. The questions of choosing them, finding their differential equation, and expressing the orthogonal matrix in terms of these parameters are considered in the present work. Several possibilities which are based on attitude determination in three dimensions are examined. It is concluded that not all 3-D methods have useful extensions to other dimensions, and that the 3-D Gibbs vector (or Cayley parameters) provide the most useful extension. An algorithm is developed using the resulting parameters, which are termed extended Rodrigues parameters, and numerical results are presented of the application of the algorithm to a fourth-order matrix