The purpose of this paper is to study tradeoffs between efficiency and precision for the general virtual network embedding (VNE) problem. To narrow the gap between solutions contributed by previous heuristic schemes and the optimal solution, and to ease the unacceptable computational burden of optimization approaches to VNE for large-scale networks, we propose the use of graph eigenspace notions for node mapping, that is, for associating virtual nodes to substrate nodes (SNs). We also contribute an inexact algorithm which projects all SNs to a 2-D eigenspace for generating a more efficient node mapping. There are some similarities between our method and numerous graph-matching strategies emerging in machine learning fields, but there are also some differences between the two, because the VNE problem is not strictly mathematical with respect to the mapping it seeks. Thus, we provide the relevant theoretical evidence to guarantee the solution quality of our scheme compared with a couple of previous VNE proposals. Simulation results demonstrate that our schemes can reach a better tradeoff point regarding runtime (that approaches the overhead of implementing eigendecomposition of a general matrix) and embedding quality metrics. Besides, our inexact algorithm using 2-D projection exhibits an improvement in quality over previous node-rank-based methods.

Petascale supercomputers are already pushing power boundaries that can be supplied or dissipated cost-effectively; greater challenges await us in the era of exascale machines. We are thus motivated to study methods of reducing the energy cost of arithmetic operations, which can be substantial in numerically intensive applications. Additionally, being both a widely-used operation in itself and an important building block for synthesizing other arithmetic operations, has received much attention in this regard. Circuit and energy costs of fast adders are dominated by their fast carry networks. The availability of simple and energy-efficient majority function in certain emerging nanotechnologies (such as quantum-dot cellular automata, single-electron tunneling, tunneling phase logic, magnetic tunnel junction, nanoscale bar magnets, and memristors) has motivated our work to reformulate the carry recurrence in terms of fully-utilized majority elements, with all three inputs usefully employed. We compare our novel designs and resulting circuits to prior proposals based on 3-input majority elements in quantum-dot cellular automata, demonstrating advantages in both speed and circuit complexity. We also show that the performance and cost advantages carry over to at least one other emerging, energy-efficient technology, single-electron tunneling, raising hopes for achieving similar benefits with other technologies, which we review very briefly.

Carry computation is a most important notion in computer arithmetic, because it dictates the speed of addition, which is in turn vital to high-speed computation, both as a directly used primitive and as a building block for synthesizing other operations. The theory of fast addition is well-established, but from time to time, changes in technology necessitate a reassessment of strategies for carry network implementation, even though the logical functions to be realized remain the same. We study the implications of the availability of simple, fast, and power-efficient majority gates (in technologies such as quantum-dot cellular automata, single-electron tunneling, tunneling phase logic, magnetic tunnel junction, and nanoscale bar magnets) to the design of carry networks, offering a reformulation of the carry recurrence that allows for building carry networks exclusively out of fully utilized majority elements. We compare our novel implementations based on 3-input majority elements to prior proposals based on these elements, demonstrating advantages in both speed and circuit complexity.

It has been reported in the literature on computational neuroscience that a rat's uncanny ability to dash back to a home position in the absence of any visual clues (or in total darkness, for that matter) may stem from its distinctive method of position representation. More specifically, it is hypothesized that the rat uses a multimodular method akin to residue number system (RNS), but with continuous residues or digits, to encode position information. After a brief review of the evidence in support of this hypothesis, and how it relates to RNS, we discuss the properties of continuous-digit RNS, and derive results on the dynamic range, representational accuracy and factors affecting the choice of the moduli, which are themselves real numbers. We conclude with suggestions for further research on important open problems concerning the process of selection, or evolutionary refinement, of the set of moduli in such a representation.

We present a new comparator design featuring wide-range and high-speed operation using only conventional digital CMOS cells. Our comparator exploits a novel scalable parallel prefix structure that leverages the comparison outcome of the most significant bit, proceeding bitwise toward the least significant bit only when the compared bits are equal. This method reduces dynamic power dissipation by eliminating unnecessary transitions in a parallel prefix structure that generates the N-bit comparison result after (log4N)+(log16N)+4 CMOS gate delays. Our comparator is composed of locally interconnected CMOS gates with a maximum fan-in and fan-out of five and four, respectively, independent of the comparator bitwidth. The main advantages of our design are high speed and power efficiency, maintained over a wide range. Additionally, our design uses a regular reconfigurable VLSI topology, which allows analytical derivation of the input-output delay as a function of bitwidth. HSPICE simulation for a 64-b comparator shows a worst case input-output delay of 0.86 ns and a maximum power dissipation of 7.7 mW using 0.15- μm TSMC technology at 1 GHz.

