An advanced spare-connection scheme for K-out-of-N redundancy is proposed for constructing fault-tolerant ring- or toroidal mesh-connected processing-node arrays able to enhance emulation of binary hypercubes by using bypass networks. With this scheme, a component redundancy configuration for a base array with a fixed number of primary nodes, such as that for 8-node ring or 32-node toroidal mesh, can be constructed by using bypass links with a segmented bus structure to selectively connect the primary nodes to a spare node in parallel. These bypass links are allocated to the primary nodes by graph-node coloring with a minimum inter-node distance of three in order to use the bypass links as the hypercube connections as well as to attain strong fault tolerance for reconfiguring the base array with the primary network topology. An extended redundancy configuration for a large fault-tolerant array can be constructed by connecting the component configurations by using external switches of a hub type provided at the bus nodes of the bypass links. This configuration has a network topology of the parallel star-connections of sub-hypercubes whose diameter is smaller than that of the regular hypercube.

First, we give a graph-theoretic formalization for the spare assignment problems for two cases of reconfiguring NN mesh-connected processor arrays with spares on a diagonal line in the array or two orthogonal lines at the edges of the array. Second, we discuss the problems for minimizing the numbers of "dangerous processors" for the cases. Here, a dangerous processor is a nonfaulty one for which there remains no spare processor to be assigned if it becomes faulty, without modifying the spare assignments to other faulty processors. The problem for the latter case, originally presented by Melhem, has already been discussed and solved by the O(N²) algorithm in [3], but it's procedure is very complicated. Using the above graph-theoretic formalization, we give efficient plain algorithms for minimizing the numbers of dangerous processors by which the problems for both the cases can be solved in O(N) time.

An optimal allocation model for the sub-processing-element (sub-PE) level redundancy is developed, which is solved by the genetic algorithms. In the allocation model, the average defect density D and the parameter δ are also considered in order to accurately analyze the element yield, where δ is defined as the ratio of the support circuit area to the total area of a PE. When the PE's area is imposed on the constraint, the optimal solutions of the model with different D and δ are calculated. The simulation results indicate that, for any fixed average defect density D, both the number of the optimal redundant sub-circuit added into a PE and the PE's yield decrease as δ increases. Moreover, for any fixed parameter δ, the number of the optimal redundant sub-circuit increases, while the optimal yield of the PE decreases, as D increases.

Available statistical skew models are too conservative in estimating the expected clock skew of a well-balanced H-tree. New closed form expressions are presented for accurately estimating the expected values and the variances of both the clock skew and the largest clock delay of a well-balanced H-tree. Based on the new model, clock period optimizations of wafer scale H-tree clock network are investigated under both conventional clocking mode and pipelined clocking mode. It is found that when the conventional clocking mode is used, clock period optimization of wafer scale H-tree is reduced to the minimization of expected largest clock delay under both area restriction and power restriction. On the other hand, when the pipelined clocking mode is considered, the optimization is reduced to the minimization of expected clock skew under power restriction. The results obtained in this paper are very useful in the optimization design of wafer scale H-tree clock distribution networks.

We examine diagnosis of processor array systems formed as two-dimensional grids, with boundaries, and either four or eight neighbors for each interior processor. We employ a parallel test schedule. Neighboring processors test each other and report the results. Our diagnostic objective is to find a fault-free processor or set of processors. The system may then be sequentially diagnosed by repairing those processors tested faulty according to the identified fault-free set. We establish an upper bound on the maximum number of faults that can be sustained without invalidating the test results under worst case conditions. We give test schedules and diagnostic algorithms that meet the upper bound as far as the highest order term. We compare these near optimal diagnostic algorithms to alternative algorithms--both new and already in the literature.

In this paper we propose a MIN (Multistage Interconnection Network) whose performance in the faulty case degrades as gracefully as possible. We focus on a two-dilated baseline network as a sort of MIN. The link connection pattern in our MIN is determined so that all the available paths established between an input terminal and an output terminal via an identical input of a SE (Switching Element) in some stage will never pass through an identical SE in the next stage. Extra links are useful in improving the performance of the MIN and do not complicate the routing scheme. There is no difference between our MIN and others constructed from a baseline network with regard to numbers of links and cross points in all SEs. The theoretical computation and simulation-based study show that our MIN is superior to others in performance, especially in robustness against concentrated SE faults in an identical stage.

In this paper, we propose the evolutionary algorithm-based reasoning system and its design methodology. In the proposed design methodology, reasoning rules behind the past cases in each task (in each case database) are extracted through genetic algorithms and are expressed as truth tables (we call them 'evolved truth tables'). Circuits for the reasoning systems are synthesized from the evolved truth tables. Parallelism in each task can be embedded directly in the circuits by the hardware implementation of the evolved truth tables, so that the high speed reasoning system with small or acceptable hardware size is achieved. We developed a prototype system using Xilinx Virtex FPGA chips and applied it to the gene boundary reasoning (GBR) and English pronunciation reasoning (EPR), which are very important practical tasks in the genome science and language processing field, respectively. The GBR and the EPR prototype systems are evaluated in terms of the reasoning accuracy, circuit size, and processing speed, and compared with the conventional approaches in the parallel AI and the artificial neural networks. Fault injection experiments are also carried out using the prototype system, and its high fault-tolerance, or graceful degradation against defective circuits that suits to the hardware implementation using wafer scale LSIs is demonstrated.

