How can you insure your code runs with no variability in execution time due to cache?

Question

In an embedded application (written in C, on a 32-bit processor) with hard real-time constraints, the execution time of critical code (specially interrupts) needs to be constant.

How do you insure that time variability is not introduced in the execution of the code, specifically due to the processor's caches (be it L1, L2 or L3)?

Note that we are concerned with cache behavior due to the huge effect it has on execution speed (sometimes more than 100:1 vs. accessing RAM). Variability introduced due to specific processor architecture are nowhere near the magnitude of cache.

Answer 1

Two possibilities:

Disable the cache entirely. The application will run slower, but without any variability.

Pre-load the code in the cache and "lock it in". Most processors provide a mechanism to do this.

Answer 2

Preallocate memory, and make sure interrupts do no affect the cache (impossible, right).

/Allan

Answer 3

It seems that you are referring to x86 processor family that is not built with real-time systems in mind, so there is no real guarantee for constant time execution (CPU may reorder micro-instructions, than there is branch prediction and instruction prefetch queue which is flushed each time when CPU wrongly predicts conditional jumps...)

Answer 4

Understand your worst case runtime for complex operations and use timers.

Answer 5

This answer will sound snide, but it is intended to make you think:

Only run the code once.

The reason I say that is because so much will make it variable and you might not even have control over it. And what is your definition of time? Suppose the operating system decides to put your process in the wait queue.

Next you have unpredictability due to cache performance, memory latency, disk I/O, and so on. These all boil down to one thing; sometimes it takes time to get the information into the processor where your code can use it. Including the time it takes to fetch/decode your code itself.

Also, how much variance is acceptable to you? It could be that you're okay with 40 milliseconds, or you're okay with 10 nanoseconds.

Depending on the application domain you can even further just mask over or hide the variance. Computer graphics people have been rendering to off screen buffers for years to hide variance in the time to rendering each frame.

The traditional solutions just remove as many known variable rate things as possible. Load files into RAM, warm up the cache and avoid IO.

Answer 6

If you make all the function calls in the critical code 'inline', and minimize the number of variables you have, so that you can let them have the 'register' type. This should improve the running time of your program. (You probably have to compile it in a special way since compilers these days tend to disregard your 'register' tags)

I'm assuming that you have enough memory not to cause page faults when you try to load something from memory. The page faults can take a lot of time.

You could also take a look at the generated assembly code, to see if there are lots of branches and memory instuctions that could change your running code.

If an interrupt happens in your code execution it WILL take longer time. Do you have interrupts/exceptions enabled?

Answer 7

If you can get your hands on the hardware, or work with someone who can, you can turn off the cache. Some CPUs have a pin that, if wired to ground instead of power (or maybe the other way), will disable all internal caches. That will give predictability but not speed!

Failing that, maybe in certain places in the software code could be written to deliberately fill the cache with junk, so whatever happens next can be guaranteed to be a cache miss. Done right, that can give predictability, and perhaps could be done only in certain places so speed may be better than totally disabling caches.

Finally, if speed does matter - carefully design the software and data as if in the old day of programming for an ancient 8-bit CPU - keep it small enough for it all to fit in L1 cache. I'm always amazed at how on-board caches these days are bigger than all of RAM on a minicomputer back in (mumble-decade). But this will be hard work and takes cleverness. Good luck!