Due to the widespread use and inherent complexity of floating-point addition, much effort has been devoted to its speedup via algorithmic and circuit techniques. We propose a new redundant-digit representation for floating-point numbers that leads to computation speedup in two ways: (1) Reducing the per-operation latency when multiple floating-point additions are performed before result conversion to nonredundant format and (2) Removing the addition associated with rounding. While the first of these advantages is offered by other redundant representations, the second one is unique to our approach, which replaces the power- and area-intensive rounding addition by low-latency insertion of a rounding two-valued digit, or twit, in a position normally assigned to a redundant twit within the redundant-digit format. Instead of conventional sign-magnitude representation, we use a sign-embedded encoding that leads to lower hardware redundancy, and thus, reduced power dissipation. While our intermediate redundant representations remain incompatible with the IEEE 754-2008 standard, many application-specific systems, such as those in DSP and graphics domains, can benefit from our designs. Description of our radix-16 redundant representation and its addition algorithm is followed by the architecture of a floating-point adder based on this representation. Detailed circuit designs are provided for many of the adder's critical subfunctions. Simulation and synthesis based on a 0.13 ¿m CMOS standard process show a latency reduction of 15 percent or better, and both area and power savings of around 58 percent, compared with the best designs reported in the literature.

The existence of parallel node-disjoint paths between any pair of nodes is a desirable property of interconnection networks, because such paths allow tolerance to node and/or link failures along some of the paths, without causing disconnection. Additionally, node-disjoint paths support high-throughput communication via the concurrent transmission of parts of a message. We characterize maximum-sized families of parallel paths between any two nodes of alternating group networks. More specifically, we establish that in a given alternating group network AN n , there exist n−1 parallel paths (the maximum possible, given the node degree of n−1) between any pair of nodes. Furthermore, we demonstrate that these parallel paths are optimal or near-optimal, in the sense of their lengths exceeding the internode distance by no more than four. We also show that the wide diameter of AN n is at most one unit greater than the known lower bound D+1, where D is the network diameter.

Moduli of the form 2nplusmn 1, which greatly simplify certain arithmetic operations in residue number systems (RNS), have been of longstanding interest. A steady stream of designs for modulo (2nplusmn 1) adders has rendered the latency of such adders quite competitive with ordinary adders. The next logical step is to approach the problem in a unified and systematic manner that does not require each design to be taken up from scratch and to undergo the error prone and labor intensive optimization for high speed and low power dissipation. Accordingly, we devise a new redundant representation of mod (2nplusmn 1) residues that allows ordinary fast adders and a small amount of peripheral logic to be used for mod (2nplusmn 1) addition. Advantages of the building block approach include shorter design time, easier exploration of the design space (area, speed, power tradeoffs), and greater confidence in the correctness of the resulting circuits. Advantages of the unified design include the possibility of fault tolerant and gracefully degrading RNS circuit realizations with fairly low hardware redundancy.

An optical transpose interconnection system (OTIS) network with n2nodes is a two-level swapped architecture built of n copies of an n-node basis network that constitute its clusters. A simple rule for intercluster connectivity (node j in cluster i connected to node i in cluster j) leads to regularity, modularity, packageability, fault tolerance, and algorithmic efficiency of the resulting networks. We prove that an OTIS (swapped) network with a connected basis network possesses maximal fault tolerance, regardless of whether its basis network is maximally fault tolerant. We also show how the corresponding maximal number of node-disjoint paths between two nodes of a swapped network can be algorithmically constructed in a manner that is independent of the existence and construction of node-disjoint paths within its basis network. Our results are stronger than previously published results and they replace a number of proofs and constructions in the literature for specific basis networks. Additionally, we use our parallel path constructions to establish that the fault diameter and wide diameter of an OTIS network is no more than 4 units greater than its diameter.

