武藤 佳恭

This paper presents performance comparisons of seven neural network models on traffic control problems in multistage interconnection networks. The decay term, three neuron models, and two heuristics were evaluated. The goal of the traffic control problems is to find conflict-free switching configurations with the maximum throughput. Our simulation results show that the hysteresis McCulloch-Pitts neuron model without the decay term and with two heuristics has the best performance. © 1993 IEEE

Toooloeical via-minimization (TVM) algorithms in two-layer channels based on the artificial neural network model are presented in this paper. TVM problems require not only assigning wires or nets between terminals without an intersection to one of two layers, but also a minimization of the number of vias, which are the single contacts of nets between two layers. The goal of our algorithms is to embed the maximum number of nets without an intersection. Two types of TVM problems are examined: split rectangular TVM (RTVM) problems and split circular TVM (CTVM) problems. Our algorithms require 3n processing elements for the n-net split RTVM problems, and 5n processing elements for the n-net split CTVM problems. The algorithms were verified by solving seven problems with 20 to 80 nets. The algorithms can be easily extended for more-than-two-layer problems. © 1993 IEEE

With the advancement of the silicon technology multi-layered VLSI circuits and PCBs (printed circuit boards) have been widely used. Based on the neural network model this paper presents the first parallel algorithm for multi-layer channel routing problems on the HVH model which minimize wiring areas in VLSI circuits and PCBs. The algorithm requires n × m × 2s processing elements for the n-net-m-track-3s-layer problem. The algorithm not only runs on a sequential machine but also on a parallel machine with maximally n × m × 2s processors. The algorithm is verified by solving seven benchmark problems where it finds better solutions than the existing algorithms for 6-12-layer problems in nearly constant time on a parallel machine. © 1993.

A parallel algorithm based on an artificial neural network model for broadcast scheduling problems in packet radio networks is presented. The algorithm requires n x m processing elements for an n-node-MSlot radio network problem. The algorithm is verified by simulating 13 different networks. © 1993 IEEE.

A parallel algorithm for finding Ramsey numbers is presented where analog/digital CMOS circuits for the hysteresis McCulloch-Pitts binary neuron are described. The hysteresis McCulloch-Pitts binary neuron model is used in order to suppress the oscillatory behaviors of neural dynamics so that the convergence time is shortened. The proposed algorithm using the hysteresis McCulloch-Pitts binary neuron found five Ramsey numbers. The analog CMOS sigmoid circuit with variable gain controls has been fabricated and tested using the SAC data acquisition board interfaced with a TMS 32010 processor. Hysteresis can be implemented by the positive feedback in the fabricated CMOS analog circuit. © 1992 Kluwer Academic Publishers.

Neural network parallel computing for balanced incomplete block design (BIBD) problems is presented in this paper. A design in which all the blocks contain the same number of varieties, and all the varieties occur in the same number of blocks, is called a block design. A block is said to be incomplete if it does not contain all the varieties. If a design is balanced, we call it a balanced incomplete block design. BIBD problems are very important for solving problems in experimental design, material relating design, and coding theory. Two methods for BIBD problems have been proposed. One uses the notion of the finite fields, and the other uses the notion of the difference sets. In general, the conventional algorithms are only able to solve the problems that satisfy an affine plane or a finite projective plane. The proposed algorithm is able to solve BIBD problems regardless of the condition of an affine plane or a finite projective plane. The proposed algorithm requires [formula ommitted] processing elements, or artificial neurons to solve the [k, 1; v]-design problem in parallel. The proposed algorithm was verified by a large number of simulation runs. The simulation results demonstrated that the number of iteration steps for the system to converge to the solution increases slightly with the problem size. © 1992 IEEE

A parallel algorithm based on a neural network model for solving clique vertex-partition problems in arbitrary non-directed graphs is presented in this paper. A clique of a graph G = (V, E) with a set of vertices V and a set of edges E is a complete subgraph of G where any pair of vertices is connected with an edge. A clique vertex-partition problem of a graph G is to partition every vertex in V into a set of disjointed cliques of G. The clique vertex-partition problem with the minimum number of cliques in an arbitrary graph is known to be NP-complete. The algorithm requires nm processing elements for the n vertex m partition problem. A total of 10 different problems with 8 vertex to 300 vertex graphs were examined where the algorithm found a solution in nearly constant time. The circuit diagram of the neural network model is also proposed in this paper. © 1992 Taylor & Francis Ltd.