This paper describes a new architecture-based microprocessor, a dynamically programmable parallel processor (DPPP), that consists of large numbers of simplified ALUs (sALU) as processing blocks. All sALUs are interconnected via a code division multiple-access bus interface that provides complete routing flexibility by establishing connections virtually through code-matching instead of physical wires. This feature is utilized further to achieve high parallelism and fault tolerance. High fault tolerance is realized without the limitations of conventional fabrication-based techniques nor providing spare elements. Another feature of the DPPP is its simple programmability, as it can be configured by compiling numerical formula input using the provided user auto-program interface. A prototype chip based on the proposed architecture has been implemented on a 4.5 mm 4.5 mm chip using 0.6 µm CMOS process.

We propose the kernel-based pattern recognition hardware and its design methodology using the genetic algorithm. In the proposed design methodology, pattern data are transformed into the truth tables and the truth tables are evolved to represent kernels in the discrimination functions for pattern recognition. The evolved truth tables are then synthesized to logic circuits. Because of this data direct implementation approach, no floating point numerical circuits are required and the intrinsic parallelism in the pattern data set is embedded into the circuits. Consequently, high speed recognition systems can be realized with acceptable small circuit size. We have applied this methodology to the image recognition and the sonar spectrum recognition tasks, and implemented them onto the newly developed FPGA-based reconfigurable pattern recognition board. The developed system demonstrates higher recognition accuracy and much faster processing speed than the conventional approaches.

We present an algorithm for computing the Minkowski sum of two surfaces of revolution with parallel axes, each defined as a rotational sweep of a slope-monotone closed curve. This result is an extension of that due to Sugihara et al., where the Minkowski sum for two slope-monotone closed curves in the plane is defined.

There exist some results showing that quantum communications are more powerful than classical communications. Moreover, although quantum entangled states do not give extra information, by using prior entanglement the quantum communication complexity of some functions is less than the classical communication complexity. The communications with prior entanglement can be regarded as a type of public coin models. In this paper, we investigate quantum communications for multi-party with prior entanglement, and show that there exists a generalized inner product function for k-party such that the quantum communication complexity is at most k bits, but the classical communication complexity needs at least 3k/2 bits. Moreover, we also provide a generalized form of prior entanglements that is effective in order to compute some type of Boolean functions.

Distributed domino effect-free checkpointing techniques can be divided into two categories: coordinated and communication-induced checkpointing. The former is inappropriate for mobile computing systems because it either forces every mobile host to take a new checkpoint or blocks the underlying computation during the checkpointing process. The latter makes every mobile host take the checkpoint independently. However, each mobile host may need to store multiple local checkpoints in stable storage. This investigation presents a novel three level synchronous checkpointing algorithm that combines the advantages of above two methods for mobile computing systems. The algorithm utilizes pre-synchronization, quasi-synchronization, and post-synchronization techniques and has the following merits: (1) Consistent global checkpoints can be ensured. (2) No mobile host is blocked during checkpointing. (3) Only twice the checkpoint size is required. (4) Power consumption is low. (5) The disconnection problem of mobile hosts can be resolved. (6) Very few mobile hosts in doze mode are disturbed. (7) It is simple and easy to implement. The proposed algorithm's numerical results are also provided in this work for comparison. The comparison reveals that our algorithm outperforms other algorithms in terms of checkpoint overhead, maintained checkpoints, power consumption, and disturbed mobile hosts.

Our aim is to develop an intuitive and effective sound retrieval method for non-expert users. Such a retrieval method should be developed to accommodate a human's perceptual features. We therefore first conducted an experiment to clarify how people represent sound. A participant listens to one sound stimulus and then conveys the sound to a partner. The results indicated that people used mostly verbal description categorized in three groups: the sound itself, the sound's situation, and the sound's impression. Based on these results, we propose three types of keywords: onomatopoeia, sound source, and adjective, which are typical keywords of the above three groups of sound description, for sound retrieval. This retrieval method was implemented for a sound database. Our method can increase the varieties of sounds able to be retrieved and allow users to intuitively search sounds because users can retrieve sounds by using keywords that are most natural to them.

In this letter, we propose a grammatical structure of the finite state network (FSN) for the recognition of Korean price sentences. It is implemented by arranging the nodes and the arcs of the FSN. Two kinds of grammatical structure are presented. Both are designed according to the grammar constraints of Korean price sentences. The grammar constraints of Korean price sentences are similar to those of English price sentences; the unit is placed after the digit; several digits form a basic group; the basic group appears recursively followed by meta-units, etc. Speaker-independent recognition experiments were conducted, and the results of the FSN's with proposed grammatical structures were compared with those of the FSN without grammatical structure.