In this letter, we consider one-to-all broadcast on distributed memory parallel computers based on message-passing, such as cluster of WSs or PCs. We present an efficient broadcast algorithm, called overlapped-two-phase broadcast (O2PB), that is an enhanced version of two-phase broadcast (2PB). The O2PB algorithm is compared with other algorithms, such as linear broadcast, tree broadcast and 2PB algorithms. According to our theoretical and experimental results, when the size of message to be broadcasted is large, the O2PB algorithm is fastest among all the algorithms. The O2PB algorithm is approximately 20% faster than the 2PB algorithm.

This paper considers a reconfiguration problem on a processor array model based on single-and-half-track switches, which is proposed for a fault tolerance technique at the fabrication time. The focus of this paper is to achieve the optimal reconfigurability, which means that whenever there exists a solution for successful reconfiguration, the designed method can find the solution. The paper consists of two parts. In the first part, we show two essential constraints that have been assumed in most of the previous studies, and make four reconfiguration classes that differ in the assumed essential constraints. Then, we present some inclusion relations among the four reconfiguration classes. As a result, it becomes clear that the most restrictive class including most of the previous methods never achieves the truly optimal reconfigurability. In the second part, we present a reconfiguration method based on sequential routing (RMSR). Although the worst-case time complexity of the RMSR is exponential in the number of processing elements, the reconfigurability of the RMSR is optimal within the most restrictive reconfiguration class. The effectiveness of the RMSR is shown by a computer simulation.

This paper describes the relation between the structure and the capability on mesh-connected computers with orthogonal broadcasting. It is shown that algorithms of maximum finding for the two-way communication model can be performed on the one-way communication model without increasing the time complexity.

Learning algorithms for Vector Quantization (VQ) are categorized into two types: batch learning and incremental learning. Incremental learning is more useful than batch learning, because, unlike batch learning, incremental learning can be performed either on-line or off-line. In this paper, we develop effective incremental learning methods by using Stochastic Relaxation (SR) techniques, which have been developed for batch learning. It has been shown that, for batch learning, the SR techniques can provide good global optimization without greatly increasing the computational cost. We empirically investigates the effective implementation of SR for incremental learning. Specifically, we consider five types of SR methods: ISR1, ISR2, ISR3, WSR1 and WSR2. ISRs and WSRs add noise input and weight vectors, respectively. The difference among them is when the perturbed input or weight vectors are used in learning. These SR methods are applied to three types of incremental learning: K-means, Neural-Gas (NG) and Kohonen's Self-Organizing Mapping (SOM). We evaluate comprehensively these combinations in terms of accuracy and computation time. Our simulation results show that K-means with ISR3 is the most comprehensively effective among these combinations and is superior to the conventional NG method known as an excellent method.

This paper describes embeddings of chordal rings and pyramids into mesh-connected computers with multiple buses which have a bus on each row and each column, called MCCMBs. MCCMBs have two types of communication. The one is local communication, provided by local links, and the other is global communication, provided by buses. By efficiently combining the two types of communication, optimal or efficient embeddings are achieved. For a large set of chordal rings, optimal embeddings, whose expansion, load, dilation and congestion are 1, are given. For pyramids, an efficient embedding based on a two phase strategy is presented. The embedding balances dilation and congestion.

To enhance fabrication yield for processor arrays, many reconfiguration schemes for replacing faulty processing elements (PE's) with spare PE's have been proposed. An array grid model based on single-track switches is one of such models. For this model, some algorithms for reconfiguring processor arrays have been proposed. However, any algorithm which can reconfigure the array, whenever the array is reconfigurable, has not been proposed as yet. This paper describes reconfiguration methods of processor arrays with faulty PE's. The methods use indirect replacements for reconfiguring arrays. First, we introduce a concept of fatal fault pattern, which makes an array unreconfigurable. Then, for the reconfiguration method with fixed spare arrangement, efficient spare arrangements are given by evaluating the probability of an occurring fatal fault pattern. Furher, we present reconfiguration algorithm with relocating spare. In the algorithm, fatal fault patterns are eliminated by relocating spare. Computer simulations show that the method has good performance of reconfiguration.

This paper proposes homogeneous neural networks (HNNs), in which each neuron has identical weights. HNNs can realize shift-invariant associative memory, that is, HNNs can associate not only a memorized pattern but also its shifted ones. The transition property of HNNs is analyzed by the statistical method. We show the probability that each neuron outputs correctly and the error-correcting ability. Further, we show that HNNs cannot memorize over the number,, of patterns, where m is the number of neurons and k is the order of connections.

Neural networks for Vector Quantization (VQ) such as K-means, Neural-Gas (NG) network and Kohonen's Self-Organizing Map (SOM) have been proposed. K-means, which is a "hard-max" approach, converges very fast. The method, however, devotes itself to local search, and it easily falls into local minima. On the other hand, the NG and SOM methods, which are "soft-max" approaches, are good at the global search ability. Though NG and SOM exhibit better performance in coming close to the optimum than that of K-means, the methods converge slower than K-means. In order to the disadvantages that exist when K-means, NG and SOM are used individually, this paper proposes hybrid methods such as NG-K, SOM-K and SOM-NG. NG-K performs NG adaptation during short period of time early in the learning process, and then the method performs K-means adaptation in the rest of the process. SOM-K and SOM-NG are similar as NG-K. From numerical simulations including an image compression problem, NG-K and SOM-K exhibit better performance than other methods.

A reconfiguration method for processor array is proposed in this paper. In the method, genetic algorithm (GA) is used for searching effective spare arrangement, which leads to successful reconfiguration. The effectiveness of the method is demonstrated by computer simulations.

To enhance fabrication yield for processor arrays, many reconfiguration schemes for replacing faulty processing elements (PE's) with spare PE's have been proposed. An array grid model based on single-tracks is one of such models. For this model, some algorithms for reconfiguring processor arrays have been proposed. However, an algorithm which can reconfigure the array, whenever the array is reconfigurable, has not been proposed yet. This paper presents two types of methods for reconfiguration of processor arrays. Both the types use indirect replacements for reconfiguring arrays. For an indirect replacement of a faulty non-spare PE, one has a fixed direction, the other has at most four directions among which one is chosen. For the former, we consider the several distribution of spare PE's, and computer simulations show a tendency in the term of difference in the distributions. The latter algorithms consist of two phases. In the first phase, rows and columns of spare PE's are decided in accordance with a rule. Several rules for deciding spare PE's are considered in this paper. In the second phase, faulty non-spare PE's are replaced with healthy spare PE's. By simulations the performance of the algorithms are evaluated and a tendency is shown in the terms of difference in disposition of spare PE's.

It is known that homogeneous networks are ones which perform parallel algorithms, and the dynamics of neural networks are applied to practical problems including combinatorial optimization problems. Both homogeneous and neural networks are parallel networks, and are composed of Boolean elements. Although a large number of studies have been made on the applications of homogeneous threshold networks, little is known about the relation of the dynamics of these networks. In this paper, some results about the dynamics, used to find the lengths of periodic and transient sequences, as built by parallel networks including threshold and homogeneous networks are shown. First, we will show that for non–restricted parallel networks, threshold networks which permit only two elements to transit at each step, and homogeneous networks, it is possible to build periodic and transient sequences of almost any lengths. Further, it will be shown that it is possible for triangular threshold networks to build periodic and transient sequences with short lengths only. As well, homogeneous threshold networks also seem to build periodic and transient sequences with short lengths only. Specifically, we will show a sufficient condition for symmetric homogeneous threshold networks to have periodic sequences with the length 1.