Recently, Melhem presented a "new" class of low-diameter interconnection (LDI) networks, (IEEE Trans. Computers, Vol. 56, No. 4, pp. 502-510). We note that LDI networks are the same as the previously known generalized de Bruijn graphs, point out an error in the decomposition of LDI networks into permutations, and find that the correct decomposition scheme is an instance of arc coloring for coset graphs. Hence, we pursue a number of general results on arc coloring of coset graphs that can be applied to this particular decomposition problem as well as within many other contexts, including complete arc coloring and normality of coset graphs.

Intervals constitute one of the most important tools for dealing with uncertainty in computations. Researchers in the fields of interval arithmetic and constraint propagation have devised elaborate methods for computing with interval variables. In this interpretation, an interval represents the proposition: "I don't know what the correct value is, but it cannot be outside this range. " However, intervals also have another use, which is captured in the statement: "Any value in this range would be fine with me. "In devising voting schemes for data fusion and fault-tolerant distributed computation, these two meanings, and a number of other lesser known variations, must be completely understood in order to design and implement meaningful voting strategies. Irregularities and paradoxes in voting schemes, extensively studied by mathematicians and social scientists, must also be taken into account to avoid serious pitfalls. In this paper, we discuss the two interpretations of interval voting, along with their practical implications, and show how voting strategies differ in their time and communication complexities, performance, and resilience according to the meaning intended and the types of failure assumed.

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

Alternating group graphs AGn, studied by Jwo and others, constitute a class of Cayley graphs that possess certain desirable properties compared with other regular networks considered by researchers in parallel and distributed computing. A different form, ANn, of such graphs, proposed by Youhou and dubbed alternating group networks, has been shown to possess advantages over AGn. For example, ANnhas a node degree that is smaller by a factor of about 2 while maintaining a diameter comparable to that of AGn, is maximally fault-tolerant, and shares some of the positive structural attributes of the well-known star graph. In this paper, we characterize the distance between any two nodes in ANnand present an optimal (shortest-path) routing algorithm for this class of networks

In view of their applicability to parallel and distributed computer systems, interconnection networks have been studied intensively by mathematicians, computer scientists, and computer designers. In this paper, we propose an asymptotically optimal method for connecting a set of nodes into a perfect difference network (PDN) with diameter 2, so that any node is reachable from any other node in one or two hops. The PDN interconnection scheme, which is based on the mathematical notion of perfect difference sets, is optimal in the sense that it can accommodate an asymptotically maximal number of nodes with smallest possible node degree under the constraint of the network diameter being 2. We present the network architecture in its basic and bipartite forms and show how the related multidimensional PDNs can be derived. We derive the exact average internode distance and tight upper and lower bounds for the bisection width of a PDN. We conclude that PDNs and their derivatives 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. Performance, algorithmic, and robustness attributes of PDNs are analyzed in a companion paper.

Perfect difference networks (PDNs) that are based on the mathematical notion of perfect difference sets have been shown to comprise an asymptotically optimal method for connecting a number of nodes into a network with diameter 2. Justifications for, and mathematical underpinning of, PDNs appear in a companion paper. In this paper, we compare PDNs and some of their derivatives to interconnection networks with similar cost/performance, including certain generalized hypercubes and their hierarchical variants. Additionally, we discuss point-to-point and collective communication algorithms and derive a general emulation result that relates the performance of PDNs to that of complete networks as ideal benchmarks. We show that PDNs are quite robust, both with regard to node and link failures that can be tolerated and in terms of blandness (not having weak spots). In particular, we prove that the fault diameter of PDNs is no greater than 4. Finally, we study the complexity and scalability aspects of these networks, concluding that PDNs and their derivatives allow the construction of very low diameter networks close to any arbitrary desired size and that, in many respects, PDNs offer optimal performance and fault tolerance relative to their complexity or implementation cost.

Digit-recurrence binary dividers are sped up via two complementary methods: keeping the partial remainder in redundant form and selecting the quotient digits in a radix higher than 2. Use of a redundant partial remainder replaces the standard addition in each cycle by a carry-free addition, thus making the cycles shorter. Deriving the quotient in high radix reduces the number of cycles (by a factor of about h for radix 2/sup h/). To make the redundant partial remainder scheme work, quotient digits must be chosen from a redundant set, such as [-2, 2] in radix 4. The redundancy provides some tolerance to imprecision so that the quotient digits can be selected based on examining truncated versions of the partial remainder and divisor. No closed form formula for the required precision in the partial remainder and divisor, as a function of the quotient digit set and the range of the partial remainder, is known. We establish tight upper bounds on the required precision for the partial remainder and divisor. The bounds are tight in the sense that each is only one bit over a well-known simple lower bound. We also discuss the implications of these bounds for the quotient digit selection process.

