Systematic generation of linear allocation functions in systolic array design

Linear allocation functions are commonly used in mapping programs expressed as systems of recurrence equations to systolic arrays. The interconnections in a systolic array are usually required to belong to a small set ofpermissible vectors. Thus, the design space of all systolic arrays that can be derived from a given program is limited, regardless of the program being mapped. By investigating the nature of this constraint of permissible interconnections, we derive upper bounds on the number of possible systolic arrays that can be derived. These bounds are surprisingly small: there can be no more than 4 linear systolic implementations of 2-dimensional recurrences, and no more than 13 (purely systolic) planar arrays for a 3-dimensional system of recurrences. We present an efficient procedure to utilize thse bounds to generate all possible linear allocation functions for a given system of recurrences, and show how it may be used for the computer-aided design of optimal systolic arrays.Supported by NSF grant MIP-8802454. Authors' email address:     

Interactive R&D portfolio analysis with project interdependencies and time profiles of multiple objectives

This paper describes a three-phase approach to assist research and development managers in obtaining the most attractive project portfolio. The screening procedure of the first phase identifies project proposals that are worthy of further evaluation keeping the number of projects entering the subsequent phase within a manageable size. In the second phase, a multiobjective integer linear programming model determines the solution space of all efficient (i.e., Pareto-optimal) portfolios. It takes into account time profiles of the objectives, various project interdependencies, logical and strategic requirements, as well as resource and benefit constraints. The third phase, finally, aims to find a portfolio which fits the decision-maker's notions. Starting with an arbitrarily selected candidate he/she iteratively sets aspiration levels for objectives or modifies upper and lower bounds. Thus, the solution space is explored until a satisfying compromise between the figures both in benefit and resource categories is reached. Our approach is numerically tractable, and, as a key feature, requires no a priori assumptions about the decision-maker's preferences. Its application is illustrated by an example.     

Efficient shield insertion for inductive noise reduction in nanometer technologies

With high clock frequencies, faster transistor rise/fall time, wider wires, and the use of Cu material interconnects, interconnect inductive noise is becoming an important design metric in digital circuits. An efficient technique to reduce the inductive noise of on-chip interconnects is to insert shields among signal wires. An efficient solution for the min-area shield insertion problem to satisfy given explicit noise bounds in multiple coupled nets is provided. The proposed algorithm determines the locations and number of shields needed to satisfy certain noise constraints. Experimental results show that the proposed approach minimizes the number of shields required to satisfy the noise constraints and uses less runtime than the best alternative reported approach.     

Quantization on the Grassmann Manifold

The problem of quantization in an Euclidean space with unitary constraints can be formulated as an unconstrained problem on a Grassmann manifold. Such constraints arise in areas such as wireless communication with multiple antennas at the transmitter and at the receiver. Due to the constraints, the distortion rate analysis developed for Euclidean spaces cannot be applied directly. This paper extends Gersho's asymptotic (large rate, small distortion) distortion bounds to the case when the source is distributed on the complex Grassmann manifold. The special structure of the Grassmann manifold and the distortion measures defined on it differentiate this problem from the traditional vector quantization in Euclidean spaces.     

Design of logical topologies: a linear formulation forwavelength-routed optical networks with no wavelength changers

We consider the problem of constructing logical topologies over a wavelength-routed optical network with no wavelength changers. We present a general linear formulation which considers routing traffic demands, and routing and assigning wavelengths to lightpaths, as a combined optimization problem. The formulation also takes into account the maximum number of hops a lightpath is permitted to take, multiple logical links in the logical topology, multiple physical links in the physical topology, and symmetry/asymmetry restrictions in designing logical topologies. The objective is to minimize congestion. We show by examples how equality and inequality logical degree constraints have a bearing on congestion. We prove that, under certain conditions, having equality degree constraints with multiple edges allowed in the design of logical topologies does not affect congestion. This helps in reducing the dimensionality of the search space and hence speeds up the search for an optimal solution of the linear formulation. We solve the linear formulation for small examples and show the tradeoff between congestion, number of wavelengths available and the maximum number of hops a lightpath is allowed to take. For large networks, we solve the linear formulation by relaxing the integer constraints. We develop topology design algorithms for large networks based on rounding the solutions obtained by solving the relaxed problem. Since the whole problem is linearizable, the solution obtained by relaxation of the integer constraints yields a lower bound on congestion. This is useful in comparing the efficiency of our heuristic algorithms. Following Bienstock and Gunluk (1995), we introduce a cutting plane which helps in obtaining better lower bounds on congestion and also enables us to reduce the previously obtained upper bounds on congestion     

