algoritmos paralelos para la multiplicación de matrices

8/10/2019 Algoritmos Paralelos para la Multiplicacin de Matrices

1/14

Algoritmos Paralelos para laMultiplicaci on de Matrices

David Aparco C ardenas

Resumen La multiplicaci on de matrices grandesrequiere mucho tiempo de computaci on como sucomplejidad es O (n 3 ). Debido a que la mayora deaplicaciones actuales requieren un mayor rendimientocomputacional con el mnimo tiempo, muchos algoritmossecuenciales y paralelos son desarrolados. Los algoritmosparalelos reducen signicativamente el tiempo de ejecuci onde los algoritmos secuenciales cuando son ejecutados convarios procesadores. Este art culo presenta una exposici ondetallada y la correspondiente implementaci on en elentorno de programaci on MPI de cuatro algoritmosparalelos para la multiplicaci on de dos matrices A y B .Los algoritmos primero y segundo son el algoritmo deDescomposici on en bloques de rayas por columnas y elalgoritmo de Descomposici on en bloques de rayas porlas respectivamente, los cuales descomponen a la matrizA en bloques de las y a la matriz B en bloques decolumnas para el primero y bloques de las para elsegundo. Los algoritmos tercero y cuarto son el algoritmode Fox y el algoritmo de Cannon respectivamente loscuales descomponen las matrices A y B en bloques desub-matrices cuadradas las cuales luego son distribuidasentre los procesadores, la diferencia entre ambas seencuentra en el desplazamiento de los sub-bloques dematrices el cual es diferente en cada algoritmo. El presenteestudio se realiza con el n de hallar experimentalmenteen una m aquina quad-core de 64 bits, el algoritmoparalelo que presenta el menor tiempo de ejecuci on parael producto de dos matrices A y B , donde el orden de lasmatrices var a en el transcurso del experimento.

Palabras Clave: computaci on paralela, bloquesde rayas, fox, cannon, mpi, sub-bloques de matrices

I. INTRODUCCI ON

L A multiplicaci on de matrices es una de lasoperaciones m as fundamentales del algebralneal, el cual tiene numerosas aplicaciones a lateor a y pr actica de la computaci on. En particular,varias aplicaciones importantes se dan debido alhecho que la multiplicaci on de matrices es unaparte sustancial de varios algoritmos conocidospara otros problemas computacionales de algebralineal y combinatoria, tales como la soluci on de

un sistema de ecuaciones lineales, la inversi on deuna matriz, la evaluaci on de la determinante deuna matriz, multiplicaci on de matrices booleanas,y el cierre transitivo de un grafo [5][11]. Comootro ejemplo, algunas transformaciones usadasen el procesamiento de se nales se basan en lamultiplicaci on de grandes matrices. Y as sepueden mencionar muchas otras aplicaciones dela multiplicaci on de matrices.[2] Por otra parte,el tiempo de la computaci on requerido para lamultiplicaci on de matrices es la parte dominante deltiempo total requerido para la computaci on de todosesos problemas, los cual es, tales problemas puedenser reducidos a la multiplicaci on de matrices ypueden ser resueltos r apidamente si la multiplicaci onde matrices es resuelta r apidamente [4]. El algoritmomas sencillo para la multiplicaci on de matricesrealiza O(n 3) operaciones. Strassen [9]fue el primeroen demostrar que este algoritmo no es optimo,dando un algoritmo de complejidad O

(n 2.81

) para el

problema. Muchas mejoras le siguieron. El algoritmopara la multiplicaci on de matrices m as r apido queexiste actualmente, con una complejidad de O (n 2.38)fue obtenido por Coppersmith y Winograd [8].Incluso luego de estas mejoras estos algoritmos handemostrado limitaciones en su rendimiento. Por estarazon, aproximaciones paralelas han sido examinadaspor d ecadas. La mayor a algoritmos paralelos para lamultiplicaci on de matrices usan la descomposici onde matrices que se basa en el n umero de procesadoresdisponibles. Esto incluye la descomposici on enbloques de rayas, el algoritmo de Cannon y elalgoritmo de Fox. El algoritmo de Cannon yel algoritmo de Fox usan la descomposici on dematrices en submatrices. Durante la ejecuci on delproceso, un procesor calcula un resultado parcialutilizando las submatrices que est an actualmentesiendo accedidas por el. Luego sucesivamente esteprocesador realiza el mismo c alculo en nuevassubmatrices, a nadiendo el nuevo resultado al previo.Cuando los subprocesos de multiplicaci on han

1


2/14

sido completados, el procesador ra z ensambla losresultados parciales y genera el resultado completode la multiplicaci on de matrices[2].

I I . C ONSIDERACIONES INICIALES

Consideraremos que el n umero de procesadoresde una m aquina es p,

Por simplicidad trabajaremos con matricescuadradas,

Las matrices a multiplicar A y B , seran tratadascomo matrices densas (esto es con poca cantidadde 0s),

T p es el tiempo que emplean p procesadorespara resolver el problema.

En el coste de comunicaciones, el tiempopara transmitir n datos entre dos procesadoresconectados es dado por ts + nt w , donde tses el tiempo empleado para establecer lacomunicaci on y tw es el tiempo que tarda entransmitir un dato.

III . M ULTIPLICACI ON S ECUENCIAL DE

M ATRICES

A. Iterativo, Algoritmo Orientado a Filas.

El producto de una matriz A de orden l m y deuna matriz B de orden m n es una matriz C deorden l n cuyos elementos est an denidos por

ci,j =

m 1

k =0a i,k bk,j

Un algoritmo secuencial implementando lamultiplicaci on de matrices de forma secuencial semuestra en la gura 1. El algoritmo requiere lmnadiciones y el mismo n umero de multiplicaciones.Por lo tanto la complejidad al multiplicar dosmatrices de orden n n usando este algoritmosecuencial es (n 3)

