Search

In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs in O(log n) time on EREW P-RAM with n/log n processor. The algorithm matches the performance of the Cole-Vishkin [CV86a] algorithm but is simple and has reasonable constant factors. [ABSTRACT FROM AUTHOR]

Automatic parallelization of code written in a sequential language such as FORTRAN is of great importance. One natural approach to loop parallelization is to assign separate invocations of a loop to different processors. However, it is often necessary to delay the starting times of loops to avoid violating data dependences. In this paper we study a scheduling problem, called the Delay Problem, that models an aspect of the loop parallelization problem. We show that the Delay Problem is NP-Complete when the precedence constraints are a set of arbitrary trees. Our major result of the paper is a polynomial time algorithm for the case where the precedence constraints are a forest of in-trees or a forest of out-trees. This covers an important practical case for the Delay Problem. [ABSTRACT FROM AUTHOR]

We show in this paper that a perfect matching of a line graph can be computed in NC. A necessary and sufficient condition for a line graph to have a perfect matching is an even number of vertices. To compute the perfect matching, we use a technique of dividing the graph into kingdoms. This result is equivalent to partitioning the edge set of a graph into edge disjoint paths of even length. [ABSTRACT FROM AUTHOR]

In this paper we introduce a general framework for compaction on a torus. This problem comes up whenever an array or row of identical cells has to be compacted. We instantiate our framework with several specific compaction algorithms: one-dimensional compaction without and with automatic jog insertion and two-dimensional compaction. [ABSTRACT FROM AUTHOR]

In this paper we present a simple three-layer assignment algorithm for planar layouts generated by a class of layout algorithms. This class of algorithms includes simple variations of the currently best algorithms for the three layer channel routing problem (CRP). More specifically, this class includes algorithms "equivalent" to the following algorithms (i-iii) developed by Mehlhorn, Preparata and Sarrafzadeh [7]. (i) The algorithm that generates planar layouts for the two-terminal net CRP with dmax tracks. (ii) The algorithm that generates planar layouts for the two- and three-terminal net CRP with at most [3dmax/2] tracks. (iii) The algorithm that generates planar layouts for the multi-terminal net CRP with at most 2dmax — 1 tracks. The planar layouts generated by these algorithms and by their "equivalent" algorithms are three-layer wirable by the layer assignment algorithm given in [8]. Our approach is different. We make simple modifications to these layout algorithms and incorporate a simple wire assignment strategy to generate three-layer wirings under the knock-knee model. Consequently, we obtain simpler and faster algorithms that generate three-layer wirings with layouts similar to the ones generated by algorithms (i) - (iii). Our algorithms are faster and conceptually simpler because there is no need to construct diagonal diagrams and legal partitions. The channel width of the wiring generated by our algorithm is identical to that of the corresponding planar layout generated by algorithms (i) - (iii). [ABSTRACT FROM AUTHOR]

In this paper, we show how to efficiently realize permutations of data stored in VLSI chips using bus interconnections with a small number of pins per chip. In particular, we show that permutations among chips from any group G can be uniformly realized in one step with a bus architecture that requires only $$\Theta (\sqrt {\left G \right} )$$ pins per chip. The bound is within a small constant factor of optimal and solves the central question left open by the recent work of Kilian. Kipnis and Leiserson on uniform permutation architectures [8]. The proof makes use of the Classification Theorem for Finite Simple Groups to show that every finite group G of nonprime order contains a nontrivial subgroup of size at least $$\sqrt {\left G \right}$$ . The latter result is also optimal and improves the old pre-Classification Theorem lower bound of G1/3 proved by Brauer and Fowler [1] and Feit [4]. [ABSTRACT FROM AUTHOR]

In this paper we present a new algorithm for wiring layouts in the square grid. This algorithm provides a rather intuitive proof that the number of layers required to wire a given layout W is at most four, and it constructs a two-layer wiring if and only if W requires two layers. The algorithm runs in O(N) time, where N is the number of grid points occupied by the layout. The technique used here can be extended in order to construct wirings of layouts in the tri-hexagonal grid that use at most five layers. [ABSTRACT FROM AUTHOR]

