Honours/Masters Projects
Evolving functions in Point-Free form using Grammatical Evolution
Problem Domain
Grammatical Evolution (GE) is a technique for evolving programs to
fit a given application. Unlike traditional Genetic Programming (GP)
GE is guaranteed to produce syntactically correct candidate programs.
One challenging problem in GP is the evolution of programs that contain
function definitions that can be called in multiple parts of the program.
Some very recent research has achieved promising results by using GE
to evolve functions into the grammar of the programming language along
with each candidate program.
Project Description
This project aims to build on existing work by using GE to evolve
functions into point-free programs. Point-free programs do not have
named variables but instead, use functions to transmit data between
functions that produce data and functions that consume data. In point-free
programs, there are natural mechanisms for calling a function with multiple
sets of data. However, the number of other choices available in the point-free
grammar makes the selection of such mechanisms unlikely during a simple
GE process. This project aims to tackle this problem by evolving the weights
of grammar selection along with individuals to increase the likelihood of
of the evolution of functions with multiple use.
Plan
This project will extend on existing work which has produced promising
results for one stage of the optimiser so far. The language expressing the
the optimiser is Stratego XT a rewriting language where rewrite rules
are kept separate from strategies for applying them. The platform currently
used for GE is GE Lib. This project will first aim to establish
the minimum sized building blocks from which it is feasible to evolve
the an optimiser. It also aims to extend the optimiser to tasks such
as commmon sub-expression elimination. The performance of the optimiser
will be benchmarked against the performance of existing hand-written
optimiser code.
Meta-Analysis for Compiler Instrumentation
Problem Domain
Most compilers are quite opaque - that is - it is difficult
to look inside them as they are working to see what they are doing.
This lack of transparency is a disadvantage in terms of debugging
for correctness and performance. This problem can be overcome
if the compiler is written in terms of sequences of simple transformations.
Compilers written this way can be traced through the whole sequence
of transformations, making it easier to track down where improvements
are needed. Unfortunately such tracing, currently,
requires the addition of trace
statements throughout the compiler definition which lengthens the code,
making it harder to maintain and understand.
Project Description
This project is to take an existing small compiler, written
in Stratego XT, and write another Stratego application to transform
it so that it produces a trace. This application of meta-analysis to
transform the compiler code will allow the tracing version of the
compiler to keep pace easily with the development of the standard
version and substantially reduce the cost of creating a tracing
compiler.
Plan
The initial part of this project will work on a small version
of the compiler to establish what is required of the compiler
to make the addition of tracing statements easy whilst still
keeping the design of the compiler elegant. The second stage
of the project will apply the meta-analysis to progressively
larger versions of the compiler, fine-tuning the process
as the project progresses.
Honours projects
Evolving an Optimiser via Grammatical Evolution
Problem Domain
Program optimisers are difficult to build and difficult to get correct.
To compound this problem,
increasingly complex machines and runtime environments are making
it difficult for the author of optimisers to guess the best settings
for optimisation. To tackle this problem, researchers have used
techniques such as iterative compilation to evolve good settings
for simple, quantifiable, optimisations such as loop unrolling and
loop tiling. However, because of the overriding need for correctness,
there have been few attempts to evolve the actual code of an optimiser.
Project Description
This project aims to extend current experiments to evolve an
optimiser for a simple language using Grammatical Evolution (GE).
GE is a Genetic Programming (GP) technique where a population of
candidate programs is evolved with the help of a fitness function
to determine the goodness of a program. GE helps this process
by ensuring that each candidate program is at least syntactically correct.
In this project, the soundness of the candidate optimisers is ensured
by building each optimiser out of a set of existing simple,
correctness-preserving, modules and strategies for combining them.
Plan
This project will extend on existing work which has produced promising
results for one stage of the optimiser so far. The language expressing the
the optimiser is Stratego XT a rewriting language where rewrite rules
are kept separate from strategies for applying these rules.
The platform currently
used for GE is GELib. This project will first aim to establish
the minimum sized building blocks from which it is feasible to evolve
the an optimiser. It also aims to extend the optimiser to tasks such
as commmon sub-expression elimination. The performance of the optimiser
will be benchmarked against the performance of existing hand-written
optimiser code.
Parallelizing Point-Free Form
Problem Domain
Various design optimisations traditionally used to make
sequential processors faster are starting to run into hard
limits. As a result, manufacturers are now producing
machines with multiple cores on each chip. For single applications,
such machines can
only be properly exploited by parallel code. Unfortunately,
traditional languages and compilers are not particularly good
at producing highly parallel code from ordinary programs.
There is a need for languages and compilers that make it easy
for the programmer to express parallel algorithms while handling
the details of mapping the algorithm to the parallel machine.
Project Description
This project is to build part of a compiler that maps
a relatively simple source language into an intermediate representation,
called point-free form and, thence, on to a parallel machine. Point-free
form is a programming language where the role of variables is replaced
with functions for transporting data between functions that produce
and consume data. Currently, a translator from the source language
to point-free form and an optimiser for point-free form have been built.
The task for this project is to take this optimised point-free form
and map it to a highly parallel machine.
Plan
The plan for this project is to encode and extend an existing set
of parallelisation rules to map sequential point-free form into
parallel point-free form. After this, the second stage is to map
the parallel point-free code into parallel code expressed in C and
MPI. This code will then be run and benchmarked on a very fast cluster
of chip multi-processors. The work will be carried out longitudinally,
with a small part of the language parallelised and mapped to C-MPI at
each stage. In this way, performance results can be quickly measured
and the approach refined.
Mapping Point-Free Programs to Parallel Hardware
Project Description
Point-Free programs, programs consisting entirely of functions, directly link operations that produce and consume data. Very often, point-free programs are implicitly parallel. This mixture of explicit communication and parallelism makes point-free programs good potential candidates for mapping to custom parallel hardware. This project is an initial exploration of the process of mapping simple point free code into custom parallel hardware on an FPGA.
Plan
The initial aim of this project is to create a small range of applications on an FPGA and measure their performance. The next stage is to manually define and test hardware descriptions corresponding to the basic constructs in point-free form. The remainder of the project will be devoted progressively defining and testing automatic translations of each point-free construct to a hardware description. Since this project is new and exploratory the emphasis will be on dividing the work to generate short test cycles and evolve the research goals according to the results obtained.
Brad Alexander Jan 2008
|
The University of Adelaide
