Search

New counting-based methods for comparing the Hamming weight of a binary vector with a constant, as well as comparing the Hamming weights of two input vectors, are proposed. It is shown that the proposed comparators are faster and simpler, both in asymptotic sense and for moderate vector lengths, compared with the best available fully digital designs. These speed and cost advantages result from a more efficient population counting, as well as the merger of counting and comparison operations, via accumulative and up/down parallel counters. Index Terms--Column compression, comparator, Hamming distance, multioperand addition, parallel counter, population count.

The pruning schemes are described using a general algebraic construction based on commutative groups. The results have provided a general framework for synthesizing and exploring pruned interconnection networks that offer lower node degrees.

The various routing algorithms for perfect difference networks (PDNs) are demonstrated. The results state that algorithms developed for a complete network can be emulated by optimal slowdown on a PDN of the same size.

The network architecture in its basic and bipartite forms is presented and it is shown how the related multidimensional perfect difference networks (PDNs) can be derived. It is concluded that PDNs and their derivates constitute worthy additions to the repertoire of network designers and may offer additional design points that can be exploited by current and emerging technologies including wireless and optical interconnects.

We introduce the notion of two-valued digit (twit) as a binary variable that can assume one of two different integer values. Posibits, or simply bits, in {0, 1} and negabits in {--1, 0}, commonly used in two's-complement representations and (n, p) encoding of binary signed digits, are special cases of twits. A weighted bit-set (WBS) encoding, which generalizes the two's-complement encoding by allowing one or more posibits and/or negabits in each radix-2 position, has been shown to unify many efficient implementations of redundant number systems. A collection of equally weighted twits, including ones with noncontiguous values (e.g., {--1, 1} or {0, 2}), can lead to wider representation range without the added storage and interconnection costs associated with multivalued digit sets. We present weighted twit-set (WTS) encodings as a generalization of WBS encodings, examine key properties of this new class of encodings, and show that any redundant number system (e.g., generalized signed-digit and hybrid-redundant systems), including those that are based on noncontiguous and/or zero-excluded digit sets, is faithfully representable by WTS encoding. We highlight this broad coverage by a tree chart having WTS representations at its root and various useful redundant representations at its many internal nodes and leaves. We further examine how highly optimized conventional components such as standard full/half-adders and compressors may be used for arithmetic on WTS-encoded operands, thus allowing highly efficient and VLSI-friendly circuit implementations. For example, focusing on the WBS-like subclass of WTS encodings, we describe a twit-based implementation of a particular stored-transfer representation which offers area and speed advantages over other similar designs based on WBS and hybrid-redundant representations. Index Terms--Arithmetic unit, carry-free addition, computer arithmetic, digit set, hybrid redundancy, number representation, redundant number system, signed-digit number system, stored-transfer representation, weighted bit-set (WBS) encoding.

Honeycomb and diamond networks are considered as alternatives to mesh and torus architectures in parallel processing.

A strategy for designing stable insertion sorters based on linear arrays with data-driven control is described. The approach involves a data item carrying a control tag to specify how it is to be operated upon by receiving cell and in performing two parallel comparisons within each cell. Results showed that highly cost-effective designs can be obtained by selecting an optimal cell size in terms of the number of comparators it contains.

Higher efficient n-way threshold and plurality algorithms are developed based on the properties of the input object space, type of voting and rule for output selection. Voting is essential for ultrareliable systems based on multi-channel computation paradigm for realization. The voting algorithm indicates how the result can be specified from input data.

This paper serves a dual purpose. It presents a unified framework and terminology for the study of computer system dependability. It also surveys the field of dependable computing in light of the proposed framework. Specifically, impairments to dependability are viewed from six levels, each being more abstract than the previous one. It is argued that all of these levels are useful, in the sense that proven dependability assurance techniques can be applied at each level, and that it is beneficial to have distinct, precisely defined terminology for describing impairments to, and procurement strategies for, computer system dependability at these levels. The six levels are: (1) Defect level or component level, dealing with deviant atomic parts. (2) Fault level or logic level, dealing with deviant signal values or path selections. (3) Error level or information level, dealing with deviant data or internal states. (4) Malfunction level or system level, dealing with deviant functional behavior. (5) Degradation level or service level, dealing with deviant performance. (6) Failure level or result level, dealing with deviant outputs or actions. Briefly, a hardware or software component may be defective (hardware may also become defective due to wear and aging). Certain system states will expose the defect, resulting in the development of faults defined as incorrect signal values or decisions within the system. If a fault is actually exercised, it may contaminate the data flowing within the system, causing errors. Erroneous information or states may or may not cause the affected subsystem to malfunction, depending on the subsystem's design and error tolerance. A subsystem malfunction does not necessarily have a catastrophic, unsafe, or even perceivable service-level effect. Finally, degradation of service could eventually lead to system failure. At each of these six levels, the complementary approaches of prevention (avoidance or removal) and tolerance are discussed in relation to inter-level transitions.

Three compression schemes for modular multiplication tables are proposed. The first provides a compression ratio similar to an existing method although the addressing protocol is simpler and the memory structure is more uniform. Results show that the new method generates additional table size reduction by a factor of 2 using more complicated peripheral hardware. The second compression method is based on squaring and more suited to large moduli applications.

A multi-level model was proposed for assessing and counteracting the causes of unreliability in computing and information systems. This model revealed that a system may be in one of seven states which includes ideal, defective, faulty, erroneous, malfunctioning, degraded and failed. It worked on the premise that some system failure, result from unsatisfiable requirements rather than from malfunction.

Periodically regular chordal (PRC) ring networks were proposed as a compromise for combining low node degree with small diameter. In the past, chordal rings were proposed as networks that combined simple routing framework of rings with the lower diameter, wider bisection and higher resilience of other architectures. Observations showed that if the assumption that each node had exactly one skip link were relaxed, richer and sparser interconnections would result without undue complications for routing algorithms.