0
$\begingroup$

I am using (essentially) the approach outlined in the paper "Statistical-based WCET estimation and validation" (http://drops.dagstuhl.de/opus/volltexte/2009/2291/pdf/Hansen.2291.pdf) to build a Gumbel distribution for worst-case execution times for a real-time software system.

To model the distribution I build a data set out of, say, the worst time in 32 successive executions of the benchmark I am using. I might then get 40 or 50 such data points and using some R get a figure for $\mu$ and for $\beta$ and from there can, say, get a figure for the limit for $10^{-5}$ or $10^{-6}$ cases.

The question is, though, is this (in some say) a measure of the worst $\frac{1}{100000}$ or $\frac{1}{1000000}$ of what are already the worst cases or a statement about the expected value of one-in-a-million (or so on) of all cases?

$\endgroup$

1 Answer 1

1
$\begingroup$

You are estimating a lower bound on how bad the worst $10^{-6}$ of data points would be. "Data points" being what you fed in: in your case, the worst of 40-50 execution times.

For what it's worth, I don't find the reason given in the paper for taking the worst times in each block and modeling those as compelling in the least. If a standard model fits well to the raw data, I would calculate the estimated upper percentiles based on that model (just use the raw data). The insistence on the Gumbel distribution is begs the question: if the raw data would be better modeled using a different distribution, then why not use that? There is no guarantee that the maximum of 50 i.i.d. random variables follows a Gumbel distribution.

A warning: This kind of estimation is a kind of extrapolation. Making decisions from these sorts of calculation is risky because a model that fits well to limited data may not fit well in the tails of the distribution.

$\endgroup$
2
  • $\begingroup$ Isn't the chi-squared test contained in the paper a test of whether the values follow a Gumbel distribution? $\endgroup$ Dec 30, 2018 at 18:09
  • $\begingroup$ A significant p-value would make it likely that there is a lack of fit with the Gumbel, but the sensitivity of the test may not be great. $\endgroup$
    – HStamper
    Dec 31, 2018 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.