The deterioration of signal integrity (SI) due to the skin effect and dielectric loss has been one of the most serious problems in the printed circuit board (PCB) trace since the clock frequency exceeded several hundred MHz. It is expected that the same problem will occur due to the same causes when the frequency exceeds several GHz in global and very long interconnects in very-large-scale integration (VLSI) and in silicon interposers. Currently, in PCBs, this problem is typically overcome by using either passive equalizers based on lumped-element circuits or active equalizers. Unfortunately, however, those equalizers are not suitable for VLSI interconnects in terms of power consumption and parasitic elements. In this paper, we apply a passive equalizer based on distributed-element circuits to global interconnects in VLSIs and silicon interposers; furthermore, we propose a design methodology for this. We fabricate a scale-up prototype of the proposed equalizer and demonstrate that the SI is improved; compared with a conventional interconnect, the jitter is reduced by 55.5%, and the eye height is increased by 75%.

This paper proposes a novel crossover operator for solving large-scale traveling salesman problems (TSPs) by using a Hybrid Genetic Algorithm (HGA) with Lin-Kernighan heuristic for local search and we tentatively name Zoning Crossover (Z-Cross). The outline of Z-Cross is firstly to set a zone in the travelling area according to some rules, secondly to cut edges connecting cities between inside and outside the zone, thirdly to exchange edges inside the zone of one parent and those of the other parent, and lastly to reconnect sub-tours and isolated cities, which come about in the 3rd step mentioned above, so as to construct a new tour of TSP. The method is compared with conventional three crossovers; those are the Maximal Preservative Crossover, the Greedy Sub-tour Crossover and the Edge Recombination Crossover, and evaluated from the viewpoints of tour quality and CPU time. Ten benchmarks are selected from the well-known TSP website of Georgia Institute of Technology, whose names are xqf131, xqg237, ..., sra104815. The experiments are performed ten times for each crossover and each benchmark and show that the Z-Cross succeeds in finding better solution and running faster than the conventional methods. Six benchmarks with size from 39,603 to 104,815 cities are selected from the TSP website and challenged the records of tour lengths. The Z-Cross betters the record of the problem rbz43748 and approaches to solutions less than only 0.02% over the known best solutions for five instances.

A pattern recognition system that can process a large amount of image data at high speed is required in many fields. In this paper, we propose an on-chip pattern recognition system that utilizes the reconfigurability of the FPGA. The features of the system are not only very high recognition speed but also an adaptive function. For example, when objects to be detected change appearance, recognition parameters must be changed to retain the recognition accuracy. The system can automatically adjust by executing on-chip partial reconfiguration. The system runs at 25MHz and can return a recognition result in one clock cycle, 40ns. To update the system, all processes needed for searching for the best recognition parameters, generating configuration data and reconfiguring the system are carried out within 30s.

This correspondence describes a hybrid genetic algorithm (GA) to find high-quality solutions for the traveling salesman problem (TSP). The proposed method is based on a parallel implementation of a multipopulation steady-state GA involving local search heuristics. It uses a variant of the maximal preservative crossover and the double-bridge move mutation. An effective implementation of the Lin-Kernighan heuristic (LK) is incorporated into the method to compensate for the GA's lack of local search ability. The method is validated by comparing it with the LK-Helsgaun method (LKH), which is one of the most effective methods for the TSP. Experimental results with benchmarks having up to 316228 cities show that the proposed method works more effectively and efficiently than LKH when solving large-scale problems. Finally, the method is used together with the implementation of the iterated LK to find a new best tour (as of June 2, 2003) for a 1904711-city TSP challenge.

Distortion of the waveform on printed circuit board (PCBs) is a serious problem in higher-frequency signals transmission. To overcome this problem, we have already proposed segmental transmission line (STL). The STL divides transmission lines into multiple segments with different line widths, those are adjusted to reshape the signal waveform by superposition of reflected waves occurring at segment boundaries. In the previous work, we reshaped the waveform at only one point in the transmission line connected with a device at a time. This paper expands the method to reshape the waveform at two points of the devices at a time. We design a DIMM (dual in-line memory module) clock-line for high-speed computers using our new method, and show effectiveness of the method.

