There exist two basic methods to interconnect n processors under the condition where the relation among each processor and its directly connected neighboring processors is perfectly regular: 1-dimensional and multi-dimensional topological connections. This paper treats three types of general topological connections, and investigates the optimal connections with a smaller number of data transmission steps. It is concluded that two kinds of them have a smaller number of data transmission steps and the smallest number of data transmission steps depends on the number n.

Reliability of single-loop networks can be improved using double loops: forward loops advancing to the neighboring node and backward loops skipping by a certain distance. In this type of double loop networks, when some nodes break down, threre exist possibilities that a message can not be transmitted to some nodes, and some other messages must take a roundabout route. Then, the delay may happen in data transmission. This phenomenon depends on the configulation of the network and the fault location. This paper investigates, first, the number of available communications, and next the maximum distance between any computer pair when two or more computers break down in the network. Finally routing algorithm to find a route where a message can be transmitted to the destination node is presented.

A multiple instruction stream-multiple data stream (MIMD) computer is a parallel computer consisting of a large number of identical processing elements. The essential feature that distinguishes one MIMD computer family from another is the interconnection network. In this paper, 2 representative types of interconnection networks are dealt with the chordal ring network and the mesh connected network. A family of regular graphs of degree 3, called chordal rings is presented as a possible candidate for the implementation of a distributed system and for fault-tolerant architectures. The symmetry of graphs makes it possible to determine message routing by using a simple distributed algorithm. Another candidate having the same property is the mesh connected networks. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the bit permute complement (BPC) class of permutations. The class of BPC permutations includes many of the frequently occurring permutations such as bit reversal, bit shuffle, bit complement, matrix transpose, etc. In this paper, we evaluate the abilities of the above networks to realize BPC permutations. In this paper, we, first, develop algorithms required 2 token storage registers in each node to realize an arbitrary BPC permutaion in both chordal ring networks and mesh connected networks. We next evaluate the ability to realize BPC permutations in these networks of an arbitrary size by estimating the number of required routing steps.

In this papers, we will discuss the different percentages of embedding certain subsystems successfully into a n-cube according to the fault model used. We will discuss two fault models: the first one assumes that, in a faulty node, the computational function of the node is lost while the communication function of the faulty node remains intact, and, in the second, the communication function is also lost. In this paper, 2 types of fault tolerable subsystem embedding schemes will be introduced. The first one embeds a complete binary tree into a n-cube with faulty nodes, and the second embeds two (n-1)-subcubes whose total number of faulty nodes is less than half the number of nodes. These schemes are divided into 4 types based on the above two models. First, we will discuss how different the successful percentages of embedding are for 2 of the different types of embedded binary trees that are based on the above two models. Then, we will analyze the possibility that the component nodes of an embedded binary tree can communicate via the faulty nodes that are located in the embedded binary tree. In the embedding process, each faulty node was replaced with a nonfaulty node that was located on another (n-1)-subcube and at a Hamming distance of 1 from the faulty node. The number of faults that led to the successful percentage of embedding will be presented as an upper bound. Next, we will discuss how different the successful embedding percentages are for the 2 types of irregular (n-1)-subcubes based on the two models; that is, if 2n-2+1 or more of the nonfaulty nodes in both of the (n-1)-subcubes can communicate or not via faulty nodes. Here also, the number of faults that led to a successful embedding percentage will be presented as a critical value.

Two approaches are known for enhancing the fault tolerance of systolic arrays through reconfiguration. They are different in the bypassing function. One leads to an easier reconfiguration procedure, whereas the other provides better utilization of nonfaulty cells. It seems that both approaches may have the same probability of successful reconfiguration for practical failure rates of cells but not for all other failure rates. In this paper, we investigate this supposition, and conclude that the two approaches perform equally well for all practical cell failure rates and array sizes.

