Scalable Linear Array Architecture with Data-Driven Control for Ultrahigh-Speed Vector Quantization

Current and future requirements for adaptive real-time image compression challenge even the capabilities of highly parallel realizations in terms of hardware performance. Previously proposed linear array structures for full-search vector quantization do not offer scalability and adaptivity in this context, because they require separate data/control pins for dynamically updating the codevectors and complicated interlock mechanisms to ensure that the regular data flow is not corrupted as a result of updates. We explore the design space for full-search vector quantizers and propose a novel linear processor array architecture in which global wiring is limited to clock and power supply distribution, thus allowing high-speed processing in spite of only limited communication with the host via the boundary processors. The resulting fully pipelined design is not only area-efficient for VLSI implementation but is also readily scalable and offers extremely high performance.     

Structural properties of Cayley digraphs with applications to mesh and pruned torus interconnection networks

Despite numerous interconnection schemes proposed for distributed multicomputing, systematic studies of classes of interprocessor networks, that offer speed-cost tradeoffs over a wide range, have been few and far in between. A notable exception is the study of Cayley graphs that model a wide array of symmetric networks of theoretical and practical interest. Properties established for all, or for certain subclasses of, Cayley graphs are extremely useful in view of their wide applicability. In this paper, we obtain a number of new relationships between Cayley (di)graphs and their subgraphs and coset graphs with respect to subgroups, focusing in particular on homomorphism between them and on relating their internode distances and diameters. We discuss applications of these results to well-known and useful interconnection networks such as hexagonal and honeycomb meshes as well as certain classes of pruned tori.     

A Group Construction Method with Applications to Deriving Pruned Interconnection Networks

A number of low degree and, thus, low complexity, Cayley-graph interconnection structures, such as honeycomb and diamond networks, are known to be derivable by systematic pruning of 2D or 3D tori. In this paper, we extend these known pruning schemes via a general algebraic construction based on commutative groups. We show that, under certain conditions, Cayley graphs based on the constructed groups are pruned networks when Cayley graphs of the original commutative groups are kD tori. Thus, our results offer a general mathematical framework for synthesizing and exploring pruned interconnection networks that offer lower node degrees and, thus, smaller VLSI layout and simpler physical packaging. Our constructions also lead to new insights, as well as new concrete results, for previously known interconnection schemes such as honeycomb and diamond networks     

Stored-transfer representations with weighted digit-set encodings for ultrahigh-speed arithmetic

Redundant representations play an important role in high-speed computer arithmetic. One key reason is that such representations support carry-free addition, that is, addition in a small, constant time, independent of operand widths. The implications of stored-transfer representation of digit sets and the associated addition schemes, as an extension of the stored-carry concept to redundant number systems, on the speed and cost of arithmetic algorithms, are explored. Two's-complement digits as the main part and any two-valued digit (twit) in place of a stored carry are allowed, leading to further broadening of the generalised signed-digit representations. The characteristics of the digit sets, possibly not having zero as a member, that allow for most efficient carry-free addition, are investigated. Circuit speed is gained from storing or saving, instead of combining through addition, the interdigit transfers generated during the carry-free addition process. Encoding efficiency is gained from using a twit-transfer set encoded by one logical bit, where more bits would otherwise be needed to represent a transfer value     

FFT computation with linear processor arrays using a data-driven control scheme

We consider the practical design of linear controllers to meet a given set ofH ₂ specifications. TheQ-parametrization reduces the problem to a quadratic minimization subject to multiple quadratic constraints, which we solve using semi-definite programming (SDP) methods. Each SDP iteration requires calculating a primal and dual search direction and minimizing the cost function along the plane defined by these search directions. The primal direction requires solving a least squares problem whose normal equation matrix is composed of a block-Toeplitz portion plus other structured matrices. We make use of Kronecker products and FFT's to greatly reduce the calculation. The dual search direction and plane search are accelerated by low-rank representations of the SDP structured matrices. As an example, we design controllers which explore the optimal tradeoff between in-band residual and out-of-band enhancement of acoustic radiation from a (mathematically modeled) submerged spherical shell, while simultaneously constraining two sensitivity measures. For this example we show that significant reduction in out-of-band enhancement is possible with only minor in-band penalties.     

Voting networks

Designs of hardware voters are presented that can be easily pipelined to accommodate extremely high data rates. Design strategies for bit-voters and word-voters are described. Examples of resultant designs are given and each design is evaluated with respect to cost and performance. Both ordinary and generalized m-out-of-n voting, with arbitrary vote assigned to the inputs, are considered. Median voters can be synthesized by simple variants of the design methods. Using currently available technology, these designs can operate at speeds of many millions of votes per second. For majority bit-voters with small values of n, a multiplexer-based design method generally yields the best realizations while for larger values of n , designs based on selection networks tend to be most efficient. For word voters, cost-effective designs based on modified or augmented sorting networks are feasible. In either case, the rich theory developed for the analysis and synthesis of parallel/pipelined sorting networks directly benefits the design process     

Optimal Placement of Spare Modules in a Cascaded Chain

A class of redundant cascaded chains with i.i.d. modules is considered in which recovery from a failure takes place by replacing the faulty module by a spare module. The complexity of the reconfiguration process depends upon the location of spare modules in the cascade. This paper deals with the question of optimally placing the spare modules in order to minimize the s-expected recovery time (down time) of the system. Exact analysis is carried out for cascades with one and two spare modules and an approximate analysis is given for three or more spares. Even though exact analysis does not seem to be practical in the general case, the symmetry of spare module positions in the special cases discussed here and linearity of the system suggest that one might expect the optimal positions to be symmetric in general. Because of this symmetry, one can reduce the number of variables to be considered in the general case, however, some inaccuracies might be introduced.     

High-speed and low-power scalable Hamming weight comparator based on a non-weighted switched-capacitor array

Many practical applications require a comparison of the Hamming weights of two N-bit binary vectors. This comparison can be performed in a fully digital manner or by a mix of analog and digital techniques. In this paper, we propose a design in the latter category that exhibits advantages in speed and power dissipation compared with the best previous designs. The proposed design comprises of two switched-capacitor arrays associated with two comparators placed in parallel, collectively providing a complete comparison outcome of “>”, “<”, or “=”. The switched-capacitor array circuit is composed of uniform capacitances, thus associating identical charges with all bits, independent of their positions in the input bit-vectors. Once charge accumulation has occurred based on the asserted inputs, the two comparators release the final decision concurrently. The structure is shown to support wide input vectors on the order of 64 bits, while requiring a small silicon area for capacitor array structures, CMOS switches, and latched comparators to compute and store the comparison outcome. HSPICE simulation shows a total power consumption of 1.136 mW, evaluated at the operating frequency of 1 GHz (based on input-to-decision delay) for 16 bit input vectors under 0.15 μm TSMC technology.     

Loaded horizontal antenna over an imperfect ground

The Fresnel reflection coefficient technique is employed to establish anE-field integral equation for the antenna current. A resistive loading of the formLambda(x) = Lambda_{0}/(1 - |x|/L)is used to load the antenna. An optimization technique is discussed for determining the value of critical loadingLambda_{0}^{c}, which enforces a traveling wave current on the antenna. Results are given for the critical loading parameters, antenna currents, input impedances and radiation patterns versus different antenna dimensions and ground permittivities and conductivities. Some representative time-domain results for such loaded antennas are also included.