	MILEPOST
	Machine Learning for Embedded Programs Optimisation

RESOURCES

A Beginner's Guide To Milepost:

For those of you who have little knowledge about compiler technology, the following FAQs will hopefully help you to understand the idea behind the Milepost project.

Q1. What is the Milepost project aim?
Q2. Why is the research important?
Q3. What is meant by machine learning?
Q4. What is the role played by machine learning?
Q5. What is a compiler?
Q6. What is a platform?

Q7. What is a processor?
Q8. What’s meant by modular and extensible?
Q9. What is meant by “reconfigurable heterogeneous” in terms of embedded processors?
Q10. What is meant by an embedded processor?

Q11. What is meant by optimisation?
Q12. What is meant by a heuristic?
Q13. What do each of the partners do?
Q14. What is a benchmark?
Q15. What is a SIMD unit?

Q1. What is the Milepost project aim?
The research aim of this project is to develop a compiler approach that can both improve its performance over time and that can automatically learn how best to optimise programs for reconfigurable heterogeneous embedded processors.
The goal is to develop a modular, extensible, self-optimizing compiler that automatically learns the best optimization heuristics based on the behaviour of the platform.

Q2. Why is the research important?
The research is necessary because current compiler technology can not keep up with architectural change and the embedded environment is continually changing. Furthermore, time-to-market is crucial because of competition. Tuning the compiler has to be fast.
This method of development is in contrast to the handcrafted approach to developing compilers, which is no longer sustainable because with each generation of reconfigurable architecture the compiler development time increases and the performance improvement achieved decreases.

Q3. What is meant by machine learning?
One can use machine-learning techniques to improve the functionality of the compiler.

Machine learning is about choosing the right options - this means that the compiler learns how best to produce the right sequence of code from previous compilations and executions. In other words, machine learning is used to predict behaviour.

Machine learning is about the compiler tuning itself automatically and thereby reducing compiler development time. Machine learning can therefore be used to simplify the life of the compiler developer.

One uses machine learning to better understand what programs do – this can lead to better optimisations.

Q4. What is the role played by machine learning?
Machine-learning techniques are at the heart of the Milepost project.

The Milepost GCC is a machine-learning-based compiler that automatically adjusts its optimization heuristics to improve the execution time, code size or compilation time of specific programs on different architectures.

Q5. What is a compiler?
A compiler is a piece of software that is used to translate program languages (high level languages), e.g. C++, Java, Fortran, into binary code (a series of 1s and 0s) - the language that machines, i.e. computers, can read and understand.
A compiler is just a piece of software, a program.
Compilers aim to make programs run faster and become energy efficient.
Compilers typically optimise problems.

Q6. What is a platform?
This is the target machine that receives the binary code, e.g. a mobile phone or an ARC 725D processor, or a Power PC.
A platform is the same as a processor.

Q7. What is a processor?
A processor is a chip (piece of hardware) found inside the machine. Types of processors include Intel Pentium or Power 1,2,3,4,5 or 6 (IBM).
A processor reads the binary code and executes it.

Q8. What’s meant by modular and extensible?
Modular implies that the compiler consists of small modules containing the compiler’s own code.
Extensible means the ability to add in more modules – this could be useful for new options for code translation.

Q9. What is meant by “reconfigurable heterogeneous” in reconfigurable heterogeneous embedded processors?
The word “heterogeneous” applies to multi-core platforms (where there is more than one processor). It means that the processors have different designs to do different tasks.
Reconfigurable means that small changes can be made to a processor in order for it to work faster or become more energy efficient, e.g. by adding new components to the processor.

Q10. What is meant by an embedded processor?
Embedded processors are the chips that are found in various devices, e.g. in mobile phones. The embedded processor chip in mobile phones is small and not very powerful, so machine learning is more applicable to use in these devices in order to make the chip more energy efficient and powerful.

Code translation process
The source (application) code is a computing language like Java, C++ code, etc.
GCC = a very complex piece of code – around 1 million lines of code for translating application code into binary!

The front end of the compiler reads the application (source) code.
The back end translates the code to the format the processor wants. The back end of a compiler has been very well studied. There can be more than one back end in a compiler. The area between the two ends is the area for optimisation. This is the area Milepost is concerned with. It can take about 50 man years to create a compiler

Optimisation box in detail:
The diagram below shows five modules and six translation paths. An optimisation box can contain more than 100 modules.

Q11. What is meant by optimisation?
Optimisation is all about improving the end results – i.e. the binary.
Translating C code into binary code is easy and not complicated, but what is complicated is the optimisation, i.e. to make this translation produce a binary output that consists of the fewest steps possible.
- Optimisation helps to reduce the number of steps in the binary code.
- Binary code is complex instruction broken down into simple steps for the processor to follow.
- There can be about 200 optimisations in a GCC compiler.
- Each optimisation box has its own heuristics.
- Binary code is transmitted to a processor, which then processes the code instructions, so ultimately one wants the binary code produced to be as fast as possible because the faster the code runs, the more the processor can do. Better optimisation heuristics can help improve the code. This is the idea behind machine learning.

Q12. What is meant by a heuristic?
Heuristics are approximate solutions to finding a good optimisation, i.e. the right rules for generating an output (as binary code) that suits the machine, the processor and the source code.
They are a trial and error method and usually involve an algorithm (a mathematical formula – a small piece of code).
There is no guarantee of finding the “right” optimisation, but with machine learning you can find a “good” optimisation as it involves training the compiler. It is very difficult to design heuristics to choose the right optimisation

Q13. What do each of the partners do?
Edinburgh – develops the technology to enable compilers to learn how best to optimize.
INRIA – develops technology for statistical collective optimization and run-time adaptation; develops MILEPOST software infrastructure and database for storing the code, the switches and the results.
ARC – provides the technology to improve their compiler and the embedded platform to target.
IBM – describes the essential features of a program in a way that allows learning to occur.
CAPS – looks at novel techniques to analyse the code (which is split into two parts) using heterogeneous parallel processors.

Q14. What is a benchmark?
A benchmark is an application (e.g. a program that can play a DVD).

Q15. What is a SIMD unit?
A SIMD unit is a piece of hardware that does many things.