We formulate array robustness theorems (ARTs) for efficient computation and communication on faulty arrays. No hardware redundancy is required and no assumption is made about the availability of a complete submesh or subtorus. Based on ARTs, a very wide variety of problem, including sorting, FFT, total exchange, permutation, and some matrix operations, can be solved with a slowdown factor of 1+o(1). The number of faults tolerated by ARTs ranges from o(min (n/sup 1-1/d/, n/d, n/h)) for n-ary d-cubes with worst-case faults to as large as o(N) for most N-node 2-D meshes or tori with random faults, where h is the number of data items per processor The resultant running times are the best results reported thus far for solving many problems on faulty arrays. Based on ARTs and several other components such as robust libraries, the priority emulation discipline, and X'Y' routing, we introduce the robust adaptation interface layer (RAIL) as a middleware between ordinary algorithms/programs and the faulty network/hardware. In effect, RAIL provides a virtual fault-free network to higher layers, while ordinary algorithms/programs are transformed through RAIL into corresponding robust algorithms/programs that can run on faulty networks.

The index-permutation graph (IPG) model is a natural extension of the Cayley graph model, and super-IPGs form an efficient class of IPGs that contain a wide variety of networks as subclasses. In this paper, we derive a number of efficient algorithms and embeddings for super-IPGs, proving their versatility. We show that a multitude of important networks can also be emulated in super-IPGs with optimal slowdown. Also, the intercluster diameter average intercluster distance, and bisection bandwidth of suitably constructed super-IPGs are optimal within small constant factors. Finally we show that when parallel computers, built as multiple chip-multiprocessors (MCMP), are based on super-IPGs, they can significantly outperform those based on hypercubes, k-ary n-cubes, and other networks in carrying out communication-intensive tasks.

We solve an open question posed by Akers and Krishnamurthy in 1986 concerning VLSI layout of star graphs. We show that the area of the optimal layout of an N-node star graph, hierarchical cubic network (HCN), or hierarchical folded-hypercube network (HFN) is N/sup 2//16/spl plusmn/o(N/sup 2/) under the Thompson model, or under the extended grid model where a node occupies a rectangle of sides that may range from n-1 to o(/spl radic/N) for the n-star, log/sub 2/N+1 to o(/spl radic/N) for the HCN, and log/sub 2/N+2 to o(/spl radic/N) for the HFN. An n-dimensional star graph this requires less area than any possible layout of a similar-size hypercube, but more than that of the much smaller n-cube. We also derive multilayer layout for star graphs that has area N/sup 2//8[L/sup 2//2]/spl plusmn/o(N/sup 2//L/sup 2/), where a node occupies a rectangle of sides ranging from [n-1/4] to o(/spl radic/N/L) and the number L of wiring layers satisfies 2/spl les/L=o(/spl radic/N/n). Finally we show that the bisection width of an N-node star graph is N/4/spl plusmn/o(N) and the bisection width of an HCN or HFN is exactly N/4.

We propose the robust algorithm-configured emulation (RACE) scheme for efficient parallel computation and communication in the presence of faults. A wide variety of algorithms originally designed for fault-free meshes, tori, and k-ary n-cubes can be transformed to corresponding robust algorithm through RACE. In particular optimal robust algorithms can be derived for total exchange (TE) and ascend/descend operations with a factor of 1+o (1) slowdown. Also, RACE can tolerate a large number of faulty elements, without relying on hardware redundancy or any assumption about the availability of a complete subarray.

