Multiplicacion Matriz-vector

Incremento en el Desempeño en la Multiplicación MatrizVector
Sotero Ordoñes Nogales1, José Antonio Muñoz Gómez1, Abimael Jiménez Pérez2
1

Departamento de Ingenierías, Universidad de Guadalajara campus CUCSur, Autlán de la
Grana, México
sotero.ordones@gmail.com, jose.munoz@cucsur.udg.mx
2
Instituto de Ingeniería y Tecnología, Universidad Autónoma de Ciudad Juárez, Ciudad Juárez,
Méxicoabimael.jimenez@uacj.mx

Abstract. This paper is focused on the analysis of several optimization techniques of serial and parallel code in order to increase the computational performance of matrix-vector multiplication. The paper presents both an exhaustive
study of described techniques, and the features of coding in detail. Several numerical studies were done, where the characteristics thatmust have the algorithm to get the best computational performance with one core and multi-core
processing using shared memory with OpenMP were determined. In particular,
we study exhaustively the influence in the computational performance employing the technique of loop unrolling and vector data processing. Numerically was
demonstrated that the best performance is obtained with an unroll-8,getting a
gain of 1.6x, and using parallel registers a gain of 2.2x is achieved. In addition,
using parallel programming were determined 4.5, 8.2 and 9.8 Gflops with 2, 4
and 8 cores, respectively.
Resumen. Este trabajo se concentra en el análisis de diversas técnicas de
optimización de código en serie y en paralelo para incrementar el desempeño
computacional de la multiplicaciónmatriz-vector. Se presenta de forma
detallada el estudio exhaustivo de las técnicas descritas así como los detalles de
codificación. Se realizan diversos estudios numéricos en donde se determinan
las características que debe tener el algoritmo para obtener el mayor
rendimiento computacional en un solo núcleo y con varios núcleos de
procesamiento empleando memoria compartida con OpenMP. En particular, seestudia exhaustivamente la influencia en el desempeño computacional
empleando la técnica de loop unrolling y el procesamiento vectorial de datos.
Mostramos numéricamente que el mejor desempeño se obtiene con unroll-8
obteniendo una ganancia de 1.6x, y empleando los registros paralelos se alcanza
2.2x. Además, empleando la programación en paralelo se determinaron 4.5, 8.2
y 9.8 Gflops 2,4,8núcleos respectivamente.
Keywords: cómputo paralelo, computación científica, técnicas de unroll,
memoria compartida, OpenMP.

1

Introducción

Una de las operaciones algebraicas más importantes en computación científica es la
multiplicación de una matriz por un vector. Esta operación es el núcleo computacional
de los esquemas iterativos modernos basados en sub-espacios de Krylov, quenos
permiten resolver de manera eficiente diversos problemas reales en las ciencias y las
ingenierías [1].
La operación matriz-vector tienen un orden de complejidad cuadrático !(!! ), para
valores de suficientemente grandes o bien cuando se realizan miles de iteraciones es
requerido optimizar el código para incrementar el desempeño computacional. Desde
un punto de vista matemático lamultiplicación matriz-vector se expresa como:
!"

(1)

donde ! es una matriz de !×! y ! es un vector con ! elementos definidos sobre el
campo de los números reales. La sección de código que implementa a (1) se muestra a
continuación.
/* ----- Ax version canónica ----- */
for(i=0; i < n; i++){
for(j=0, c[i] = 0; j < n; j++)
c[i] = c[i] + A[i][j] * x[j];
}
Esta forma de codificacióncorresponde a la forma básica o canónica de implementar
la operación, la cual es correcta desde el punto de vista del álgebra matricial, pero
deficiente en el área de computación científica. Esta forma de implementación tiene
un bajo desempeño computacional.
Existen una gran variedad de bibliotecas de código libre dedicadas a la optimización
de operaciones del álgebra matricial. En particular, la...