Abs-max mais rápido da matriz de flutuação

StackOverflow https://stackoverflow.com/questions/817604

Pergunta

Preciso desenhar medidores de pico para áudio em tempo real. Mínimo 44100 amostras por segundo vezes um mínimo de 40 fluxos. Cada buffer está entre 64 e 1024 amostras. Preciso pegar o ABS Max de cada buffer. (Estes são então alimentados através de uma espécie de filtro de passa baixa e desenhados em intervalos de cerca de 20ms.)

for(int i = 0; i < numSamples; i++)
{ 
      absMaxOfBuffer = MAX( fabs( buffer[i] ), absMaxOfBuffer);
}

É assim que eu faço agora. Eu gostaria de fazer isso muito mais rápido. Os buffers têm flutuações na faixa de -1 a 1, daí os Fabs.

Pergunta, existe uma maneira complicada do Quicksort-esque de fazer isso mais rápido?

Falha nisso, o abdômen sem ramificação e as funções máximas para carros alegóricos, eles existem?

Editar: a plataforma primária é Linux/GCC, mas uma porta do Windows está planejada (provavelmente com Mingw).

Editar, o segundo:
Eu aceitei o OneByone por causa da parte em relação à estrutura de Algo real, que era central para a questão.
Vou tentar desenrolar o loop para quatro na época, zerando as placas e, em seguida, obtendo o máximo com o SSE (instrução MAXPS) e veja se isso não descasca a banana. Obrigado pelas sugestões, eu votei alguns de vocês, como vice-campeões. :)

Foi útil?

Solução

Fabs e comparação são muito rápidos para os carros alegóricos IEEE (como rápido, um rápido-operatório em princípio).

Se o compilador não estiver prejudicando as duas operações, tocá -lo até que faça ou encontre a implementação para sua arquitetura e compre -a você mesmo.

Talvez você possa tirar algo do fato de que positivo Os flutuadores IEEE vão na mesma ordem que os números inteiros com os mesmos padrões de bits. Aquilo é, 

f > g   iff   *(int*)&f > *(int*)&g

Então, depois de fabricar o Fabs, acho que um máximo sem ramificação para o INT também funcionará para o Float (supondo que eles sejam do mesmo tamanho, é claro). Há uma explicação de por que isso funciona aqui: http://www.cygnuss-oftware.com/papers/comparingfloats/comparingfloats.htm. Mas seu compilador já sabe tudo isso, assim como sua CPU, para que não faça diferença.

Não existe uma maneira mais rápida da complexidade de fazê-lo. Seu algoritmo já é O (n), e você não pode superar isso e ainda olhar para todas as amostras.

Eu acho que provavelmente há algo no SIMD do seu processador (ou seja, SSE2 na Intel) que ajudaria, processando mais dados por ciclo do relógio do que o seu código. Mas eu não sei o quê. Se houver, será possível várias vezes mais rápido.

Você provavelmente poderia paralelizar em uma CPU com vários núcleos, especialmente porque está lidando com 40 fluxos independentes de qualquer maneira. Isso será, na melhor das hipóteses, alguns fatores mais rapidamente. "Just", inicie o número apropriado de threads extras, divida o trabalho entre eles e use a primitiva mais leve que puder para indicar quando todos estão completos (talvez uma barreira de rosca). Não estou muito claro se você está traçando o máximo de todos os 40 fluxos, ou o máximo de cada um separadamente, então talvez você não precise sincronizar os threads do trabalhador, além de garantir que os resultados sejam entregues no próximo estágio sem corrupção de dados.

Provavelmente vale a pena dar uma olhada na desmontagem para ver o quanto o compilador desenrolou o loop. Tente desenrolá -lo um pouco mais, veja se isso faz alguma diferença.

Outra coisa a pensar é quantos cache você está recebendo e se é possível reduzir o número, dando ao cache algumas pistas para que possa carregar as páginas certas antes do tempo. Mas não tenho experiência com isso, e não teria muita esperança. __builtin_prefetch é o encantamento mágico no GCC, e acho que o primeiro experimento seria algo como "Prepare o início do próximo bloco antes de entrar no loop deste bloco".

Em que porcentagem da velocidade necessária você está atualmente? Ou é um caso de "o mais rápido possível"?

Outras dicas

Há um Fabs sem ramificação documentado em http://www.scribd.com/doc/2348628/the-agregate-magic-algorithms

Observe também que as versões recentes do GCC incluirão um sem ramificação fabs Para você, usando instruções MMX. Há também fmin e fmax, mas o GCC não inclui esses (você receberá um call fmin).

Coisas para tentar:

  • fabs () pode não ser uma função embutida.
  • Instruções especiais de montagem podem ajudar. Na Intel, o SSE tem uma instrução para calcular o máximo de quatro carros alegóricos ao mesmo tempo.
  • Falha nessa, a especificação IEEE 754 é tal que se A e B forem não negativo Floats, então a <b é equivalente a *(int *) e a < *(int *) e b. Além disso, para qualquer A, você pode calcular -a de A lançando o MSB. Juntos, essas propriedades podem permitir alguns hacks de lança um pouco.
  • Você realmente precisa do máximo de cada amostra? Talvez o máximo possa ocorrer mais de uma vez, abrindo a possibilidade de não examinar todas as entradas.
  • Você pode calcular o máximo de forma de streaming?

Você pode querer olhar para Eigen.

É uma biblioteca de modelo C ++ que usa SSE (2 e posterior) e conjuntos de instruções Altivec com fallback gracioso ao código não vetorizado.

Velozes. (Veja Benchmark).
Os modelos de expressão permitem remover inteligentemente os temporários e permitir a avaliação preguiçosa, quando isso é apropriado - Eigen cuida disso automaticamente e lida com alias também na maioria dos casos.
A vetorização explícita é realizada para os conjuntos de instruções SSE (2 e posterior) e Altivec, com fallback gracioso ao código não vetorizado. Os modelos de expressão permitem executar essas otimizações globalmente para expressões inteiras.
Com objetos de tamanho fixo, a alocação de memória dinâmica é evitada e os loops são desenrolados quando isso faz sentido.
Para matrizes grandes, atenção especial é dada à facilidade de cache.

Responder a uma pergunta com outra pergunta não está exatamente respondendo, mas ei ... também não sou desenvolvedor de C ++.

Como você está desenvolvendo isso no C ++ e está fazendo DSP, você não pode se conectar ao Matlab ou Octave (que é o OpenSource) à matemática para o seu e apenas obtenha o resultado?

Já existem funções (como Conv, FFT, IFFT, FIR e plotting UTIL funções como FREQZ, STEM, Gráfico, plotagem, malha etc.) implementadas nesses pedaços de software. Eu dei uma olhada no Photoshop e há uma grande pasta chamada MATLAB ... com alguns arquivos .m que recebem chamadas do aplicativo, envie -o para uma coisa dinâmica do Matlab e depois retorne o resultado ao aplicativo.

Espero que ajude.

Otimizações fáceis que vejo:

  • Traduza o loop para uma versão aritmética do ponteiro (assumindo que seu compilador não veja isso)
  • O padrão IEEE 754 define sua representação como magnitude de sinal. Portanto, definir o bit mais significativo para 0 será o mesmo que chamar Fabs (). Talvez essa função já use esse truque.

Para o seu propósito, você pode encaixá -lo em vez de assumir o valor absoluto; como matematicamente | a | <| B | Se a^2 <b^2 e vice -versa. A multiplicação pode ser mais rápida que Fabs () em algumas máquinas (?), Eu não sei.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top