The numbers of passes required to realize permutations in the class of Bit Permute-Complement (BPC) permutations such as Bit-Reversal, Matrix-Transpose, Perfect-Shuffle, and Bit-Complement permutations in delta and extrastage delta networks are obtained. The influence of the faults in the networks on the number of passes required for them is also investigated. First, how different are the time complexities required when using a route decision algorithm and an improved algorithm having taken some inherent properties into consideration is discussed and solved by obtaining real data. Next, how many passes are required to realize BPC permutations in delta networks when faults are present and when not present, and how many passes can be reduced by using an extra-stage are discussed continuously. As an important criterion for the fault tolerance of multistage interconnecting networks, Dynamic Full Access (DFA) has been suggested. A weakness of DFA as applied to BPC permutations is that the ability to realize such permutations in a finite number of passes can not be always measured by a criterion of DFA, because of the uneven distributions of paths required for the permutations. This reason suggests the ability to realize such permutations must be investigated from the different angle.

Reliability of single-loop networks can be improved using double loops: forward loops advancing to the neighboring node and backward loops skipping by a certain distance. In this type of double loop networks, when some nodes break down, there exist possibilities that a message can not be transmitted to some nodes and many messages concentrate on some specific nodes to take a roundabout route. Then, the delay may happen in date transmission. These phenomena depend on the situation of faulty nodes. This paper, first, presents a routing algorithm to find a route where a message can be transmitted to the destination node when a multi-node failure arises. Next, the upper bound of transmission steps required to transmit n packets in parallel from respective starting nodes to respective destination nodes is investigated.

In this paper we estimate the number of permutations realizable in fault-tolerant multistage interconnection networks designed to tolerate faults on any switching element. The Parallel Omega network and the INDRA network are representative types of fault-tolerate multistage interconnection networks designed to tolerate a single fault. In order to evaluate the enhancement in the function of network by preparing the hardware redundancy for fault-tolerance, we estimate the number of permutations realizable in fault-tolerant networks. This result enables us to set up a standard to evaluate the hardware redundancy required to tolerate multifaults from the viewpoint of the enhancement of network function. This paper concludes that in the case where the number of inputs is up to 32 the increase ratio of the number of realizable permutations is no more than 1/0.73 even if the tolerance to multifaults is prepared instead of the tolerance to a single fault.

Some properties of an optimum set of paths which pass all arcs of a graph are presented. It is shown that the unique existence of the optimum set depends on the configuration of a graph. The set is of use as the minimum set of test cases to the path test.

In this paper we discuss a fall-safe of an asynchronous sequential machine. Though several methods have already been reported on the realization of the fail-safe circuit, we can find advantages of the method explained in this paper in the following points: First the state transition function in the form of an ON-SET function, second the consideration for a masked-fault. In order to realize the state transition function only by ON-SET functions, the delay circuit is inserted into input circuit and the input for one state transition is re-formed into two parts. It is reported that a guarantee against a masked-fault is easily attained because of ON-SET realization. In the method described in this paper the state assignment of the input and of the excitation circuit adopt the constant weight equidistant codes and the circuit is guaranteed to be rece-free. By this method the circuit can be operated with the guaranty of a fail-safe even if masked-faults exist.

This paper presents an optimum design method of reliable networks. This paper, first, discusses several design methods for undirected graphs. It is shown that one new method of them gives graphs with the minimum diameter in a certain domain. In order to obtain optimum graph when the number of nodes and degree are given, this paper next discusses a method to obtain modified graphs with larger connectivity and also with the minimum diameter from known graphs which have diameter 1 over the minimum.

Reliability of single-loop networks can be improved using double loops: foward loops advancing to the neighboring node and backward loops hopping by a certain distance. This paper investigates the number of live transmission lines when two computers break in the network, and discusses the tolerant ability to the failures.

There exists a method to simultaneously obtain test paths and test data in conformity with the structure and path conditions of objective program. This paper discusses a method to simultaneously obtain a set of test paths of satisfying a desired coverage rate and test data of testing the test paths.