AbstractÐHoneycomb and diamond networks have been proposed as alternatives to mesh and torus architectures for parallel processing. When wraparound links are included in honeycomb and diamond networks, the resulting structures can be viewed as having been derived via a systematic pruning scheme applied to the links of 2D and 3D tori, respectively. The removal of links, which is performed along a diagonal pruning direction, preserves the network's node-symmetry and diameter, while reducing its implementation complexity and VLSI layout area. In this paper, we prove that honeycomb and diamond networks are special subgraphs of complete 2D and 3D tori, respectively, and show this viewpoint to hold important implications for their physical layouts and routing schemes. Because pruning reduces the node degree without increasing the network diameter, the pruned networks have an advantage when the degree-diameter product is used as a figure of merit. Additionally, if the reduced node degree is used as an opportunity to increase the link bandwidths to equalize the costs of pruned and unpruned networks, a gain in communication performance may result. Index TermsÐCayley graph, k-ary n-cube, network topology, processor array, pruned torus network, VLSI layout. 1

Current VLSI technology allows more than two wiring layers and the number is expected to rise in future. In this paper we show that, by designing VLSI layouts directly for an L-layer model, the layout area for a variety of networks can be reduced by a factor of about (L/2)/sup 2/ compared to the layout area required under a 2-layer model, and the volume and maximum wire length can be reduced by a factor of about L/2, leading to considerably lower cost and/or higher performance. The proposed layouts for k-ary n-cubes, hypercubes, butterfly networks, cube-connected cycles (CCC), folded hypercubes, generalized hypercubes, k-ary n-cube cluster-c, hierarchical hypercube networks, reduced hypercubes, hierarchical swap networks, and indirect swap networks, are the best layouts reported for these networks thus far and are optimal within a small constant factor under both the Thompson model and the multilayer grid model. All of our layouts are optimally scalable in that we can allow each network node to occupy the largest possible area (e.g., o(N/L/sup 2/) for hypercubes) without increasing the leading constant of the layout area, volume, or maximum wire length.

We present a scheme for optimal VLSI layout and packaging of butterfly networks under the Thompson model, the multilayer grid model, and the hierarchical layout model. We show that when L layers of wires are available, an N-node butterfly network can be laid out with area 4N2/L2 log22 N + o (N2/L2 log2 N), maximum wire length 2N/L log2 N + o (N/L log N), and volume 4N2/L log22 N + o (N2/L log2 N) , under the multilayer 2-D grid model, where only one active layer (for network nodes) is required and L layers of wires are available.

In this paper, we present the index-permutation (IP) graph model, and apply it to the systematic development of efficient hierarchical networks. We derive several classes of interconnection networks based on IP graphs to achieve desired properties; the results compare favorably with popular interconnection networks, as measured by topological (e.g., node degree and diameter) and algorithmic properties, and are particularly efficient in view of their sparse inter-module communication patterns. In particular, the diameters of suitably-constructed super-IP graphs, a subclass of IP graphs, are optimal within a factor of 1+o(1), given their node degrees. The IP graph model can also be used as a common platform that unifies the architectures and algorithms for a vast variety of interconnection networks.

The Petersen graph is a Moore graph that has node degree 3, diameter 2, and optimal network size 10. In this paper, we present a class of interconnection networks, called cyclic Petersen networks (CPNs), which efficiently extend the Petersen graph to obtain larger networks with small diameter and node degree. We derive balanced routing algorithms and efficient embeddings for CPNs. In particular, we show that many normal mesh algorithms can be emulated on CPNs with a slowdown factor of about 1.1. We also show that complete CPNs can embed meshes, tori, meshes of trees, and folded Petersen networks with dilation 3, hypercubes and generalized hypercubes with dilation 4, and pyramids with dilation 5.

We present a strategy for designing stable insertion sorters based on linear arrays with data-driven control. The novelty of our approach lies in each data item carrying a control tag to specify how it is to be operated upon by a receiving cell and in performing two parallel comparisons within each cell. To assure first-in/first-out handling of equal key values, some data items must be marked to reflect their past histories. Such marking is conveniently carried out by modifying the data item's control tag. It is the combination of the above features that allows us to derive the first single-cycle priority queue that operates in fully pipelined mode, with no broadcasting of data values or control signals. By performing more than two parallel comparisons in each cell, the VLSI implementation cost of our stable sorter can be reduced. We show that highly cost-effective designs can be obtained by selecting an optimal cell size in terms of the number of comparators it contains.