Input :a[0..l 1, 0..m 1]b[0..m 1, 0..n 1]Output :c[0..l 1, 0..n 1]

1: for i 0, l 1 do

2: for j

0, n

1 do3: c[i, j ] 04: for k 0, m 1 do5: c[i, j ] c[i, j ] + a[i, j ] b[ j, k ]6: end for7: end for8: end for

Fig. 1. Multiplicaci on de Matrices Secuencial

Considere la gura 2. Durante cada iteraci on delbucle externo indexado por i, cada elemento de lamatriz B es le do. Si la matriz B es demasiadogrande para el cach e, entonces los elementos le dosposteriormente en cach e desplazar an a los elementosledos anteriormente en cach e, sigicando que enla siguiente iteraci on del loop indexado por i,todos los elementos de B necesitar an ser le dos encach e nuevamente. Por lo tanto una vez que lasmatrices alcancen un determinado tama no, la tasa deaciertos de la memoria cach e cae dramaticamente,disminuyendo el rendimiento de la CPU.[2]

Fig. 2. En cada iteraci on del bucle indexado por i, la la i de lamatriz A y toda la matriz B son le das, mientras la la i de C esescrita.

IV. A LGORITMOS PARALELOS PARA LAM ULTIPLICACI ON DE M ATRICES

A. Descomposici on en bloques de rayas.

Es una aproximaci on de grano no, donde lasubtarea b asica es el c alculo de un elemento dela matriz C.

cij = ( a i , bT j )

a i = ( a i0, a i1,...,a i (n 1) ), bT j = ( b0 j , b1 j ,...,b (n 1) j )T

2


3/14

El numero de subtareas b asicas es igual a n2, comoregla el n umero disponible de procesadores es menora n2( p < n 2), as que ser a necesario realizar elescalamiento de la subtarea.La subtarea agregada es el c alculo de una la de lamatriz C (el n umero de subtareas es n).La distribuci on de datos ser a la descomposici onen bloques de rayas por las para la matriz A y ladescomposici on en bloques de rayas por columnaspara la matriz B.[1]

Fig. 3. Descomposici on en bloques de rayas por las en las matrizA, y por columnas en la matriz B.

An alisis de las Dependencias de Informaci on.

Cada subtarea tiene una la de la matriz A yuna columna de la matriz B.

En cada iteraci on cada subtarea realiza elcalculo del producto interno de su lay columna, como resultado el elementocorrespondiente de la matriz C es obtenido.

Luego cada subtarea i, 0 i < n , env a sucolumna de la matriz B a la subtarea con elnumero (i + 1) mod n.

Luego de todas las iteraciones del algoritmo,todas las columnas de la matriz B estuvierondentro de cada subtarea una despu es de otra.

Fig. 4. Primera etapa, a cada procesador se le entrega una la y unacolumna de la matriz A y B respectivamente, y luego se procede aobtener el resultado del producto de la por columna.

Fig. 5. Segunda etapa, se envian los bloques de columnas de la matrizB en sentido horario, y luego se procede a obtener el resultado delproducto la por columna.

Fig. 6. Tercera etapa, se procede a realizar los mismo que la segundaetapa.

Fig. 7. Cuarta etapa, se procede a realizar los mismo que la terceraetapa.

Agregaci on y Distribuci on de las Subtareas entrelos Procesadores.

En el caso en el que el n umero de procesadoresp es menor que el n umero de subtareas b asicasn, los c alculos pueden ser agregados de talmanera que cada procesador ejecutar a variosproductos internos entre las de la matriz Ay columnas de la matriz B. En este casoluego de completar el c alculo, cada subtareaagregada b asica determina varias las de lamatriz resultante C.

Bajo tales condiciones la matriz inicial A esdescompuesta en p rayas horizontales y lamatriz B es descompuesta en p rayas verticales.

La distribuci on de las subtareas entrelos procesadores tiene que vericar losrequerimientos de una representaci on efectivade la estructura del anillo de las dependenciasde informaci on de las subtareas.

Otra posible aproximaci on para la distribuci on dedatos es la descomposici on en bloques de rayas

3


4/14

para las matrices A y B.

Fig. 8. Descomposic on en bloques de rayas por las en las matrizA y en la matriz B.

An alisis de las Dependencias de Informaci on.

Cada subtarea tiene una la de la matriz A yuna la de la matriz B.

En cada iteraci on las subtareas realizan lamultiplicaci on elemento a elemento de las las;como resultado la la de resultados parcialespara la matriz C es obtenida.

Luego cada subtarea i, 0 i < n , enva su lade la matriz B hacia la subtarea con el n umero(i + 1) mod n.

Luego de todas las iteraciones todas las las dela matriz B estuvieron dentro de cada subtareauna despu es de otra.

Fig. 9. Primera etapa, a cada procesador se le entrega una la de lamatriz A y una la de la matriz B, y luego se procede a obtener elresultado parcial del producto de la por la.

Fig. 10. Segunda etapa, se envian los bloques de las de la matriz Ben sentido horario a los procesadores, y luego se procede a obtenerel resultado del producto parcial la por la.

Fig. 11. Tercera etapa, se procede a realizar los mismo que la segundaetapa.

Fig. 12. Cuarta etapa, se procede a realizar los mismo que la terceraetapa.

B. Algoritmo de Fox.La distribuci on de datos presenta un esquema de

tablero de damas.

Fig. 13. Esquema de tablero de damas.

La subtarea b asica es un procedimiento que calculatodos los elementos de un bloque de la matriz C.

A00 ...A 0(q 1)...

A(q 1)0 ...A (q 1)( q 1)

B 00 ...B 0(q 1)...

B (q 1)0 ...B (q 1)( q 1) =

C 00 ...C 0(q 1)...