In a recent series of papers [FL1, FL2, FL3], we have proven the existence of decision algorithms with low-degree polynomial running times for a number of well-studied VLSI layout, placement and routing problems. These results make use of the powerful Robertson-Seymour theorems on the well-partial-ordering of graphs under both the minor and immersion orders. In the present paper, we study the complexity of construction versions of these problems, focusing on efficient self-reduction strategies. We introduce a notion of fast self-reduction in this setting and develop a general technique, which we term scaffolding, that is useful in the design of fast self-reduction algorithms. [ABSTRACT FROM AUTHOR]

Most work on the problem of synthesizing a systolic array from a system of recurrence equations is restricted to systems of uniform recurrence equations. In this paper, this restriction is relaxed to include systems of affine recurrence equations. A system of uniform recurrence equations typically can be embedded in spacetime so that the distance between a variable and a dependent variable does not depend on the problem size. Systems of affine recurrence equations which are not uniform, do not enjoy this property. A method is presented for converting a system of affine recurrence equations to an equivalent system of recurrence equations that is uniform, except for points near the boundaries of its index sets. A characterization of those systems of affine recurrence equations that can be so converted is given, along with an algorithm that decides if a system is amenable to such a conversion, and a procedure that converts those affine systems which can be converted. [ABSTRACT FROM AUTHOR]

A sequential random access machine can permute n data items in n steps. However, Gottlieb and Kruskal have shown that any bounded degree machine with P processors requires Ω((n/P) log P) time to permute n data items and this result makes the issue of optimal speedup interesting for interconnection networks. In this paper, we consider the issue of optimal speedup for sorting and graph problems and provide the following results: (1) If a network with P processors can permute P elements in O(log P) time, then n data items can be sorted on this network in Θ((n/P) log n) time when n≥P1+ɛ. An important consequence of this result is that a single step of any Concurrent Read Concurrent Write PRAM (CRCW-PRAM) algorithm that uses n processors and O(n) memory space, can be simulated optimally (when n≥P1+ɛ) by any network with P processors that can permute P data items in O(log P) time. (2) The connected components, biconnected components, and the minimum spanning forest can be determined in optimal time for any network that has P processors as long as P ≤ n2 / log2n and as long as this network can perform a restrictive set of permutations of P items in O(log P) time. Our paradigm for solving graph problems is quite general and it can be extended to optimally compute the median of n numbers on interconnection networks. [ABSTRACT FROM AUTHOR]

Let G=(V,E) be a given network, and d a positive integer. A d-scheduling of G is an infinite sequence of rounds [r1,r2...], such that for each i, ri is a non-empty subset of V, and the distance between any two nodes in ri is greater than d. A d-scheduler is a protocol that determines a d-scheduling of G. Of special interest is the case d=1, which corresponds to a proper communication schedule of the half-duplex model, where information can move in either direction of a communication line, but not simultaneously. This case corresponds also to a proper scheduling of processes in a resource sharing system, where an edge represents a resource shared by two processes, and every process needs all its resources to operate. Another application of this scheduler is a collision-free protocol for radio-networks (this corresponds to d=2). In this paper a simple d-scheduler is presented and analyzed. We first show that the resulting scheduling is periodic and fair. Then we give a complete characterization of this scheduling for trees and cycles. We study the period length of that scheduling, and the main result is a worst-case exponential lower bound for this length. We also study other issues concerning these schedulings; optimal rate schedulings are given for some classes of graphs, although the problem of finding optimal schedulings for any d is NP-complete. [ABSTRACT FROM AUTHOR]

This paper concerns the message complexity of broadcast in arbitrary point-to-point communication networks. Broadcast is a task initiated by a single processor that wishes to convey a message to all processors in the network. We assume the widely accepted model of communication networks, in which each processor initially knows the identity of its neighbors, but does not know the entire network topology. Although it seems obvious that the number of messages required for broadcast in this model equals the number of links, no proof of this basic fact has been given before. We show that the message complexity of broadcast depends on the exact complexity measure. If messages of unbounded length are counted at unit cost, then broadcast requires Θ(V) messages, where V is the set of processors in the network. We prove that if one counts messages of bounded length then broadcast requires Θ(E) messages, where E is the set of edges in the network. Assuming an intermediate model in which each node knows the topology of the network in radius ρ ≥ 0 from itself, we prove tight upper and lower bounds of Θ(min{E, V1+Θ(1)/ρ}) on the number of messages of bounded length required for broadcast. Both the upper and the lower bounds hold for both synchronous and asynchronous network models. The same results hold for the construction of spanning trees, and various other global tasks. [ABSTRACT FROM AUTHOR]