Channel assignment algorithms satisfying cochannel and adjacent channel reuse constraints in cellular mobile networks

Improved channel assignment algorithms for cellular networks were designed by modeling the interference constraints in terms of a hypergraph. However, these algorithms only considered cochannel reuse constraints. Receiver filter responses impose restrictions on simultaneous adjacent channel usage in the same cell or in neighboring cells. We first present some heuristics for designing fixed channel assignment algorithms with a minimum number of channels satisfying both cochannel and adjacent channel reuse constraints. An asymptotically tight upper bound for the traffic carried by the system in the presence of arbitrary cochannel and adjacent channel use constraints was developed by Deora (1995). However, this bound is computationally intractable even for small systems like a regular hexagonal cellular system of 19 cells. We have obtained approximations to this bound using the optimal solutions for cochannel reuse constraints only and a further graph theoretic approach. Our approximations are computationally much more efficient and have turned out to track very closely the exact performance bounds in most cases of interest.     

Processor Utilization Bounds for Real-Time Systems With Precedence Constraints

This paper presents a novel approach to computing tight upper bounds on the processor utilization for general real-time systems where tasks are composed of subtasks and precedence constraints may exist among subtasks of the same task. By careful analysis of preemption effects among tasks, the problem is formulated as a set of linear programming (LP) problems. Observations are made to reduce the number of LP problem instances required to be solved, which greatly improves the computation time of the utilization bounds. Furthermore, additional constraints are allowed to be included under certain circumstances to improve the quality of the bounds.     

Frame analysis for biorthogonal cosine-modulated filterbanks

This paper addresses the efficient computation of frame bounds for cosine-modulated filterbanks. We derive explicit expressions for the eigenvalues of the frame operator that can be easily computed from the prototype's polyphase components. The number of channels and the downsampling factor may be even or odd, and the oversampling factor is supposed to be an integer. The analysis of low-delay, biorthogonal filterbanks; shows that prototypes solely designed to minimize the stopband energy may lead to wide open frames and, thus, to an undesirable numerical behavior. Because the computational cost of determining the frame bounds with the proposed method is very low, we can directly use the bounds during prototype optimization and obtain prototypes with minimum stopband energy under the condition of fixed frame bounds. Various design examples are presented.     

Upper bounds for constant-weight codes

Let A(n,d,w) denote the maximum possible number of codewords in an (n,d,w) constant-weight binary code. We improve upon the best known upper bounds on A(n,d,w) in numerous instances for n⩽24 and d⩽12, which is the parameter range of existing tables. Most improvements occur for d=8, 10, where we reduce the upper bounds in more than half of the unresolved cases. We also extend the existing tables up to n⩽28 and d⩽14. To obtain these results, we develop new techniques and introduce new classes of codes. We derive a number of general bounds on A(n,d,w) by means of mapping constant-weight codes into Euclidean space. This approach produces, among other results, a bound on A(n,d,w) that is tighter than the Johnson bound. A similar improvement over the best known bounds for doubly-constant-weight codes, studied by Johnson and Levenshtein, is obtained in the same way. Furthermore, we introduce the concept of doubly-bounded-weight codes, which may be thought of as a generalization of the doubly-constant-weight codes. Subsequently, a class of Euclidean-space codes, called zonal codes, is introduced, and a bound on the size of such codes is established. This is used to derive bounds for doubly-bounded-weight codes, which are in turn used to derive bounds on A(n,d,w). We also develop a universal method to establish constraints that augment the Delsarte inequalities for constant-weight codes, used in the linear programming bound. In addition, we present a detailed survey of known upper bounds for constant-weight codes, and sharpen these bounds in several cases. All these bounds, along with all known dependencies among them, are then combined in a coherent framework that is amenable to analysis by computer. This improves the bounds on A(n,d,w) even further for a large number of instances of n, d, and w     