Several neuron models and artificial neural networks have been intensively studied since Mc Culloch and Pitts proposed the simplified neuron model in 1943. In this paper a generalized maximum neural network for parallel computing is introduced to solve the module orientation problem which belongs to the class of NP-complete problems. The goal of the module orientation problem in VLSI circuits or printed circuit boards is to minimize the total wire length by flipping each module with respect to its vertical and/or horizontal axes of symmetry. The circuit diagram of the generalized maximum neural network is shown and compared with the best known algorithm proposed by Libeskind-Hadas and Liu. The theoretical/empirical convergence analysis is discussed where a massive number of simulation runs were performed using more than one thousand instances. As far as we have observed the behavior of the proposed system, it converges within O(1) time regardless of the problem size and it performs better than the best known algorithm in terms of the solution quality and the computation time. © 1992 Taylor & Francis Ltd.

Summary form only given, as follows. A neural network model for traffic controls in multistage interconnection networks is discussed. The goal of the neural network model is to find conflict-free traffic flows to be transmitted among given I/O traffic demands in order to maximize the network throughput. The model requires n processing elements for the traffic control in an n × n multistage interconnection network. The model runs not only on a sequential machine but also on a parallel machine with maximally n processors. The model was verified by solving ten 32 × 32 network problems. 2 2

Summary form only given. A novel scheduling approach has been developed based on the deterministic Hopfield model for high-level synthesis. The model uses a four-dimensional neural network architecture to schedule the operations of a dataflow graph and maps them to specific functional units. Neural network-based scheduling is achieved by formulating the scheduling problem in terms of an energy function and by using the motion equation corresponding to the variation of energy. The algorithm searches the scheduling space in parallel and finds the optimal schedule. The main contribution of the present work is an efficient scheduling algorithm under time and resource constraints. The algorithm is based on moves in the scheduling space, which correspond to moves towards the equilibrium point (lowest energy state) in the dynamic system space. The neurons' motion equation is the heart of this guided movement mechanism and guarantees that the state of the system always converges to the lowest energy state.

A neural network parallel algorithm for finding Ramsey numbers in two-coloring is described. The Ramsey number R(r,b) is given by the smallest value of N, where all edges of a complete graph of (N-1) vertices are colored either red or blue, and red-colored and blue-colored subgraphs should not form any complete subgraph of r vertices and b vertices, respectively. A superimposed red-colored and blue-colored subgraph is called a Ramsey graph. The parallel algorithm, which is based on the hysteresis McCulloch-Pitts neural network, found five Ramsey numbers successfully. The neural network requires n(n-1) neurons for a Ramsey number of an n-vertex complete graph. The simulation result for the algorithm is so promising that it may be possible to find unknown Ramsey numbers.

This paper presents a new scheduling approach for high-level synthesis based on a deterministic modified Hopfield model. Our model uses a four dimensional neural network architecture to schedule the operations of a data flow graph (DFG) and maps them to specific functional units. Neural Network-based Scheduling (NNS) is achieved by formulating the scheduling problem in terms of an energy function and by using the motion equation corresponding to the variation of energy. The algorithm searches the scheduling space in parallel and finds the optimal schedule. The main contribution of this work is an efficient parallel scheduling algorithm under time and resource constraints appropriate for implementing on a parallel machine. The algorithm is based on moves in the scheduling space, which correspond to moves towards the equilibrium point (lowest energy state) in the dynamic system space. Neurons' motion equation is the core of this guided movement mechanism and guarantees that the state of the system always converges to the lowest energy state.

The purpose of this research was to develop a noise tolerant and faster processing approach for in vivo and in vitro spectrophotometric applications where distorted spectra are difficult to interpret quantitatively. A PC based multilayer neural network with a sigmoid activation function and a generalized delta learning rule was trained with a two component (protonated and unprotonated form) pH-dependent spectrum generated from microspectrophotometry of the vital dye neutral red (NR). The network makes use of the digitized absorption spectrum between 375 and 675 nm. The number of nodes in the input layer was determined by the required resolution. The number of output nodes determined the step size of the quantization value used to distinguish the input spectra (i.e. defined the number of distinct output steps). Mathematic analysis provided the conditions for which this network is guaranteed to converge. Simulation results showed that features of the input spectrum were successfully identified and stored in the weight matrix of the input and hidden layers. After convergent training with typical spectra, a calibration curve was constructed to interpret the output layer activity and therefore, predict interpolated pH values of unknown spectra. With its built-in redundant presentation, this approach needed no preprocessing procedures (baseline correction or intensive signal averaging) normally used in multicomponent analyses. The identification of unknown spectra with the activities of the output layer is a one step process using the convergent weight matrix. After learning from examples, real time applications can be accomplished without solving multiple linear equations as in the multiple linear regression method. This method can be generalized to pattern oriented sensory information processing and multi-sensor data fusion for quantitative measurement purposes. © 1992 Springer-Verlag.