C (q 1)0 ...C (q 1)( q 1)

C ij =q 1

s =0

A is B sj

An alisis de las Dependencias de Informaci on. Las subtareas con el n umero (i,j) calculan

el bloque C ij , de la matriz resultante C.Como resultado, la subtareas forman la mallabidimensional q q .

Cada subtarea tiene 4 bloques de matrices:

4


5/14

El bloque C ij de la matriz resultante C, elcual es calculado en la subtarea.

El bloque Aij de la matriz A, el cual fueubicado en la subtarea antes de que elcalculo empiece.

Los bloques Aij y B ij de la matriz A y dela matriz B, los cuales son recibidos porla subtarea durante los c alculos.[3]

- durante la iteracion l, 0 l < q , el algoritmorealiza:

La subtarea (i,j) env a su bloque Aij de lamatriz A a todas las subtareas de la mismala horizontal i de la malla; el ndice j, el cualdetermina la posici on de la subtarea en la la,puede ser obtenido usando la ecuaci on:

j = ( i + l) mod q,

Cada subtarea realiza la multiplicaci on de losbloques recibidos Aij y B ij y luego a nade elresultado al bloque C ij .

C ij = C ij + A ij B ij

Cada subtarea (i,j) env a su bloque B ij a suvecino, el cual est a previamente en la mismalnea vertical (los bloques de las subtareas dela primera la son enviadas a las subtareas dela ultima la de la malla).[3]

Fig. 14. Se procede a enviar el bloque de matriz correspondiente dela matriz A a trav es de su la, luego se calcula el producto con lamatriz B.

Fig. 15. Se procede a desplazar las las de la matriz B una posici onhacia arriba en forma circular.

Fig. 16. Se procede a enviar los siguientes bloques de matrices de lamatriz A a trav es de sus las.

Fig. 17. Se procede a hallar el producto de la matriz A y la matrizB, mediante los bloques de matrices.

Escalando y Distribuyendo las Subtareas entrelos Procesadores.

Los tama nos de los bloques de matrices puedenser seleccionados de tal manera que el n umerode subtareas puede coincidir con el n umerodisponible de procesadores p,

La ejecuci on m as eciente del algoritmoparalelo de Fox puede ser provista cuando la

5


6/14

topolog a de la red de comunicaci on es unamalla bidimensional.

En este caso las subtareas pueden serdistribuidas entre los procesadores en una formanatural: La subtarea (i,j) tiene que ser ubicadaen el procesador pi,j .

C. Algoritmo de Cannon.

La distribuci on de datos presenta un esquema detablero de damas.

Fig. 18. Esquema de las Dependencias de Informaci on.

La subtarea b asica es un procedimiento, quecalcula todos los elementos de un bloque de la matrizC .

A00 ...A 0(q 1)...

A(q 1)0 ...A (q 1)( q 1)

B 00 ...B 0(q 1)...

B (q 1)0 ...B (q 1)( q 1) =

C 00 ...C 0(q 1)

...C (q 1)0 ...C (q 1)( q 1)

C ij =q 1

s =0

A is B sj

An alisis de las Dependencias de Informaci on. La subtarea con el n umero (i, j ) calcula

el bloque C ij de la matriz resultante C .Como resultado, las subtareas forman la mallabidimensional q q .

La distribuci on inicial de los bloques dematrices en el algoritmo de Cannon esseleccionado de tal manera que la multiplicaci ondel primer bloque puede ser realizada sin env ode datos adicionales:

Al inicio cada subtarea (i, j ) tiene losbloques Aij y B ij ,

Para la i- esima la de la malla de subtareaslos bloques de la matriz A son desplazados(i 1) posiciones a la izquierda,

Para la j- esima columna de la malla desubtareas los bloques de la matriz B sondesplazadas ( j 1) posiciones hacia arriba,

La operaci on de env o de datos es un ejemplode comunicaci on de desplazamiento circular,

Fig. 19. Redistribuci on de los bloques de matrices en la primeraetapa del algoritmo

Luego de la redistribuci on, el cual ha sidoefectuado en la primera etapa, los bloques dematrices pueden ser multiplicados sin ning unenv o de datos adicional,

Para obtener el resto de bloques luego de laoperaci on de multiplicaci on de bloques:

Los bloques de la matriz A son desplazadosuna posici on a la izquierda a lo largo delas la de la malla,

Los bloques de la matriz B son desplazadosun posici on hacia arriba a los largo de lascolumnas de la malla.

Escalando y Distribuyendo las Subtareas entrelos Procesadores.

Los tama nos de los bloques de matricespueden ser seleccionados de tal manera queel numero de subtareas coincida con el n umerode procesadores disponibles p,

6


7/14

La ejecuci on m as eciente del algoritmoparalelo de Cannon puede ser proveida cuandola topolog a de la red de comunicaciones es unamalla bidimensional.

En este caso las subtareas pueden serdistribuidas entre los procesadores de unamanera natural: la subtarea

(i, j

) tiene que ser

ubicada en el procesador pij [2].

V. I MPLEMENTACI ON EN MPI

A. Algoritmos de Descomposici on en bloques derayas.

La implementaci on de los algoritmos dedescomposici on en bloques de rayas por columnasy por las se realiza de la siguiente manera:Primeramente en la implementaci on de ladescomposici on en bloques de rayas por columnasse crea un nuevo tipo de variable con la funci onMPI Type vector, lo cual nos permite poder crearun tipo de variable en MPI que referencia a lascolumnas de B.Luego se procede a enviar los bloques de las de lamatriz A a todos los procesadores con la funci onMPI Scatter, posteriormente se procede a enviar losbloques de columnas de la matriz B a todos losprocesadores.El env o de los bloques de rayas de B esdiferente seg un sea por columnas o por las. Sila descomposici on por bloques de rayas para Bes por las entonces est a se realiza simplementecon la funci on MPI Scatter, mientras que parael algoritmo de descomposici on por bloques derayas por columnas, se utiliza la variable columncreada anteriormente para el env o y recepci onde columnas. La implementaci on de la funci onque permite enviar bloques de columnas de B sepresenta en el C odigo 1.

