multiplicación rápida de los valores en una matriz

¿Hay una forma rápida de multiplicar los valores de una matriz de flotador en C++, para optimizar esta función (donde count es un múltiplo de 4):multiplicación rápida de los valores en una matriz

void multiply(float* values, float factor, int count) 
{ 
    for(int i=0; i < count; i++) 
    { 
     *value *= factor; 
     value++; 
    } 
}

Una solución debe trabajar en Mac OS X y Windows, Intel y no Intel. Piensa en SSE, vectorización, compilador (gcc vs. MSVC).

Fuente

2010-09-09 Jakob

Parece que ya sabes la respuesta. ¿Estás atrapado de alguna manera, o esperas que alguien más escriba el código para ti? –

¡Esto no es Rent-a-Coder! – Skizz

¿Qué tamaño de matriz se espera que sea (> 1,> 10,> 100,> 1000,> 10000)? ¿Considera usar optimización de múltiples núcleos (hilos) en su caso? ¿Hay alguna restricción conocida sobre la matriz por adelantado, otra es que el conteo es múltiplo de 4? – Suma

Si quiere que su código sea multiplataforma, entonces tendrá que escribir un código independiente de la plataforma, o tendrá que escribir una carga de #ifdef s.

¿Ha intentado desenrollar algún bucle manual y ver si hace alguna diferencia?

Fuente

2010-09-09 11:21:07

Dado que se conoce el count es un múltiplo de 4, se puede desenrollar el bucle ...

void multiply(float* values, float factor, int count) 
{ 
    count = count >> 2; // count/4 
    for(int i=0; i < count ; i++) 
    { 
     *value *= factor; 
     *(value+1) *= factor; 
     *(value+2) *= factor; 
     *(value+3) *= factor; 
     value += 4; 
    } 
}

Fuente

2010-09-09 11:24:19 st0le

Esto seguramente no será más rápido, ya que tiene la misma cantidad de multiplicaciones, con una aritmética de puntero más compleja que la original. Me interesaría ver sus medidas para apoyar que esto sea una mejora. –

GCC hace esto con '-funroll-loops'. –

@Steve: Esto bien podría hacer la diferencia, dependiendo de qué tan bueno sea el compilador (y cuán bueno es el predictor de bifurcación de la CPU). La relación de multiplicaciones a ramas condicionales ha aumentado de 1: 1 a 4: 1. –

responsabilidad: Obviamente, esto no funcionará en el iPhone, iPad, Android, o sus equivalentes futuras .

#include <mmintrin.h> 
#include <xmmintrin.h> 

__m128 factor4 = _mm_set1_ps(factor); 
for (int i=0; i+3 < count; i += 4) 
{ 
    __m128 data = _mm_mul_ps(_mm_loadu_ps(values), factor4); 
    _mm_storeu_ps(values, data); 
    values += 4; 
} 
for (int i=(count/4)*4; i < count; i++) 
{ 
    *values *= factor; 
    value++; 
}

Fuente

2010-09-09 11:29:07 rwong

funcionará en x86 Android –

¿Has pensado en OpenMP?

La mayoría de las computadoras modernas tienen CPU multi-core y casi todos los compiladores importantes parecen tener OpenMP incorporado. Usted gana velocidad a cualquier costo.

Ver Wikipedia's article on OpenMP.

Fuente

2010-09-09 11:32:44 Bigbohne

La mejor solución es mantenerlo simple y dejar que el compilador lo optimice para usted. GCC sabe sobre SSE, SSE2, altivec y qué más. Si su código es demasiado complejo, su compilador no podrá optimizarlo en todos los destinos posibles.

Fuente

2010-09-09 11:35:56

Como mencionaste, existen numerosas arquitecturas que tienen extensiones SIMD y SIMD es probablemente tu mejor opción en lo que respecta a la optimización. Sin embargo, todos son específicos de la plataforma y C y C++ ya que los lenguajes no son SIMD amigables.

Lo primero que debes hacer es habilitar las banderas específicas de SIMD para tu compilación. El compilador puede reconocer patrones que se pueden optimizar con SIMD.

Lo siguiente es escribir el código SIMD específico de la plataforma usando los intrínsecos del compilador o el ensamblado cuando corresponda. Sin embargo, debe mantener una implementación portátil que no sea SIMD para las plataformas que no tienen una versión optimizada. #ifdef s habilite SIMD en plataformas que lo admitan.

Por último, al menos en ARM pero no está seguro en Intel, tenga en cuenta que los tipos enteros y flotantes más pequeños permiten un mayor número de operaciones paralelas por cada instrucción SIMD.

Fuente

2010-09-09 13:27:33 doron

Creo que no hay mucho que hacer que haga una gran diferencia. Tal vez puedas acelerarlo un poco con OpenMP o SSE. Pero las CPU modernas ya son bastante rápidas. En algunas aplicaciones, el ancho de banda/latencia de la memoria es en realidad el cuello de botella y empeora. Ya tenemos tres niveles de caché y necesitamos algoritmos inteligentes de captación previa para evitar grandes retrasos. Por lo tanto, tiene sentido pensar en los patrones de acceso a la memoria también.Por ejemplo, si se implementa como un multiply y un add y utilizar de esta manera:

void multiply(float vec[], float factor, int size) 
{ 
    for (int i=0; i<size; ++i) 
    vec[i] *= factor; 
} 

void add(float vec[], float summand, int size) 
{ 
    for (int i=0; i<size; ++i) 
    vec[i] += summand; 
} 

void foo(float vec[], int size) 
{ 
    multiply(vec,2.f,size); 
    add(vec,9.f,size); 
}

que está básicamente pasar dos veces por encima del bloque de memoria. Dependiendo del tamaño del vector, podría no encajar en la memoria caché L1, en cuyo caso pasar dos veces agrega algo de tiempo extra. Esto obviamente es malo y deberías tratar de mantener los accesos a la memoria "local". En este caso, un solo bucle

void foo(float vec[], int size) 
{ 
    for (int i=0; i<size; ++i) { 
    vec[i] = vec[i]*2+9; 
    } 
}

es probable que sea más rápido. Como regla general: Intente acceder a la memoria de forma lineal e intente acceder a la memoria "localmente", es decir, intente reutilizar los datos que ya están en la caché L1. Solo una idea.

Fuente

2010-09-09 13:46:34 sellibitze

multiplicación rápida de los valores en una matriz

Respuesta

Cuestiones relacionadas