Segmentation of the images obtained from magnetic resonance imaging (MRI) is an important step in the visualization of soft tissues in the human body. The multispectral nature of the MRI has been exploited in the past to obtain better performance in the segmentation process. The new emerging field of artificial neural networks promises to provide unique solutions for the pattern classification of medical images. In this preliminary study, we report the application of Hopfield neural network for the multispectral unsupervised classification of MR images. We have used winner-take-all neurons to obtain a crisp classification map using proton density-weighted and T2-weighted images in the head. The preliminary studies indicate that the number of iterations to reach “good” solutions was nearly constant with the number of clusters chosen for the problem. © 1992 IEEE

This paper presents the first algorithm for finding a knight's tour on the general chessboard where the proposed algorithm is based on neural network computing. In the knight's tour problem a knight must traverse all of the squares on an m × n chessboard but visit every square once and only once and return to the originated square where the knight moves in an L-shape route. © 1992.

High-order RNA structures are involved in regulating many biological processes; various algorithms have been designed to predict them. Experimental methods to probe such structures and to decipher the results are tedious. Artificial intelligence and the neural network approach can support the process of discovering RNA structures. Secondary structures of RNA molecules are probed by autoradiographing gels, separating end-labeled fragments generated by base-specific RNases. This process is performed in both conditions, denaturing (for sequencing purposes) and native. The resultant autoradiograms are scanned using line-detection techniques to identify the fragments by comparing the lines with those obtained by 'alkaline ladders'. The identified paired bases are treated by either one of two methods to find the foldings which are consistent with the RNases' 'cutting' rules. One exploits the maximum independent set algorithm; the other, the planarization algorithm. They require, respectively, n and n processing elements, where n is the number of base pairs. The state of the system usually converges to the near-optimum solution within about 500 iteration steps, where each processing element implements the McCulloch-Pitts binary neuron. Our simulator, based on the proposed algorithm, discovered a new structure in a sequence of 38 bases, which is more stable than that formerly proposed. © 1992. 2

A parallel algorithm based on the neural network model for finding a near-maximum clique is presented in this paper. A maximum clique of a graph G is a maximum complete subgraph of G where any two vertices are adjacent. The problem of finding a maximum clique is NP-complete. The parallel algorithm requires n processing elements for an n-vertex graph problem. The algorithm is verified by solving 230 different graph problems. The simulation results show that our computation time on a Macintosh IIfx is shorter than that of two better known algorithms on a Cray 2 and an IBM 3090 while the solution quality is similar. The algorithm solves a near-maximum clique problem in nearly constant time on a parallel machine with n processors. © 1992.

This paper presents a general purpose algorithm for solving the Unfriendly Beehive Game. The proposed algorithm will utilize an artificial neural network to solve the problem. The neural network will use a simple partial differential (motion) equation expressed in terms of its natural constraints. Each constraint within the equation represents a simple connection to an artificial neuron. Each connection strength (or synaptic strength) is weighted by multiplicative constants and summed together. The result is an input that is adjusted in the direction that decreases the error or conflict. Using this information, the system derives a simple binary state output in an attempt to solve the puzzle. Given an overall time slot in which to resolve all conflicts, the system iteratively strives to arrive at the state of the global minimum. The proposed algorithm will be able to solve a variety of real-world problems, including: facility layouts for maximizing productivity and safety, classroom assignment for minimizing pupil conflict, crop and plant placement for maximizing yields, and chemical placement within shipping boxes to reduce the possibility of chemical interactions. © 1992.

A parallel algorithm for channel assignment problems in cellular radio networks is presented in this paper. The channel assignment problem involves not only assigning channels or frequencies to each radio cell, but also satisfying frequency constraints given by a compatibility matrix. The proposed parallel algorithm is based on an artificial neural network composed of nm processing elements for an n-cell-m-frequency problem. The algorithm runs not only on a sequential machine but also on a parallel machine with up to a maximum of nm processors. The algorithm was tested by solving eight benchmark problems where the total number of frequencies varied from 100 to 533. The algorithm found the solutions in nearly constant time with nm processors. The simulation results showed that the algorithm found better solutions than the existing algorithm in one out of eight problems. © 1992 IEEE

A maximum neuron model is proposed in order to force the state of the system to converge to the solution in neural dynamics. The state of the system is always forced in a solution domain. The artificial maximum neural network is used for the module orientation problem and the bipartite subgraph problem. The usefulness of the maximum neural network is empirically demonstrated by simulating randomly generated massive nstances (examples) in both problems. In randomly generated more than one thousand instances our system always converges to the solution within one hundred iteration steps regardless of the problem size. Our simulation results show the effectiveness of our algorithms and support our claim that one class of NP-complete problems may be solvable in a polynomial time. © 1992 Springer-Verlag.