Three main parameters characterize the efficiency of algorithms that solve the Consensus Problem. The ratio between the total number of processors and the maximum number of faulty processors (n and t, respectively), the number of rounds, and the size of any single message. Lower bounds exist for each one of the three. In this paper we present two families of algorithms, each achieving the lower bound for one parameter and a trade-off between the other two. The first family includes algorithms where, given an integer k, the algorithm always requires the minimal possible number of rounds (t+1), with n=k(3t+1) processors and messages of size at most tO(t/k). To the second family belong algorithms in which all messages are of one bit size, the number of processors is tO((k+1)/k) and the number of rounds is t+tO((k−1)/k). These two families are based on a very simple algorithm with (2t+1)(t+1) processors using the minimal number of rounds and the minimal message size (one bit). [ABSTRACT FROM AUTHOR]

We prove that $$(1 + \sqrt 6 /2)n$$ is a time lower bound independent of indexing schemes for sorting n2 items on an n×n mesh-connected processor array. We distinguish between indexing schemes by showing that there exists an indexing scheme which is provably worse than the snake-like row-major indexing for sorting. We also derive lower bounds for various indexing schemes. All these results are obtained by using the chain argument which we provide in this paper. [ABSTRACT FROM AUTHOR]

This paper studies the problem of sorting N items on a P processor parallel machine, where N≥P. The central result of the paper is a new algorithm, called cubesort, that sorts N=P1+1/k items in O(k P1/k log P) time using a P processor shuffle-exchange. Thus for any positive constant k, cubesort provides an asymptotically optimal speed-up over sequential sorting. Cubesort also sorts N = P log P items using a P processor shuffle-exchange in O(log3 P/loglog P) time. Both of these results are faster than any previously published algorithms for the given problems. Cubesort also provides asymptotically optimal sorting algorithms for a wide range of parallel computers, including the cube-connected cycles and the hypercube. An important extension of the central result is an algorithm that simulates a single step of a Priority-CRCW PRAM with N processors and N words of memory on a P processor shuffle-exchange machine in O(k P1/k log P) time, where N=P1+1/k. [ABSTRACT FROM AUTHOR]

The aim of this paper is to study an H2/H∞ terminal state estimation problem using the classical theory of Nash equilibria. The H2/H∞ nature of the problem comes from the fact that we seek an estimator which satisfies two Nash inequalities. The first reflects an H∞ filtering requirement in the sense alluded to in [4], while the second inequality demands that the estimator be optimal in the sense of minimising the variance of the terminal state estimation error. The problem solution exploits a duality with the H2/H∞ control problem studied in [2, 3]. By exploiting duality in this way, one may quickly extablish that an estimator exists which staisfies the two Nash inequalities if and only if a certain pair of cross coupled Riccati equations has a solution on some optimisation interval. We conclude the paper by showing that the Kalman filtering, H∞ filtering and H2/H∞ filtering problems may all be captured within a unifying Nash game theoretic framework. [ABSTRACT FROM AUTHOR]

In this paper we consider a feedback interconnection of two linear time invariant systems, one of which is fixed and the other is uncertain with the uncertainty being a box in the space of coefficients of the numerator and denominator polynomials. This kind of system arises in robust control analysis and design problems. We give several results for the Nyquist plots and stability margins of such families of systems based on the extremal segments of rational functions introduced by Chapellat and Bhattacharyya [1]. These CB segments play a fundamental characterizing role in many control design problems. [ABSTRACT FROM AUTHOR]

In this paper, a complete solution for the ℓ1 sampled-data problem is furnished for arbitrary plants. Then ℓ1 sampled-data problem is described as follows: Given a continuous-time plant, with continuous-time performance objectives, design a digital controller that delivers this performance. This problem differs from the s-tandard discrete-time methods in that it takes into consideration the inter-sampling behaviour of the closed loop system. The resulting closed loop system dynamics consists of both continuous-time and discrete-time dynamics and thus such systems are known as "Hybrid" systems. It is shown that given any degree of accuracy, there exists a standard discrete-time ℓ1 problem, which can be determined apriori, such that for any controller that achieves a level of performance for the discrete-time problem, the same controller achieves the same performance within the prescribed level of accuracy if implemented as a sampled-data controller. [ABSTRACT FROM AUTHOR]

