Investor Relations

10 pages
7 views

Quo Vadis evolvable hardware

Please download to get full document.

View again

of 10
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Quo Vadis evolvable hardware
Transcript
  QuoVadisEvolvableHardware? Moshe Sipper, Daniel Mange, and Eduardo Sanchez From Darwin to Darware:Why computer engineers have started listening to Mother (Nature).  W  hether one looks outside the window or stands infront of a mirror, nature’s work is evident in all itsglory. Be it a pine tree, a flea, or a human being,nature has designed highly complex machines, theconstruction of which is still well beyond our cur-rent engineering capabilities. Nature is the grandest engineer known to man—thougha blind one at that: her designs come into existence through the slow process, over mil-lions of years, known as evolution by natural selection [2]. As put forward by CharlesDarwin in his 1859 masterpiece, On the Origin of Species  , evolution is based on “...onegeneral law, leading to the advancement of all organic beings, namely, multiply, vary, letthe strongest live and the weakest die.’’ [1]. 50  April 1999/Vol. 42, No. 4 COMMUNICATIONSOF THE ACM  The evolutionary process is based on four basicprinciples: • Individual organisms vary in viability in the envi-ronments that they occupy. • This variation is heritable. • Individuals tend to produce more offspring thancan survive on the limited resources available in theenvironment. • In the ensuing struggle for survival, the individuals best adapted to the environment arethe ones that will survive to reproduce. The continual workings of this process over the millennia cause populations of organisms tochange, generally becoming better adapted to theirenvironments.Evolution has not only produced ingenious solu-tions to specific problems—for example, structuraldesigns such as eyes or wings—but indeed has found(and founded) entirely new  processes  to aid in theemergence of complex organisms. Two of the mostimportant ones are ontogeny and  learning  .Most natural organisms consist of numerous ele-mental units called cells (for example, a humanbeing is composed of approximately sixty trillion cells). Eachand every cell con-tains the entire plan of theorganism, known as the  genome  : a one-dimensional chain of deoxyribonu-cleic acid (DNA) that contains theinstructions necessary for the making of theindividual. Known also as multicellular organisms,they develop through the process of ontogeny, which involves the successive divisions of a fertilizedmother cell, ultimately resulting in a completebeing. The genome—or  genotype  —thus gives rise tothe so-called  phenotype  : the mature organism thatemerges from the ontogenetic process. The geno-type-phenotype distinction is fundamental innature: while it is the phenotype that is subjected tothe survival battle, it is the genotype that retains theevolutionary benefits.Ontogeny can be viewed as one of nature’stricks for combating the information explosioninherent in the definition of a complex design:rather than define a one-to-one plan (a homuncu-lus), nature uses a compressed definition that ismore akin to a recipe or a construction program.Further compression can be attained by introduc-ing the process of learning. The organism thatemerges from the ontogenetic process is not fully equipped to handle every aspect of its daily exis-tence, but rather proceeds to improve its behaviorby learning how to cope with new situations asthey are encountered (this is most notable among mammals). The introduction of learning reducesthe amount of information that needs to beencoded in the genome.Over the past few years a growing number of computing scientists and engineers have been turn-ing to nature, seeking inspiration to augment thecapabilities of their artificial systems. In a recentpaper [10], Sipper et al. noted that such bio-inspired  systems can be partitioned along three axes, corre-sponding to the three processes mentionedpreviously: phylogeny (evolution),ontogeny, and epigenesis (learning); they dubbed this the POE  model. Whileresearch in this area can be traced back tothe 1950s, when the first computers were used to carry out simulationsbased on these ideas, much of therecent work is centered on the con-struction of actual hardwaredevices.The ultimate goal of bio-inspired system engineers is to create more adaptive systems, in which “adaptive” refers to a system’s ability to undergo modifi-cations according to changing circum-stances, thus ensuring its continuedfunctionality. One often speaks of an envi-ronment and of a system’s adjustment to changing environmental conditions. The fact that hardwareevolves is perhaps not surprising in and of itself,after all, the Intel 80  x  86 “species’’ evolved from a mere 29,000 transistors in 1978 (the 8086) to7,500,000 transistors in 1997 (the Pentium II), notto mention the many functionalities that have beenadded over the years. 1 Thus, the processor hasadapted to its environment, which is, ultimately, theusers. This evolutionary process involves what issometimes referred to as the “hand of God’’: theengineer who designs the chip. With bio-inspiredhardware the aim is to reduce the amount of humandesign necessary. The ultimate goal is to build a sys-tem that will evolve, develop (in an ontogeneticsense), and learn—in short, adapt—on its own, thatis, with no human intervention. As an example, 1 Intel chip history: www.visionbs.com/intel.htm COMMUNICATIONSOF THE ACM  April 1999/Vol. 42, No. 4 51  52  April 1999/Vol. 42, No. 4 COMMUNICATIONSOF THE ACM imagine some future chip family that evolves on itsown from the “8086’’ epoch to the “Pentium’’epoch. Obviously, it will need to be equipped withthe ability to accrue additional material resources (as with natural evolution); what is far from obvious atthis point is how to induce this kind of ability. Insummary, we want to replace the human engineer with a blind yet potentially more powerful one.There is still a long road to travel before we cancreate an autonomously evolving system. Our intentin this article is to describe a number of currentmilestones, and to trace some of the possible devel-opments of the near future. From Carbon to Silicon: Configurable Circuits  Within the field of bio-inspired hardware, a majorenabling technology is that of configurable circuits,and especially field-programmable gate arrays, orFPGAs. FPGAs, which have been coming of ageover the past few years, are large, fast integrated cir-cuits that can be modified or configured at almostany point by the end user [12]. The primary distinction that this technology brings about is that between  programmable  circuitsand configurable  ones [7]. A programmable circuitceaselessly iterates through a three-phase loop, wherean instruction is first  fetched  from memory, after which it is decoded  , then to be passed on to the final execute  phase. The execute phase may require severalclock cycles; the process is then repeated for the nextinstruction, and so on. A configurable circuit, on theother hand, can be regarded as having a single, non-iterative fetch phase: the so-called configurationstring  , fetched from mem-ory, requires no furtherinterpretation, and isdirectly used to configurethe hardware. No furtherphases or iterations areneeded, as the circuit is now configured for the task athand. The ability to controlthe hardware in such a directmanner is a double-edgedsword: the user is able toaccess a much wider rangeof functionalities, with theprice to be paid being a more arduous design task. Within the domain of configurable computing one can distinguish betweentwo types of configurationstrings: static and dynamic [7]. A static configura-tion string, aimed at configuring the circuit to per-form a given function, is loaded once at the outset,after which it does not change during the executionof the task at hand. Static applications are mainly aimed at attaining the classic goal in computing:that of improving performance, either in terms of speed, resource utilization, or area usage. Dynamicconfigurability involves a configuration string thatcan change during execution of the task at hand.Dynamic systems are able to undergo modificationsaccording to changing circumstances, thus continu-ing to function within their dynamic environments. As such, they represent an excellent substrate forimplementing the adaptive systems discussed in thisarticle. Figure 1. The Firefly evolware board. The system is an evolv-ing, one-dimensional, non-uniform cellular automaton. Each of the 56 cells contains a genome that represents its rule table;these genomes are initialized randomly, to be subjected toevolution. The board contains the following components: (1)LED indicators of cell states (top), (2) switches for manuallysetting the initial states of cells (top, below LEDs), (3) XilinxFPGA chips (below switches), (4) display and knobs for con-trolling two parameters (‘time steps’ and ‘configurations’) of the cellular programming algorithm (bottom left), (5) a syn-chronization indicator (middle left), (6) a clock pulse genera-tor with a manually adjustable frequency from 0.1Hz to 1MHz(bottom middle), (7) an LCD display of evolved rule tablesand fitness values obtained during evolution (bottom right),and (8) a power-supply cable (extreme left). (Note that thelatter is the system’s sole external connection.)  Two Examples of Current-Day Bio-Inspired Hardware In the following section we will describe twodynamic systems inspired by two of the processesoutlined previously: evolution and ontogeny. Learn-ing hardware, as well as more in-depth expositions of the systems discussed herein can be found in therecent book by Mange and Tomassini [4].  Evolving hardware: The Firefly machine. Theidea of applying the biological principle of naturalevolution to artificial systems, introduced more thanfour decades ago, has experienced impressive growthin the past few years. Usually grouped under the term evolutionary algorithms or evolutionary computation ,are the domains of genetic algorithms, evolutionstrategies, evolutionary programming, and geneticprogramming [6]. As a generic example of artificialevolution we consider genetic algorithms. A genetic algorithm is an iterative procedure thatinvolves a constant-size population of individuals,each one represented by a finite string of symbols—the genome—encoding a possible solution in a givenproblem space. This space, referred to as the searchspace, comprises all possible solutions to the prob-lem at hand. The algorithm sets out with an initialpopulation of individuals that is generated at ran-dom or heuristically. In every evolutionary step,known as a generation, the individuals in the currentpopulation are decoded and evaluated according tosome predefined quality criterion, referred to as thefitness function. To form a new population (the nextgeneration), individuals are selected according totheir fitness and transformed via genetically inspiredoperators, of which the most well known are crossover (“mixing’’ two or more genomes to formnovel offspring) and mutation (randomly flipping bits in the genomes). Iterating this evaluation-selec-tion-crossover-mutation procedure, the genetic algo-rithm may eventually find an acceptable solution,that is, one with high fitness.Evolutionary algorithms are common nowadays,having been successfully applied to numerous prob-lems from different domains, including optimiza-tion, automatic programming, circuit design,machine learning, economics, immune systems,ecology, and population genetics, to mention a few.One of the recent uses of evolutionary algorithmsis in the burgeoning field of evolvable hardware, which involves, among others, the use of FPGAs asa platform on which evolution takes place [8, 10].The Firefly machine is one such example; our goal inconstructing it was to demonstrate a system in which all evolutionary operations (fitness evaluation, selec-tion, crossover, and mutation) are carried out online  ,that is, in hardware [9, 10]. Firefly is based on the cellular automata model, a discrete dynamical system that performs computa-tions in a distributed fashion on a spatially extendedgrid [9]. A cellular automaton consists of an array of cells, each of which can be in one of a finite numberof possible states, updated synchronously in discretetime steps according to a local, identical  interactionrule. The state of a cell at the next time step is deter-mined by the current states of a surrounding neigh-borhood of cells. This transition is usually specifiedin the form of a rule table, delineating the cell’s nextstate for each possible neighborhood configuration.The cellular array (grid) is n -dimensional, where n =1, 2, 3 is used in practice. Here, we consider a one-dimensional grid, in which each cell can be inone of two states (0 or 1), and has three neighbors(itself, and the cells to its immediate left and right);the rule table thus comprises eight bits since thereare eight possible neighborhood configurations.Non-uniform cellular automata have also been con-sidered; for these the local update rule need not beidentical for all grid cells [9].Based on the cellular programming evolutionary algorithm [9], we implemented an evolving, one-dimensional, non-uniform cellular automaton. Each COMMUNICATIONSOF THE ACM  April 1999/Vol. 42, No. 4 53 The ultimate goal  of bio-inspired system engineers is to create more adaptive systems, in which “adaptive” refers to a system’s ability to undergo modifications according to changing circumstances, thus ensuring its continued functionality.  of the system’s 56 binary-state cells contains a genome that represents its rule table. These genomesare initialized at random, to be subjected to evolu-tion. The system must evolve to resolve a global syn-chronization task: upon presentation of a randominitial configuration of cellular states, the cellularautomaton must reach, after a bounded number of time steps, a configuration whereupon the states of the cells oscillate between all 0s and all 1s on succes-sive time steps (this may be compared to a swarm of fireflies, which evolve over time to flash on and off in unison). Due to the local connectivity of the sys-tem, this global behavior—which involves the entiregrid—represents a difficult task. Nonetheless, by applying cellular programming, the system evolves(that is, the genomes change) such that the task issolved. The machine is depicted in Figure 1.The Firefly machine exhibits complete onlineevolution; all its operations are carried out in hard- ware with no reference to an external computer.This demonstrates that evolving ware, or evolware  ,can be constructed [9]. Such evolware systems per-mit enormous gains in execution speed (for exam-ple, Firefly runs 1000 times faster than a simulationon a high-performance workstation). While thesynchronization task is not a real-world applicationand was selected to act as a benchmark problem forour evolware demonstration, Firefly does open upinteresting avenues for future research. Evolwaremachines that operate in an autonomous mannercan be used to construct autonomous mobile robots,as well as for the constructionof controllers for noisy,changing environments [10]. Ontogenetic hardware:The BioWatch. The BioWatchis one of the applicationsdesigned as part of the Embry-onics (embryonic electronics)project, whose final objective isthe development of very large-scale integrated circuits, whichare capable of self-repair andself-replication [3, 4]. Thesetwo bio-inspired properties,characteristic of the living  world, are achieved by trans-posing certain features of cellu-lar organization in nature ontothe two-dimensional world of integrated circuits in silicon.The BioWatch is an artificial “organism’’ designedto count minutes (from 00 to 59) and seconds (from00 to 59); it is thus a modulo-3600 counter. Thisorganism is one-dimensional and is comprised of four cells with identical physical connections and anidentical set of resources. The organization is multi-cellular (as with living beings), with each cell realiz-ing a unique function, described by its gene (seeFigure 2a).The genome is the set of all the genes of theBioWatch, and each gene is a sub-program, charac-terized by a set of instructions and by its horizontalcoordinate  X   . Storing the whole genome in each cellrenders the cell universal, that is, capable of realizing any gene of the genome. This is another bio-inspired property: each of our (human) cells alsocontains the entire genome, though only part of it isused (for example, liver cells do not use the samegenes as muscle cells). Depending on its position inthe organism, each cell interprets the genome,extracting and executing the gene that configures it.The BioWatch thus performs what is known in biol-ogy as cellular differentiation (see Figure 2b).Self-repair of an artificial organism allows partialreconstruction of the srcinal device in case of a  54  April 1999/Vol. 42, No. 4 COMMUNICATIONSOF THE ACM 234X= 1 Countmod 10Countmod 6Countmod 10Countmod 6 Figure 2a. Multicellular organization of the BioWatch. 6X= 123410610610610610610610610 Figure 2b. Cellular differentiation of the BioWatch. 555(5) 42(3)(4) 3X= 1 mod6mod10mod6mod10 Spare partsOriginal counter New counterNew counter Faulty cell   Figure 3. Self-repair of the BioWatch. Old coordinates areshown in parentheses.
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x