Chordal rings have been proposed in the past as networks that combine the simple routing framework of rings with the lower diameter, wider bisection, and higher resilience of other architectures. Virtually all proposed chordal ring networks are node-symmetric, i.e., all nodes have the same in/out degree and interconnection pattern. Unfortunately, such regular chordal rings are not scalable. In this paper, periodically regular chordal (PRC) ring networks are proposed as a compromise for combining low node degree with small diameter. By varying the PRC ring parameters, one can obtain architectures with significantly different characteristics (e.g., from linear to logarithmic diameter), while maintaining an elegant framework for computation and communication. In particular, a very simple and efficient routing algorithm works for the entire spectrum of PRC rings thus obtained. This flexibility has important implications for key system attributes such as architectural satiability, software portability, and fault tolerance. Our discussion is centered on unidirectional PRC rings with in/out-degree of 2. We explore the basic structure, topological properties, optimization of parameters, VLSI layout, and scalability of such networks, develop packet and wormhole routing algorithms for them, and briefly compare them to competing fixed-degree architectures such as symmetric chordal rings, meshes, tori, and cube-connected cycles.

In this paper, we propose a new presentation of graphs, called the index-permutation (IP) graph model, and apply it to the systematic development of communication-efficient interconnection networks. We derive several new classes of interconnection networks based on IP graphs to achieve the desired properties. We show that the diameters of some classes of IP graphs are optimal within a factor of 1+0(1) given their node degrees. Designs based on IP graphs can balance system resources by appropriately selecting network parameters, thus providing adaptability to future technology and application requirements.

Gaussian cubes are derived by removing links from a hypercube in a periodic fashion. By varying the partition parameter, one can obtain networks with different characteristics, while maintaining a basic framework for computation and communication. Unfortunately, such networks are in general not regular, making it difficult to derive their topological properties explicitly. In this paper, we study the diameter of Gaussian cubes and show the trade-off between cost and performance.

We introduce a pruning scheme to reduce the node degree of k-ary n-cube from 2n to 4. The links corresponding to n-2 of the n dimensions are removed from each node. One of the remaining dimensions is common to all nodes and the other is selected periodically from the remaining n-1 dimensions. Despite the removal of a large number of links from the k-ary n-cube, this incomplete version still preserves many of its desirable topological properties. In this paper, we show that this incomplete k-ary n-cube belongs to the class of Cayley graphs, and hence, is node-symmetric. It is 4-connected with diameter close to that of the k-ary n-cube.

In this paper we propose simple and efficient algorithms for sorting on incomplete meshes. No hardware redundancy is required and no assumption is made about the availability of a complete submesh. The proposed robust sorting algorithms are very efficient when only a few processors are faulty and degrade gracefully as the number of faults increases. In particular we show that 1-1 sorting (1 key per healthy processor) in row-major or snakelike row-major order can be performed in 3n+o(n) communication and comparison steps on an n/spl times/n incomplete mesh that has an arbitrary pattern of o(/spl radic/n) faulty processors. This is the fastest algorithm reported thus far for sorting in row-major and snakelike row-major orders on faulty meshes and the time complexity is quite close to its lower bound.

In this paper, we propose a new class of interconnection networks, called swapped networks, for general-purpose parallel processing. Swapped networks not only generate a wide class of high-performance interconnection networks, but also generalize, and serve to unify, many proposed parallel architectures as well as their algorithms. We show that swapped networks can efficiently emulate hypercubes, high-dimensional meshes, or generalized hypercubes, while having node degrees significantly smaller than the emulated network in each case. We also show that some subclasses of swapped networks can achieve asymptotically optimal diameters. Swapped networks are highly modularized, make the use of fixed-degree building blocks possible for any practically realizable system, and lead to the construction of high-performance scalable networks with reasonable cost.

N-version programming (NVP) and acceptance testing (AT) are techniques for ensuring reliable computation results from imperfect software. Various symmetric combinations of NVP and AT have also been suggested. We take the view that one can insert an AT at virtually any point in a suitably constructed multi-channel computation graph and that judicious placement of ATs will lead to cost-effective reliability improvement. Hence, as a general framework for the creation, representation, and analysis of combined NVP-AT schemes, we introduce MTV graphs, and their simplified data-driven version called DD-MTV graphs, composed of computation module (M), acceptance test (T), and voter (V) building blocks. Previous NVP-AT schemes, such as consensus recovery blocks, recoverable N-version blocks, and N-self-checking programs can be viewed as special cases of our general combining scheme. Results on the design and analysis of new NVP-AT schemes are presented and the reliability improvements are quantified. We show, e.g., that certain, somewhat asymmetric, combinations of M, T, and V building blocks can lead to higher reliabilities than previously proposed symmetric arrangements having comparable or higher complexities.

