|
|
|
|
This paper introduces an idea which the authors hope and believe will create not only a new branch of Artificial Life, but may also serve as the basis for a radically new approach to electronic and computer design. The idea can be expressed in two words, ``evolvable hardware''. Software configurable hardware, such as programmable logic arrays, are on the market which accept a bit string instruction which is used to configure or ``wire up'' a hardware circuit to give it a desired architecture. This can be done an indefinite number of times. By treating the bit string instruction as a Genetic Algorithm ``chromosome'', one has the means to evolve hardware. This paper reports on a successful experiment to simulate the evolution of a GAL16V8 hardware chip, which solves the 6-multiplexor problem. The concept of evolvable hardware can be used to build ``Darwin Machines'', i.e. special devices which are capable of adapting to their environment by modifying their own hardware architecture using genetic learning techniques.
In this chapter, we describe a parallel processing architecture for Evolvable Hardware (EHW) which changes its own hardware structure in order to adapt to the environment in which it is embedded. This adaptation process is a combination of genetic learning with reinforcement learning. Our goal by implementing adaptation in hardware is to produce a flexible and fault-tolerant architecture which responds in real-time to a changing environment. If we succeed we are convinced that EHW will prove to be a key technology for building autonomous agents.
We describe a high-speed pattern recognition system using Evolvable Hardware (EHW), which can change its own hardware structure by genetic learning in order to adapt best to the environment. The purpose of the system is to show that EHW can work as a recognition device with such robustness for the noise as seen in the recognition systems based on neural networks. The advantage of EHW compared with a neural network is the high processing speed and the readability of the learned result. The readability means that the result is understandable in terms of Boolean functions. In this paper, we describe the architecture, the learning algorithm and the experiment on the pattern recognition system using EHW.
This paper describes a function-level Evolvable Hardware (EHW). EHW is hardware which is built on programmable logic devices (e.g. PLD and FPGA) and whose architecture can be reconfigured by using a genetic learning to adapt to new unknown environments in real time. EHW can adapt in real-time to such an environmental changes. It is demonstrated that the function-level hardware evolution can attain much higher performances than the gate-level evolution , in neural network applications (e.g. two-spiral). VLSI architecture of the function-based FPGA dedicated to function level evolution is also described.
Evolvable hardware (EHW) has attracted increasing attentions since early 1990's with the advent of easily reconfigurable hardware such as field programmable logic array (FPGA). It promises to provide an entirely new approach to complex electronic circuit design and new adaptive hardware. EHW has been demonstrated to be able to perform a wide range of tasks from pattern recognition to adaptive control. However, there are still many fundamental issues in EHW remain open. This paper reviews the current status of EHW, discusses the promises and possible advantages of EHW, and indicates the challenges we must meet in order to develop practical and large-scale EHW.
We have investigated the possibility of applying Evolvable Hardware (EHW) to data compression applications. One of the interesting area in data compression is Predictive Coding which we used for compressing block of data in the hardware configuration of EHW. The advantage of this approach is simplicity, adaptability, real time implementation for motion pictures and advantage of using non-linear prediction functions. Several configurations of EHW are tested to find the optimal system for data compression and the results show good performance compared with Neural Networks and JPEG approaches.
In this paper, we study the possibility of using Evolvable Hardware (EHW) for scheduling real-time traffic in Asynchronous Transfer Mode (ATM) networks. EHW is hardware which is built on programmable logic devices and whose architecture can be reconfigured by using genetic learning to adapt to new environments. A novel design is the function-level EHW based on Field Programmable Gate Array (FPGA) chips, where a number of Programmable Floating processing Units (PFUs) are embedded in one chip. The selectable high-level hardware functions of each PFU make the function-level EHW to be suitable for a wide variety of applications in practice. In our experiment, a statistical multiplexer at an ATM node is modeled for the purpose of generating training data. Superposed bursty cell streams are applied to the model of the multiplexer. The EHW is trained by the collected data in the learning phase. After learning is complete, the best chromosome is tested with respect to various traffic characteristics and the Quality Of Service (QOS) requirements of the cell traffic. Simulation results show that the function-level EHW performs the control well for cell scheduling problem in ATM networks.
Recently there has been great interest in the design and study of evolvable systems based on Artificial Life principles in order to control the behavior of physically embedded systems such as mobile robots. This paper examines an evolutionary navigation system for a mobile robot using a Boolean function approach implemented on gate-level evolvable hardware (EHW). The task of the mobile robot is to reach a goal represented by a colored light while avoiding obstacles during its motion. Using the evolution principles to build the desired behaviors, we show that the Boolean function approach using gate-level evolvable hardware is sufficient. We demonstrate the effectiveness of the generalization ability of EHW by comparing the method with a Boolean function approach implemented on a random access memory (RAM). The results show that the evolvable hardware system obtains the desired behaviors in twice fast time and that the EHW generates a robust robot behavior insensitive to the robot position and the obstacles configurations.
In this paper. we explore the potential of Evolvable Hardware (EHW) for online adaptation in real-time applications. We follow a top-down approach here. We first review existing adaptation and learning techniques and take a look at, their suitability for driving hardwar evolution. Then we discuss some research problems whose solution will improve the performance of EHW.
Evolvable Hardware (EHW) is a hardware which modifies its own hardware structure according to the environmental changes. EHW is implemented on a programmable logic device (PLD), whose architecture can be altered by downloading a binary bit string, i.e. architecture bits. The architecture bits are adaptively acquired by genetic algorithms (GA). The target task of EHW is "Boolean concept formation", which has been intensively studied in machine learning literatures. Although many evolutionary or adaptive techniques were proposed to solve this class of problems, there have been ver y few comparative studies from the viewpoint of computational learning theory. This paper describes machine learning approach to the gate-level EHW, i.e. 1) MDL-based improvement of fitness evaluation, and 2) comparative studies of efficiency by PAC criterion. We also discuss the current extension of EHW and related works.
This paper investigates the application of function-level Evolvable Hardware (EHW) to the adaptive equalization of digital communication channel. EHW is hardware that is built on programmable logic devices such as field programmable gate arrays. Its architecture can be reconfigured by using genetic learning to adapt to new, unknown environments in real time. We propose an EHW-based adaptive equalizer whose adaptive capability and fast processing speed make possible high-speed channel equalization. Simulation results show that the EHW-based equalizers have superior performance to traditional equalizers based on the linear transversal filter.
This paper proposes the methodology for hardware evolution by genetic programming (GP). By adopting Binary Decision Diagrams (BDDs) as hardware representation, larger circuits can be evolved, and they will be easily verified by utilizing commercial CAD software. The hardware descriptions specified in BDDs are improved by GP operators, to synthesize various combinatorial logical circuits. From the viewpoint of GP, however, some constraints of BDD must be satisfied during its search process. In other words, GP must search not only in phenotype space, but also in genotype space. In order to resolve this problem, in this paper, we attempt two approaches. One concerns the operations to obtain BDDs satisfying the genotypical constraints, and the other is the method for balancing phenotypic and genotypic evaluations.
This paper describes a new type of Evolvable Hardware (EHW). While most EHW research employs hardware evolution at the level of primitive gates (i.e., gate-level evolution), our alternative synthesizes hardware circuits with higher-level functions. We call this evolution function-level evolution. In this paper, two applications of function-level EHW are described. One is for adaptive equalization in digital mobile communication. The other is for lossy data compression.
Evolvable Hardware (EHW) is hardware which is built on programmable logic devices and whose architecture can be reconfigured by using genetic learning to adapt to new environments. The function-level EHW was designed based on Field Programmable Gate Array (FPGA) chips, where a number of Programmable Floating processing Units (PFUs) are embedded in one chip. The selectable high-level hardware functions of each PFU make the function-level EHW suitable for a wide variety of applications in practice. In this paper, we study on-line adaptive cell scheduling in Asynchronous Transfer Mode (ATM) networks by using the function-level EHW. A flexible cell scheduling mechanism is proposed, which can not only guarantee the cell delay constraint for the real-time traffic, but also improve the overall performance of the network. The on-line adaptive control, offered by the EHW, can perform required traffic control even though the traffic behavior is changed. Simulation results reveal the on-line adaptive control effects for an ATM multiplexer.
This paper describes an evolvable hardware (EHW) system for generalized neural network learning. We have developed an ASIC VLSI chip, which is a building block to configure a scalable neural network hardware system. In our system, both the topology and the hidden layer node functions of a neural network mapped on the chips are dynamically changed using a genetic algorithm. Thus, the most desirable network topology and choice of node function (e.g. Gaussian or sigmoid) for a given application can be determined adaptively. This approach is particularly suited to applications requiring ability to cope with time-varying problems and real-time timing constraints. The chip consists of 15 Digital Signal Processors (DSPs), whose functions and interconnections are reconfigured dynamically according to the chromosomes of the genetic algorithm. Incorporation of local learning hardware increases the learning speed significantly. Simulation results on the prediction of chaotic data and adaptive equalization in digital mobile communication are also given. Our system is two orders of magnitude faster than a Sun SS20 on the corresponding problem.
We have investigated the possibility of applying Evolvable Hardware (EHW) to lossless image compression. EHW is a hardware that its configuration changes by an evolutionary algorithm. One of the successful methods in image compression is prediction coding which is based on pixel prediction function using neighbor pixels. Most of the algorithms in lossless image compression use fixed linear functions for pixel prediction. We have designed special hardware for the lossless image compression by classification of neighbor patterns and defining a set of functions. An evolutionary algorithm modifies each function depending on their local performance. By using functions included in EHW and changing them in real time an adaptive prediction system is established. Here we test the EHW system for pixel prediction and later we will apply it for error prediction to enhance the performance of compression. Simulation results for pixel prediction are compared with some common methods in image compression and a better performance is achieved.
Recently there has been a great interest in the design and study of evolvable and autonomous systems in order to control the behavior of physically embedded systems such as a mobile robot. This paper studies an evolutionary navigation system for a mobile robot using an evolvable hardware (EHW) approach. This approach is unique in that it combines learning and evolution, which was usually realized by software, with hardware. It can be regarded as an attempt to make hardware ``softer''. The task of the mobile robot is to reach a goal represented by a colored ball while avoiding obstacles during its motion. We show that our approach can evolve a set of rules to perform the task successfully. We also show that the evolvable hardware system learned off-line is robust and able to perform the desired behaviors in a more complex environment which is not seen in the learning stage.
Evolvable Hardware (EHW) is a hardware which modifies its own hardware structure according to the environmental changes. EHW is implemented on a programmable logic device (PLD), whose architecture can be altered by downloading a binary bit string, i.e. architecture bits. The architecture bits are adaptively acquired by genetic algorithms (GA). This paper describes the fundamental principle of the gate-level EHW and its improvement by the MDL-based fitness evaluation. The effectiveness of our approach is shown by comparative experiments and a successful application. We also discuss the current extension of EHW and related works.
Selective cell discarding is used for traffic control and congestion control in Asynchronous Transfer Mode (ATM) networks. Whenever congestion occurs at a network element, the element will selectively discard the cells that contain less significant information to recover from the congestion. An optimal control should keep a good balance among traffic conditions, number of dropped cells, and network throughput in order to dissolve the congestion problem properly. Evolvable hardware (EHW) is a promising device to offer on-line adaptive control in real-time environments. In this paper, we approach the possibility of using EHW for adaptive threshold cell discarding in ATM networks. We examined the control effect of the proposed scheme by means of simulation. The simulation results show that the proposed scheme based on EHW is effective for applying intelligent cell discarding in an ATM element.
We have investigated the possibility of applying Evolvable Hardware (EHW) to data compression applications. Evolvable Hardware can be defined as a hardware architecture that an evolutionary algorithm like Genetic Algorithms changes the hardware configuration. The hardware we used here for EHW contains a wide range of non-linear functions and can be optimised for different applications such as image compression. Predictive coding is one of successful algorithms for image compression and we used this approach for compressing block of data in the hardware configuration of EHW. By applying non-linear functions implemented on EHW and evolving them using genetic algorithms, an adaptive non-linear predictive coding is established for data compression. Simulation results are compared with other common methods in data compression and a better performance is achieved.
This paper describes an evolvable hardware (EHW) system for generalized neural network learning. We have developed an ASIC VLSI chip, which is a building block to configure a scalable neural network hardware system. In our system, both the topology and the hidden layer node functions of a neural network mapped on the chips are dynamically changed using a genetic algorithm. Thus, the most desirable network topology and choice of node function (e.g. Gaussian or sigmoid) for a given application can be determined adaptively. This approach is particularly suited to applications requiring ability to cope with time-varying problems and real-time timing constraints. The chip consists of 15 Digital Signal Processors (DSPs), whose functions and interconnections are reconfigured dynamically according to the chromosomes of the genetic algorithm. Incorporation of local learning hardware increases the learning speed significantly. Simulation results on adaptive equalization in digital mobile communication are also given. Our system is two orders of magnitude faster than a Sun SS20 on the corresponding problem.
Recently there has been great interest in the design and study of evolvable systems in order to control the behavior of physically embedded systems. Due to the complexity of their architecture and their interaction with the environment, a Model-based Autonomous System approach was proposed by Williams to integrate a priori knowledge and reasoning methods of different kinds. But the difficulty of precomputing all possible interactions obliges also the autonomous system to self configure itself by modifying its own structure as well as self modeling by adapting or even building a model using for example sensor information. This paper examines the architecture of a self configuration component of a model-based autonomous system using a evolvable hardware (EHW). The self configure component is applied to a navigation system for a mobile robot. It uses a Boolean function approach implemented on gate-level reconfigurable hardware. The task of the mobile robot is to reach a goal represented by a colored ball while avoiding obstacles during its motion. Using the evolution principles to build the desired behaviors, we show that the Boolean function approach using gate-level reconfigurable hardware is sufficient. We demonstrate the effectiveness of the generalization ability of the Boolean function approach using EHW by creating off-line the robot behavior and the advantage of the hardware implementation to speed up the on-line adaptation. The results show that the evolvable hardware system is able to create a robust robot behavior insensitive to the gap between the real and simulated world.
Recently there has been great interest in the idea that evolvable systems based on the principles of Artificial Life can be used to continuously and autonomously adapt the behavior of physically embedded systems such as mobile robots, plants and intelligent home devices. At the same time, we have seen the introduction of evolvable hardware(EHW): new integrated circuits that are able to adapt their hardware autonomously and almost continuously to changes in the environment (Higuchi et al. 1992). This paper describes how a navigation system for a physical mobile robot can be evolved using a Boolean function approach implemented on evolvable hardware. The task of the mobile robot is to track a moving target represented by a colored ball, while avoiding obstacles during its motion. Our results show that a dynamic Boolean function approach is sufficient to produce this navigation behavior. Although the classical model-free evolution method is often infeasible in the real world due to the number of possible interactions with the environment, we demonstrate that a model-based evolution method can reduce the interactions with the real world by a factor of 250, thus allowing us to apply the evolution process on-line and to obtain an adaptive tracking-avoiding system, provided the implementation can be accelerated by the utilization of evolvable hardware.
This paper describes an image compression system based on Evolvable HardWare (EHW) for High Precision Printers (HPP). These printers are especially flexible for book publishing, but require large disk space for images, in particular those of higher resolution. To increase the printing speed and reduce the disk space, the images should be compressed. The system for this compression must be 1) adaptive, so that it changes depending on image characteristics and 2) on-line, which means implemented in hardware. The standard compression methods have a simple template change strategy which is not efficient for the images of HPP. We used an EHW system for compressing HPP images in real time. The EHW is a type of adaptive hardware which allows evolutionary algorithms to change the hardware configuration in real time. It works as fast as other compression systems (like JBIG standard), but changes the image modeling to reflect the changes in the image characteristics. Simulation results show more than a 50% increase in compression ratio compared to JBIG for the printer system.
*****************
This paper describes a data compression chip for the high-precision electrophotographic printer using Evolvable Hardware (EHW). EHW is a new hardware paradigm which combines Genetic Algorithm (GA) and reconfigurable hardware technology such as FPGA (Field Programmable Gate Array). In EHW, GA is used to search for the most desirable hardware structure to a given task. If the task requirement changes, GA is invoked to get a better hardware structure and EHW is reconfigured that way. In data compression, EHW is used to implement the most adequate compression method directly in hardware according to the characteristics of the target image. The EHW-based compression chip attains approximately twice the compression compared with the international standard called JBIG. This chip is the first EHW-chip to lead to a commercial product.
Recently there has been great interest in the idea that evolvable systems based on the principles of Artificial Life can be used to continuously and autonomously adapt the behavior of physically embedded systems such as mobile robots, plants and intelligent home devices. At the same time, we have seen the introduction of evolvable hardware(EHW): new integrated circuits that are able to adapt their hardware autonomously and almost continuously to changes in the environment. This paper describes how a navigation system for a physical mobile robot can be evolved using a dynamic Boolean function approach implemented on evolvable hardware. The task of the mobile robot is to track a moving target represented by a colored ball, while avoiding obstacles during its motion in a non-deterministic and not stationary environment. Our results show that a dynamic Boolean function approach is sufficient to produce this navigation behavior. Although the classical model-free evolution method is often infeasible in the real world due to the number of possible interactions with the environment, we demonstrate that a model-based evolution method can reduce the interactions with the real world by a factor of 250, thus allowing us to apply the evolution process on-line and to obtain an adaptive tracking-avoiding system, provided the implementation can be accelerated by the utilization of evolvable hardware.
This paper describes a data compression system using Evolvable Hardware (EHW) for digital color electrophotographic (EP) printers. EP printing is an important technology within digital printing, which is currently having a significant impact on the printing and publishing industry. Although, it requires data-compression to reduce the cost for transferring and storing large EP images, traditional techniques can not handle this data-compression well. This paper explains how EHW can be used as a compression system. EHW can change the compression method according to the characteristics of the image. The proposed EHW-based compression system can compress approximately twice as much data as JBIG, the current international standard.
The advantage of Evolvable Hardware (EHW) over traditional hardware is its capacity for dynamic and autonomous adaptation, which is achieved through by Genetic Algorithms (GAs). In most EHW implementations, these GAs are executed by software on a personal computer (PC) or workstation (WS). However, as a wider variety of applications come to utilize EHW, this is not always practical. One solution is to have the GA operations carried out by the hardware itself, by integrating these together with reconfigurable hardware logic like PLA (Programmble Logic Array) or FPGA (Field Programmable Gate Array) on to a single LSI chip. A compact and quickly reconfigurable EHW chip like this could service as an off-the-shelf device for practical applications that require on-line hardware reconfiguration. In this paper, we describe an integrated EHW LSI chip that consists of GA hardware, reconfigurable hardware logic, a chromosome memory, a training data memory, and a 16-bit CPU core (NEC V30). An application of this chip is also described in a myoelectric artificial hand, which is operated by muscular control signals. Although, work on using neural networks for this is being carried out, this approach is not very promising due to the long learning period required for neural networks. A simulation is presented showing that not only is the EHW performance slightly better than with neural networks, but that the learning time is considerably reduced.
This paper describes an analogue EHW (Evolvable Hardware) chip for Intermediate Frequency (IF) filters, which are widely used in cellular phones. When analogue Integrated Circuits (ICs) and Large-Scale Integrated Circuits (LSIs) are manufactured, the values of the analogue circuit components, such as resistors or capacitors, often vary from the precise design specifications. Analogue LSIs with such defective components can not perform at required levels and thus have to be discarded. However, the chip proposed in this paper can correct these discrepancies in the values of analogue circuit components by genetic algorithms (GAs). Simulations have shown that 95\% of the chips can be adjusted to satisfy the specifications of the IF filters. Using this analogue EHW chip has two advantages, namely, (1) improved yield rates and (2) smaller circuits, which can lead to cost reductions and efficient implementation of LSIs. The chip is scheduled to appear in the fourth quarter of 1998.
Great interest have been shown in the application of the principles of artificial life to physically embedded systems such as mobile robots, computer networks, home devices able continuously and autonomously to adapt their behavior to changes of the environments. At the same time researchers have been working on the development of evolvable hardware, and new integrated circuits that are able to adapt their hardware autonomously and in real time in a changing environment. This article describes the navigation task for a real mobile robot and its implementation on evolvable hardware. The robot must track a colored ball, while avoiding obstacles in an environment that is unknown and dynamic. Although a model-free evolution method is not feasible for real-world applications due to the sheer number of possible interactions with the environment, we show that a model-based evolution can reduce these interactions by two orders of magnitude, even when some of the robot's sensors are blinded, thus allowing us to apply evolutionary processes online to obtain a self-adaptive tracking system in the real world, when the implementation is accelerated by the utilization of evolvable hardware.
We propose the use of bottleneck networks implemented by evolvable hardware for the adaptive blind equalization of digital communication channels. Blind Channel equalization is a method of recovering the original symbols by compensating for channel distortion at the receiver's end without any known training sequence for the startup period. If the non-linear channel distortion is too severe to ignore, the conventional blind equalizers suffer from severe performance degradation because they are based on linear transversal filters. The proposed equalizer overcomes this difficulty via the bottleneck network implemented by evolvable hardware. Using a genetic algorithm, the network on the hardware is trained to minimize an energy function based on the maximum likelihood estimation. Simulation results show that the proposed equalizers have superior performance to popular CMA blind equalizers.
Recently there has been great interest in the idea that evolvable systems based on the principles of Artificial Life can be used to continuously and autonomously adapt the behavior of physically embedded systems such as mobile robots, plants and intelligent home devices. At the same time, we have seen the introduction of evolvable hardware: new integrated circuits that are able to adapt their hardware autonomously and almost continuously to changes in the input data or environment. This paper describes how a navigation system for a physical mobile robot can be evolved on-line using a Boolean function approach implemented on gate-level evolvable hardware (EHW). The task of the mobile robot is to track a moving target represented by a colored ball, while avoiding obstacles during its motion. Our results show that the dynamic Boolean function approach is sufficient to produce this navigation behavior. We show that a model-based evolution approach can reduce the interaction with the environment by a two orders of magnitude compared to the classical model-free approach using no a priori knowledge. Thus, it allows us to obtain an on-line adaptive tracking system in the real world, provided the implementation can be accelerated using evolvable hardware.
Evolvable hardware (EHW) has attracted increasing attention since the early 1990's with the advent of easily reconfigurable hardware, such as field programmable gate arrays (FPGA's). It promises to provide an entirely new approach to complex electronic circuit design and new adaptive hardware. EHW has been demonstrated to be able to perform a wide range of tasks from pattern recognition to adaptive control. However, there are still many fundamental issues in EHW that remain open. This paper reviews the current status of EHW, discusses the promises and possible advantages of EHW, and indicates the challenges we must meet in order to develop practical and large-scale EHW.
In contrast to conventional hardware, in which the structure is irreversibly fixed in the design process, evolvable hardware is designed to adapt, as the chameleon changes its color to blend in with the environment, to changes in task requirements or in the environment, through its ability to reconfigure its own hardware structure dynamically and autonomously. This capacity for adaptation, achieved by employing efficient search algorithms known algorithms, has great potential for the development of innovative industrial applications. Although the concept of EHW is relatively new, some EHW chips are already being evaluated for their commercial value. In this article, we introduce four EHW chips currently being developed as part of MITI's Real-World Computing Project; an analog EHW chip for cellular phones, a neural network EHW chip capable of autonomous reconfiguration, a data compression EHW chip for electrophotographic printers, and an adaptive control EHW chip for use in prosthetic hands and robot navigation.
This paper introduces two Evolvable Hardware LSIs for neural network applications. They are developed as part of MITI's Real World Computing Project. One is self-reconfigurable neural network chip for ontogenic neural network processing, having the processing capability equivalent to 10 Pentium II chips. The other LSI is used in the pattern recognition for myoelectric artificial hand control.
This paper describes an Evolvable Hardware (EHW) chip, and the application of this chip as a controller for myoelectric prosthetic hand. The chip consists of Genetic Algorithm (GA) hardware, reconfigurable hardware logic, a chromosome memory, a training data memory, and a 16-bit CPU core (NEC V30). This paper also briefly introduces other EHW chips being developed as part of the Ministry of International Trade and Industry's (MITI) Real World Computing Project (RWCP), which include an analogue EHW chip for cellular phones, a neural networkEHW chip cap able of autonomous reconfiguration, and a data compression EHW chip for electrophotographic printers.
This paper describes the application of genetic algorithms to the biomedical engineering problem of a multi-function myoelectric prosthetic hand controller. This is achieved by an innovative LSI chip (EHW chip), i.e., a VLSI implementation of Evolvable Hardware (EHW), which can adapt its own circuit structure to its environment autonomously and quickly by using genetic algorithms. Usually, a long training period (almost one month) is required before multi-function myoelectric prosthetic hands can be controlled, however, the EHW chip controller developed here can reduce this period and it has been designed for easy implementation within a prosthetic hand. There are plans to commercialize the prosthetic hand with the EHW chip, and the medical department of Hokkaido University has already decided to adopt this for clinical treatment.
This paper describes Evolvable HardWare (EHW) chips which we are developing and some examples of their applications mainly concerning the image data compression for electrophotographic (EP) printer. EHW is a technology which can open up new application fields, since it can flexibly reconfigure the circuit structure to adapt to the environment or the change of environment while the traditional hardware cannot change its functionality. EHW has two remarkable features; adaptability and processing speed. It searches for its optimal circuit configuration using the powerful search procedure such as Genetic Algorithm. Then, we can apply EHW to the application area without the detailed prior knowledge. Moreover, it can run much faster than the software systems because the result of adaptation is implemented on its hardware circuit directly. The data compression EHW chip, whose background and architecture are explained in this paper, is one of the most important applications of EHW. It is developed to be used for the EP printing which is the latest generation technology in the printing and publishing industry. The EP printer requires the very fast and efficient lossless data compression method, or it must have very wide data-buses and large storage devices to support the mass-printing (hundreds sets of hundreds different pages) with high speed (120 MB/sec in the case of 1200 dpi and A4-size). The data compression EHW chip exhibits twice better compression ratio than the international standard method, and processes the data very fast because of the hardware implementation. It compress the target image by adaptive prediction of pixel values as follows: The neighboring image pixels correlate closely with each other, and their values can be predicted by referring the states of their neighborhoods. The accuracy of the prediction strongly influences the compression ratio, because we don't have to code the pixel values predicted correctly in the compressed data. The accuracy depends on the patterns of pixel locations which are referred at the prediction. But the optimal pattern of one image differs from that of another image, and the different regions in one image may have different optimal patterns. Therefore, the EHW chip searches for the optimal pattern in every divided sub-image. In the rest of this paper, three other EHW chips developed in our laboratory are also explained briefly: all-in-one EHW, neuro-EHW and analog EHW. They have special features, and contribute to pioneer the brand-new practical applications, EMG-controlled artificial hand, robot navigation, analog IF filter, and so on. They are considerable evidences to show that EHW is a promising technology of various industry.
This paper describes the GRD (Genetic Reconfiguration of DSPs) chip, which is evolvable hardware designed for neural network applications. The GRD chip is a building block for the configuration of a scalable neural network hardware system. Both the topology and the hidden layer node functions of a neural network mapped on the GRD chips are dynamically reconfigured using a genetic algorithm (GA). Thus, the most desirable network topology and choice of node functions (e.g. Gaussian or sigmoid function) for a given application can be determined adaptively. This approach is particularly suited to applications requiring the ability to cope with time-varying problems and real-time constraints. The GRD chip consists of a 100Mhz 32-bit RISC processor and fifteen 33Mhz 16-bit DSPs connected in a binary-tree network. The RISC processor is the NEC V830 which executes mainly the GA. According to chromosomes obtained by the GA, DSP functions and the interconnection among them are dynamically reconfigured. The GRD chip does not need a host machine for this reconfiguration. This is desirable for embedded systems in practical industrial applications. Simulation results on chaotic time series prediction are two orders of magnitude faster than on a Sun Ultra 2.
In contrast to conventional hardware where the structure is irreversibly fixed in the design process, Evolvable Hardware (EHW) is designed to adapt to changes in task requirements or changes in the environment, through its ability to reconfigure its own hardware structure dynamically and autonomously. This capacity for adaptation, achieved by employing efficient search algorithms known as genetic algorithms, has great potential for the development of innovative industrial applications. This paper introduces EHW chips and six applications currently being developed as part of MITI's Real-World Computing Project; an analog EHW chip for cellular phones, a clock-timing architecture for Giga hertz systems, a neural network EHW chip capable of autonomous reconfiguration, a data compression EHW chip for electrophotographic printers, and a gate-level EHW chip for use in prosthetic hands and robot navigation.
There are increasing demands for high-speed LSIs such as Pentium III(500 MHz) and DEC Alpha (600MHz). However, these fast digital systems have poor yield rates. In early stages of mass production of such LSIs, it is believed that yield rates might be less than 10 %. One of the reasons for poor yield rates is that the timing delays between digital components are not the same as the design specifications. Such discrepancy comes from the variations in the values of parasitic capacitances and resistors along data lines between digital components. Those values differ significantly depending on LSIs. The LSIs that do not satisfy the design specifications are just discarded, leading to poor yields rates. In order to solve this problem, we propose an EHW (EvolvableHardware) -based clock architecture for high speed digital systems. In stead of just discarding the chips that do not meet the specifications, we genetically adjust the clock timings in the LSI and let it satisfy the specifications. We have developed a LSI, which is used in the high-speed memory tester, to show the advantages of the clock architecture. Simulation results show that the number of LSIs which can operate at 800 MHz increases from 2.9 % to 51.1 % after the clock timing circuits are evolved by genetic algorithms. Therefore, this clock architecture is expected to be one of the basic LSI technologies for GigaHz digital systems.
Microwave circuits are indispensable for mobile and multi-media communication. However, these circuits are very difficult to design, because of the nature of distributed-constant circuits in the microwave range (i.e., over 1 GHz). These circuits are also difficult to adjust for optimum performance, even for experienced engineers. These related problems make development costs of microwave circuits very high. In order to overcome these problems, we propose an EHW-based microwave circuit where performance adjustment is carried out automatically by a GA. This new approach of integrating a performance adjustment function within the circuit eliminates many of the design problems with associated these circuits. In this paper, we present an EHW-based image-rejection mixer circuit, which we have developed with this approach, and experimental data that demonstrates that the automatically adjusting circuit is capable of outperforming a circuit adjusted by an experienced engineer.
We have developed a high-speed pattern recognition system using evolvable hardware (EHW). EHW is hardware that can change its own structure by genetic learning for maximum adaptation to the environment. The purpose of the system is to show that recognition devices based on EHW are possible and that they have the same robustness against noise as devices based on an artificial neural network (ANN). The advantage of EHW compared with ANN is the high processing speed and the readability of the learned result. In this paper, we describe the learning algorithm, the architecture, and the experiment involving the pattern recognition system that uses EHW. We also compare the processing speed of the pattern recognition system with two types of ANN dedicated hardware and discuss the performance of the system.
Genetic-algorithm based techniques have been used to successfully calibrate both analogue and digital VLSI chips. This paper investigates the potential of applying the developed techniques to a generic high-speed digital system, which comprises an analogue-to-digital converter and digital logic integrated on a single chip. It is concluded that evolvable calibration techniques are most likely to be applied to VLSI design where the actual value of a variable is critical rather than the more common instance of the variable having to be greater than a given value or the quantity of interest is the ratio of two matched components. Probably the best example of this is delay. As clock frequencies approach 1GHz, variation of buffer delay and clock skew become increasingly important.