This paper studies the L1-optimal control problem for SISO systems with rational controllers. It is shown that the infimal achievable norm with rational controllers is as small as that with irrational controllers. Also a way to construct a rational suboptimal controller is studied. [ABSTRACT FROM AUTHOR]

In this paper, we study robust stability and stabilizability of sampled-data control systems composed of a continuous-time plant and a discrete-time compensator together with sample/hold devices, using the frequency domain method. Our study is not confined only to the case of standard (i.e., single-rate) sampled-data controllers but also extended to the case of multirate sampled-data controllers. Specifically, we compare, by numerical examples, the tolerable amounts of the uncertainty of a given continuous-time plant for which the robust stabilization can be attained in the three cases: the cases of a continuous-time controller, a single-rate sampled-data controller, and a multirate sampled-data controller. The result will be useful for estimating the deterioration caused by use of sampled-data controllers in place of continuous ones, or evaluating the advantages of the multirate sampled-data scheme over the standard one. [ABSTRACT FROM AUTHOR]

In this paper, we consider an optimization problem for sampled data control systems in the sense of the L2 induced norm of the linear operator with continuous-time inputs and outputs. The problem is a worst case design and a counterpart of the H∞-optimization problem for purely continuous-time or discrete-time systems. Hence, it can be applied to the robust controller design taking account of the intersample behavior for sampled-data feedback systems. We show that the optimization problem for a 4-block generalized continuous-time plant with a digital controller can be solved with a γ-iteration on a certain discrete-time 4-block plant which depends on γ. The computation algorithm with three exponentiations is also derived. [ABSTRACT FROM AUTHOR]

It is well known that tracking to continuous-time signals by sampled-data systems presents various difficulties. For example, the usual discrete-time model is not suitable for describing intersample ripples. In order to adequately handle this problem we need a framework that explicitly contains the intersample behavior in the model. This paper presents an infinite-dimensional yet time-invariant discrete-time model which contains the full intersample behavior as information in the state. This makes it possible to clearly understand the intersample as a result of a mismatch between the intersample tracking signal and the system zero-directional vector. This leads to an internal model principle for sampled-data systems, and some nonclassical feature arising from the interplay of digital and continuous-time behavior. [ABSTRACT FROM AUTHOR]

It is well-known that optimal Hankel-norm approximations are seldom unique for multivariable systems. This comes from the Hankel-norm being somewhat of a crude criterion for the reduction of multivariable systems. In this paper, the strengthened condition originated with N. J. Young is employed to restore the uniquess. A statespace algorithm for the computation of super-optimal solution is presented. [ABSTRACT FROM AUTHOR]

This paper extands first the covariance assignment theory for continuous time systems to the assignment of a covariance upper bound in the presence of structured perturbations. A systematic way is given to construct an assignable covariance upper bound for the purpose of robust design. [ABSTRACT FROM AUTHOR]

This paper presents a framework for modelling and robust control of linear systems based on a graph point of view. Basic concepts such as linearity, causality, stabilizability can be defined as properties of the graph of a system. Uncertainty is naturally thought of in terms of perturbations of the graph. Modelling and approximation are also fundamentally related to the graph of the system. Robustness will be quantified in the graph setting using the gap metric. Necessary and sufficient conditions for robustness will be explained geometrically in terms of the graphs of the plant and controller. A flexible structure design example will be discussed. [ABSTRACT FROM AUTHOR]

In this paper, we showed some case studies of robust control of mechanical systems. In this paper, dividing the uncertainties in the dynamical model of robot systems into two cases, that is (i) Structured Uncertainty and (ii) Unstructured Uncertainty, and then we showed control strategy which suited for each case through some experiments. We can say that the next step in the field of robot motion control is to consider both uncertainties at once. [ABSTRACT FROM AUTHOR]

This paper presents a design method of model reference robust adaptive control systems (MRRACS) with fixed compensator for a single-input single-output (SISO) linear time-invariant continuous-time plant in the presence of bounded unknown deterministic disturbances and unmodeled dynamics. The fixed compensator is designed based on H∞-optimal theory. The aim of the proposed control structure is realization of harmonizing the adaptive control to the robust control. [ABSTRACT FROM AUTHOR]