Waveform distortion is a serious problem in higher-frequency signals on printed circuit boards (PCB). In order to overcome this problem, the segmental transmission line (STL) has already been proposed. However, the STL requires segments of wide-range widths. The wide-range line-width impedes higher optimization of waveforms and it also causes cost-increment in the PCB manufacturing. In this paper, we propose a novel STL with variable length segments in order to overcome the difficulties in previous work. We also develop a design methodology using a GA to determine the parameters for the proposed STL. We apply our new STL to the clock line in the actual PCB, and show its effectiveness compared with the previously proposed STL.

In this paper, we proposed an improved method in the prediction of stage-specific TREs associated with four classes of developmentally regulated genes in Dictyostelium discoideum. TRE selection with a direct comparison of e-scores produced lots of the false positive results. In order to reduce false-positive prediction, we applied a normalization method to e-scores and predicted TREs in each developmentally regulated Dd gene sequence. Among the top 25 putative TREs in vegetative and culmination stage, we found two experimentally known TREs out of 6 known TREs in the TRANSFAC database. We also predicted five TREs experimentally known from the literature in the simulation results.

Finding transcription regulatory elements (TREs) is one of most important tasks in current bioinformatics and functional genomics and is the first step to discover regulatory mechanisms of gene expression. The goal of this paper is to detect class-specific TREs associated with four classes of developmentally regulated genes in Dictyostelium discoideum (Dd) with statistically significant measure. Applying a DP matching to 5' UTR sequences of Dd with generated candidate TREs, we calculate the evaluation score (E-score) for given candidate TREs. Based on the proposed selection criteria of TREs, we choose putative class-specific TREs among candidate TREs in each developmentally regulated class of Dd. According to the simulation result with 49 sequences in V expression stage, 43 in A, 42 in S, and 47 in C, we predicted class-specific putative TREs, corresponding to a P /spl les/ 10/sup -3/ such as "aataattt", "attacaaa", and "attaatat" in V, "ttattcta", "atgtgtta", and "aaaattga" in A, "atttcaat", "aataattg", and "acaacaac" in S, "aaaaaatt", "ttaataat", and "atagtttt" in C expression stage of Dd. We could achieve 17.8 times faster TRE detection via parallel computing algorithm with 32 processor machines.

Standardized I/O interfaces such as USB, E1A/T1A-232, PS/2, Ethernet, IEEE 1394, etc., gives us "High Connectivity" that means connections between different devices are guaranteed and users do not have to take care of the connections. However the standardized I/O interfaces are not optimized to all devices and various standards confuse users. We propose a novel I/O interface named Meta-I/O Interface in which reconfigurable LSIs such as FPGAs are used to solve these problems. In Meta-I/O Interface, peripheral devices, which are named Self-Informational Devices (SIDs), have individual non-volatile memories (ROMs) storing the I/O-circuit-configuration-data that are loaded in the FPGAs in the digital equipment through the common standardized connectors. The Meta-I/O Interface prototype is now under development and the circuit sizes are estimated using several current I/O interfaces.

In previous work, we have proposed a parallel hybrid genetic algorithm (PHGA) which can find high quality solution from the mathematical viewpoint for the multiple protein sequence alignment. We present new improvements to the PHGA. Local alignment information is added to the weighted sum-of-pairs objective function to achieve better alignment from the biological viewpoint. We also extend our method to run in parallel on a cluster of machines instead of a multi-processor machine to speed it up.

Ensuring the signal integrity even under pico-second switching-time in PCBs (printed circuit boards) as well as in VLSI chips is one of the most important goals in a PCB design. To achieve the goal, we propose a novel methodology of the PCB trace design in which the traces are regarded as segmental-transmission-lines of individual impedances. Also, the impedances are optimized by minimizing signal distortions due to multiple reflections in the transmission lines through genetic algorithms. Our design system shows excellent experimental results which achieves almost ideal signal wave forms without any signal distortion.

We propose a novel architecture for variable comparator named RPCA (Reconfigurable Parallel Comparation Architecture) making full use of the reconfigurability of FPGA. In the RPCA, an appropriate comparator to each task can be chosen and implemented under the speed/data-size tradeoff. An RPCA-based pack-filter prototype using XILINX XCV300E-6PQ240C and RealTeK RTL8201BL is developed and filtering speed of 120ns for 128 IPs and 1,360ns for 2,048 IPs are obtained under the speed/data-size trade-off.

