Abstract
The topic for this dissertation is the optimisation of computer programs, as they are being
compiled, using discrete optimisation techniques. The techniques introduced aim to
optimise the runtime performance of programs executing on certain types of processors.
A very important component of this dissertation is the movement of complexity from the
processor to the compiler. Therefore both computer architecture and compilers are important
supporting topics. The data output of the compiler is processed using information
about the processor to produce execution information which is the goal of this dissertation.
Concepts related to instruction level parallelism are covered in two parts. The first part
discusses implicit parallelism, where parallel instruction scheduling is performed by the
processor. The second part discusses explicit parallelism, where the compiler schedules
the instructions. Explicit parallelism is attractive because it allows processor design to be
simplified resulting in multiple benefits.
Scheduling the instructions to execute while adhering to resource limitations is the area
of focus for the rest of the dissertation. In order to find optimal schedules the problem is
modelled as a mathematical program. Expressing instructions, instruction dependencies
and resource limitations as a mathematical program are discussed in detail with several
algorithms being introduced. Several aspects prevent the mathematical programs from
being solved in their initial state, therefore additional techniques are introduced.
A heuristic algorithm is introduced for scheduling instructions in a resource limited environment.
The primary use of this heuristic is to reduce the computational complexity of
the problem. However, this heuristic algorithm can be used to generate good schedules
on its own.
Finally information regarding a practical implementation of a compiler that implements
the introduced techniques is introduced as well as experimental results. The experimental
results are generated from a series of test programs illustrating the complete process and
the computational complexity of the algorithms employed.
Smith, T.H.C., Prof.