¿Por qué aumenta la multiplicación de matrices más lenta que la mía?

Question

he implementado una multiplicación de matrices con boost::numeric::ublas::matrix (ver my full, working boost code)

Result result = read(); 

boost::numeric::ublas::matrix<int> C; 
C = boost::numeric::ublas::prod(result.A, result.B); 

y otro con el algoritmo estándar (ver full standard code):

vector< vector<int> > ijkalgorithm(vector< vector<int> > A, 
            vector< vector<int> > B) { 
    int n = A.size(); 

    // initialise C with 0s 
    vector<int> tmp(n, 0); 
    vector< vector<int> > C(n, tmp); 

    for (int i = 0; i < n; i++) { 
     for (int k = 0; k < n; k++) { 
      for (int j = 0; j < n; j++) { 
       C[i][j] += A[i][k] * B[k][j]; 
      } 
     } 
    } 
    return C; 
} 

Éste es cómo probar la velocidad:

time boostImplementation.out > boostResult.txt 
diff boostResult.txt correctResult.txt 

time simpleImplementation.out > simpleResult.txt 
diff simpleResult.txt correctResult.txt 

Ambos programas leen un archivo de texto codificado que contiene dos matrices 2000 x 2000 ces. Ambos programas fueron compilados con estas banderas:

g++ -std=c++98 -Wall -O3 -g $(PROBLEM).cpp -o $(PROBLEM).out -pedantic 

que tiene 15 segundos para mi aplicación y otra 4 minutos para el impulso a la ejecución!

edición: Después de compilar con

g++ -std=c++98 -Wall -pedantic -O3 -D NDEBUG -DBOOST_UBLAS_NDEBUG library-boost.cpp -o library-boost.out 

llegué 28,19 segundos para la ikj-algoritmo y 60,99 segundos de Boost. Entonces, Boost sigue siendo considerablemente más lento.

¿Por qué el impulso es mucho más lento que mi implementación?

Answer 1

El rendimiento más lento de la versión uBLAS se puede explicar en parte por las características de depuración de este último, como lo señaló TJD.

Aquí es el tiempo que tarda la versión uBLAS con la depuración en:

real 0m19.966s 
user 0m19.809s 
sys  0m0.112s 

Aquí está el tiempo empleado por la versión uBLAS con la depuración de apagado (-DNDEBUG -DBOOST_UBLAS_NDEBUG opciones del compilador es nuestra):

real 0m7.061s 
user 0m6.936s 
sys  0m0.096s 

Así que con eliminando errores, la versión uBLAS es casi 3 veces más rápida.

restante diferencia de rendimiento se puede explicar por citar la siguiente sección de uBLAS FAQ "¿Por qué es tan uBLAS mucho más lento que (ATLAS) BLAS":

Un objetivo importante del diseño de ublas es ser lo más general posible.

Esta generalidad casi siempre tiene un costo. En particular, la plantilla de función prod puede manejar diferentes tipos de matrices, como las escasa o triangulares. Afortunadamente, uBLAS proporciona alternativas optimizadas para la multiplicación de matrices densas, en particular, axpy_prod y block_prod. Estos son los resultados de la comparación de diferentes métodos:

ijkalgorithm prod axpy_prod block_prod 
    1.335  7.061 1.330  1.278 

Como se puede ver tanto axpy_prod y block_prod son algo más rápido que su puesta en práctica.Medir solo el tiempo de cálculo sin E/S, eliminar la copia innecesaria y elegir cuidadosamente el tamaño de bloque para block_prod (utilicé 64) puede hacer la diferencia más profunda.

Vea también uBLAS FAQ y Effective uBlas and general code optimization.

Answer 2

Creo que su compilador no optimiza lo suficiente. El código uBLAS hace un uso intensivo de las plantillas y las plantillas requieren una gran cantidad de optimizaciones. Me encontré con su código a través de MS VC 7.1 compilador en modo de lanzamiento de 1000x1000 matrices, me da

10.064 s para uBLAS

7.851 s para el vector del

la diferencia es todavía allí, pero de ninguna manera abrumadora . El concepto central de uBLAS es la evaluación diferida, por lo que prod(A, B) evalúa los resultados solo cuando es necesario, p. prod(A, B)(10,100) se ejecutará en ningún momento, ya que solo ese elemento se calculará realmente. Como tal, en realidad hay sin algoritmo dedicado para la multiplicación de matrices enteras que podría optimizarse (ver a continuación). Pero se puede ayudar a la biblioteca un poco, declarando

matrix<int, column_major> B; 

reducirá el tiempo de funcionamiento a 4.426 s que late su función con una mano atada. Esta declaración hace que el acceso a la memoria sea más secuencial al multiplicar matrices, optimizando el uso de la memoria caché.

P.S. Después de haber leído la documentación de uBLAS hasta el final;), debería haber descubierto que en realidad hay una función dedicada para multiplicar matrices completas a la vez. 2 funciones: axpy_prod y opb_prod. Así

opb_prod(A, B, C, true); 

incluso en la matriz row_major B sin optimizar ejecuta en 8.091 seg y está a la par con su algoritmo de vector de

P.P.S. Hay incluso más optimizaciones:

C = block_prod<matrix<int>, 1024>(A, B); 

ejecuta en 4.4 s, no importa si B es column_ o row_ importante. Considere la descripción: "La función block_prod está diseñada para matrices grandes densas". ¡Elija herramientas específicas para tareas específicas!

Answer 3

Creé un pequeño sitio web Matrix-Matrix Product Experiments with uBLAS. Se trata de integrar una nueva implementación para el producto matriz-matriz en uBLAS. Si ya tiene la biblioteca de impulso, solo consta de 4 archivos adicionales. Entonces es bastante autónomo.

Me interesaría que otros pudieran ejecutar los puntos de referencia simples en diferentes máquinas.