This paper considers a model of an n-dimensional toroidal rectangular interconnection network with the virtual cut-through routing. The network performance as a function of network parameters and the message load is analyzed. An exact analytical expression for the saturation point and the latency as a function of message generation rate under the mean field theory approximation have been obtained. The saturation point has been found proportional to the number of the torus dimensions and inversely proportional to the message length and to the length of the path from the source to the destination. The transition to saturation state is a second-order(continuous) phase transition with a critical exponent equal to 1.

An analytical model of a network with 2-dim torus topology and virtual cut-through routing has been considered in order to find out and analyze certain relationships between network parameters, load and performance. An exact expression for the saturation point (message generation rate at which network saturates) and expressions for the latency as a function of the message generation rate under the assumptions of the mean field theory have been obtained. It has been found that the saturation point is inversely proportional to the message length and to the distance between the source and destination. The theoretical results are in a good agreement with small-scale simulation experiments.

Theoretical models and numerical results for performance of the computer interconnection networks with heterogeneous activity are presented. The networks are modeled as a ring or as 2-dim toroidal square lattice of nodes with local processors with two or, respectively, four output ports/buffers. The processors generate messages with two different rates, λ1or λ2, per clock cycle and per output buffer, depending on the intensity of the flow of the arriving messages. The average queue lengths and average latencies are obtained. The model of independent queues and the Jackson theorem are not applicable for this type of networks. It is shown that the networks undergo the phase transition of the second order with non-trivial critical exponents.

A simple network model with torus topology and the virtual cut-through routing have been considered in order to find out and analyze certain relationships that can be used as a starting point for a deeper theoretical analysis and further research. An expression for the saturation point (message generation rate at which network saturates) and approximate expressions for the latency as a function of the message generation rate have been obtained. Simulation experiments for various values of network parameters (mesh size, message path length, and message length) have been performed. It is found that if the mesh linear dimension is at least twice as large as the message path length (the distance from source to destination) the network behavior (latency and saturation point) does not depend on the mesh size. Both theoretical and empirical results show that the saturation point is inversely proportional to the message length.

It is shown how information contained in the pair-wise correlations between atoms of a gas can be used to convert completely heat taken from a thermostat into mechanical work in a process of relaxation of the system to its thermal equilibrium state. Both classical correlations and quantum correlations (entanglement) are considered. The amount of heat converted into work is proportional to the entropy defect of the initial state of the system. The equivalence relation between information and work is explicitly demonstrated for the case of two-particle correlations. The amount of work obtained per particle is twice as large in the case of entanglement as in the case of classical correlations.

The problem of preventing deadlocks and livelocks in computer communication networks, in particular, those with wormhole routing, is considered. The method to prevent deadlocks is to prohibit certain turns (i.e., the use of certain pairs of connected edges) in the routing process, in such a way that eliminates all cycles in the graph. We propose a new algorithm that constructs a minimal (irreducible) set of turns that breaks all cycles and preserves connectivity of the graph. The algorithm is tree-free and is considerably simpler than earlier cycle-breaking algorithms. We prove its properties and present lower and upper bounds for minimum cardinalities of cycle-breaking connectivity preserving sets for graphs of general topology as well as for planar graphs. In particular, the algorithm guarantees that not more than 1/3 of all turns in the network become prohibited. We also present experimental results on the fraction of prohibited turns, the distance dilation, as well as on the message delivery times and saturation loads for the proposed algorithm in comparison with known tree-based algorithms. The proposed algorithm outperforms substantially the tree-based algorithms in all characteristics considered.

In this paper we consider the problem of constructing minimal cycle-breaking sets of turns for graphs that model communication networks, as a method to prevent deadlocks in the networks. We present a new cycle-breaking algorithm called simple cycle-breaking or SCB algorithm that is considerably simpler than earlier algorithms. The SCB algorithm guarantees that the fraction of prohibited turns does not exceed 1/3. Experimental simulation results for the SCB algorithm are shown.

A multiprocessor networks modeled as a ring and as a 2D toroidal lattice of nodes are considered. Each node generates messages with probability lambda per clock cycle per output port. Once an output buffer is not empty, the output port sends out exactly one message every clock cycle. We derive analytical expressions for the queue length distribution, the average number of messages in buffers, and the latency. The network experiences a phase transition from equilibrium to the saturation regime, and the critical exponent is equal to 1. Simulations demonstrate an excellent agreement with theoretical predictions and validate the assumption of independent queues. A model of a ring network where the message generating rate depends on the intensity of the incoming messages is studied by simulation. The results show the emergence of dependences between queues in closely located nodes, and changes in the values of the critical load and critical exponent.

Since reversible computing requires preservation of all information throughout the entire computational process, it implies that all the errors that appear as a result of the interaction of the information-carrying system with uncontrolled degrees of freedom must be corrected. This can only be done at the expense of an increase in the entropy of the environment corresponding to the dissipation of the "noisy" part of the energy of the system in the form of heat. This paper gives an expression of that energy in terms of the effective noise temperature, and calculates the relationship between the energy dissipation rate and the rate of computation

