Evolving Machine Microprograms

The realization of a control unit can be done using a complex circuitry or microprogramming. The latter may be considered as an alternative method of implementation of machine instructions that can reduce the complexity and increase the flexibility of the control unit. The microcode efficiency and speed are of vital importance for the computer to execute machine instructions fast. This is a difficult task and it requires expert knowledge. It would be interesting and very helpful to have automated tools that, given a machine instruction description, could generate an efficient and correct microprogram. A good option is to use evolutionary computation techniques, which have proved been effective in the evolution of computer programs. In this paper, we intend to show how evolutionary computing techniques could be used to face this problem of generating efficient microprograms. We have developed a microarchitecture simulator of a real machine in order to evaluate an individual and to assign it the fitness value (to determine whether this candidate solution correctly implements the instruction machine). The proposed method is successful in generating correct solutions, not only for the machine code instruction set, but for new machine instructions not included in such set. We have shown that our approach can generate microprogramms to execute (to schedule microinstructions) the machine level instructions for a real machine. Moreover, this evolutive method could be applied to any microarchitecture just by changing the microinstruction set and pre-conditions of each machine instruction to guide evolution.

The poster, the source code of the proposed method and the full-length paper are available for download at http://atc.ugr.es/pedro/ev-micropr

Advertisements

Automatic Generation of XSLT Stylesheets Using Evolutionary Algorithms

Finally I’m going to be present in the Mankind History after my first publication in an international conference! It just a poster, but it’s still quite cool. It was presented in the GECCO’08 Conference, in  Atlanta, where some intrepid GeNeura members drank a lot  of Coca-Cola, even the (suspicious) beer flavoured Coca-Cola.

Here is the abstract:

This paper introduces a procedure based on genetic programming to evolve XSLT programs (usually called stylesheets or logicsheets). XSLT is a general purpose, document-oriented functional language, generally used to transform XML documents or, in general, solve any problem that can be coded as an XML document. The proposed solution uses a tree representation for the stylesheets as well as diverse specific operators in order to obtain, in the studied cases and a reasonable time, a XSLT stylesheet that performs the transformation.

You can download the draft from here, or the poster from here. The poster is orange, perfect for these summer days ;)

Now I am preparing my suitcase in order to go to the PPSN conference in Dortmund, where I will present an improvement of this algorithm.

Pablo