Voting on large collections of input objects is becoming increasingly important in data fusion, signal and image processing applications, learning algorithms, and distributed computing. To achieve high speed in voting, the multiple processing resources typically available in such applications should be utilized; hence the need for parallel voting algorithms. We develop efficient parallel algorithms for threshold voting which generalize and extend previous work on both sequential threshold voting and parallel majority voting. Our discussion centers on unweighted threshold (m-out-of-n) voting. However, we observe that under certain conditions, the results can be extended to efficient weighted threshold voting. We show how a known O(n)-time sequential algorithm for m-out-of-n voting can be parallelized through a simple divide-and-conquer strategy. When m = 𝛉(n), the resulting algorithm has O(log2n) time complexity on n-processor PRAM and hypercubic computers and O(k2n1/k) time complexity on a k-dimensional mesh with n processors. We also analyse the time complexity of the algorithm for m = o(n) and its special case of m = 𝛉(1).

Several useful associative memory algorithms deal with identifying extreme values (maximum or minimum) in a specified field of a selected subset of words. Previously proposed algorithms for such extreme-value searches are bit-sequential in nature, even when implemented on fully parallel associative memories. We show how multiple-bit search capability of a fully parallel associative memory can be used to advantage in reducing the expected search time for finding extreme values. The idea is to search for the all-ones pattern within subfields of the specified search field in lieu of, or prior to, examining bit slices one at a time. Optimal subfield length is determined for both fixed-size and variable-size bit groupings and the corresponding reduction in search time is quantified. The results are extended to rank-based selection where the jth largest or smallest value in a given field of a selected subset of words is to be identified. We conclude that significant reduction in the number of search cycles is possible in most practical extreme-value search and selection problems.

S. Kawahito et al. (1988) presented multiplier designs using the binary-tree reduction feature of certain highly redundant radix-2 representations, along with multiple-valued current-mode circuit techniques, and shown them to compare favorably to those based on less redundant binary signed-digit and carry-save numbers. We point out that these representation schemes, and their potential advantages, have been discussed in earlier publications and that a more general view of the parallel-carries addition process exploited in these multipliers leads to other potentially useful representations. The authors reply is also given.

Approximate Chinese-remainder-theorem decoding of residue numbers is a useful operation in residue arithmetic. The decoding yields an approximation to (X mod M)M, in the range [0, 1), where X is the input number and M is the product of all moduli. We show the error distribution and worst-case errors for both the truncation and rounding versions of the approximate decoding procedure. We also prove that, contrary to some published accounts, limiting the dynamic range is ineffective in reducing the maximal error.>

A special carry-free circuit for the evaluation of conditions of the type A+B=K is proposed by Cortadella and Llaberia (1992), and its usefulness for reducing the negative effects of conditional branches in pipelined architectures is noted. It is shown that the same advantages are offered by another equally simple circuit based on carry-save redundant numbers and (3, 2)-counters. This alternative circuit has other potential applications and much of it may in fact be already present in some ALU's.>

Ordinary signed-digit (OSD) number representation systems have been defined for any radix r>or=3 with digit values ranging over the set (- alpha . . .,-1,0,1. . ., alpha ), where alpha is an arbitrary integer in the range r/20 and beta >0) explicitly. Zero detection, sign detection, and overflow handling are also treated in depth.>