A subset C of vertices in an undirected graph G=(V,E) is called a 1-identifying code if the sets I(v)={u/spl isin/C:d(u,v)/spl les/1}, v/spl isin/V, are nonempty and no two of them are the same set. It is natural to consider classes of codes that retain the identification property under various conditions, e.g., when the sets I(v) are possibly slightly corrupted. We consider two such classes of robust codes. We also consider dynamic identifying codes, i.e., walks in G whose vertices form an identifying code in G.

Ethernet networks rely on the so-called spanning tree protocol (IEEE 802.1d) in order to break cycles, thereby avoiding the possibility of infinitely circulating packets and deadlocks. This protocol imposes a severe penalty on the performance and scalability of large gigabit Ethernet backbones, since it makes inefficient use of expensive fibers and may lead to bottlenecks. We propose a significantly more scalable cycle-breaking approach, based on the novel theory of turn-prohibition. Specifically, we introduce, analyze and evaluate a new algorithm, called tree-based turn-prohibition (TBTP). We show that this polynomial-time algorithm maintains backward-compatibility with the IEEE 802.1d standard and never prohibits more than 1/2 of the turns in the network, for any given graph and any given spanning tree. Through extensive simulations on a variety of graph topologies, we show that it can lead to an order of magnitude improvement over the spanning tree protocol with respect to throughput and end-of-end delay metrics. In addition, we propose and evaluate heuristics to determine the replacement order of legacy switches that results in the fastest performance improvement.

We consider the problem of data reconciliation, which we model as two separate multisets of data that must be reconciled with minimum communication. Under this model, we show that the problem of reconciliation is equivalent to a variant of the graph coloring problem and provide consequent upper and lower bounds on the communication complexity of reconciliation. Further, we show by means of an explicit construction that the problem of reconciliation is, under certain general conditions, equivalent to the problem of finding error-correcting codes for a general class of errors. Under this equivalence, reconciling with little communication is linked to codes with large size, and vice versa. We show analogous results for the problem of multiset verification, in which we wish to determine whether two multisets are equal using minimum communication. As a result, a wide body of literature in coding theory may be applied to the problems of reconciliation and verification.

We investigate a new class of codes for the optimal covering of vertices in an undirected graph G such that any vertex in G can be uniquely identified by examining the vertices that cover it. We define a ball of radius t centered on a vertex /spl upsi/ to be the set of vertices in G that are at distance at most t from /spl upsi/. The vertex /spl upsi/ is then said to cover itself and every other vertex in the ball with center /spl upsi/. Our formal problem statement is as follows: given an undirected graph G and an integer t/spl ges/1, find a (minimal) set C of vertices such that every vertex in G belongs to a unique set of balls of radius t centered at the vertices in C. The set of vertices thus obtained constitutes a code for vertex identification. We first develop topology-independent bounds on the size of C. We then develop methods for constructing C for several specific topologies such as binary cubes, nonbinary cubes, and trees. We also describe the identification of sets of vertices using covering codes that uniquely identify single vertices. We develop methods for constructing optimal topologies that yield identifying codes with a minimum number of codewords. Finally, we describe an application of the theory developed in this paper to fault diagnosis of multiprocessor systems.

Proposes a new approach for identification of faulty processing elements based on an analysis of the compressed test response of the system. The test response is compressed first in space and then in time, and faulty processing elements are identified by hard decision decoding of the corresponding space-time signature. The approach results in considerable savings in hardware required for diagnostics.>

An analysis and design of a pseudorandom pattern generator, (PRPG), based on a linear recurrence, for built-in self-test (BIST) boundary scan design is presented. The authors present for the case when r>or=s, a design of an s-stage PRPG capable of producing 2/sup s/-1 distinct r-bit patterns within 2/sup s/-1 clock pulses independent of the hardware realization of the PRPG. For the case when r>

A novel approach to the identification of a faulty processing element, based on an analysis of the compressed response of the system, is proposed. The test response is compressed first in space and then in time, and a faulty processing element is identified by a hard-decision decoding of the corresponding space-time signature. The overhead analysis and the solution for the hardware minimization problem are presented for several important classes of systems. The proposed method results in considerable hardware savings.>

Minimum distance decoding (MDD) for a general error-correcting linear code is a hard computational problem that recently has been shown to beNP-hard. The complexity of known decoding algorithms is determined by\min (2^{k},2^{n-k}), wherenis the code length andkis the number of information digits. Two new algorithms are suggested that reduce substantially the complexity of MDD. The algorithms use a new concept of zero neighbors--a special set of codewords. Only these codewords (which can be computed in advance) should be stored and used in the decoding procedure. The number of zero neighbors is shown to be very small compared with\min (2^{k},2^{n-k})forn \gg 1and a wide range of code ratesR = k/n. For example, forR \approx 0.5this number grows approximately as a square root of the number of codewords.