void desc_col_send (float * matrix_A,float * matrix_B,float * local_A,float * local_B,MPI_Datatype column,int n,int my_rank,int local_n) {

int i, j;/ * Creacion de un nuevo tipo de variable

llamado column * / MPI_Type_vector(n, 1 , n, MPI_FLOAT, &column);

MPI_Type_commit( &column);

/ * Enviar los bloques de filas de la matriz Aa todos los procesadores * /

MPI_Scatter(matrix_A, local_n * n, MPI_FLOAT,local_A, local_n * n, MPI_FLOAT, 0 ,MPI_COMM_WORLD);

/ * Enviar los bloques de columnas de la matrizB a todos los procesadores * /

if (my_rank == 0 ) {for (i = 0 ; i < local_n; i ++ ) {

MPI_Sendrecv( &matrix_B[local_n * my_rank + i],1 , column, 0 , 0 , &local_B[i * n], n, MPI_FLOAT,0 , 0 , MPI_COMM_WORLD, &status);

}for (i = 1 ; i < size; i ++ ) {

for (j = 0 ; j < local_n; j ++ ) {MPI_Send( &matrix_B[local_n * i + j], 1 ,

column, i, 0 , MPI_COMM_WORLD);}

}

} else {for (j = 0 ; j < local_n; j ++ ) {

MPI_Recv( &local_B[j * n], n, MPI_FLOAT, 0 ,0 , MPI_COMM_WORLD, &status);

}}

}

Codigo 1. Funci on para enviar los bloques de las de la matriz

A y los bloques de columnas de la matriz B en el algoritmo de

Descomposici on en bloques de rayas por columnas.

Luego se realiza la implementaci on del buclede etapas, el cual halla los productos parciales de lamatriz resultante C.Finalmente, se recogen todos los bloques de losresultados de la matriz C en un solo resultadocon la funci on MPI Gather. El algoritmo de ladescomposici on en bloques de rayas por las realizaoperaciones an alogas s olo que se envian las de Ben lugar de columnas.

Las implementaciones del algoritmo dedescomposici on en bloques de rayas por columnasy del algoritmo de descomposici on en bloques derayas por las se encuentran en el C odigo 2 y elCodigo 3 respectivamente.

void desc_columnas (float * matrix_A,float * matrix_B,float * matrix_C,float * local_A,float * local_B,float * local_C,MPI_Datatype column,int n,int my_rank,int size,int local_n) {

int stage, i, j, k, temp, q, source, dest, ind;

7


8/14

/ * Envio de los valores de n y local_n a todoslos procesadores * /

MPI_Bcast( &local_n, 1 , MPI_INT, 0 , MPI_COMM_ WORLD);

MPI_Bcast( &n, 1 , MPI_INT, 0 , MPI_COMM_WORLD);

desc_col_send( &matrix_A, &matrix_B, &local_A,&local_B, column, n, local_n, my_rank);

/ * Se definen el destino y la fuente del enviode los bloques de columnas de la matriz B * /

source = (my_rank - 1 + size) % size;dest = (my_rank + 1 ) % size;q = n / local_n;

/ * Se definen el bucle de etapas delalgoritmo * /

for (stage = 0 ; stage < q; stage ++ ) {for (i = 0 ; i < local_n; i ++ ) {

for (k = 0 ; k < local_n; k ++ ) {temp = (my_rank - stage + size) % size;ind = local_n * temp + i * n + k;local_C[ind] = 0.0 ;/ * Realizar el producto de local_A y

local_B * / for (j = 0 ; j < n; j ++ ) {

local_C[ind] +=local_A[j + i * n] * local_B[j +k * n];

}}}/ * Se envia y recibe los bloques de columnas

de la matriz B * / MPI_Send(local_B, local_n * n, MPI_FLOAT,

dest, 0 , MPI_COMM_WORLD);MPI_Recv(local_B, local_n * n, MPI_FLOAT,

source, 0 , MPI_COMM_WORLD, &status);}

/ * Recolectar los bloques de filas de local_C de cada procesador en matrix_C * /

MPI_Gather(local_C, local_n * n, MPI_FLOAT,matrix_C, local_n * n, MPI_FLOAT, 0 ,MPI_COMM_WORLD);

}

Codigo 2. Implementaci on del algoritmo de descomposici on por

bloques de las para la matriz A y por bloques de columnas para la

matriz B en MPI.

void desc_filas (float * matrix_A,float * matrix_B,float * matrix_C,float * local_A,float * local_B,float * local_C,int n,int my_rank,int size,int local_n) {

int stage, i, j, k, q, source, dest, ind;/ * Enviar los valores de local_n y n a todos

los procesadores * / MPI_Bcast( &local_n, 1 , MPI_INT, 0 ,

MPI_COMM_WORLD);MPI_Bcast( &n, 1 , MPI_INT, 0 , MPI_COMM_WORLD);

/ * Enviar los bloques de filas de A a todoslos procesadores * /

MPI_Scatter(matrix_A, local_n * n, MPI_FLOAT,

local_A, local_n * n, MPI_FLOAT, 0 ,MPI_COMM_WORLD);

/ * Enviar los bloques de filas de B a todoslos procesadores * /

MPI_Scatter(matrix_B, local_n * n, MPI_FLOAT,local_B, local_n * n, MPI_FLOAT,0 , MPI_COMM_WORLD);

/ * Se definen el destino y la fuente del enviode los bloques de columnas de la matriz B * /

source = (my_rank - 1 + size) % size;dest = (my_rank + 1 ) % size;q = n / local_n;

Set_to_zero(local_C);/ * Se definen el bucle de etapas del

algoritmo * / for (stage = 0 ; stage < q; stage ++ ) {

ind = (my_rank - stage + size) % size;for (j = 0 ; j < local_n; j ++ ) {

for (i = 0 ; i < n; i ++ ) {/ * Realizar el producto de local_A y

local_B * / for (k = 0 ; k < local_n; k ++ ) {

local_C[i + j * n] +=local_A[local_n * ind +k +j * n] * local_B[i + k * n];

}}

}/ * Se envia y recibe los bloques de filas

de la matriz B * / MPI_Send(local_B, local_n * n, MPI_FLOAT,dest, 0 , MPI_COMM_WORLD);

MPI_Recv(local_B, local_n * n, MPI_FLOAT,source, 0 , MPI_COMM_WORLD, &status);

}/ * Recolectar los bloques de filas de local_C

de cada procesador en matrix_C * / MPI_Gather(local_C, local_n * n, MPI_FLOAT,

matrix_C, local_n * n, MPI_FLOAT, 0 ,MPI_COMM_WORLD);

}

