Estatísticas corretas para relatar resultados de aceleração

Digamos que eu tenha versões lentas e rápidas de algum código e queira relatar um número de aceleração comparando os dois. Eu executo a versão lenta times e a versão rápida times, produzindo times e . A maneira mais simples de produzir uma aceleração é a média dos meios: $n$ $m$ $(s_1, \ldots, s_n)$ $(f_1, \ldots, f_m)$ No entanto, isso não leva em consideração os outliers.

\frac{\bar{s}}{\bar{f}} = \frac{m \sum_{i < n} s_{i}}{n \sum_{j < m} f_{j}}

$\frac{\bar{s}}{\bar{f}} = \frac{m \sum_{i<n} s_i}{n \sum_{j<m} f_j}$

Pergunta : Qual é a melhor estatística a ser usada ao relatar números de aceleração?

statistics publications Geoffrey Irving
fonte

Qual é o tamanho do desvio padrão em comparação com a média? Faça o que fizer, você deve relatar o que fez e provavelmente colocar barras de erro, se elas forem grandes. Se eles são realmente grandes, você deve investigar a fonte. A maioria dos códigos de computador deve ser executada de maneira bastante determinística no tempo, a menos que haja um componente aleatório no próprio programa ou você esteja compartilhando recursos do computador com outras pessoas (isso pode ser rede ou disco, não apenas nós do cluster). Se a competição por recursos de disco for o problema, considere relatar o desempenho com a E / S desativada (bastante comum) - apenas observe isso.

Bill Barth

No Edison (um supercomputador Cray), tenho uma diferença de 2% entre duas amostras. No meu laptop, vejo um desvio padrão de 6 a 8%, medido em 10 amostras. Ambos são apenas para o kernel de computação, sem E / S.

Geoffrey Irving

Para esclarecer por que estou mencionando discrepâncias, se as variações já são razoavelmente baixas: essa é uma quantidade estatística suficientemente fundamental que eu gostaria de saber a maneira ideal de denunciá-la, mesmo as maneiras não ideais são boas neste caso particular.

Geoffrey Irving

A questão é o que você está tentando comunicar, e a fórmula comunicaria isso melhor? Acho que nunca vi um artigo que relatasse a variabilidade de aceleração de corrida em corrida, a menos que a causa fosse central para o jornal. Dado que postulamos uma relação linear entre tempo de execução e contagem de processador / tarefa / encadeamento, você provavelmente está bem em usar a proporção de médias, mas depois a barra de erro com a proporção de max-para-min e min-para-max se você acha que é importante mostrar o intervalo. Além disso, você provavelmente deve examinar as opções de escala de frequência e fixação de tarefas para reduzir sua variabilidade. :)

Bill Barth

Pode haver muitos truques na eliminação de E / S. Entre otimizações do compilador e truques de "Copiar na gravação", pode haver laços realmente não óbvios para baixo. Eu costumo seguir o protótipo de d1 = loadData (); d2 = cópia (d1); r1 = algo (d2); r2 = algo (d1) e considere apenas o tempo da segunda execução.

meawoppl

Respostas:

Além de tudo o que Bill Barth já disse acima, deixe-me mencionar que as pessoas costumam relatar o mais rápido de várias corridas. A lógica é que o tempo de execução real é o ideal tempo de execução mais qualquer número de lentidão resultantes de outros processos em execução, os atrasos do sistema operacional, atrasos na rede, etc. Uma vez que estes são todos os ruídos que não está interessado, usando o mais rápido tempo de execução vem mais próximo do que realmente queremos saber.

Wolfgang Bangerth
fonte

Infelizmente, esse princípio não ajuda ao relatar uma aceleração entre dois algoritmos.

Geoffrey Irving

@GeoffreyIrving, por que não? Ambos os algoritmos têm uma expectativa teórica de desempenho versus tamanho do problema (ou contagem de processadores ou outro parâmetro não estatístico) com termos de ordem inferior e independentes de parâmetro ignorados. Usar o tempo mais rápido (e observar esse fato) é simplesmente ajudar você a ignorar esses termos adicionais. O que parece ser uma boa estratégia. A menos que você nos diga de maneira diferente, parece que você está tentando descobrir como comunicar a diferença entre os algoritmos de maneira mais eficaz, e a sugestão de Wolfgang é convencional e esperada, para que possa transmitir melhor essas informações.

Bill Barth

Opa, sim, você está certo. Felizmente retiro minha declaração.

Geoffrey Irving

(+1) Uma questão paralela: concluo o que você vê sobre distribuição de ruído não simétrica , etc. Digamos que eu faça uma implementação A, e uma implementação B e as comparei e depois de uma quantidade razoável de execuções, o O quantil 25, a mediana e a média são ~ 4,5x mais rápidas em A que B, enquanto o quantil 0% é ~ 3x. Ao comparar a implementação A a B, apesar de:: yes A is theoretically only ~3x faster, uma aceleração de ~ 3x não é representativa da aceleração esperada ao usar a implementação A em vez de B? (Este é um exemplo da vida real por sinal)

usεr11852

@ usεr11852: Tudo depende do sistema em que você está. Se a sua mediana ou o 25º quantil estão tão distantes que distorcem as estatísticas da maneira que você propõe aqui, é provável que você esteja em um sistema com muito ruído. Por exemplo, ele pode ser usado por outras pessoas ao mesmo tempo, etc. Isso pode não ser representativo dos sistemas que os outros têm para suas repetidas experiências, e me parece que você está vendendo demais os resultados nesse caso. Então, ainda sugiro relatar as melhores execuções. Faça o que fizer, você deve relatar no artigo quais estatísticas você usa.

Wolfgang Bangerth

Sugiro que você use a mediana para fornecer uma estimativa estatística. Diferentemente da média, a mediana não é corrompida pelos valores discrepantes.

Jan
fonte

Para dados em que todo o ruído é positivo (ou seja, com uma distribuição de ruído não simétrica), a mediana é tão ruim quanto qualquer outra estatística. Para tempos de execução, esse é realmente o caso, veja minha resposta acima.

Wolfgang Bangerth

Se o desvio padrão não for desprezível, você poderá usar dois gráficos de caixas lado a lado, construídos cada um com o tempo de um dos algoritmos. Eles não são de todo o modo padrão na análise numérica, mas fazem um ótimo trabalho ao exibir esse tipo de informação.

Federico Poloni
fonte