4. Branch optimisations and code optimisations

Branch Optimisations

Pipelines offer significant speed up if the pipeline can be kept full.

instr A
instr B
if COND
	instr A
	instr B
else
	instr A
	instr B
instr G
instr H

• Delayed branching

  Delayed branching: fetch instructions after the conditional. When executing instr B, we could start fetching instr G since it doesn’t depend on the outcome of the conditional statement.

  Link to original

• Branch prediction

  Branch prediction: ==speculatively fetch the next instruction from one of the branches. We could fetch either instr C or instr E and hope we fetch the correct one. If we guess wrong, data has to be removed from registers==.

  To pick the correct branch (in branch prediction), we can choose a few options: ?

  • We could pick randomly, yielding 50% success rate.
  • Could use static prediction, hence analyse the code at compile-time, yielding 80% success rate on average. (from SPEC analysis)
  • Use dynamic prediction: during run-time keep track of how often each branch is taken and when the conditional is encountered in the future, fetch the most common branch. This does require some training ahead of time.

  Link to original

Code Optimisations

Sometimes performing code optimisations at the software level can yield better results. Some common tips include:

• Use appropriate data types: don’t use say double when int is fine
• Eliminate unnecessary branches: minimise the no. of branches by combining conditions and removing those that will never execute
• Use multiplication instead of division
• Profile programs: identify parts of the program using most CPU time

Compiler Optimisations

In modern high-level languages, the compiler does most of the optimisations for us. Sometimes attempted optimisations may be detrimental, often it’s better to just give the compiler as much information as possible rather than trying to optimising it by hand.