Codigo 3. Implementaci on del algoritmo de descomposici on por

bloques de las para la matriz A y por bloques de las para la matriz

B en MPI.

B. Algoritmos de Fox y Cannon.

Para la implementaci on de los algoritmos deFox y de Cannon, escribiremos una funci on quecrea varios comunicadores y asociaciones de datos.Como esto requiere una gran cantidad de variables,y adem as usaremos esta informaci on en otrasfunciones, pondremos esto en una estructura parafacilitar el paso como par ametro.La creaci on de una topolog a cartesiana enMPI nos va a permitir en las implementacionescorrespondientes a los algoritmos de Fox y deCannon, un manejo m as facil de los env os debloques a traves de las las y las columnas delas respectivas mallas de procesos, ya que esto nospermite crear subcomunicadores en las y columnas.Para esto vamos a usar una estructura que identicaa cada proceso, incluyendo los comunicadores de los

8


9/14

cuales el proceso forma parte. La implementaci onde la estructura se muestra en el C odigo 4.

typedef struct {/ * Total de procesos * / int p;/ * Comunicador del grid * / MPI_Comm comm;/ * Comunicador para la fila * / MPI_Comm row_comm;/ * Comunicador para la columna * / MPI_Comm col_comm;/ * Orden del grid * / int q;/ * Numero de fila * / int my_row;/ * Numero de columna * / int my_col;/ * Rank en el comunicador delgrid * / int my_rank;

} GRID_INFO_T;

Codigo 4. Implementaci on de la estructura que identica a cada

proceso.

Tambi en se va a utilizar una estructura querepresenta a la matriz local en cada proceso, es decirel sub-bloque de matriz que cada proceso recibeluego de haber realizado la descomposici on ensub-bloques de matrices y la respectiva distribuci onentre los procesos.El C odigo 5 muestra la implementaci on de laestructura que representa a la matriz local en cadaproceso.