A two-dimensional mesh of processing elements (PE's) with separable row and column buses (i.e., broadcast mechanisms for rows and columns that can be logically divided into a number of local buses through the use of PE-controlled switches) has been shown to be quite effective for semigroup computation, prefix computation, and a wide class of other computations that do not require excessive communication or data routing. For meshes with separable row/column buses, the authors show how semigroup and prefix computations can be performed with the same asymptotic time complexity without the provision of buses for every row and every column and discuss the VLSI implications of this new architecture.>

Hardware number radix converters may be required at the input and output interfaces of high-speed arithmetic processors implemented in VLSI. Systolic hardware realisation of the radix conversion process along with hardware implementation details are discussed in this paper. The main results are that it is always possible to accept one input digit in a continuous stream of k-digit operands on every clock tick and that the total conversion delay (from the acceptance of the first digit of an operand to the emergence of the first digit in the corresponding k′-digit result) is k + k′/b clock ticks, where b is a design tradeoff parameter affecting the cell complexity, intercell communication, and possibly the clock period in the systolic converter.

Unidirectional errors arise as a result of common VLSI failure modes and certain connection faults, particularly with serial data transmission. A totally ordered set of symbols to be encoded in an order-preserving manner for unidirectional error detection is considered. General order-preserving encoding and the special case of difference-preserving encoding, (when the value nu is encoded with its separate data part representing nu +b to facilitate arithmetic operations) are considered and optimal codes are devised for each case.>

Signed-digit (SD) number representation systems have been defined for any radix r>or=3 with digit values ranging over the set (- alpha , . . ., -1, 0, 1, . . ., alpha ), where alpha is an arbitrary integer in the range 1/2r>

Signed-digital number representation systems have been defined for any radix r>or=3 with digit values ranging over the set (- alpha ,...,-1,0,1,..., alpha ), where alpha is an arbitrary integer in the range r/2>

Although a state encoding scheme for systolic counters has been presented earlier, several important practical problems such as zero test, sign detection, overflow, underflow, and modulo-n (cyclic) counting have not been dealt with adequately. In this paper, design principles for unary and binary systolic up/down counters are presented. The unary counters, which are attractive when dealing with relatively small counts, are based on the systolic stack concept. The binary counters use conventional binary number representation, with several tags associated with each bit position. The binary counter design presented can be generalized to counters with higher-radix state encodings.

We show that except for a few special cases allowing smaller tables, the lookup table used for achieving k digits of convergence after the initial multiplication (or for obtaining the approximate reciprocal of the divisor with k − 1 digits of accuracy) in iterative division methods must have at least (r−-l) rk words of k + I digits, r being the number representation base. In the important special case of r = 2 with k ≥5, a 2k-word table with k-bit entries can be used, since the initial digit is always 1. It is also shown that a table of this optimal size can always be constructed. The special cases corresponding to r = 3 with k = 1, and r = 2 with k ≤ 4, allow smaller tables than the general case and are thus handled separately.

A data structure is proposed which enables efficient determination of family relations of common interest with the minimum amount of information on each individual. The problem of updating information due to births, deaths, marriages and divorces is considered. Algorithms for determining the immediate relatives of each individual are given and a framework is established for writing procedures to determine other relatives.

Arithmetic error codes constitute a class of error codes that are preserved during most arithmetic operations. Effectiveness studies for arithmetic error codes have shown their value for concurrent detection of faults in arithmetic processors, data transmission subsystems, and main storage units in fault-tolerant computers. In this paper, it is shown that the same class of codes is also quite effective for detecting storage errors in both shift-register and magnetic-recording mass memories. Some of the results are more general and deal with properties of arithmetic error codes in detecting unidirectional failures. For example, it is shown that a low-cost arithmetic error code with check modulus A = 2N - 1 can detect any unidirectional failure which affects fewer than N bits. The use of arithmetic error codes for checking of mass memories is further justified since it eliminates the need for hard-core or self-checking code translators and reduces the number of different types of code checkers required.

Recent advances in computer technology have made the design of large and very flexible associative processors possible. Such systems are extremely complex and must be adequately protected against failures if they are to be used in critical application areas such as air traffic control or for performing control functions in fault-tolerant computers. This paper summarizes the results of a study which has indicated the techniques that are applicable in the design of fault tolerant associative processors. Associative processors are divided into four classes of fully parallel, bit-serial, word-serial, and block-oriented systems. A technique for modularizing the design of an associative processor is given. The detection of errors within modules is discussed for the four classes mentioned above. Several schemes for reconfiguration are discussed which allow us to establish an appropriate inter-communication pattern after replacing the faulty module by a spare. The design of a fault-tolerant associative processor, which uses some of the techniques discussed previously, is presented.

A stochastic sequential machine model is employed to investigate some of the problems concerning the reliability of sequential machines. Two methods, using the notions of entropy for stochastic automata and principal entries in their transition matrices, are used and compared for reliability estimates. The problem of synthesizing automata of given known reliability through replication and voting is also examined.