patternMinor
Identifying system events affecting timing behavior of an application
Viewed 0 times
eventsapplicationsystembehaviortimingidentifyingaffecting
Problem
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:
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#52637, answer score: 3
Revisions (0)
No revisions yet.