論文

A near-optimum parallel algorithm for one-dimensional gate assignment problems is presented in this paper where the problem is NP-hard. The proposed system is composed of an n×n two-dimensional maximum neural network for (n+2)-gate assignment problems. Our algorithm has discovered the improved solution in the benchmark problem over the existing algorithms.

A parallel algorithm for the n-task-n-person assignment problem is presented in this paper. The proposed algorithm is based on the artificial neural network model where a large number of simple processing elements are used. Through a large number of simulation runs, it was empirically shown that the state of the system can converge to the solution within a hundred iteration steps regardless of the problem size n. The proposed algorithm using n2 processing elements requires computational bounds of a nearly O(1) time.

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

Topological 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 3 n processing elements for the n-net split RTVM problems, and 5 n 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.

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.

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.

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.

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.

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 n2 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.

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.

The graph partitioning problem is a famous combinatorial problem and has many applications including VLSI circuit design, task allocation in distributed computer systems and so on. In this paper, a novel neural network for the m-way graph partitioning problem is proposed where the maximum neuron model is used. The unidirected graph with weighted nodes and weighted edges is partitioned into several subsets. The objective of partitioning is to minimize the sum of weights on cut edges with keeping the size of each subset balanced. The proposed algorithm was compared with the genetic algorithm. The experimental result shows that the proposed neural network is better or comparable with the other existing methods for solving the m-way graph partitioning problem in terms of the computation time and the solution quality.

A near-optimum parallel algorithm for solving PLA folding problems is presented in this paper where the problem is NP-complete and one of the most fundamental problems in VLSI design. The proposed system is composed of n X n neurons based on an artificial two-dimensional maximum neural network where n is the number of inputs and outputs or the number of product lines of PLA. The two-dimensional maximum neurons generate the permutation of inputs and outputs or product lines. Our algorithm can solve not only a simple folding problem but also multiple, bipartite, and constrained folding problems. We have discovered improved solutions in four benchmark problems over the best existing algorithms using the proposed algorithm.

A parallel algorithm for solving meeting schedule problems is presented in this paper where the problem is NP-complete. The proposed system is composed of two maximum neural networks which interact with each other. One is an M×S neural network to assign meetings to available time slots on a timetable where M and S are the number of meetings and the number of time slots, respectively. The other is an M×P neural network to assign persons to the meetings where P is the number of persons. The simulation results show that the state of the system always converges to one of the solutions and that the solution quality of the proposed algorithm does not degrade with the problem size.

A near-optimum parallel algorithm for solving facility layout problems is presented in this paper where the problem is NP-complete. The facility layout problem is one of the most fundamental quadratic assignment problems in Operations Research. The goal of the problem is to locate N facilities on an N-square (location) array so as to minimize the total cost. The proposed system is composed of N x N neurons based on an artificial two-dimensional maximum neural network for an N-facility layout problem. Our algorithm has given improved solutions for several benchmark problems over the best existing algorithms.

The no-three-in-line problem is one of unsolved problems in number theorem. The goal of the no-three-in-line problem is to locate 2N points on an N × N squares array where no three points are in line. The proposed algorithm uses N2 hysteresis McCulloch-Pitts neurons as the processing elements for the N × N array problem. Our neural network algorithm has discovered several different solutions for up to N = 25.

This paper investigates the scaling properties of neural networks for solving job-shop scheduling problems. Specifically, the Tank-Hopfield linear programming network is modified to solve mixed integer linear programming with the addition of step-function amplifiers. Using a linear energy function, our approach avoids the traditional problems associated with most Hopfield networks using quadratic energy functions. Although our approach requires more hardware (in terms of processing elements and resistive interconnects) than a recent approach by Zhou et al. [2], the neurons in the modified Tank-Hopfield network do not perform extensive calculations unlike those described by Zhou et al.

A balloon net model is introduced and demonstrated for discovering improved solutions in one of unsolved problems in geometry which is referred to as a problem of `Spreading points in a square'. How should n points be arranged in a unit square so that the minimum distance between them is the greatest? Note that d(n) is the greatest possible minimum distance between n points in a unit square. Exact results are known for n≤9 and n = 14, 16, 25, and 36. Many investigators including Schaer, Meir, Kirchner, Wengerodt, Goldberg, Schluter, Valette and others have studied this geometrical problem for many years. The best known result is summarized in the book of `Unsolved Problems in Geometry' (H.T. Croft. K.J. Falconer and R.K. Guy/1991). We have found improved solutions for n = 13 and n = 15 by the proposed algorithm.