typedef struct {// Indica el orden del sub-bloque

int n_bar;/ * Define un alias para el orden del sub-bloque * / #define Order(A) ((A)->n_bar)/ * Vector que almacena los elementos del sub-bloque * /

float entries[MAX];/ * Define un alias para un elemento del subloque * / #define Entry(A, i, j) ( * (((A)->entries) + ((A) -> n_bar) * (i) + (j)))} LOCAL_MATRIX_T;

Codigo 5. Implementaci on de la estructura que representa a la matriz

local en cada proceso.

En la implementaci on se dene un nuevotipo de datos llamado local matrix mpi t el cualrepresenta una matriz local en cada proceso a partirde la estructura LOCAL MATRIX T lo que nos vaa permitir y facilitar el env o y recepci on de bloquesde matrices entre las y columnas conforme vayaavanzando el algoritmo.Luego de crear un comunicador de la topolog acartesiana que se requiere para todos los

procesadores con la funci on MPI Cart create,se procede a particionar la malla de procesos creadaen submallas, tanto para las las como para lascolumnas, es decir, se crean comunicadores quepermitan comunicaci on entre los procesos de unala o una columna en la malla de procesos globalcon la funci on MPI Cart sub para el consecuenteenv o y recepci on de bloques de submatrices atrav es de las o columnas.Las coordenadas de cada proceso en la malla deprocesos que se cre o se obtiene con la funci onMPI Cart coords las cuales luego se guardan enlas variables grid.my row para la la y grid.my colpara la columna a la cual pertenece cada procesos,las mismas que se encuentran en la estructuramencionada en el C odigo 4.Los algoritmos de Fox y de Cannon tienes similaresimplementaciones, variando b asicamente en elmovimiento de los sub-bloques de matrices de lamatriz B en cada etapa.

Las implementaciones de los algoritmos deFox y de Cannon se muestran en el C odigo 6 y elCodigo 7 respectivamente.

void Fox (int n,GRID_INFO_T * grid,LOCAL_MATRIX * local_A,

LOCAL_MATRIX * local_B,LOCAL_MATRIX * local_C) {

LOCAL_MATRIX * temp_A;

int stage; / * Representa laetapa del algoritmo * /

int bcast_root;int n_bar;int source;int dest;MPI_Status status;

n_bar = n / grid -> q; / * Indica el orden delsub-bloque (matriz local) * /

Set_to_zero(local_C);

/ * Calcula las direcciones para eldesplazamiento circular de B * /

source = (grid -> my_row + 1 ) %grid -> q;dest = (grid -> my_row + grid -> q - 1 ) %grid -> q;

/ * Almacena espacio para el envio del bloquede A * /

temp_A = Local_matrix_allocate(n_bar);

/ * Bucle de etapas * / for (stage = 0 ; stage < grid -> q; stage ++ ) {

/ * Calcula que bloque se va a enviar atraves de las filas * /

bcast_root = (grid -> my_row + stage) %grid -> q;/ * Se encarga del envio de los bloques de A

a traves de sus filas * / if (bcast_root == grid -> my_col) {

MPI_Bcast(local_A, 1 , local_matrix_mpi_t ,

9


10/14

bcast_root, grid -> row_comm);Local_matrix_multiply(local_A, local_B,

local_C);} else {

MPI_Bcast(temp_A, 1 , local_matrix_mpi_t ,bcast_root, grid -> row_comm);

Local_matrix_multiply(temp_A, local_B,local_C);

}/ * Se encarga del desplazamiento de los

bloques de B a traves de sus columnas * / MPI_Sendrecv_replace(local_B, 1 ,local_matrix_mpi_t , dest, 0 , source, 0 ,grid -> col_comm, &status);

} / * for * /

} / * Fox * /

Codigo 6. Implementaci on del algoritmo de Fox en MPI.

void Cannon (int n ,GRID_INFO_T * grid ,LOCAL_MATRIX_T * local_A,LOCAL_MATRIX_T * local_B,LOCAL_MATRIX_T * local_C

) {

int stage;int source_r, source_c;int dest_r, dest_c;MPI_Status status;

Set_to_zero(local_C);

for (stage = 0 ; stage < grid -> q; stage ++ ) {if (stage == 0 ) {

source_r = (grid -> my_col + grid -> my_row)% grid -> q;dest_r = (grid -> my_col + grid -> q - grid -> my_row)

% grid -> q;source_c = (grid -> my_row + grid -> my_col)

% grid -> q;dest_c = (grid -> my_row + grid -> q - grid -> my_col)

% grid -> q;MPI_Sendrecv_replace(local_A, 1 ,

local_matrix_mpi_t , dest_r, 0 , source_r, 0 ,grid -> row_comm, &status);

MPI_Sendrecv_replace(local_B, 1 ,local_matrix_mpi_t , dest_c, 0 , source_c, 0 ,grid -> col_comm, &status);

Local_matrix_multiply(local_A, local_B,local_C);

} else {source_r = (grid -> my_col + 1 ) % grid -> q;dest_r = (grid -> my_col + grid -> q - 1 )

% grid -> q;source_c = (grid -> my_row + 1 ) % grid -> q;dest_c = (grid -> my_row + grid -> q - 1 )

% grid -> q;MPI_Sendrecv_replace(local_A, 1 ,

local_matrix_mpi_t , dest_r, 0 , source_r,0 , grid -> row_comm, &status);

MPI_Sendrecv_replace(local_B, 1 ,local_matrix_mpi_t , dest_c, 0 , source_c,0 , grid -> col_comm, &status);

Local_matrix_multiply(local_A, local_B,local_C);

}

} / * for * /

} / * Cannon * /

Codigo 7. Implementaci on del algoritmo de Cannon en MPI.

VI. E VALUACI ON E XPERIMENTAL

Todos los experimentos fueron ejecutados en unamaquina con un procesador dual-core Intel Core T M

i3-2350M corriendo con 2.30 GHz, 4GB de RAM,y 500 GB de disco duro. El procesador simulaun procesador quad-core mediante la tecnolog ahyperthreading. El sistema operativo utilizado fueUbuntu 13.10 de 64 bits.

Los experimentos se desarrollaron con unnumero cuadrado perfecto de procesos, ya quees el n umero requerido por los algoritmos deFox y Cannon. Adem as el orden de las matricesfueron divisibles por la ra z cuadrada del n umerode procesos. Los algoritmos de descomposici onpor bloques de rayas por las y por columnas norequieren este requisito, solo necesitan que el ordende las matrices sean divisibles por el n umero deprocesos. Para la uniformidad en la realizaci ondel experimento se tomaron un n umero cuadradoperfecto de procesos.

El primer experimento desarrollado fue la evaluaci onde todos los algoritmos, tanto el secuencial comolos paralelos. El algoritmo secuencial se corri ocon s olo un proceso, mientras que los algoritmosparalelos se corrieron con 4 procesos. obteniendolos tiempos en segundos en la tabla 1. Se obtuvoclaramente una reducci on del tiempo de ejecuci onen los algoritmos paralelos en comparaci on con elalgoritmo secuencial.Esta diferencia se hizo mas evidente cuando elorden de las matrices crec a.

Tabla 1 : Algoritmos para la Multiplicaci on de Matrices, Secuencial y Paralelos, desde el m as r apido al m as lento.

n Algoritmo1 Desc. por Columnas2 Desc. por Filas3 Fox y Cannon4 Secuencial

El segundo experimento desarrollado fue lacomparaci on de rendimiento entre los algoritmosparalelos corridos con diferente n umero de procesos,

10


11/14

precisamente con 4 y 9 procesos.Al realizar la ejecuci on de los algoritmos con4 procesos, se obtiene como resultado que losalgoritmo de Fox y Cannon tienen un rendimientomuy similar, los cuales son los m as lentos, luegoviene el algoritmo de Descomposici on en bloquesde rayas por las y siendo el algoritmo m as rapidoel algoritmo de Descomposici on en bloques derayas por columnas.

Tabla 2 : Algoritmos Paralelos para la Multiplicaci on de Matricesdesde el m as r apido al m as lento.

n Algoritmo1 Desc. por Columnas2 Desc. por Filas3 Fox y Cannon

Al realizar la ejecuci on de los algoritmos con9 procesos, se obtiene como resultado unaralentizaci on del tiempo de ejecuci on de losalgoritmos lo cual se debe a la no existencia delos 9 procesadores f sicos, ya que la m aquinasolo cuenta con un procesador quad-core simuladomediante hyperthreading, adem as las operacionesque realiza cada procesador es independiente deotras operaciones, as que lo que sucede es quecada procesaor realiza el trabajo de dos o m asprocesadores, consecuentemente ralentizando elproceso. A un bajo esta deciencia de procesadoresse obtiene el mismo resultado que al correrlo con4 procesadores, es decir los algoritmos de Foxy Cannon muestran un rendimiento muy similarsiendo los algoritmos m as lentos, luego vieneel algoritmo por Descomposici on en bloques derayas por las y siendo el algoritmo m as r apido elalgoritmo de Descomposici on en bloques de rayaspor columnas.

Los tama nos de los sub-bloques de matricesen los algoritmos de Fox y Cannon no semodicaron debido a la necesidad de que el n umerode procesadores debe ser siempre un cuadradoperfecto, as que se necesitar an 4, 9, 16, 25, ...procesadores, con lo cual la m aquina en la cual serealiz o el experimento no cont o.Si se realizaran las pruebas con un n umero cuadradoperfecto de procesadores los resultados podr anvariar, siendo la diferencia entre el tiempo deejecuci on de los algoritmos paralelos diferente.

Las Tabla 3 muestra los tiempos de ejecuci onde los algoritmos secuencial, descomposici on enbloques de rayas por columnas, descomposici on enbloques de rayas por las, algoritmo de Fox y elalgoritmo de Cannon. Los tiempos se obtuvieronpara diferentes valores de n, donde n es el ordende las matrices. La Tabla 4 y la Tabla 5 muestralo mismo que la Tabla 3 s olo que para algoritmosparalelos, donde varian el orden de las matrices as como tambien el numero de procesos usados.

Tabla 3 : Resultados de las pruebas con el algoritmo secuencial ycon los algoritmos paralelos con 4 procesos.

n secuencial fox cannon columnas las100 0.013 0.007 0.004 0.011 0.003200 0.115 0.036 0.034 0.037 0.027300 0.421 0.109 0.106 0.106 0.085

400 1.020 0.266 0.253 0.263 0.195500 2.197 0.515 0.509 0.520 0.380600 4.905 0.945 0.914 0.906 0.651700 8.316 1.556 1.572 1.489 1.042800 12.744 2.472 2.341 2.353 1.560900 19.459 3.772 3.920 3.685 2.254

1000 28.275 5.332 5.410 5.327 3.1201100 37.625 7.383 6.967 7.535 4.1381200 46.006 10.048 9.590 9.305 5.3691300 63.223 13.148 13.079 13.265 6.8161400 80.378 16.148 16.093 16.612 8.7181500 102.166 21.094 20.721 21.134 10.3651600 121.269 23.475 24.043 23.505 13.0481700 155.612 30.737 30.700 31.229 15.219

1800 185.411 36.888 37.088 37.227 18.0651900 223.159 43.847 43.436 44.885 21.5162000 250.386 51.197 51.091 47.893 24.892

Nota : n indica el orden de las matrices; los tiempos obtenidos est anen segundos.

Fig. 20. Gr aco comparativo entre los algoritmos para lamultiplicaci on de matrices.

11


12/14

Fig. 21. Gr aco comparativo entre los algoritmos para la multiplicaci onde matrices.

Tabla 4 : Resultados de las pruebas de la comparaci on entre losalgoritmos paralelos con 4 procesos.

n fox cannon columnas las500 0.555 0.562 0.413 0.594

1000 5.748 5.821 3.618 5.7601500 24.694 22.441 12.188 22.4662000 56.297 53.960 29.205 51.3372500 115.826 109.863 55.995 109.9013000 197.441 195.338 94.616 194.7743500 333.874 335.016 149.720 307.5274000 485.203 486.080 216.485 461.495

4500 747.743 746.517 312.831 687.3615000 1057.940 1071.888 414.371 1010.247


Fig. 22. Gr aco comparativo entre los algoritmos paralelos para lamultiplicacion de matrices.


Tabla 5 : Resultados de las pruebas de la comparaci on entre losalgoritmos paralelos con 9 procesos.

n fox cannon columnas las600 1.200 1.183 0.880 1.556

1200 9.774 9.972 5.867 9.6391800 36.180 35.707 20.724 36.1402400 88.718 86.349 43.916 79.4923000 190.054 192.634 88.463 175.8643600 309.693 308.910 147.635 300.1384200 544.088 532.041 228.694 526.6504800 809.645 810.702 341.534 780.3685400 1237.267 1220.376 487.096 1091.212


Fig. 24. Gr aco comparativo entre los algoritmos paralelos para lamultiplicaci on de matrices.

12


13/14


VII. D ISCUSIONES

La reducci on del tiempo de ejecuci on entre elalgoritmo secuencial y los algoritmos paralelos sefundamenta b asicamente en la reducci on signicativade la cantidad de bucles realizados por el algoritmo.Si consideramos que el algoritmo secuencial tiene 3bucles anidados con cada bucle de tama no n. Estotoma mucho tiempo, especialmente si n es lo bastantegrande.En el algoritmo de descomposici on en bloques derayas por columnas y por las existen tambi en 3bucles anidados, pero solo uno de ellos es de tama non, mientras que los otros dos son de tama no local n,donde local n depende de el n umero de procesosusados, mientras mayor sea el n umero de procesosentonces, menor ser a local n y por lo tanto menorser a el trabajo que realice cada proceso terminandomas rapidamente.En los algoritmos de Fox y Cannon hay unbucle global de tama no igual al n umero deetapas que necesita el algoritmo para nalizar suejecuci on. El bucle global engloba a la funci onLocal matrix multiply la cual es una funci on quetiene tres bucles anidados de tama no igual al ordende las sub-matrices en las cuales se ha divididolas matrices A y B. Por lo tanto si el orden delas sub-matrices es menor, entonces menor ser atambi en el tiempo de ejecuci on de los algoritmos.Recordemos que el orden de las submatrices dependedel numero de procesos que se escoja para correr elprograma, mientras mayor sea el n umero de procesos,

entonces menor ser a el orden de las sub-matrices ypor lo tanto se reducir a el tiempo de ejecuci on delos algoritmos de Fox y Cannon.En general si el n umero de procesadores aumentaentonces el tamano de los bucles en los algoritmosparalelos disminuye y por lo tanto el tiempo deejecuci on disminuye.

VIII. C ONCLUSIONES

Los algoritmos paralelos para la multiplicaci onde matrices permiten reducir el tiempo de ejecuci onsignicativamente respecto al algoritmo secuencial,y esto se hace a un mas evidente cuando el orden delas matrices empieza a crecer.

Los algoritmos paralelos m as r apidos obtenidosexperimentalmente fueron los algoritmos de

Descomposici on en bloques de rayas por columnasy Descomposici on en bloques de rayas porlas, siendo el m as r apido el algoritmo deDescomposici on en bloques de rayas por columnas.

La superioridad de los algoritmos deDescomposici on en bloques de rayas por lasy de Descomposici on en bloques de rayas porcolumnas sobre los algoritmos de Fox y Cannon sedeben b asicamente a los costos de comunicaci onentre procesos, ya que en los algoritmos de Fox y

Cannon existe una mayor divisi on en sub-bloquesde las matrices a diferencia de los algoritmosde Descomposici on en bloques de rayas, lo cualimplica una mayor cantidad de comunicacionesentre los procesos.Si el numero de procesadores f sicos con los que secuenta no es muy grande entonces conviene m asusar el algoritmo de descomposici on en bloques derayas por columnas, de otra manera convendr a masusar el algoritmo de Fox o el algoritmo de Cannon.Los c odigos de las implementaciones de

los algoritmos paralelos en MPI parala multiplicaci on de matrices se puedenencontrar en la siguiente direccion web :https://github.com/DavidAparco/MatrixMultiplication

IX. T RABAJOS RELACIONADOS Y T RABAJOS AF UTURO

Existen varios otros algoritmos paralelos adem asde los mencionados en este art culo que presentanuna aproximaci on diferente a los tratados en este

13


14/14

art culo como el algoritmo de SUMMA [14],PUMMA [15] y DIMMA[16].En este trabajo hemos desarrollado los algoritmosparalelos para la multiplicaci on de matrices, loscuales fueron corridos en una m aquina quad-corede 64 bits, lo cual limit o el an alisis experimentalde los algoritmos de Fox y Cannon, ya que nose cont o con una mayor cantidad de procesadores.Los trabajos a futuro buscar an poder correr losalgoritmos paralelos en m aquinas con un mayornumero de procesadores, adem as de aplicar losalgoritmos paralelos a problemas pr acticos comola predicci on del clima, sistemas de bases de datos,compresi on de datos y otros. Adem as un trabajo afuturo podr a ser la implementaci on en OpenMP delos algoritmos tratados en este art culo.

R EFERENCIAS B IBLIOGR AFICAS

[1] V. Kumar, A. Grama, A. Gupta, G. Karypis, Introduction toParallel Computing , 2nd ed. Addison-Wesley, 2003.

[2] M. J. Quinn, Parallel Programming in C with MPI and OpenMP .New York,NY:McGraw-Hill, 2004.

[3] G. C. Fox, S. W. Otto, A. J. G. Hey, Matrix Algorithms on a Hypercube I: Matrix Multiplication . Parallel Computing. 4H.17-31

[4] M. Nakkeeran, R. M. Chandrasekaran, Parallel Matrix Multiplication Implementation In Distributed Environment Through RMI . Journal of Theoretical and Applied InformationTechnology. 2005-2011. 73-78

[5] Ziad A. A. Alqadi, Musbah Aqel, Ibrahiem M. M. El

Emary, Performance Analysis and Evaluation of Parallel Matrix Multiplication Algorithms . World Applied Sciences Journal.2008. 211-214

[6] Yuster Raphael, Uri Zwick, Fast Sparse Matrix Multiplication .12th Annual European Symposium on Algorithms. 2004

[7] V. Pan, How to multiply matrices faster . Lecture Notes inComputer Science, Volume 179. Springer-Verlag. 1985

[8] D. Coppersmith, S. Winograd, Matrix multiplication viaarithmetic progressions . Journal of Symbolic Computation.1990. 9:251-280

[9] V. Strassen, Gaussian elimination is not optimal . NumerischeMathematik. 1969. 13:354-356

[10] R. Yuster, U. Zwick, Detecting short directed cycles usingrectangular matrix multiplication and dynamic programming . InProc. of 15th SODA. 2004. 247-253

[11] N. Alon, R. Yuster, U. Zwick, Finding and counting given lengthcycles . Algorithmica . 1997. 17:209-223

[12] D. Kratsch, J. Spinrad, Between O (nm ) and O (n ). In Proc.of 14th SODA. 2003. 709-716

[13] A. Shpilka, Lower bounds for matrix product . SIAM Journalon Computing. 2003. 32:1185-1200

[14] Robert A. van de Geijn, Jerrell Watts, SUMMA : ScalableUniversal Matrix Multiplication Algorithm . Concurrency Comput.Practice Experience, 9 (1997), pp 255-274

[15] Choi J., J. J. Dongarra, and D. W. Walker, PUMMA :Parallel Universal Matrix Multiplication Algorithms on distributed memory concurrent computers . Concurrency: Practice andExperiencce, Vol. 6(7), 543-570, 1994

[16] Jaeyooung Choi, , A New Parallel Matrix Multiplication Algorithm on Distributed-Memory Concurrent Computers . HighPerformance Computing on the Information Superhighway, 1997,pp 224-229

algoritmos paralelos para la multiplicación de matrices

Documents