Re: Statistical theory behind OProfile

Hello,

Armv5 is on the board that we're using for our software.  I'm
attempting to get a test board that could have more recent hardware
for the next project, but such would likely not be used for the
release system, plus there may be other problems with system
compatibility that are beyond my knowledge (hardware is not my strong
suit).  In short, it is currently not possible to get performance
measures on a more recent board for the current environment, but it
may be so in the future.  I was thinking there may be a few ways to
try and mitigate the bias if it existed (and it from the replies it
does), but it may not be possible to do so in the environment.

~Donald Johnson

On Sun, May 31, 2015 at 7:41 PM, William Cohen <[email protected]> wrote:
> On 05/31/2015 11:34 AM, Andi Kleen wrote:
>> Donald Johnson <[email protected]> writes:
>>
>>> I wanted to use oprofile and apply some statistical work while
>>> profiling some the programs I work on.  I'm wondering what the
>>> statistical theory and probably also computer science theory behind
>>> the program is.  There are two sources I've found on the subject that
>>> I can currently access.
>>
>> If you find out please let me know. I always wondered about
>> a sound theory too. But some notes based on experience below.
>>>
>>> "A Randomized Sampling Clock for CPU Utilization Estimation and Code
>>> Profiling"[2] is a paper on the subject that I would like to find more
>>> material like it on, but I am terrible at traversing academia and the
>>> like.  It goes through the general process that statistical profiling
>>> is and what distributions it comes from, but more interestingly it
>>> specifies the bias that can arise from timers that do not have
>>> sufficient randomness attached to them.
>>
>> The default periods are not randomized (but the events happening in the
>> workload may be). Some choice of periods can minimize bias though
>> (e.g. using primes)
>>
>>> However, the article is 12
>>> years old, so the implementation details that produce bias may not
>>> apply.
>>
>> The distribution depends on both the used event and the workload.
>> For example a workload that just runs the same loop over and over
>> has very different sampling characteristics, than a more varied workload
>> which runs many different kinds of short events.
>>
>> Some events also depend on multiple workloads, for example
>> cache misses of shared caches in multi-core systems when the different
>> cores are running multiple loads.
>>
>> Another factor is the sampling period, and how it related to the
>> frequency of workload changes (according to the sampling theorem)
>>>
>>> In short, I wondering what sort of behind-the-scenes process oprofile
>>> is statistically.  It just returns samples.  I'd like to know the
>>> distribution it would come from (which seems to be the Poisson
>>> distribution based on my sources) so I may gather some intuition from
>>> the output.  I also want to know if OProfile does its sampling in a
>>> manner that may introduce bias.
>>
>> Yes it can introduce (sometimes serious) bias.
>>
>>> The environment I am working on is an armv5 board, which means I have
>>> to use release 0.9.9 for software interrupts.
>>
>> That's a very poor environment for performance monitoring. Better use
>> some system with a real PMU, where you can use event driven sampling,
>> which tends to be more accurate than time driven sampling.
>
> Hi,
>
> The timer interrupts are one of the things most likely to have baising in the samples.  There may be a number of other events that are triggered by that same timer interrupt.  Any particular reason for using the armv5 hardware? armv5 hardware is very old.
>
> As Andi mentioned using the PMU is allows more flexibility in setting the sampling interval.  People are encourage to use a prime number for the intervals to minimize the chance that some short event interval is a factor of the sample interval. However, that could still lead to over/under-sampling if the things being sampled are close to some multiple of the sampling interval.   Perfmon did ranomization to attempt to avoid these issues [1][2].
>
> [1] http://www.hpl.hp.com/hosted/linux/mail-archives/perfmon/2003-March/000036.html
> [2] http://perfmon2.sourceforge.net/man/pfmon.html
>
> -Will

------------------------------------------------------------------------------