Re: Back End Generators

John Heron <heronj@smtplink.NGC.COM> wrote:
>Another related question is: are there any other discrete
>approximations to optimization that might be applied. Genetic
>algorithms perhaps? I'm not totally sure what they are. I looked at a
>book once, and I remember saying to myself "This looks like AI stuff,
>I'm not interested." Maybe, my loss!


There are a few things from Genetic Algorithms (GAs) and its subfields
such as Genetic Programming (GP) which may interest you.


Peter Nordin [1], has a system in which he evolves machine code to
perform the task of a Neural Network. Tom Ray [2] was one of the
first to start (or gain notice for) evolving some form machine code in
his Tierra system. Ray found that some individuals in the population
were able to evolve code that unrolled loops. Currently, Tierra has
been extended to parallel simulations on the CM-5 by Kurt Thurling of
TMC.


Steven J. Beaty of Cray Computer has done work on instruction
scheduling with GAs [3].


Ranora Ryder (trin0008@sable.ox.ac.uk) wrote recently in
comp.ai.genetic on work that his group had done on evolving players
for CoreWar, but went on to say:


> Our recent work has been directed to evolving RISC machine
>code into programs to do trivial (to us) programming problems. We
>felt it best to resort to a para-code which translates into RISC
>machine code but the para-code can be more flexible and less
>contrived than the para-code for Corewars (Redcode). The results
>look favourable and the method has the capacity to surprise it's
>writers. Many old chestnut techniques of m-code optimisation have
>been rediscovered eg better addition chains for {1,2,3,4,...N-1}^e
>mod N where e is constant and e>14 see Knuth vol 1 or 2. New
>surprising and non-intuitive optimisations have been discovered so
>the method has the 'What the hell is going on? I didn't program
>this!' factor. We are still some way off evolving a better word
>processor unfortunately! Evolving RISC m-code is fast as it can be
>executed directly and for many problems it it easy to find a nice
>fast fitness function. I recomend it.


If anyone else has information on ideas similar to this, I would
appreciate hearing them, and my apologies if I am completely off-track
here.


Mark


References:


[1] Peter Nordin, ``A Compiling Genetic Programming System that
Directly Manipulates the Machine Code.'' in Advances in Genetic
Programming, ed. K. E. Kinnear, Jr., MIT Press, 1994.


[2] Thomas S. Ray, ``An Evolutionary Approach to Synthetic Biology:
Zen and the Art of Creating Life.'' Artificial Life (1)1/2, 1994, MIT
Press. This is new journal, and this paper will give refs to other
pieces of work Ray has done.


[3] Beaty's works are on mostly online:
http://www.craycos.com/~beaty/vitae.html
--
Mark D. Smucker --- smucker@cs.wisc.edu
Department of Computer Sciences, University of Wisconsin-Madison
--

Return to the comp.compilers page.
Search the comp.compilers archives again.