c++ - online - multiplicacion de matrices java

¿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 (vea mi código completo de boost que funciona )

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 (vea el código estándar completo ):

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;
}

Así es como pruebo 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 de 2000 x 2000. Ambos programas fueron compilados con estos indicadores:

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

¡Tengo 15 segundos para mi implementación y más de 4 minutos para la implementación de impulso!

editar: después de compilarlo con

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

Obtuve 28.19 segundos para el algoritmo ikj y 60.99 segundos para Boost. Entonces, Boost sigue siendo considerablemente más lento.

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

Answer 1

Creo que tu 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. Ejecuté su código a través del compilador MS VC 7.1 en modo de lanzamiento para matrices de 1000x1000, me da

10.064 s para uBLAS

7.851 s para el vector

La diferencia sigue ahí, 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, por ejemplo, prod(A, B)(10,100) se ejecutará en poco tiempo, ya que solo se calculará ese elemento. Como tal, en realidad no existe un algoritmo dedicado para la multiplicación de la matriz completa que pueda optimizarse (ver más abajo). Pero podrías ayudar a la biblioteca un poco, declarando

matrix<int, column_major> B;

reducirá el tiempo de funcionamiento a 4.426 s, lo que supera 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é.

PD Al haber leído la documentación de uBLAS hasta el final;), debiste haber descubierto que en realidad hay una función dedicada para multiplicar matrices enteras a la vez. 2 funciones: axpy_prod y opb_prod . Asi que

opb_prod(A, B, C, true);

incluso en row_major no optimizado, la matriz B se ejecuta en 8.091 segundos y está a la par con su algoritmo de vector

PPS Aún hay más optimizaciones:

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

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

Answer 2

Un 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í está el tiempo que toma la versión de uBLAS con la depuración en:

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

Aquí está el tiempo tomado por la versión de uBLAS con depuración desactivada (se -DNDEBUG -DBOOST_UBLAS_NDEBUG compilador -DNDEBUG -DBOOST_UBLAS_NDEBUG ):

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

Entonces, con la eliminación de errores, la versión de uBLAS es casi 3 veces más rápida.

La diferencia de rendimiento restante se puede explicar citando la siguiente sección de boost.org/doc/libs/1_49_0/libs/numeric/ublas/doc/index.htm de boost.org/doc/libs/1_49_0/libs/numeric/ublas/doc/index.htm "¿Por qué UBLAS es mucho más lento que (atlas-) BLAS"?

Un objetivo de diseño importante 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 dispersas o triangulares. Afortunadamente, uBLAS proporciona alternativas optimizadas para la multiplicación de matriz densa, en particular, axpy_prod y block_prod . Aquí están los resultados de comparar diferentes métodos:

ijkalgorithm   prod   axpy_prod  block_prod
   1.335       7.061    1.330       1.278

Como puede ver, tanto axpy_prod como block_prod son algo más rápidos que su implementación. Medir solo el tiempo de cálculo sin E / S, eliminar la copia innecesaria y la elección cuidadosa del tamaño de bloque para block_prod (utilicé 64) puede hacer la diferencia más profunda.

Ver también boost.org/doc/libs/1_49_0/libs/numeric/ublas/doc/index.htm y uBlas Efectivo y optimización de código general .

Answer 3

Creé un pequeño sitio web Experimentos de productos Matrix-Matrix con 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 si otros pudieran ejecutar los puntos de referencia simples en diferentes máquinas.