Since McCulloch and Pitts proposed an artificial neuron model in 1943, several neuron models have been investigated. This paper proposes the first parallel improvement algorithm using the maximum neural network model for the bipartite subgraph problem. The goal of this NP-complete problem is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that our algorithm finds a solution within 200 iteration steps and the solution quality is superior to that of the best existing algorithm. The algorithm is extended for the k-partite subgraph problem, where no algorithm has been proposed. © 1992 IEEE

A parallel algorithm for channel routing problems is presented in this paper. The channel routing problem is very important in the automatic layout design of VLSI circuits and printed circuit boards. The problem is to route the given interconnections between two rows of terminals on a multilayer channel where the channel area must be minimized. Although several algorithms have been proposed for two-layer problems, two-Iayer-and-over-the-cell problems, and three-layer problems, the current advancement of VLSI chip technology allows us to use four layers composed of two metal layers and two polysilicon layers for routing in a chip. The goal of the proposed parallel algorithm is to find the near-optimum routing solution for the given interconnections in a short time. The algorithm is applied for the four-layer channel routing problems where it requires n × m × 2 processing elements for the n-netm-track problem. The algorithm has three advantages over the conventional algorithms: 1) it can be easily modified for accommodating more than four-layer problems, 2) it runs not only on a sequential machine but also on a parallel machine with maximally n ×m × 2 processors, and 3) the program size is very small. The algorithm is verified by solving seven benchmark problems where the algorithm finds routing solutions in a nearly constant time with n × m × 2 processors. © 1992 IEEE

A new parallel processing algorithm for solving string search problems is presented in this paper. The proposed algorithm uses 0(m x n) processors where n is the length of a text and m is the length of a pattern. It requires two and only two iteration steps to find the pattern in the text, while the best existing parallel algorithm needs the computation time 0(loglog n). © 1992 IEEE

In manufacturing memory chips, Redundant Random Access Memory (RRAM) technology has been widely used because it not only provides repair of faulty cells but also enhances the production yield. RRAM has several rows and columns of spare memory cells which are used to replace the faulty cells. The goal of our algorithm is to find a spare allocation which repairs all the faulty cells in the given faulty-cell map. The parallel algorithm requires In processing elements for the n x n faulty-cell map problem. The algorithm is verified by many simulation runs. Under the simulation the algorithm finds one of the near-optimum solutions in a nearly constant time with 0(n) processors. The simulation results show the consistency of our algorithm. The algorithm can be easily extended for solving rectangular or other shapes of fault map problems. Reader Aids - Purpose: Present a new algorithm Special math needed for explanations: Probability Special math needed to use results: None Results useful to: Reliability theoreticians and analysts. © 1991 IEEE

A hysteresis binary McCulloch-Pitts neuron model is proposed in order to suppress the complicated oscillatory behaviors of neural dynamics. The artificial hysteresis binary neural network is used for scheduling time-multiplex crossbar switches in order to demonstrate the effects of hysteresis. Time-multiplex crossbar switching systems must control traffic on demand such that packet blocking probability and packet waiting time are minimized. The system using n×n processing elements solves an n×n crossbar-control problem with O(1) time, while the best existing parallel algorithm requires O(n) time. The hysteresis binary neural network maximizes the throughput of packets through a crossbar switch. The solution quality of our system does not degrade with the problem size. © 1991 Springer-Verlag.

Coloring map problem. The map-coloring problem is defined that one wants to color the regions of a map in such a way that no two adjacent regions (that is, regions sharing some common boundary) are of the same color. This paper presents a parallel algorithm based on the McCulloch-Pitts binary neuron model and the Hopfield neural network. It is shown that the computational energy is always guaranteed to monotonically decrease with the Newton equation. A 4 X n neural array is used to color a map of n regions where each neuron as a processing element performs the proposed Newton equation. The capability of our system is demonstrated through a large number of simulation runs. The parallel algorithm is extended for solving the K-colorability problem. The computational energy is presented for solving a four. © 1991 IEEE

A neural network model for broadcasting scheduling in multihop packet radio networks is presented. The problem of broadcast scheduling with a minimum number of time slots is NP-complete. The proposed neural network model finds a broadcasting schedule with a minimal number of time slots where it requires n processing elements for an n-node radio network. Fifteen different radio networks were examined where the neural network model found an m-time-slot solution in O(m) time with n processors.