A calculus for network delay. II. Network analysis

For pt.I see ibid., vol.37, no.1, p.114-31 (1991). A method to analyze the flow of data in a network consisting of the interconnection of network elements is presented. Assuming the data that enters the network satisfies burstiness constraints, burstiness constraints are derived for traffic flowing between network elements. These derived constraints imply bounds on network delay and buffering requirements. By example, it is shown that the use of regulator elements within the network can reduce maximum network delay. It is also found that such a use of regulator elements can enlarge the throughput region where finite bounds for delay are found. Finally, it is shown how regulator elements connected in series can be used to enforce general burstiness constraints     

A simple derivation of the coding theorem and some applications

Upper bounds are derived on the probability of error that can be achieved by using block codes on general time-discrete memoryless channels. Both amplitude-discrete and amplitude-continuous channels are treated, both with and without input constraints. The major advantages of the present approach are the simplicity of the derivations and the relative simplicity of the results; on the other hand, the exponential behavior of the bounds with block length is the best known for all transmission rates between0and capacity. The results are applied to a number of special channels, including the binary symmetric channel and the additive Gaussian noise channel.     

Estimation of lower and upper bounds on the power consumption fromscheduled data flow graphs

In this paper, we present an approach for the calculation of lower and upper bounds on the power consumption of data path resources like functional units, registers, I/O ports, and busses from scheduled data flow graphs executing a specified input data stream. The low power allocation and binding problem is formulated. First, it is shown that this problem without constraining the number of resources can be relaxed to the bipartite weighted matching problem which is solvable in O(n)³. n is the number of arithmetic operations, variables, I/O-access or bus-access operations which have to be bound to data path resources. In a second step we demonstrate that the relaxation can be efficiently extended by including Lagrange multipliers in the problem formulation to handle a resource constraint. The estimated bounds take into account the effects of resource sharing. The technique can be used, for example, to prune the design space in high-level synthesis for low power before the allocation and binding of the resources. The application of the technique on benchmarks with real application input data shows the tightness of the bounds     

Bounds from noisy linear measurements

An estimation problem in which a finite number of linear measurements of an unknown function is available, and in which the only prior information available concerning the unknown function consists of inequality constraints on its magnitude, is ill-posed in that insufficient information is available from which point estimates of the unknown function can be made with any reliability, even with exact measurements. An alternative to point estimation involves the computation of bounds on linear functionals of the unknown function in terms of the measurements. A generalization is described of the bounding technique to problems in which the measurements are inexact. The bounds are defined in terms of a primal optimization problem. A deterministic interpretation of the bounds is given, as well as a probabilistic one for the case of additive Gaussian measurement noise. An unconstrained dual optimization problem is derived that has an interesting data-adaptive filtering interpretation and provides an attractive basis for computation. Several aspects of the primal and dual optimization problems are investigated that have important implications for the reliable computation of the bounds.     

Upper bounding service capacity in multi-hop wireless SSMA-based ad hoc networks

Upper bounds on the service carrying capacity of a multi-hop, wireless, SSMA-based ad hoc network are considered herein. The network has a single radio band for transmission and reception. Each node can transmit to, or receive from, multiple nodes simultaneously. We formulate the scheduling of transmissions and control of transmit powers as a joint, mixed-integer, nonlinear optimization problem that yields maximum return at minimum power subject to SINR constraints. We present an efficient tabu search-based heuristic algorithm to solve the optimization problem and rigorously assess the quality of the results. Through analysis and simulation, we establish upper bounds on the VoIP call carrying capacity of the network as function of various parameters. We discuss the pros and cons of using SSMA as a spectrum sharing technique in wireless ad hoc networks.     

Some large availability models: computation and bounds

