Identifying system events affecting timing behavior of an application

Question

Q: What are those events (system level and architecture level) that can cause an application to take longer to terminate and complete the job?

My question is purely in the context of Worst Case Execution Time (WCET) analysis.

I have gathered a short list of events, which I think are the contributors to WCET of an application, by utilizing some knowledge about computer-architecture:

• A wrong branch prediction
• Cache misses
• Pipleline stalls
• Fetch related delays
• . . .

I would like to enrich this list both in breadth and length. So any addition to the list of such events or the details of how any particular event causes a delay is most welcomed.

P.S. If my question if not well formulated, please do help me to improve.

Answer 1

You forgot the most obvious factor: the input of the program. The time taken by a program heavily depends on the input unless it does not have any input or the input comes from a small fixed set.

Other factors can be classified into two classes: 1) Internal factors and 2) External factors.

Internal factors:
1) Input
2) Waiting for I/O
3) Waiting for System resources like memory/semaphores etc.
4) How effectively memory is cached in CPU (may be different for different runs, what you have termed as cache misses.)
5) Disruptions in instruction pipeline
6) Interactive events
7) If the process needs to swap in/out some pages to swap area
8) If the process uses other hardware such as graphics card/audio/network
9) Hardware interrupts from graphics card/audio/network
10) Clock interrupts
11) Scheduler running
12) If the process is multi-threaded, then delays because of thread switching
13) If the process is multi-core and you need to share data between core, delay depends on the architecture of the CPU

External factors:
1) Multiprocessing (the biggest culprit)
2) Priority of the process
3) Context switching
4) Operating System preemptions
5) Hardware errors and service interruptions (of course)
6) Communication with other processes
7) Communication with other processes in other machies
8) Input that is not readily available, (it is available as a stream)

We need to have a good guess of running time of a process for majority of scheduling algorithms and for real-time systems. But a perfect calculation is simply impossible in real cases. The usual practice is to run the process for typical (or typically worse) case input many times, make a guess and then over estimate it. This is done even in real-time system, if I understand correctly. In quite a few real-time systems the running process quite arbitrarily demands a guarantee of what it thinks is the over-estimated time it will take to finish the computation.

Answer 2

I'd agree that your list includes many items that can cause execution to lengthen. But those are all directly related to the execution of the application code itself.

Also consider events which have nothing directly to do with the application itself such as:

Context Switching: IF another process is allowed to preempt your application, there is a cost to saving and restoring your process's state, not to mention the unknown time that the other process will run. Your scheduling algorithm will determine if this is a cost and steps that can be taken to control it.

Device interrupts - usually the process being interrupted is still considered the current process, but system level interrupt handling code is the code running. The current process waits until the interrupt is handled and a Return from Interrupt instruction restores the process state and process instructions resume. Interrupts can occur at "random" intervals and it is difficult to accurately predict the effect on any given run of a process. It's possible to measure average numbers of interrupts and interrupt stack time on some systems and use those averages. Time spent in individual interrupt routines is largely dependent upon the programmers who wrote the routines. Best practice is to do the minimum required processing in the interrupt routine and provide some mechanism for less critical processing to be done later at a lower priority. For VERY critically time sensitive code, interrupts can be blocked on most systems (by privileged code), but again best practice is to limit this code to the minimum.

Interval Clock Interrupts - These are more predictable than device interrupts but also stop the flow of your program to perform system level activities (updating system clocks, check scheduling queues, checking timer events, etc.).

Hardware errors - These are events that are unpredictable and cause interrupts that behave similar to device interrupts. Error interrupts are not always able to be blocked, but if these are occurring it is usually possible to eliminate them by repairing the hardware.