A novel neural network approach called gradual neural network (GNN) is presented for segmented channel routing in field programmable gate arrays (FPGA's). FPGA's contain predefined segmented channels for net routing, where adjacent segments in a track can be interconnected through programmable switches for longer segments. The goal of the FPGA segmented channel routing problem, known to be NP-complete, is to find a conflict-free net routing with the minimum routing cost. The GNN for the N-net-M-track problem consists of a neural network of NxM binary neurons and a gradual expansion scheme. The neural network satisfies the constraints of the problem, while the gradual expansion scheme seeks the cost minimization by gradually increasing activated neurons. The energy function and the motion equation are newly defined with heuristic methods. The performance is verified through solving 30 instances, where GNN finds better solutions than existing algorithms within a constant number of iteration steps.

A novel neural network approach called "Evolutionary Neural Network (ENN)" is presented for the module orientation problem. The goal of this NP-complete problem is to minimize the total wire length by flipping circuit modules with respect to their vertical and/or horizontal axes of symmetry. In order to achieve high quality VLSI systems, it is strongly desired to solve the problem as quickly as possible in the design cycle. Based on the concept of the genetic algorithm, the evolutionary initialization scheme on neuron states is introduced so as to provide a high quality solution within a very short time. The performance of ENN is compared with three heuristic algorithms through simulations on 20 examples with up to 500 modules. The results show that ENN can find the best solutions in the shortest time.

This paper presents a binary Hopfield neural network approach for finding a broadcasting schedule in a low-altitude satellite system. Our neural network is composed of simple binary neurons on the synchronous parallel computation, which is greatly suitable for implementation on a digital machine. With the help of heuristic methods, the neural network of a maximum of 200000 neurons can always find near-optimum solutions on a conventional workstation in our simulations.

A novel neural-network approach called gradual neural network (GNN) is presented for a class of combinatorial optimization problems of requiring the constraint satisfaction and the goal function optimization simultaneously. The frequency assignment problem in the satellite communication system is efficiently solved by GNN as the typical problem of this class. The goal of this NP-complete problem is to minimize the cochannel interference between satellite communication systems by rearranging the frequency assignment so that they can accommodate the increasing demands. The GNN consists of NxM binary neurons for the N-carrier-M-segment system with the gradual expansion scheme of activated neurons. The binary neural network achieves the constrain satisfaction with the help of heuristic methods, whereas the gradual expansion scheme seeks the cost optimization. The capability of GNN is demonstrated through solving 15 instances in practical size systems, where GNN can find far better solutions than the existing algorithm.

This paper presents a new approach using a neural network model for the multilayer topological via minimization problem in a switchbox. Our algorithm consists of three steps: 1) dividing multiterminal nets into two-terminal nets, 2) finding a layer-assignment of the two-terminal nets by a neural network model so as to minimize the number of unassigned nets, and 3) embedding one via for each unassigned net by Marek-Sadowska's algorithm. The neural network model is composed of N/spl times/M processing elements to assign N two-terminal nets in an M-layer switchbox. The performance of our algorithm is verified by 15 benchmark problems where it can find optimum or near-optimum solutions. In the two-layer Burstein's switchbox, our algorithm finds a 15-via solution while the best known solution requires 20 vias.

Microprogramming is a basic technique that realizes functionally specialized processors in a functionally distributed multiprocessor system which consists of many small processors. In such a multiprocessor system, it is necessary to change processor functions dynamically in order to back up a heavily loaded processor or a failed processor by a lightly loaded processor. This paper proposes a mechanism for exchanging processor functions in firmware level and shows a hardware organization which realizes the mechanism in an experimental system. In order to clarify the design conditions of an operating system and microprograms, the performance of the mechanism is analyzed from the load balancing point of view. Moreover, the conditions which the mechanism must satisfy are derived.

This paper discusses the design of interconnection modules for a multiprocessor system which consists of many small and functionally specialized processors. It is proposed that the information, i.e. programs, data etc., used in the system should be divided into three categories; private information, command data and shared data, according to the analysis of software simulation results. Private information is stored in a memory provided exclusively for each processor. Command data is transferred directly between processors to initiate a function in other processors. Shared data is stored in a memory shared by several processors. For command data and shared data, two different connection modules are provided; the interprocessor connection module using common bus technique, and the processor-memory connection module using crossbar switch technique. The effects of information partitioning on the performance and cost of the system are analyzed. It is verified that the interprocessor connection module technique is preferable than a few possible alternatives through the design analysis and the implementation of a pilot model system.

This paper discusses the structure and efficiency of a computer complex constructed of many small, tightly coupled, functionally dedicated processors called a Poly-Processor System (PPS). The objective of the PPS is to realize a computer system which has easier expandability, higher reliability and better cost-to-performance ratio than existing systems.