Abs-max más rápido de la matriz flotante

Question

Necesito dibujar medidores de pico para audio en tiempo real.Mínimo 44100 muestras por segundo multiplicadas por un mínimo de 40 transmisiones.Cada búfer tiene entre 64 y 1024 muestras.Necesito tomar el máximo de abdominales de cada búfer.(Luego, estos se pasan a través de una especie de filtro de paso bajo y se extraen a intervalos de aproximadamente 20 ms).

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

Así es como lo hago ahora.Me gustaría hacerlo mucho más rápido.Los buffers tienen flotadores en el rango de -1 a 1, de ahí las fabulosas.

Pregunta, ¿existe alguna forma complicada de clasificación rápida de ciencia ficción de hacer esto más rápido?

En su defecto, funciones ABS sin brazos y MAX para flotadores, ¿existen?

editar:La plataforma principal es Linux/gcc pero está prevista una adaptación a Windows (probablemente con mingw).

editar, el segundo:
Acepté a uno por uno debido a la parte relacionada con la estructura real del algoritmo que era central para la pregunta.
Intentaré desenrollar el bucle a cuatro a la vez, poner a cero los bits de signo y luego obtener el máximo con SSE (instrucción maxps) y ver si eso no pela el plátano.Gracias por las sugerencias, he votado a algunos de ustedes como finalistas.:)

Answer 1

las fabs y la comparación son realmente rápidas para los flotadores IEEE (como, en principio, una operación de entero único).

Si el compilador no está alineando ambas operaciones, púlselo hasta que lo haga o encuentre la implementación para su arquitectura e instálelo usted mismo.

Quizás pueda obtener algo del hecho de que los flotantes IEEE positivos van en el mismo orden que los enteros con los mismos patrones de bits. Es decir,

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

Entonces, una vez que haya fabs'ed, creo que un max sin ram para int también funcionará para float (suponiendo que sean del mismo tamaño, por supuesto). Hay una explicación de por qué esto funciona aquí: http: //www.cygnus-software .com / papers / comparingfloats / comparingfloats.htm . Pero su compilador ya sabe todo esto, al igual que su CPU, por lo que es posible que no haga ninguna diferencia.

No hay una forma más rápida de hacerlo. Su algoritmo ya es O (n), y no puede superar eso y aún así mirar cada muestra.

Supongo que probablemente haya algo en el SIMD de su procesador (es decir, SSE2 en Intel) que ayudaría al procesar más datos por ciclo de reloj que su código. Pero no se que. Si lo hay, entonces posiblemente sea varias veces más rápido.

Probablemente podría paralelizar en una CPU multinúcleo, especialmente porque de todos modos se trata de 40 transmisiones independientes. En el mejor de los casos, serán algunos factores más rápidos. " Solo " inicie el número apropiado de subprocesos adicionales, divida el trabajo entre ellos y use la primitiva más ligera que pueda para indicar cuándo están completos (tal vez una barrera de subprocesos). No tengo muy claro si está trazando el máximo de las 40 transmisiones, o el máximo de cada una por separado, por lo que tal vez no necesite sincronizar los subprocesos de trabajo, aparte de garantizar que los resultados se entreguen a la siguiente etapa sin corrupción de datos.

Probablemente valga la pena echarle un vistazo al desmontaje para ver cuánto ha desenrollado el compilador el bucle. Intente desenrollarlo un poco más, vea si eso hace alguna diferencia.

Otra cosa a tener en cuenta es cuántos errores de caché está recibiendo y si es posible reducir el número dándole al caché algunas pistas para que pueda cargar las páginas correctas con anticipación. Pero no tengo experiencia con esto, y no tendría muchas esperanzas. __builtin_prefetch es el encantamiento mágico en gcc, y supongo que el primer experimento sería algo así como " capta el comienzo del siguiente bloque antes de ingresar el ciclo para este bloque " ;.

¿Qué porcentaje de la velocidad requerida está actualmente? ¿O es un caso de & Quot; tan rápido como sea posible & Quot ;?

Answer 2

Hay una fábrica sin sucursales documentada en http://www.scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms

Tenga en cuenta también que las versiones recientes de GCC incorporarán un sistema sin sucursales fabs para usted, usando instrucciones MMX.También hay fmin y fmax, pero GCC no los integrará (obtendrás un call fmin).

Answer 3

Cosas para probar:

• fabs () podría no ser una función en línea.
• Las instrucciones especiales de montaje pueden ayudar. En Intel, SSE tiene una instrucción para calcular el máximo de cuatro flotantes a la vez.
• En su defecto, la especificación IEEE 754 es tal que si a y b son flotantes no negativos , entonces a < b es equivalente a * (int *) & amp; a < * (int *) & amp; b. Además, para cualquier a, puede calcular -a desde a volteando el MSB. Juntas, estas propiedades podrían habilitar algunos trucos de bit-twiddling.
• ¿Realmente necesita el máximo de cada muestra? Quizás el máximo pueda ocurrir más de una vez, abriendo la posibilidad de no examinar cada entrada.
• ¿Puedes calcular el máximo de una manera de transmisión?

Answer 4

Es posible que desee ver Eigen .

Es una biblioteca de plantillas de C ++ que utiliza SSE (2 y posterior) y conjuntos de instrucciones AltiVec con un respaldo elegante al código no vectorizado .

  

Rápido. (Ver punto de referencia).
   Las plantillas de expresión permiten eliminar de forma inteligente los temporales y permitir una evaluación diferida, cuando sea apropiado; Eigen se encarga de esto automáticamente y también maneja los alias en la mayoría de los casos.
  La vectorización explícita se realiza para los conjuntos de instrucciones SSE (2 y posteriores) y AltiVec, con un respaldo elegante al código no vectorizado. Las plantillas de expresión permiten realizar estas optimizaciones globalmente para expresiones completas.
   Con objetos de tamaño fijo, se evita la asignación dinámica de memoria y los bucles se desenrollan cuando eso tiene sentido.
   Para matrices grandes, se presta especial atención a la compatibilidad con caché.

Answer 5

responder una pregunta con otra pregunta no es exactamente responder, pero bueno ... tampoco soy desarrollador de C ++.

Dado que está desarrollando esto en C ++ y está haciendo dsp, ¿no puede conectarse a matlab u octava (que es de código abierto) a las matemáticas para su y solo obtener el resultado?

ya hay funciones (como conv, fft, ifft, fir y plotear funciones de utilidad como freqz, stem, graph, plot, mesh, etc.) implementadas en esas piezas de software. Eché un vistazo en Photoshop y hay una gran carpeta llamada MATLAB ... con algunos archivos .m que reciben llamadas de la aplicación, la envían a un objeto matlab dinámico y luego devuelven el resultado a la aplicación.

Espero que ayude.

Answer 6

Optimizaciones fáciles que veo:

• traduce el bucle a una versión aritmética de puntero (suponiendo que su compilador no vea esto)
• el estándar IEEE 754 define su representación como magnitud de signo. Por lo tanto, establecer el bit más significativo en 0 será lo mismo que llamar a fabs (). Tal vez esta función ya usa este truco.

Answer 7

Para su propósito, puede cuadrarlo en lugar de tomar el valor absoluto; como matemáticamente | a | < | b | si a ^ 2 < b ^ 2 y viceversa. La multiplicación puede ser más rápida que fabs () en algunas máquinas (?), No lo sé.