A dynamic analytic solution is described for a 2^N state general availability model with N components having constant failure and repair rates. From this model, a family of models is developed using truncation and/or attenuation of transition rates. Expressions are derived for steady-state solutions. Then spread-sheet programs are: (1) given for obtaining these solutions, and (2) compared with BASIC programs yielding the same results. State probabilities of these truncation and level-attenuation models are either greater than or less than comparable states in the general model. Thus the states of the general model become either lower bounds or upper bounds for states in these two model types. Other bounds can be constructed from single exponentials based on steady-state probabilities. From this family of models, bounds should exist on state probabilities in models of similar structure but different constraints on failure and repair rates. A specific model is pursued where failures are restricted to any 2 components; and the failure rate of one component is assumed to change on second level of failure. Under these conditions, dynamic bounds on state-probabilities of the initial-state and some, but not all, steady state bounds on the other state probabilities can be found. Examples illustrate various bounds     

Performance bounds on image registration

Registration is a fundamental step in image processing systems where there is a need to match two or more images. Applications include motion detection, target recognition, video processing, and medical imaging. Although a vast number of publications have appeared on image registration, performance analysis is usually performed visually, and little attention has been given to statistical performance bounds. Such bounds can be useful in evaluating image registration techniques, determining parameter regions where accurate registration is possible, and choosing features to be used for the registration. In this paper, Crame/spl acute/r-Rao bounds on a wide variety of geometric deformation models, including translation, rotation, shearing, rigid, more general affine and nonlinear transformations, are derived. For some of the cases, closed-form expressions are given for the maximum-likelihood (ML) estimates, as well as their variances, as space permits. The bounds are also extended to unknown original objects. Numerical examples illustrating the analytical performance bounds are presented.     

Performance impact of partial reconfiguration on multihop lightwavenetworks

Rearrangeable multihop lightwave networks can be dynamically reconfigured to adapt the connectivity among network stations to prevailing traffic conditions. With no limitations on the tunability range of the transmitters and/or receivers allocated to each network station, all connection diagrams can be realized among network stations, within the constraints of the number of transmitters and receivers at each station. Since the number of wavelengths in use may be very large, the tunability range of transmitters/receivers will be restricted, in practice, to some limited set of contiguous wavelengths, or waveband. As a result, all connection diagrams might not be achievable and the network may loose some of its ability to adapt to traffic changes through reconfiguration. We derive bounds on the performance degradation experienced by the network as a function of the tunability restrictions. We then propose and analyze a waveband decomposition, illustrating how networks with good performance can be designed with tunability constraints on the transceivers. We also describe other architectures (subcarrier division multiplexing, multi-fiber physical topology) to which our model and analysis readily apply     

Cascaded Network Optimization Program

A user-oriented computer program package is presented that will analyze and optimize certain cascaded linear time-invariant electrical networks such as microwave filters and all-pass networks. The program is organized in such a way that future additions or deletions of performance specifications, constraints, optimization methods, and circuit elements are readily implemented. Presently, a variety of two-port lumped and distributed elements, all-pass C-type sections and all-pass D-type sections can be treated as fixed or variable between upper and lower bounds on the parameters. Adjoint network sensitivity formulas are incorporated. The Fletcher-Powell or Fletcher optimization methods can be called to optimize in the least pth sense of Bandler and Charalambous an objective function incorporating simultaneously, at the user's discretion, input reflection coefficient, insertion loss, group delay, and the parameter constraints (if any). The program is particularly flexible in the way in which response specifications are handled at any number of, in general, overlapping frequency bands. The package, which is written in Fortran IV, has been tested on a CDC 6400 digital computer.     

Chebyshev Design of Linear-Phase FIR Filters With Linear Equality Constraints

By using basis transformation, the Chebyshev approximation of linear-phase finite-impulse response (FIR) filters with linear equality constraints can be converted into an unconstrained one defined on a new function space. However, since the Haar condition is not necessarily satisfied in the new function space, the alternating property does not hold for the solution to the resulted unconstrained Chebyshev approximation problem. A sufficient condition for the best approximation is obtained in this brief, and based on this condition, an efficient single exchange algorithm is derived for the Chebyshev design of linear-phase FIR filters with linear equality constraints. Simulations show that the proposed algorithm can converge to the optimal solution in most cases and to a near-optimal solution otherwise. Design examples are presented to illustrate the performance of the proposed algorithm.