In this paper, we have discussed the problem to find a controller which satisfies (a) internal stability, (b) robust tracking, (c) the exact model matching and (d) the specified H∞ control performance related to the feedback properties. First, we have obtained a necessary and sufficient condition for such a controller to exist. Then, we have parametrized all such controllers, where (i) the two-degree-of-freedom compensator configuration and (ii) the free parameter of the H∞ suboptimal controller are fully exploited. [ABSTRACT FROM AUTHOR]

This paper presents a variable adaptive law, which is robust to bounded disturbances. Combining with the dead zone, the proposing adaptive law uses a sort of the σ-modified adaptive law in the small estimation error region. Viability of the adaptive law, in comparing with the dead zone type adaptive law, is shown by theoretical analysis and a simple numerical simulation. [ABSTRACT FROM AUTHOR]

Classical model reference adaptive control schemes require the following assumptions on the plant: A1) minimum phase; A2) known upper bound of the plant order; A3) known relative degree; and A4) known sign of high frequency gain. It is well-known that the robustness of the adaptive systems is a potential problem, and it requires many sophisticated techniques to fix it. In this paper, we consider the same model reference control problem via robust control. By further assuming that the boundedness of the parameter uncertainties of the plant (which is a very weak assumption), we show that a linear time-invariant dynamic output feedback controller can be constructed to give the following property: the closed-loop system is internally stable and its transfer function is arbitrarily close to the reference model. This method provides simple controllers and good robustness. It also has potential to cope with large size fast time-varying uncertainties. [ABSTRACT FROM AUTHOR]

In this paper, we will derive complete parametrization of the H∞ FI controller and that of the H∞ sdtate feedback (SF) controller. And we will determine the obtained dynamical free parameters so that they minimizes an H2 control performance and will show the condition when the whole controller becomes a constant feedback gain other than the central solution F∞. [ABSTRACT FROM AUTHOR]

This paper is concerned with robust stability in combination with nominal performance. We pose an H∞ norm bound on one transfer matrix to guarantee robust stability. Under this constraint we minimize an upper bound for the H2 norm of a second transfer matrix. This transfer matrix is chosen so that its H2 norm is a good measure for performance. We extend earlier work on this problem. The intention is to reduce this problem to a convex optimization problem. [ABSTRACT FROM AUTHOR]

In this paper data from a measles epidemic on a University campus is analyzed and is used to formulate a problem of the optimal distribution of vaccine during an epidemic. It is determined that the optimal strategy is to distribute the vaccine as soon as possible without regard to the spatial distribution between dormitory complexes. The result are obtained using extensive computer simulations. [ABSTRACT FROM AUTHOR]

Some results in stochastic adaptive control for the ARMAX system and its time-varying analogue are surveyed. Including one or other result in this paper is to demonstrate the theoretical possibility of stochastic adaptive control, rather than to mean its importance in applications. The emphasis is on the convergence aspect of the problem. Proofs for some results are outlined where appropriate. The paper first presents convergence and consistency results on parameter estimates, given by the stochastic gradient (SG) and the extended least squares (ELS) algorithms, which are the basis of all adaptive controls considered in the paper. Then the paper discusses the following adaptive control problems: adaptive tracking, including both SG- and ELS-based trackers; adaptive model reference control; adaptive stabilization and adaptive LQ control. Special attention is paid to achieving both optimality of control performance and consistency of parameter estimates under minimal conditions imposed on the system. Finally, robustness analysis and systems with time-varying parameters are concerned. [ABSTRACT FROM AUTHOR]

Asynchronous transfer mode (ATM) networks transport information as 53-byte cells that follow one another from the source to the destination. The different streams of cells (called virtual circuits) share buffers in the switching nodes of the network. Typically, cell streams are bursty. These fluctuations in the streams may lead switch buffers to overflow and, therefore, to lose cells. In this paper, we explain a procedure for estimating the spare capacity of switches in the network. The network can use these estimates to decide whether or not to accept new calls and how to route them. The difficulty that we address is obtaining fast and accurate estimates of the low loss probability. We propose quick estimators based on results from the theory of large deviations. [ABSTRACT FROM AUTHOR]