# Predicting Execution Time of DSP programs

I've been tasked with predicting the performance of our DSP code, for the obvious reasons (reduce time to market, add certainty in choosing chips, etc.)

Consider a system composed of many subsystems with timing results $$P_{i}$$ (in seconds) (filters, gains, dynamics processing etc.) with a clockrate $$C$$ (seconds/sample) and sampling rate $$Fs$$ (samples/second)

Our initial assumption is that:

$$\text{CPU utilization} = 100\% * \sum_{i}^{i=N}{P_{i}*Fs/C} \stackrel{!}{=} \texttt{top -d 1}$$

i.e. CPU utilization estimate should equal the output of top -d 1`.

However, this doesn't hold up to real data! It's always underestimated.

We measure individual subsystems by wrapping each of them in a test harness and timing their execution. Our system runs in a single thread and on a single core.

Depending on the platform, we can get within 5 to 20%, but always underestimating top.

Why is this?

I can find nothing in the performance literature that lines up with our assumption, but the explanations are so numerous that it's almost like "we don't really know why we can't predict performance."

I am beginning to think that the solution is monitoring like a hawk during early development and scaling back the system complexity as we uncover new solutions.

However, it would be pretty awesome if we could design a system with the performance requirements ahead of time. Our requirements have largely been determined by "this is better than the old thing the vendor had, and what we had before worked with our old system."

1. Top is terrible tool for measuring CPU time. Set up a bunch of counters or timer around the execution of individual and collect statistics on that.
2. Each of your block should have a "should cost" that's based on number of arithmetic operations plus some overhead for looping and conditionals relative to the instruction set of the processor. Compare each blocks actual cost to the "should cost" and look for major discrepancies
3. If the total doesn't add up, it's often caused by cache misses, pipeline stalls, memory bottlenecks, interrupts, or some other service barging in. Again, proper instrumentation can shed some light on what's happening.
• I keep hearing that top is terrible, but why? I believe it measures jiffies at intervals and subtracts them to estimate usage, but how is this different than measuring execution time? Re: adding up operations, that is a great idea. I believe a profiler will shed some more insight onto the actual bottlenecks. Thanks for your answer Hilmar, I have some direction to go with now and some explanation for discrepancies. – panthyon May 5 '19 at 14:23
• Top a is a statistical tool and you can never tell whether your code takes time or whether it's interrupts, blocked threads, I/O stalls, cache misses, etc. It's representative of the long term averaged system performance, but it doesn't tell you anything about short dynamic behavior (which is important for real time systems) and it's useless in debugging the problem. – Hilmar May 6 '19 at 10:49
• Thank you for the detailed explanation @Hilmar! In other words we must instrument a profiler like LTTNG (or perhaps you have another recommendation?) to identify discrepancies... on a positive note I found that the discrepancy between top and bottom up is less than 3% on 80% of our platforms, but this discrepancy is significantly worse when we look at newer 64-bit platforms. – panthyon May 6 '19 at 14:06

we can get within 5 to 20%, but always underestimating top.

Now, if it is always that much underestimated (as you stated so) then multiply your estimate with an approximate scale to get the more accurate (realistic) estimate...

The reasons could be many and data transfers within the cpu-ram system are among the leading hard to predict...

• It is always underestimated but by an unknown amount that does not scale with CPU rate or any known factor. One strategy I've thought of is collecting data for every platform and developing a statistical model, which could be updated with every new platform for refined accuracy. Regarding difficulty of prediction, how did you know that data transfers are hard to predict? Do you have a good reference on the topic of performance? – panthyon May 4 '19 at 23:31
• Data transfers are dependent on cache and a lot of things happen there... You can find CPU architecture details for learning cache management behaviour if you wish... But I guess multiplying your estimation with a small enough scale so that it provides a slight overestimate is not a bad idea. And yes in general it's quite hard to predict them before the actual system is operated. – Fat32 May 5 '19 at 0:01