Software Optimization Techniques #1: An Introduction To Optimizing Embedded Software

2011-01-21

This week we begin a series of blog posts on optimizing embedded software with the aim of improving (i.e. reducing) worst-case execution times.

Software optimization techniques which improve worst-case execution times #1: An Introduction To Optimizing Embedded Software

Most textbooks teach a style of programming that is suited to writing general-purpose programs. Typically the chapters on code optimisation discuss techniques aimed at making the program ‘run faster’, with the emphasis on improving the average case execution time.

However, if you’re developing for real-time systems, you need to consider the longest time the software takes to run. In this situation, you need to look at reducing worst-case rather than average case execution times.

Improvements in WCET can be achieved by removing variability from the program. The most obvious way to remove variability is to engineer software with a single path through the code.

Optimization techniques:

Improve the efficiency of the code
Remove code from the worst-case path
Reduce variability (also helps to reduce complexity)

What to look out for when optimizing embedded systems software:

Execution times are the only effective method of comparing different implementations. Sometimes code structures or algorithms that are expected to be faster turn out to take longer than a simple implementation. This is particularly true for code running on advanced microprocessors. Therefore, you need to measure on the same platform you intend to deploy.
Devising smarter high-level algorithms and implementations usually brings bigger gains than low-level code optimisation. Once a better algorithm has been found, then if necessary, there will still be scope for low-level improvements.
Optimisations that work well on one microprocessor may result in very long execution times on another. To do an effective job of code optimisation it is necessary to have a good understanding of what basic operations the target processor can perform efficiently and what strategies the compiler uses for producing efficient code.
Using appropriate compiler optimisation switches can make a significant difference to execution times without requiring code modifications. It is therefore recommended that compiler optimisations be fully explored prior to any code changes being made.