Reconfigurable architecture for the probabilistic neural network (PNN) is proposed and the PNN hardware system is developed using FPGAs. In the system, preprocessing circuits as well as the PNN can be reconfigured adapting each task. Potential performance of the PNN cannot be brought out until the total reconfigurability including the preprocessing is achieved. The developed system shows high recognition accuracy with high processing speed for some image recognition tasks.

This paper presents a parallel hybrid genetic algorithm (GA) for solving sum-of-pairs multiple protein sequence alignment. The method is based on a multiple population GENITOR-type GA and involves local search heuristics. It is then extended to parallel to exploit the benefit of a multiprocessor system. Benchmarks from the BAliBASE library are used to validate the method.

We propose a novel reasoning algorithm SKBR (symbolical kernel-bases reasoning) that is an extension of the conventional pattern recognition algorithm KB (kernel based method) to the symbolical recognition, or reasoning. We apply SKMR to the splicing boundary prediction problem in human and other species DNA data, and show a new rule extracted from the splice site boundary. We also develop a SKBR hardware system using FPGA and memory LSIs. Performance evaluation of the system shows its very short reasoning time of less than 100 micro-second/query.

Evolvable reasoning hardware and its genetic algorithm-based design methodology is proposed. In the evolvable reasoning hardware, each reasoning task's case database is transformed into truth tables, which are evolved to obtain generalization capability through genetic algorithms. Circuits are synthesized from the evolved truth tables. Because the parallelism in each task can be embedded directly in the circuits by the direct hardware implementation of the case database, the evolved reasoning hardware provides high speed reasoning with small circuit size. We develop a prototype of the reasoning hardware and apply it to the exon/intron boundary prediction that is one of the most important tasks in the genome informatics.

An extension of the kernel-based pattern recognition method using a genetic algorithm is proposed. The method is suited to evolvable pattern recognition hardware using FPGAs. In the conventional method one common kernel function is used in the superposition to make discrimination functions. In the extended method each region of the kernel function is optimized individually. For the kernel-region optimization we use a genetic algorithm to solve a large combinatorial problem almost impossible to solve using any brute-force search. A chromosome represents the kernel region in an n-dimensional pattern space, and each locus corresponds to one of the candidates (genes) for an edge length of the kernel region. We have applied the extended method to a sonar spectrum recognition problem and obtained a recognition accuracy of 83.9%, which is much higher than the 62.0% obtained using the conventional kernel-based method and is also better than 82.7% obtained using the nearest neighbor method and the 83.0% obtained using a neural network (backpropagation algorithm). We have analyzed the individually optimized kernel regions and shown that the GA process automatically extracts features in the patterns and embeds the features in the kernel regions.

A fast method of GP based model building for time series prediction is proposed. The method involves two newly-devised techniques. One is regarding determination of model parameters: only functional forms are inherited from their parents with genetic programming, but model parameters are not inherited. They are optimized by a backpropagation-like algorithm when a child (model) is newborn. The other is regarding mutation: nodes which require a different number of edges, can be transformed into different types of nodes through mutation. This operation is effective at accelerating complicated functions e.g. seismic ground motion. The method has been applied to a typical benchmark of time series and many real world problems.

In this paper, we present a new genetic-algorithm-based design methodology for reasoning VLSI chips, called as LoDETT (logic design with the evolved truth table). In LoDETT, each task's case database is transformed into truth tables, which are evolved to obtain generalization capability (i.e. rules behind the past cases) through genetic algorithms. Digital circuits are synthesized from the evolved truth-tables. Parallelism in each task can be embedded directly in the circuits by the direct hardware implementation of the case database. We applied LoDETT to the English pronunciation reasoning (EPR) problem, resulting in a GATalk chip. A GATalk chip has been designed with about 270K gates, and its reasoning time is about 100 ns for each phoneme. A prototype of the GATalk chip has been implemented using Xilinx XC4010 FPGA chips. It achieved a reasoning accuracy of 81.9% which is almost the same accuracy as NETTalk in neural networks and MBRTalk in parallel AI.

An evolutionary design methodology for sonar spectrum recognition chip is proposed and the prototype chip is developed. In the design, sonar spectrum data are transformed to truth-tables and the truth-tables are evolved to obtain generalization capability by using genetic algorithms. Digital circuits are designed by synthesizing the evolved truth-tables. Parallelism in the data can be embedded in the circuits directly by this direct hardware implementation technique of the sonar spectrum data. The circuit size of the developed chip was 4,134 gates, and this was small enough to be implemented onto a standard FPGA (field programmable gate array) chip. Operation speed of the chip was less than 1.0 micro-second per spectrum. Moreover the chip achieved the recognition accuracy of 91.7%, which was higher than those in the backpropagation and the k-NN algorithm.

We propose a parallel SOM algorithm to speedup the fundamental SOM calculation using parallel computer environments. In the parallel SOM algorithm synaptic weights are updated in parallel corresponding to multiple stimuli (inputs). Parallelism in the proposed algorithm is based on the analogy of the biological neural networks in which neurons respond to the stimuli in parallel. Performance is evaluated by implementing the newly developed performance simulator in a personal computer-cluster under the message passing interface library (MPI) environment. A speedup ratio of about 5.0 is achieved with 8 processors (personal computers) when the width of the neighborhood function is less than 5% of the total number of neurons in the SOM network.

In this paper, we propose a parallel backpropagation algorithm using the genetic algorithm to reduce the learning time to reach the optimal solution. Genetic algorithm is used in parallel previous to the parallel backpropagation regarding the set of weights in the feedforward neural network as chromosomes, and well-evolved chromosomes (sets of excellent initial weights) are used in the parallel backpropagation. Performance of the proposed algorithm was evaluated experimentally in 5-bit and 8-bit parity problems using the massively parallel computer CP-PACS. The learning speeds were about 3 times and about 7 times faster than those of the simple parallel backpropagation in the 5-bit and the 8-bit parity problems, respectively.

This paper proposes a multi-modal neural network model composed of a pre-processing module and a post-processing module in order to enhance the nonlinear characteristics of neural networks. The pre-processing module is made of Chebyschev polynomials and transforms input data into spectra. The post-processing module is made of multilayer neural network and associates according to the spectral inputs generated by the pre-processing module. Fundamental experiments upon pattern recognition and functional approximation and experiments applying the method to a control problem result that the method enable one to build small scale neural model for nonlinear systems and to perform learning in shorter time.

MY-NEUPOWER is an inexpensive massively parallel computer, which is composed of 512 processor elements densely packaged in a desktop-size cabinet. Communication using a common broadcast-bus and integer-representation circuits are the fundamental architecture of the machine. In this paper, we present effective implementation techniques of backpropagation (BP) and memory-based reasoning (MBR) onto MY-NEUPOWER. Speed and scalability with these techniques are measured, and high performance with cost-effectiveness is shown being compared with those of other computers. Effect of the integer representation is also evaluated and shown not to reduce the learning and reasoning performance.

The self-organizing map (SOM) implemented by wafer-scale integration (WSI) will provide significantly high speed and desktop-size hardware for many practical applications such as pattern classification, image-processing, and robotics. Due to the synergistic effect of all neurons for ordering, the SOM-WSI is expected to reach the desired global-ordering state even in the presence of defective neurons. This fault tolerant capability, however, has not yet been studied. In this paper, we propose a fundamental SOM-WSI structure and its defect model. From the defect model, we derive a critical-stuck-output and show that if the defective neuron's stuck-output is larger than the critical-stuck-output, the defective SOM can eventually organize itself completely tolerating defects. In an ordinary digital design of a neuron, the critical-stuck-output is proved to be small. Therefore, we can expect high-fault tolerance in the SOM-WSI. Experiments are carried out by injecting defective neurons in a neurocomputer currently used as a prototype of the SOM-WSI. The experimental result agrees well with the proposed theory. In addition, we derive an equation to estimate the degree of fault-tolerance in the SOM hardware by expanding the critical-stuck-output calculation. The derived equation can be used to determine the fundamental design parameters in the SOM-WSI as well as other neurocomputer designs.

A wafer-scale-integration (WSI) neural network has been fabricated and evaluated. 576 digital neurons are integrated and interconnected with each other on a 5-in silicon wafer by using 0.8-μm CMOS. Neural functions are faithfully mapped to binary digital circuits. The 9-bit output and the 8-bit synapse weight of each neuron are variable. A time-sharing digital bus architecture overcomes the disadvantage of digital neuron circuits. This WSI neural network can be connected with a host computer and used for a wide range of artificial neural networks. The 16-city traveling salesman problem could be solved in less than 0.1 s by using this network. This speed was 10 times faster than a Hitachi supercomputer. Larger artificial neural networks can be realized by simply connecting WSIs