Escola Tècnica Supe io d’Enginye ia In o mà ica
Uni e si a Poli ècnica de València
Es udio compa a i o de las p es aciones de di e en es modelos de
p og amación pa alela
T abajo Fin de G ado
G ado en Ingenie ía In o má ica
Au o : En ique Gil A cas
Tu o : Fede ico Silla Jiménez
2014-15
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
2
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
3
Resumen
Hoy día disponemos de múl iples soluciones pa a el p ocesamien o de g andes olúmenes de
da os, pe o no es i ial selecciona la más adecuada pa a cada ipo de si uación. Debemos ene
en cuen a, en cada caso, el ipo de ha dwa e disponible, la can idad de in o mación que
que emos p ocesa y la ecnología so wa e aplicable en e o os muchos aspec os.
En es e abajo hemos p o undizado en dis in os pa adigmas de p og amación an o pa alela
como dis ibuida. Basándonos en un sencillo algo i mo de mul iplicación de ma ices, hemos
ealizado di e sas implemen aciones a pa i de dis in as soluciones so wa e (MPI, OpenMP,
P h eads, CUDA, e c) y las hemos p obado sob e di e sos ipos de ha dwa e (p ocesado es,
a je as g á icas y cop ocesado es ec o iales), ealizando un análisis de los esul ados y
ex ayendo conclusiones.
Palab as cla e: MPI, OpenMP, P h eads, CUDA, AVX, clus e , compa ida, dis ibuida,
pa alela, cop ocesado , GPU, In iniBand.
Abs ac
Nowadays, we ha e a lo o solu ions o p ocess big amoun s o da a, bu i is no easy o
selec he mos adequa e on each kind o si ua ion. We should ake ca e o : The di e en
a ailable ha dwa es, he amoun o da a o p ocess and he applicable so wa e echnology
In his s udy we wen in dep h wi h di e en pa adigms o pa allel and dis ibu ed
p og aming. We ha e aken a simple ma ix mul iplica ion algo i hm as base o de elop a ious
implemen a ions using di e en so wa e solu ions (MPI, OpenMP, P h eads, CUDA, e c) and
we es ed hem o e di e en ypes o ha dwa e (p ocesso s, cop ocesso s and g aphics ca ds)
making an analysis o he esul s and d awing conclusions.
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
4
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
5
Tabla de con enidos
1. In oducción. ................................................................................................................. 8
2. En o nos de compu ación pa alela y dis ibuida. ............................................................ 11
2.1 Compu ación pa alela. .......................................................................................... 11
2.2 Compu ación dis ibuida. ...................................................................................... 11
2.3 Ley de Amdahl. .................................................................................................... 11
2.4 Memo ia compa ida y memo ia dis ibuida. .......................................................... 12
2.5 Hilos o h eads. .................................................................................................... 13
2.5.1 p h eads.h. .................................................................................................... 14
2.5.2 OpenMP. ...................................................................................................... 14
2.6 Message Passing In e ace. .................................................................................... 15
2.7 Ha dwa e. ........................................................................................................... 15
2.7.1 Red de in e conexión. ................................................................................. 15
2.7.2 Cop ocesado ec o ial. .............................................................................. 19
2.7.3 GPU. ........................................................................................................... 20
3. P og amas ealizados. .................................................................................................. 22
In oducción. .................................................................................................................. 22
3.1 Tes MPI. ............................................................................................................ 22
3.2 Tes MPI + P h eads. ........................................................................................... 26
3.3 Tes MPI + OpenMP. ........................................................................................... 30
3.4 Recopilación. ....................................................................................................... 34
3.5 EFECTO DE LA MEMORÍA. .............................................................................. 34
3.5.1 Tes MPI s MPI ( anspues a). ....................................................................... 35
3.5.2 Tes MPI + P h eads s MPI + P h eads ( anspues a). ..................................... 37
3.5.3 Tes MPI + OpenMp s MPI + OpenMP ( anspues a). .................................... 39
3.5.4 Recopilación. .................................................................................................... 41
3.6 Cop ocesado ec o ial: unciones in ínsecas. ...................................................... 44
3.7 Cop ocesado ec o ial: au o ec o izado . ............................................................. 49
3.8 Recopilación. ....................................................................................................... 52
3.9 GPU. ................................................................................................................... 53
3.10 Recopilación inal. ................................................................................................ 57

Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
6
4. Conclusiones. .............................................................................................................. 58
5. Bibliog a ía. ................................................................................................................ 60
Anexo: Guía de usua io pa a el clus e DISCA ...................................................................... 61
1 CONEXIÓN .............................................................................................................. 62
1.1 Conexión VPN ................................................................................................... 62
1.2 Conexión SSH ................................................................................................... 62
1.3 Den o del F on end ......................................................................................... 63
2 TRABAJANDO CON MPI ........................................................................................ 64
3 HÍBRIDOS DE MEMORIA COMPARTIDA ............................................................ 65
3.1 MPI + OMP ....................................................................................................... 66
3.2 MPI + PTHREADS ............................................................................................ 67
4 MPI + CUDA ............................................................................................................. 67
5 MPI + COPROCESADOR VECTORIAL ................................................................... 67
6 LINKS DE INTERÉS ................................................................................................ 69
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
7
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
8
1. In oducción.
Los ab ican es de mic op ocesado es, como In el o AMD, han desa ollado a lo la go
de los años diseños cada ez más elabo ados con la inalidad de aumen a las p es aciones de los
compu ado es. En es e sen ido, cuando debido a p oblemas de disipación de calo ya no les ue
posible con inua aumen ando la ecuencia de eloj a la que abajaban sus p oduc os, se
lanza on a la búsqueda de nue as o mas de inc emen a la po encia compu acional de sus
desa ollos, c eando inalmen e lo que hoy en día es algo habi ual pa a odos: los p ocesado es
mul inúcleo (mul ico e).
Los p ocesado es mul inúcleo se basan en inclui a ios núcleos de compu ación den o
del mismo encapsulado, cada uno de ellos abajando ípicamen e a ecuencias de eloj algo
meno es que las que se u iliza ían en un chip con un único núcleo. Sin emba go, a pesa de las
meno es ecuencias de eloj u ilizadas, las p es aciones globales del p ocesado mul inúcleo
son no ablemen e mayo es que las de los diseños an e io es basados en un único núcleo siemp e
y cuando la aplicación que se ejecu e en dicho p ocesado sea capaz de epa i sus a eas en e
los di e en es núcleos del p ocesado , momen o en el cual se puede llega a consegui
impo an es educciones en el iempo de ejecución.
Pa a consegui que una aplicación man enga los di e en es núcleos del p ocesado en
uso, se suelen usa mecanismos de p og amación de memo ia compa ida basados en hilos
( h eads). Median e es e mecanismo el p og amado di ide la compu ación a ealiza en
di e en es hilos de ejecución y asigna cada uno de es os hilos a un núcleo di e en e del
p ocesado , de o ma que odos a ancen en su ejecución de o ma concu en e. Ob iamen e,
hace al a man ene los di e en es hilos sinc onizados, hecho que acaba complicando la
p og amación de la aplicación. Po es a azón, se han c eado en o nos de p og amación como
OpenMP, que acili an la p og amación con hilos, aunque en ocasiones puede esul a en una
lige a pé dida de p es aciones dado que algunas de las decisiones de p og amación las oma el
compilado .
En cualquie caso, hay nume osos p oblemas de g an en e gadu a que incluso con el
uso de los múl iples núcleos de un p ocesado (o con los núcleos de los di e sos p ocesado es
exis en es en un compu ado dado) aún p esen an iempos de ejecución demasiado ele ados. Po
ello, y con la inalidad de educi es os ele ados iempos de ejecución, se hace uso de
mecanismos de paso de mensajes, como la lib e ía MPI (Message Passing In e ace), que
pe mi en dis ibui la compu ación a ealiza en e los di e en es nodos de un clús e , usando un
modelo de memo ia dis ibuida no compa ida. Nó ese que en cada compu ado in oluc ado en
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
9
la ejecución de la aplicación dis ibuida aún se puede segui u ilizando la p og amación basada
en hilos.
Finalmen e, en los úl imos años se ha dado un g an sal o en la educción del iempo de
ejecución de nume osas aplicaciones a base de usa acele ado es de di e en e índole. Quizás el
ipo de acele ado más u ilizado sea la GPU (G aphics P ocessing Uni s), que no es o a cosa
que una a je a g á ica de las comúnmen e u ilizadas en los o denado es de sob emesa pa a
do a les de capacidades g á icas pa a mos a en anas y ambién pa a los ideojuegos, pe o
adap adas pa a su uso en compu ación. Cabe des aca que el uso de las GPUs es compa ible con
la p og amación basada en hilos y con la p og amación basada en lib e ías de paso de mensajes,
pudiendo combina las es écnicas pa a log a mayo es educciones del iempo de ejecución.
En es e abajo se p e ende p o undiza en la compu ación pa alela y dis ibuida. A lo
la go de la ca e a se han e isado de o ma b e e los concep os más sencillos de es as écnicas.
No obs an e, en es e abajo se amplían de o ma no able los conocimien os sob e es as écnicas
especialmen e a ni el p ác ico. Pa a ello se u ilizan di e sos pa adigmas de p og amación y
combinándolos en e sí, ealizando además un es udio compa a i o de los endimien os que se
ob ienen en cada caso. Pa a ello, se pa e de un algo i mo sencillo como es la mul iplicación de
ma ices, que esul a muy ú il pa a ca ga de abajo un clús e de compu ado es y se modi ica
pa a adap a lo a los modelos de p og amación mencionados, de mane a que el alumno ealiza á
di e sas implemen aciones de dicho algo i mo usando dis in as he amien as an o so wa e
como ha dwa e. A ni el so wa e se u iliza án las ecnologías OpenMP, MPI, P h eads,
unciones in ínsecas pa a ec o ización, au o ec o ización y CUDA. És as se u iliza án
combinadas en e sí, usando siemp e el lenguaje de p og amación C como nexo. Respec o a la
pa e ha dwa e, se desa olla án implemen aciones pa a su ejecución en p ocesado es
mul inúcleo, en cop ocesado es ec o iales y en GPUs.
El segundo obje i o de es e abajo ha sido p oba dichas implemen aciones en un
en o no eal en uncionamien o, pa a ello nos hemos se ido del clus e que ges iona el G upo
de A qui ec u as Pa alelas del depa amen o DISCA de la ETSINF en la Uni e sidad
Poli écnica de Valencia. Cuando se abaja con un clus e hay que ene en cuen a sus
ca ac e ís icas p opias como el ipo de ha dwa e del que dispone, po ejemplo: la ma ca y
modelo de los p ocesado es, si hay o no a je as g á icas y de qué ipo, la can idad de memo ia
RAM po nodo, el ipo de ed de in e conexión en e nodos, si dispone de una in e az de disco
du o compa ida, e c. Igual de impo an e es conoce el ipo de so wa e ins alado, en nues o
caso es necesa io conoce la implemen ación disponible de MPI, ya que en e unas y o as
pueden habe su iles di e encias, como po ejemplo, el amaño máximo de mensaje, que pa a
noso os es un ac o de e minan e en nues a a ea. También nos es i al conoce qué e sión de
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
16
2.7.1.1 Topología.
Un ac o impo an e de la ed es su opología. Cuando amos a ealiza el mon aje de
un clus e eó icamen e nos gus a ía ene una conexión ísica di ec a en e odos los pa es de
nodos del clus e . No obs an e, si en dicho clus e enemos un núme o ele ado de equipos muy
p obablemen e nos amos a encon a con limi aciones ísicas y económicas. Po ello hay que
ecu i a o o ipo de opologías como po ejemplo en anillo, en o o, en es ella,…
Con una es uc u a en anillo cada e minal se conec a únicamen e con o os dos
miemb os de la ed. Es a opología iene el incon enien e de que si que emos en ia un mensaje
a un equipo que es á en la pa e más alejada del anillo el mensaje end á que pasa a a és de
odos los equipos que encuen e en su camino, inc emen ando po an o la la encia del mismo.
Ilus ación 2: Topología anula .
Ilus ación 3: Topología o oide.

Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
17
En la ilus ación an e io emos una disposición o oidal de dos dimensiones, cada
equipo es á conec ado di ec amen e con o os cua o miemb os de la ed, de es a mane a se
educe el núme o de sal os pa a comunica los pa es más alejados de la ed. No obs an e, el
cos e económico de una opología en o o es mucho más ele ado que o as opologías más
sencillas, como po ejemplo la opología en es ella.
La o ganización en o ma de es ella educe el núme o máximo de sal os pa a
comunica pa es de nodos a dos. Como incon enien e enemos que odo el á ico pasa po el
nodo cen al. Una op imización pa a es e modelo es sus i ui el nodo cen al po un swi ch.
En los clus e s ac uales, y debido a azones económicas de adquisición del
equipamien o y de mon aje y man enimien o de la ed, la opología más u ilizada hoy en día es
la es ella jun o con o as de i adas, como pueden se a ias es ellas in e conec adas. Es e es el
caso, po ejemplo, de edes E he ne . O as edes de mayo es p es aciones, como In iniBand,
ambién pueden adap a es a opología.
2.7.1.2 Enlaces.
Una de las p incipales ca ac e ís icas de la ed es la asa de bi s que no es más que el
núme o de bi s que se ansmi en po unidad de iempo en e dos e minales a a és de la p opia
Ilus ación 4: Topología en es ella.
Ilus ación 5: Topología en es ella con swi ch
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
18
ed. Cuan o mayo sea la asa de bi s, los mensajes a da án menos iempo en llega y an es se á
posible p ocesa los. El elemen o ha dwa e que a a de e mina dicha asa es el enlace, jun o con
las a je as de ed (capas del ni el de enlace y ísico de la pila de p o ocolos TCP/IP).
Típicamen e se u iliza cable compues o de pa es enzados de cob e ( ambién se usa
cable coaxial o ib a óp ica) pa a mon a edes E he ne , en unción de la ca ego ía del cable
amos a pode abaja con dis in os es ánda es que nos o ecen di e en es asas de bi s, las
soluciones come ciales llegan has a 1Gbi /s aunque se han desa ollado es ánda es pa a
unciona a 10Gbi /s.
Sin emba go, el clus e sob e el que amos a abaja dispone de ecnología In iniBand.
In iniBand es á compues o po enlaces se ie bidi eccionales que pueden añadi se en g upos de 4
o 12, llamados 4X o 12X. Es os enlaces pueden abaja a dis in os da a a es: SDR (Single
Da a Ra e), DDR (Double Da a Ra e), QDR (Quad Da a Ra e), FDR (Fou een Da a Ra e), y
EDR (Enhanced Da a Ra e). Ac ualmen e se es á abajando en desa olla HDR (High Da a
Ra e) que pod á abaja a 200 Gb/s en enlaces 4X.
El clus e de A qui ec u as Pa alelas en el momen o de ealiza es e T abajo Final de
G ado abajaba con enlaces 4X y FDR o eciendo 56 Gb/s en cada di ección del enlace.
Recien emen e se han ac ualizado es os enlaces pa a abaja con EDR o eciendo un ancho de
banda de 100 Gb/s.
In iniBand usa una opología conmu ada de o ma que a ios disposi i os pueden
compa i la ed al mismo iempo. Los da os se ansmi en en amas de has a 4 kB que se
ag upan pa a o ma mensajes. Un mensaje puede se una ope ación de acceso di ec o a
memo ia emo a, de lec u a o esc i u a sob e un nodo emo o, un en ío o ecepción po el canal,
una ope ación de ansacción e e sible o una ansmisión mul icas .
Ilus ación 6: Conec o RJ-45 pa a cable de pa es enzados.
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
19
2.7.2 Cop ocesado ec o ial.
El cop ocesado es un p ocesado suplemen a io al p ocesado p incipal. Realiza
ope aciones en coma lo an e, a i mé icas, g á icas, de p ocesamien o de señal, p ocesamien o
de s ings, enc ip ación, e c. El cop ocesado po sí mismo no puede coge ins ucciones de la
memo ia ni hace ope aciones de en ada/salida en e o as limi aciones sino que es á
subo dinado a ealiza las unciones que el p ocesado p incipal le solici e. Los p ocesado es
ac uales de In el con ienen a ios cop ocesado es, g acias a la g an can idad de ansis o es que
es posible in eg a hoy en dia.
Cada nodo del clus e dispone de 12 cop ocesado es ec o iales (uno po núcleo) los
cuales son compa ibles con la ecnología AVX que nos o ece 16 egis os de 256 bi s que nos
pe mi en aloja , po ejemplo, ec o es de 4 doubles o de loa s.
Los p ocesado es abajan con un modelo SISD (single ins uc ion single da a) pe o los
cop ocesado es ec o iales nos pe mi en ejecu a ins ucciones SIMD (single ins uc ion
mul iple da a) pudiendo ealiza ope aciones sob e múl iples da os simul áneamen e. De es a
o ma, po ejemplo, esul a sencillo aplica una misma ope ación a los elemen os de un ec o .
Ilus ación 7: Conec o de enlace In iniBand.
Ilus ación 8: Ejemplo de egis o AVX-256.
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
20
Ilus ación 9: Esquema de aplicación de una ope ación suma, elemen o a elemen o, sob e
dos ec o es
2.7.3 GPU.
La unidad de p ocesamien o g á ico o GPU (G aphics P ocessing Uni ) es un
cop ocesado dedicado al p ocesamien o de g á icos, pa a alige a la ca ga de abajo del
p ocesado cen al en aplicaciones como los ideojuegos o aplicaciones 3D in e ac i as. La
GPU implemen a cie as ope aciones g á icas llamadas p imi i as op imizadas pa a el
p ocesamien o g á ico. Una de las p imi i as más comunes pa a el p ocesamien o g á ico en 3D
es el an ialiasing, que sua iza los bo des de las igu as pa a da les un aspec o más ealis a.
Adicionalmen e exis en p imi i as pa a dibuja ec ángulos, iángulos, cí culos y a cos. Las
GPU ac ualmen e disponen de g an can idad de p imi i as, buscando mayo ealismo en los
e ec os. De es a o ma, mien as g an pa e de lo elacionado con los g á icos se p ocesa en la
GPU, el p ocesado p incipal (CPU) puede dedica se a o o ipo de cálculos.
Una de las mayo es di e encias con la CPU es iba en su a qui ec u a. A di e encia del
p ocesado cen al, que iene una a qui ec u a de on Neumann, la GPU se basa en un modelo
de mul i-p ocesado . Es e modelo acili a el p ocesamien o en pa alelo y la g an segmen ación
que posee la GPU pa a sus a eas.
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
21
En es e sen ido, se in en a ap o echa la g an po encia de cálculo de las GPU pa a
aplicaciones no elacionadas con los g á icos, en lo que desde ecien emen e se iene a llama
GPGPU, o GPU de p opósi o gene al (Gene al Pu pose GPU, en sus siglas en inglés).
La imagen mues a una abs acción de un sopo e mul i-co e x64+GPU pa a
compu ación. Dispone de has a 512 p ocesado es o ganizados en 16 g upos de 32 p ocesado es
llamados mul i-p ocesado es, es os úl imos abajan con un modelo de a qui ec u a SIMT
(single ins uc ion mul iple h ead), cuando la GPU p ocesa una ins ucción gene a g upos de 32
h eads llamados wa ps que ealizan el p ocesamien o de los da os en pa alelo.
Ilus ación 10: A qui ec u a de una N idia Fe mi-class GPU

Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
22
3. P og amas ealizados.
In oducción.
En es e abajo in de g ado hemos ealizado di e sos p og amas pa a p o undiza en el
conocimien o de la p og amación pa alela y dis ibuida. Po ello hemos lle ado a cabo
di e en es es s pa a comp oba el compo amien o de las implemen aciones que hemos
desa ollado combinando di e en es pa adigmas de p og amación pa alela con modelos de
memo ia compa ida y dis ibuida. Las p uebas se han lle ado a cabo sob e 8 nodos con
p ocesado es de ipo In el Xeon de 24 co es cada uno y con 32 GB de memo ia RAM. Además,
cada nodo posee una GPU N idia Tesla K20 y una a je a de ed In iniBand Connec x-3 (FDR)
a 56 Gbps. En dichos nodos disponemos de M aPich2 la cual es una e sión desa ollada en el
Ne wo k-Based Compu ing Labo a o y en la Ohio S a e Uni e si y basada en Mpich que es una
implemen ación de la in e az de MPI. También se dispone de las lib e ías P h eads, OpenMP y
CUDA.
Pa a pone a p ueba los di e en es en o nos de p og amación, se ha pa ido de un p ime
p og ama MPI que ealiza la mul iplicación de dos ma ices. Pos e io men e es e p og ama se ha
ex endido pa a que haga uso de h eads median e la lib e ía P h eads. También se ha ex endido
pa a que haga uso de la lib e ía OpenMP. Es as implemen aciones se han u ilizado
pos e io men e como pun o de pa ida pa a p oba cie os aspec os de diseño, como puede se el
uso e icien e de la memo ia caché o el pa ón de accesos a memo ia (median e el uso de
ma ices anspues as). Finalmen e se ha implemen ado la mul iplicación de ma ices, usando
MPI como base, pa a la ejecución sob e cop ocesado es ec o iales y GPUs.
Pa a cada implemen ación hemos ealizados p uebas con ma ices de ipo double de
1536x1536, 3072x3072, 6144x6144 y 12288x12288 elemen os. A con inuación p esen amos
los di e en es casos es udiados:
3.1 Tes MPI.
En es a p ime a ap oximación hemos ejecu ado un algo i mo que únicamen e u iliza
MPI, de mane a que el p oceso con el ank = 0 (el ank es una e ique a numé ica que iden i ica
inequí ocamen e cada p oceso) es el enca gado de gene a las ma ices A y B pa a después
dis ibui las en e el es o de p ocesos. Se han gene ado 24 p ocesos en cada nodo in oluc ado,
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
23
an os como co es de los que disponen. Cada p oceso ecibe un subconjun o de ilas de la ma iz
A y una copia comple a de la ma iz B, pos e io men e calcula su pa e de la mul iplicación
ma icial y inalmen e de uel e su esul ado pa cial al p oceso maes o el cual compone los
esul ados en la ma iz C.
Simpli icación del código:
#include <mpi.h>
#include <s dio.h>
#include <s dlib.h>
// SIZE: Al o y ancho de las ma ices A,B y C
#de ine SIZE 3072
// Recibe el pun e o de una ma iz [SIZE][SIZE] y la ellena con doubles en e [0-100[
oid ill_ma ix(double* x) {
long i, j;
o (i = 0; i < SIZE; ++i) {
o (j = 0; j < SIZE; ++j) {
x[i * SIZE + j] = (double)( and() % 100);
}
}
}
in main(in a gc, cha *a g []){
// Decla ación de a iables
in my ank, P, om, o, i, j, k;
double *A, *B, *C, *A_local, *C_local;
MPI_S a us s a us;
// Inicialización de MPI
MPI_Ini (&a gc, &a g );
MPI_Comm_ ank(MPI_COMM_WORLD, &my ank);
MPI_Comm_size(MPI_COMM_WORLD, &P);
// om: posición de la p ime a ila de la ma iz A que debe calcula cada p oceso
om = my ank * SIZE/P;
// o: posición de la úl ima ila de la ma iz A que debe calcula cada p oceso
o = (my ank+1) * SIZE/P;
// Rese a de memo ia en cada p oceso pa a la sección de la ma iz A que le co esponde a cada uno
A_local = malloc (SIZE * (SIZE/P) * sizeo (double));
// Rese a de memo ia en cada p oceso pa a la ma iz de esul ados locales
C_local = malloc (SIZE * (SIZE/P) * sizeo (double));
// Rese a de memo ia en cada p oceso pa a la ma iz B
B = malloc (SIZE * SIZE * sizeo (double));
// El siguien e código solo lo ejecu a a el p oceso p incipal o mas e
i (my ank==0) {
// Rese a de memo ia pa a la ma iz A
A = malloc (SIZE * SIZE * sizeo (double));
// Rese a de memo ia pa a la ma iz esul ado C
C = malloc (SIZE * SIZE * sizeo (double));
// Puebla la ma iz A con alo es
ill_ma ix(A);
// Puebla la ma iz A con alo es
ill_ma ix(B);
}
// El p oceso mas e en ía una copia de la ma iz B a odos los p ocesos
MPI_Bcas (B, SIZE*SIZE, MPI_DOUBLE, 0, MPI_COMM_WORLD);
// El p oceso mas e en ía la sección que de la ma iz A que le co esponde calcula a cada p oceso
MPI_Sca e (A, SIZE*SIZE/P, MPI_DOUBLE, A_local, SIZE*SIZE/P, MPI_DOUBLE, 0,
MPI_COMM_WORLD);
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
24
// Cada p oceso calcula el esul ado de la mul iplicación ma icial de su pa e de la ma iz A y lo gua da en
la ma iz C_local
// I e amos po cada una de las ilas que iene que calcula cada p oceso
o (i=0; i<SIZE/P; i++){
// La a iable j nos ma ca la columna de B
o (j=0; j<SIZE; j++) {
// La a iable k nos indica la columna de A y la ila de B
o (k=0; k<SIZE; k++){
C_local[i * SIZE + j] += A_local[i * SIZE + k] * B[k * SIZE + j];
}
}
}
// Todos los p ocesos en ian sus esul ados pa ciales al p oceso mas e que los ecoge en la ma iz C
MPI_Ga he (C_local, SIZE*SIZE/P, MPI_DOUBLE, C, SIZE*SIZE/P, MPI_DOUBLE, 0,
MPI_COMM_WORLD);
// Se inalize MPI
MPI_Finalize();
// Fin de la ejecución
e u n 0;
}
En el código del p og ama se puede obse a que cada p oceso MPI ese a memo ia
RAM pa a albe ga la ma iz B en e a y la pa e co espondien e de las ma ices A y C. Po o a
pa e el p oceso mas e inicializa las ma ices A y B, a con inuación en ía la ma iz B a odos
los p ocesos MPI con un b oadcas y ambién la pa e de la ma iz A que necesi a cada uno con
un sca e . Después, odos los p ocesos calculan la pa e de la ma iz esul ado que ienen
asignada. Pa a inaliza el p oceso mas e ecibe odas las secciones de la ma iz esul ado con
un ga he y inaliza la ejecución.
Resul ados:
Ilus ación 11: Compa a i a de iempos de ejecución de la e sión en MPI.
0
1000
2000
3000
4000
5000
6000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
MPI
12288 x 12288
6144 x 6144
3072 x 3072
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
25
La ilus ación 11 mues a que en la ejecución con ma ices de amaño 12288x12288 con
1 y 2 nodos se ob iene una mejo a de endimien o del 66% en luga de un 100% eó ico que
supond íamos ya que hemos duplicado el núme o de nodos. Es a di e encia es debida a que
aunque el núme o de ope aciones a i mé icas en los dos casos pe manece cons an e no ocu e
igual con la can idad de mensajes de comunicación en e p ocesos de MPI ya que enemos en el
p ime caso 24 ins ancias del p og ama y en el segundo 48. Es e hecho se epi e cada ez que
inc emen amos el núme o de nodos in oluc ados, po lo que podemos obse a como la
pendien e de la cu a disminuye p og esi amen e debido a la sob eca ga de comunicaciones.
Ilus ación 12: Compa a i a de iempos de ejecución de la e sión en MPI (eje Y en escala loga í mica en base
10).
Dado que en la ilus ación 11 es di ícil dis ingui las cu as pa a los amaños más
pequeños de ma iz, la ilus ación 12 mues a los mismos esul ados en escala loga í mica pa a
el eje Y.
Es udiando los da os en la ilus ación 12 podemos ap ecia en la p ueba con amaño de
1536x1536 que la pendien e se in ie e, es e hecho nos indica que el bene icio ob enido po
dis ibui las ope aciones a i mé icas sob e más nodos es in e io al cos e del inc emen o de las
comunicaciones en e nodos con lo que ob enemos un dec emen o del endimien o.
1
10
100
1000
10000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
MPI
12288 x 12288
6144 x 6144
3072 x 3072
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
32
}
MPI_Ga he (C_local, SIZE*SIZE/P, MPI_DOUBLE, C, SIZE*SIZE/P, MPI_DOUBLE, 0,
MPI_COMM_WORLD);
MPI_Finalize();
e u n 0;
}
Al igual que en la e sión P h eads, en cada nodo se man iene una única copia de la
ma iz B. La di e encia p incipal de u iliza di ec i as OpenMp en luga de la lib e ía p h eads.h
es que no es necesa io inicializa explíci amen e los hilos, sino que u ilizando dichas di ec i as
le indicamos al compilado que secciones del código que emos que se ejecu en en pa alelo. Es
el p opio compilado el enca gado de gene a el código pa a la c eación y ges ión de los hilos.
OpenMP pe mi e especi ica el scope de cada a iable y ambién pe mi e abaja con a ios
ipos de secciones con dis in os compo amien os como egiones pa alelas, secciones c í icas o
sec ions.
Resul ados:
Ilus ación 15: Compa a i a de iempos de ejecución de la e sión en MPI combinada con OpenMP.
0
1000
2000
3000
4000
5000
6000
7000
8000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
MPI + OpenMP
12288 x 12288
6144 x 6144
3072 x 3072
1536 x 1536

Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
33
Ilus ación 16: Compa a i a de iempos de ejecución de la e sión en MPI combinada con OpenMP (eje Y en
escala loga í mica en base 10).
En las ilus aciones 15 y 16 se mues a que hemos ob enido unos esul ados lige amen e
peo es que en la e sión MPI + P h eads pe o con un cos e de implemen ación más bajo, a su
ez se ía más sencillo en un u u o ealiza modi icaciones sob e es e código que en el u ilizado
en la e sión de P h eads.
0
1000
2000
3000
4000
5000
6000
7000
8000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
MPI + OpenMP
12288 x 12288
6144 x 6144
3072 x 3072
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
34
3.4 Recopilación.
Ilus ación 17: Compa a i a de los iempos de ejecución de las es e siones pa a un amaño de ma iz de
12288x12288.
A modo de esumen, La ilus ación 17 mues a las es implemen aciones en conjun o
pa a el amaño de ma ices de 12288x12288 elemen os, emos cómo pese a que la e sión MPI
es la más e icien e ejecu ada sob e un único nodo, su di e encia espec o a las e siones de
memo ia compa ida disminuye con o me aumen a el núme o de nodos in oluc ados debido al
cos e en comunicaciones. En las p uebas con 8 nodos ya se obse a cómo se in ie e la
endencia. También emos que OpenMP es la e sión menos e icien e.
3.5 EFECTO DE LA MEMORÍA.
Has a aho a nos habíamos cen ado en dis in as lib e ías que nos pe mi en abaja con
los modelos de memo ia dis ibuida y compa ida pa a mejo a el endimien o de nues o
so wa e. Pe o exis e o o ac o de e minan e pa a maximiza la e iciencia: la ges ión de la
memo ia caché. Es un hecho que se pie de mucho iempo de compu ación mien as se hacen
accesos a bloques de memo ia caché los cuales pueden de i a en sus i ución de bloques a
0
1000
2000
3000
4000
5000
6000
7000
8000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI] s [MPI + OpenMP] s [MPI + P h eads]
MPI
MPI + P h eads
MPI + OpenMP
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
35
a és de los dis in os ni eles de la je a quía de es a memo ia. Cla amen e no podemos ni
que emos con ola manualmen e el p oceso de sus i ución de bloques de la memo ia caché,
pe o lo que sí que podemos hace es p epa a los da os en una es uc u a al que minimice el
núme o de bloques solici ados a la caché.
En el caso de nues o algo i mo de mul iplicación de ma ices sabemos que pa a
calcula , po ejemplo, el alo esul an e en la posición de la ila 2 columna 1 de la ma iz
esul ado lo ob enemos de mul iplica los elemen os de la ila 2 de la ma iz A con los
elemen os de la columna 1 de la ma iz B. Rápidamen e nos damos cuen a de que cuando el
sis ema solici e un bloque de memo ia pa a lee un alo de la ma iz A ecibi á dicho bloque
que con end á el da o solici ado y un conjun o de da os adicionales y con iguos pe enecien es
ambién a la misma ila de la ma iz A que necesi a emos en las siguien es i e aciones de
nues o algo i mo. Sin emba go, cuando solici emos un bloque pa a ob ene un alo de la
ma iz B no pod emos eu iliza el es o de alo es que ienen en dicho bloque ya que, como
hemos dicho, necesi amos accede po columnas a es a ma iz y nos encon amos que en e un
da o y o o de los que eque imos hay an os alo es como la dimensión de la ma iz.
Podemos mejo a es e compo amien o ácilmen e haciendo que el p oceso inicial
ansponga la ma iz B, de es a mane a el cálculo a ealiza se ía de ila po ila en luga de ila
po columna con lo que eu ilizamos cada bloque a ias eces, educiendo el núme o o al de
sus i uciones de bloque y mejo ando no ablemen e el endimien o del p og ama.
Las modi icaciones que hemos enido que ealiza a las es e siones de nues o
algo i mo han sido:
- Añadi una unción a la que le pasamos el pun e o de la ma iz B y anspone sus
elemen os.
- Hace que el p oceso mas e ealice una llamada a dicha unción jus o después de
pobla la ma iz B.
- Cambia los índices en el bucle de cálculo.
En las siguien es subsecciones amos a analiza los bene icios de anspone la ma iz B
pa a los mismos casos is os en las secciones an e io es.
3.5.1 Tes MPI s MPI ( anspues a).
Modi icaciones del código:
…
oid anspose_ma ix(double* m){
long i, j;
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
36
double mp;
o (i=0; i<SIZE; i++) {
o (j=i; j<SIZE; j++){
mp = m[i * SIZE + j];
m[i * SIZE + j] = m[j * SIZE + i];
m[j * SIZE + i] = mp;
}
}
}
…
i (my ank==0) {
A = malloc (SIZE * SIZE * sizeo (double));
C = malloc (SIZE * SIZE * sizeo (double));
ill_ma ix(A);
ill_ma ix(B);
anspose_ma ix(B);
}
…
o (i=0; i<SIZE/P; i++){
o (j=0; j<SIZE; j++) {
o (k=0; k<SIZE; k++){
C_local[i * SIZE + j] += A_local[i * SIZE + k] * B[j * SIZE + k];
}
}
}
…
Resul ados:
Ilus ación 18: Compa a i a de los iempos de ejecución de la e sión MPI con la e sión MPI en la que se
anspone la ma iz B.
0
1000
2000
3000
4000
5000
6000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI] s [MPI ( anspues a)]
12288 x 12288
12288 x 12288
6144 x 6144
6144 x 6144
3072 x 3072
3072 x 3072
1536 x 1536
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
37
La ilus ación 18 mues a mejo as de casi un 400% cuando u ilizamos la
implemen ación que acili a la eu ilización de bloques en la memo ia cache. Es o hace que haya
un g an dec emen o del cos e en comunicaciones en e el p ocesado y la memo ia cen al, lo
que aumen a la impo ancia ela i a del cos e en comunicaciones en e p ocesos MPI ya que
es e pe manece in ac o, po lo que la educción del endimien o cuando abajamos con más
nodos es mayo . Es e compo amien o lo pe cibimos iendo cómo las cu as de la e sión
anspues a son menos p onunciadas.
Ilus ación 19: Compa a i a de los iempos de ejecución de la e sión MPI con la e sión MPI en la que se
anspone la ma iz B (eje Y en escala loga í mica en base 10).
La ilus ación 19 mues a que como la compu ación se ha op imizado, las
comunicaciones ienen un peso mayo espec o del o al del iempo de ejecución. Po an o, la
in e sión de endencia que an es se obse aba en la cu a de “1536x1536”, aho a ambién se
obse a en la cu a “3072x3072 ”.
3.5.2 Tes MPI + P h eads s MPI + P h eads ( anspues a).
Modi icaciones del código:
1
10
100
1000
10000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI] s [MPI ( anspues a)]
12288 x 12288
12288 x 12288
6144 x 6144
6144 x 6144
3072 x 3072
3072 x 3072
1536 x 1536
1536 x 1536

Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
38
…
oid anspose_ma ix(double* m){
long i, j;
double mp;
o (i=0; i<SIZE; i++) {
o (j=i; j<SIZE; j++){
mp = m[i * SIZE + j];
m[i * SIZE + j] = m[j * SIZE + i];
m[j * SIZE + i] = mp;
}
}
}
…
i (my ank==0) {
A = malloc (SIZE * SIZE * sizeo (double));
C = malloc (SIZE * SIZE * sizeo (double));
ill_ma ix(A);
ill_ma ix(B);
anspose_ma ix(B);
}
…
oid *ope a e( oid *pa am) {
s uc *da a = pa am;
in i, j, k;
o (i=da a-> om; i<da a-> o; i++){
o (j=0; j<SIZE; j++) {
o (k=0; k<SIZE; k++)
C_local[i * SIZE + j] += A_local[i * SIZE + k] * B[j * SIZE + k];
}
}
}
…
Resul ados:
Ilus ación 20: Compa a i a de los iempos de ejecución de la e sión MPI + P h eads con la e sión MPI +
P h eads en la que se anspone la ma iz B.
0
1000
2000
3000
4000
5000
6000
7000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI + P h eads] s [MPI + P h eads ( anspues a)]
12288 x 12288
12288 x 12288
6144 x 6144
6144 x 6144
3072 x 3072
3072 x 3072
1536 x 1536
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
39
La ilus ación 20 mues a que los speed-up llegan has a el 500%, lo que indica que una
mejo a en la ges ión de la memo ia cache se hace más no able en un en o no de memo ia
compa ida. Es o nos da pis as sob e po qué ob eníamos mejo es iempos cuando ejecu ábamos
en un solo nodo con la e sión MPI que con las e siones de memo ia compa ida. Es posible
que sea po una mala ges ión de la cache en el segundo caso.
Ilus ación 21: Compa a i a de los iempos de ejecución de la e sión MPI + P h eads con la e sión MPI +
P h eads en la que se anspone la ma iz B (eje Y en escala loga í mica en base 10).
La ilus ación 21 mues a cómo las mejo as de endimien o son más p opo cionales al
aplica una op imización a la sección compu acional que en la e sión MPI. Es o es debido a
que el peso de la pa e de comunicaciones es mucho meno en el caso de modelos de memo ia
compa ida y a ec a menos a los iempos de ejecución.
3.5.3 Tes MPI + OpenMp s MPI + OpenMP ( anspues a).
Modi icaciones del código:
…
oid anspose_ma ix(double* m){
long i, j;
double mp;
o (i=0; i<SIZE; i++) {
o (j=i; j<SIZE; j++){
1
10
100
1000
10000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI + P h eads] s [MPI + P h eads ( anspues a)]
12288 x 12288
12288 x 12288
6144 x 6144
6144 x 6144
3072 x 3072
3072 x 3072
1536 x 1536
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
40
mp = m[i * SIZE + j];
m[i * SIZE + j] = m[j * SIZE + i];
m[j * SIZE + i] = mp;
}
}
}
…
i (my ank==0) {
A = malloc (SIZE * SIZE * sizeo (double));
C = malloc (SIZE * SIZE * sizeo (double));
ill_ma ix(A);
ill_ma ix(B);
anspose_ma ix(B);
}
…
o (i= om; i< o; i++){
o (j=0; j<SIZE; j++) {
o (k=0; k<SIZE; k++){
C_local[i * SIZE + j] += A_local[i * SIZE + k] * B[j * SIZE + k];
}
}
}
…
Resul ados:
Ilus ación 22: Compa a i a de los iempos de ejecución de la e sión MPI + OpenMP con la e sión MPI +
OpenMP en la que se anspone la ma iz.
0
1000
2000
3000
4000
5000
6000
7000
8000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI + OpenMP] s [MPI + OpenMP ( anspues a)]
12288 x 12288
12288 x 12288
6144 x 6144
6144 x 6144
3072 x 3072
3072 x 3072
1536 x 1536
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
41
En la ilus ación 22 se mues a que con OpenMP ob enemos has a un 530% de mejo a
del endimien o que es lige amen e supe io que la e sión ealizada con P h eads.
Ilus ación 23: Compa a i a de los iempos de ejecución de la e sión MPI + OpenMP con la e sión MPI +
OpenMP en la que se anspone la ma iz (eje Y en escala loga í mica en base 10).
La ilus ación 23 nos o ece al igual que la e sión con P h eads unas mejo as más
homogéneas que la e sión MPI.
3.5.4 Recopilación.
A con inuación mos amos dos g á icos que esumen lo is o has a aho a sob e uso de
en o nos de memo ia dis ibuida y compa ida y sob e la disposición óp ima de los da os.
1
10
100
1000
10000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
MPI + OpenMP ( anspues a)
12288 x 12288
12288 x 12288
6144 x 6144
6144 x 6144
3072 x 3072
3072 x 3072
1536 x 1536
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
48
Ilus ación 28: Compa a i a de los iempos de ejecución de la e sión MPI + AVX (in ínsecas) con la e sión
MPI + AVX (in ínsecas) en la que se anspone la ma iz B.
Ilus ación 29: Compa a i a de los iempos de ejecución de la e sión MPI + AVX (in ínsecas) con la e sión
MPI + AVX (in ínsecas) en la que se anspone la ma iz B (eje Y en escala loga í mica en base 10).
Las ilus aciones 28 y 29 mues an, según lo espe ado, una g an mejo a del endimien o
al anspone la ma iz, en algunos casos po encima del 600%.
0
1000
2000
3000
4000
5000
6000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI + AVX (in ínsecas) ] s
[MPI + AVX (in ínsecas, anspues a)]
12288 x 12288
12288 x 12288
6144 x 6144
6144 x 6144
3072 x 3072
3072 x 3072
1536 x 1536
1536 x 1536
1
10
100
1000
10000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI + AVX (in ínsecas) ] s
[MPI + AVX (in ínsecas, anspues a)]
12288 x 12288
12288 x 12288
6144 x 6144
6144 x 6144
3072 x 3072
3072 x 3072
1536 x 1536
1536 x 1536

Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
49
A modo de esumen, En la ilus ación 30 se compa a la e sión MPI + AVX
(in ínsecas, anspues a) con su homóloga en p ocesado MPI ( anspues a), ob enemos
aumen os de la e iciencia en o no al 60%.
Hemos comp obado que podemos mejo a el iempo de ejecución si nues o p og ama,
o una pa e de él, es suscep ible de se ejecu ado sob e el cop ocesado ec o ial. Po o o lado,
ambién sabemos que la implemen ación de algo i mos ec o iales es más complicada y además
se educe en g an medida su po abilidad a o os sis emas ya que hab ían de se
ecnológicamen e compa ibles (no odos los cop ocesado es sopo an las mismas ins ucciones
ec o iales).
3.7 Cop ocesado ec o ial: au o ec o izado .
Pa a llega a un comp omiso en e mejo a de endimien o y sencillez de
implemen ación podemos ayuda nos de los au o ec o izado es. GCC dispone de un
au o ec o izado muy sencillo de u iliza , simplemen e añadiendo el lag –O3 en el comando de
compilación ob end emos una e sión de nues o algo i mo que ejecu a á sob e el cop ocesado
las ope aciones que c ea opo unas.
0
200
400
600
800
1000
1200
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI] s [MPI + Cop ocesado ( unciones
in insecas, anspues a)]
MPI anspues a
MPI + Cop o.( unc. In ínsecas)
Ilus ación 30: Compa a i a MPI ( anspues a) con MPI con ejecución en cop ocesado con
unciones in ínsecas ( anspues a) pa a un amaño de ma iz de 12288x12288.
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
50
Las siguien es ilus aciones mues an los esul ados ob enidos as compila la e sión
inicial MPI pa a el p ocesado con es e lag de con ol:
Ilus ación 31: Compa a i a de iempos de ejecución de la e sión en MPI au o ec o izada.
Ilus ación 32: Compa a i a de iempos de ejecución de la e sión en au o ec o izada (eje Y en escala
loga í mica en base 10).
0
1000
2000
3000
4000
5000
6000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
MPI + AVX (au o ec o izado)
12288 x 12288
6144 x 6144
3072 x 3072
1536 x 1536
0
1000
2000
3000
4000
5000
6000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
MPI + AVX (au o ec o izado)
12288 x 12288
6144 x 6144
3072 x 3072
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
51
Seguidamen e se compa an los iempos ob enidos con las e siones au o ec o izadas de
MPI y de MPI ( anspues a):
Ilus ación 33: Compa a i a de iempos de ejecución de la e sión en MPI + AVX (au o ec o izada) y de la
MPI + AVX (au o ec o izada, anspues a).
0
1000
2000
3000
4000
5000
6000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI + AVX (au o ec o izado)] s
[MPI + AVX (au o ec o izado, anspues a)]
12288 x 12288
12288 x 12288
6144 x 6144
6144 x 6144
3072 x 3072
3072 x 3072
1536 x 1536
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
52
Ilus ación 34: Compa a i a de iempos de ejecución de la e sión en MPI + AVX (au o ec o izada) y de la
MPI + AVX (au o ec o izada, anspues a) (eje Y en escala loga í mica en base 10).
Las ilus aciones 33 y 34 mues an que una ez más ob enemos g andes mejo as al
anspone la ma iz B, en es e caso la mejo a en e las e siones au o ec o izadas no mal y
anspues a llega a se del 1500%. El au o ec o izado es mucho más e icien e cuando le
acili amos los da os de una o ma óp ima, como ya ocu ía en las e siones pa a CPU.
3.8 Recopilación.
A con inuación mos amos una g á ica con la ecopilación de esul ados de las cinco
e siones is as has a aho a pa a un amaño de ma iz de 12288x12288 haciendo en odos los
casos la ansposición de la ma iz B an es del cálculo:
1
10
100
1000
10000
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
[MPI + AVX (au o ec o izado)] s
[MPI + AVX (au o ec o izado, anspues a)]
12288 x 12288
12288 x 12288
6144 x 6144
6144 x 6144
3072 x 3072
3072 x 3072
1536 x 1536
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
53
Ilus ación 35: Compa a i a de iempos de ejecución pa a un amaño de ma iz de 12288x12288 y
ansponiendo la ma iz B.
En la ilus ación 35 se puede ap ecia que hemos ob enido los mejo es al u iliza el
cop ocesado , siendo los mejo es esul ados los de la e sión au o ec o izada. Si compa amos la
e sión MPI ( anspues a) pa a p ocesado con la au o ec o izada la mejo a llega a se del
300%. Es o es g acias al al o g ado de op imización que se ealiza al compila el código.
También hemos de ene en cuen a en es e caso que al no ealiza ninguna modi icación al
código seguimos man eniendo el mismo ni el de po abilidad que eníamos con la e sión pa a
p ocesado .
3.9 GPU.
Nues o úl imo es ambién es á cen ado en el ap o echamien o de los dis in os ha dwa es
disponibles. En es e caso hemos es udiado los endimien os ob enidos si asladamos el cómpu o
a las a je as g á icas. El clus e sob e el que abajamos dispone de a je as g á icas de la ma ca
N idia y modelo Tesla K20 con 1.17 T lops de ope aciones en coma lo an e de doble p ecisión,
5 GB de memo ia y 2496 co es. N idia nos acili a el lenguaje de p og amación CUDA.
0
200
400
600
800
1000
1200
1400
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
Recopilación de esul ados
MPI
MPI + P h eads
MPI + OpenMP
MPI + AVX in insecas
MPI + AVX au o ec o izado

Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
54
P og ama en es e lenguaje equie e cie a des eza ya que se ha de ene en cuen a el modelo de
a je a del que se dispone, los di e en es ni eles de memo ia con los que abaja, se ha de
ges iona el lujo de in o mación en e la CPU y la GPU, e c. Pe o CUDA nos o ece la lib e ía
CUBLAS que implemen a el es ánda BLAS pa a el cálculo ma icial.
En el clus e disponemos de la e sión 5.5 de la lib e ía CUBLAS y es con la que
hemos ealizado nues a implemen ación. Teniendo en cuen a que cada nodo dispone de una
única a je a g á ica solo necesi amos c ea un único p oceso MPI po nodo ya que no
ob end íamos ningún bene icio c eando una cola de abajo.
Código simpli icado:
#include <s dio.h>
#include <s dlib.h>
#include <mpi.h>
#include <cublas_ 2.h>
#include <cuda_ un ime.h>
#de ine SIZE 12288
oid ill_ma ix(double* x) {
long i, j;
o (i = 0; i < SIZE; ++i) {
o (j = 0; j < SIZE; ++j) {
x[i * SIZE + j] = (double)( and() % 100);
}
}
}
oid anspose_ma ix(double* m){
long i, j;
double mp;
o (i=0; i<SIZE; i++) {
o (j=i; j<SIZE; j++){
mp = m[i * SIZE + j];
m[i * SIZE + j] = m[j * SIZE + i];
m[j * SIZE + i] = mp;
}
}
}
in main(in a gc, cha *a g []){
in my ank, P, om, o, i, j, k;
double alpha = 1.0;
double be a = 0.0;
double *A, *B, *C, *A_local, *C_local;
double *de A, *de B, *de C;
MPI_S a us s a us;
cublasHandle_ handle;
cublasS a us_ cublas_s a us;
cublasPoin e Mode_ * mode;
MPI_Ini (&a gc, &a g );
MPI_Comm_ ank(MPI_COMM_WORLD, &my ank);
MPI_Comm_size(MPI_COMM_WORLD, &P);
om = my ank * SIZE/P;
o = (my ank+1) * SIZE/P;
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
55
A_local = malloc (SIZE * (SIZE/P) * sizeo (double));
C_local = malloc (SIZE * (SIZE/P) * sizeo (double));
B = malloc (SIZE * SIZE * sizeo (double));
i (my ank==0) {
A = malloc (SIZE * SIZE * sizeo (double));
C = malloc (SIZE * SIZE * sizeo (double));
ill_ma ix(A);
ill_ma ix(B);
}
MPI_Bcas (B, SIZE*SIZE, MPI_DOUBLE, 0, MPI_COMM_WORLD);
MPI_Sca e (A, SIZE*SIZE/P, MPI_DOUBLE, A_local, SIZE*SIZE/P, MPI_DOUBLE, 0,
MPI_COMM_WORLD);
// Cada p oceso ese a memo ia en la GPU pa a su sección de la ma iz A
cudaMalloc( ( oid **)&de A, SIZE * (SIZE/P) * sizeo (double) );
// Cada p oceso ese a memo ia en la GPU pa a la ma iz B
cudaMalloc( ( oid **)&de B, SIZE * SIZE * sizeo (double) );
// Cada p oceso ese a memo ia en la GPU pa a la ma iz esul ado
cudaMalloc( ( oid **)&de C, SIZE * (SIZE/P) * sizeo (double) );
// Se copian las ma ices en la GPU
cudaMemcpy( de A, A_local, SIZE * (SIZE/P) * sizeo (double), cudaMemcpyHos ToDe ice);
cudaMemcpy( de B, B, SIZE * SIZE * sizeo (double), cudaMemcpyHos ToDe ice);
// Inicializamos un manejado que man end á el con ex o de ejecución en la GPU y que i emos pasando en
cada llamada que hagamos a unciones de la lib e ía CUBLAS
cublas_s a us = cublasC ea e(&handle);
// En la a iable Cublas_s a us ecibi emos los posibles códigos de e o , hemos de comp oba que cada
unción se ejecu a co ec amen e
i (cublas_s a us != CUBLAS_STATUS_SUCCESS){
p in ("handle c ea e ail n"); e u n 1;
}
// Realizamos la mul iplicación ma icial en la GPU indicandole cuales son los ec o es y las dimensiones
de es os
cublas_s a us = cublasDgemm(handle, CUBLAS_OP_T, CUBLAS_OP_T, SIZE/P, SIZE, SIZE, &alpha,
de A, SIZE, de B, SIZE, &be a, de C, SIZE/P );
i (cublas_s a us == CUBLAS_STATUS_SUCCESS){
p in ("cublasDgemm OK n");
}else{
p in ("cublasDgemm BAD");
}
// Ex aemos de la GPU a memo ia p incipal el ec o esul ado
cudaMemcpy( C_local, de C, SIZE * (SIZE/P) * sizeo (double), cudaMemcpyDe iceToHos );
// Libe amos el espacio ese ado en la GPU
cudaF ee(de A);
cudaF ee(de B);
cudaF ee(de C);
MPI_Ga he (C_local, SIZE*SIZE/P, MPI_DOUBLE, C, SIZE*SIZE/P, MPI_DOUBLE, 0,
MPI_COMM_WORLD);
// Des uimos el manejado
cublas_s a us = cublasDes oy(handle);
i (cublas_s a us != CUBLAS_STATUS_SUCCESS){
p in ("cublasDes oy ailed n"); e u n 1;
}
// Hemos de anspone la ma iz esul ado po queCUBLAS abaja con colum-majo -o de po cues iones
de endimien o y noso os necesi amos la espues a en ow-majo -o de
i (my ank==0) {
anspose_ma ix(C);
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
56
}
MPI_Finalize();
e u n 0;
}
Obse ando el código emos que una ez que cada nodo dispone de las ma ices que
necesi a, ha de copia las en la memo ia de la GPU. Pa a ello p ime o ese a espacio en dicha
memo ia con la o den cudaMalloc y después copia el con enido de las ma ices con
cudaMemcpy. Pos e io men e se ealiza la mul iplicación ma icial y se copia la ma iz esul ado
desde la GPU a la memo ia p incipal. Finalmen e odos los p ocesos en ían sus ma ices
esul ado pa ciales al p oceso mas e el cual ha de anspone la ma iz esul ado pa a pode
p esen a los da os co ec amen e.
Resul ados:
Ilus ación 36: Compa a i a de iempos de ejecución de la e sión MPI + CUBLAS.
La ilus ación 36 mues a unos esul ados espec acula es. Vemos que ninguna de las
ca gas de abajo que hemos u ilizado son lo su icien emen e g andes como pa a que nos
me ezca la pena implica más de un nodo en la ejecución. De hecho ob enemos peo es iempos
de ejecución debido a la sob eca ga de comunicaciones.
0
5
10
15
20
25
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
MPI + CUBLAS
12288 x 12288
6144 x 6144
3072 x 3072
1536 x 1536
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
57
3.10 Recopilación inal.
Ilus ación 37 : Compa a i a de iempos de ejecución pa a un amaño de ma iz de 12288x12288 y
ansponiendo la ma iz B.
La ilus ación 37 mues a que CUBLAS esul a has a 17 eces más ápido que la e sión
au o ec o izada, la cual e a la más e icien e has a aho a. Como se puede obse a en el código
uen e, CUBLAS es una lib e ía de al o ni el que nos abs ae en g an medida de CUDA,
pe mi iendo una implemen ación bas an e sencilla. A pa i de la e sión 6.0 de CUBLAS se
uel e incluso más ácil la p og amación ya que no equie e la ges ión manual de la subida y
bajada de bloques de memo ia a la GPU sino que le podemos pasa la e e encia de las ma ices
pa a que el sis ema se enca gue del es o. Además se incluye la posibilidad de abaja con
a ias a je as sob e el mismo nodo.
0
200
400
600
800
1000
1200
1400
1 2 3 4 5 6 7 8
Tiempo en segundos
Núme o de nodos
Recopilación de esul ados
MPI
MPI + P h eads
MPI + OpenMP
AVX in insecas
AVX au o ec o izado
cublas
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
64
$ scp -P 3322 a chi o. x pepi o@clus e .gap.up .es:
2 TRABAJANDO CON MPI
Lo p ime o, como ya se ha mencionado an es, es añadi la u a del di ec o io “bin” de
MPI a la a iable PATH.
$ expo PATH=$PATH:/us /mpi/gcc/m apich2-2.0/bin/
Aho a enemos disponibles los comandos ípicos que necesi amos pa a abaja con
MPI. Pa a compila un a chi o p og amado en C pa a su ejecución en MPI u iliza emos
“mpicc”, po ejemplo:
$ mpicc –o miApp miApp.c
An es de ejecu a nada se ecomienda c ea un “hos ile”, que no es más que un a chi o
de ex o en el que esc ibimos, sepa ados po líneas, el nomb e de odos los nodos en los que
que emos que se ejecu e el algo i mo jun o con el núme o máximo de p ocesos que pe mi imos
que se ejecu en simul áneamen e en cada nodo. Po ejemplo, enemos un a chi o con el nomb e
“h _mpi” que con iene:
nodo1:8
nodo2:8
Es e a chi o indica ía que nues o p og ama se a a ejecu a en los nodos “nodo1” y
“nodo2” y que, como mucho, se an a ejecu a simul áneamen e 8 ins ancias del p og ama en
cada nodo. No malmen e el núme o máximo de ins ancias suele se el mismo que el núme o de
co es que iene disponibles cada nodo. Pa a ejecu a el algo i mo an e io u iliza íamos el
comando:
$ mpiexec –hos ile h _mpi –np 16 miApp
Como emos, le hemos pasado el “hos ile” con el p e ijo “-hos ile” y ambién le
hemos indicado el núme o o al de p ocesos (16) con el p e ijo “-p”. Mien as el algo i mo se
es é ejecu ando pod emos comp oba que odo unciona co ec amen e accediendo a cada nodo
in oluc ado en la ejecución y u ilizando la o den:
$ op

Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
65
Debe íamos e , como mucho, an as ins ancias del p og ama como el núme o máximo
de p ocesos que le asignamos p e iamen e en el “hos ile” a dicho nodo.
3 HÍBRIDOS DE MEMORIA COMPARTIDA
Si u ilizamos MPI en soli a io es a emos ejecu ando nues o p og ama en un en o no de
memo ia dis ibuida an a in e como in a nodo ya que se c ean ins ancias independien es del
mismo que se dis ibuyen en e odos los co es disponibles del clus e .
Pe o quizás que amos ap o echa nos de las en ajas de ejecu a nues os p og amas en
un en o no de memo ia compa ida in a nodo, es deci , c eando una única ins ancia de
ejecución en cada nodo y esa ins ancia gene a á an os hilos como co es enga disponibles el
nodo, con lo que op imiza íamos el uso de memo ia. Podemos consegui es o combinando, po
ejemplo, MPI con OMP o MPI con P h eads.
Impo an e: Si amos a op a po usa una de es as combinaciones debemos ene en
cuen a que la e sión de MVAPICH de que disponemos en el Clus e , po de ec o, iene
con igu ada la a inidad de asignación de p ocesos a “1”. Ello conlle a que odos los hilos que se
ejecu en en un nodo lo hagan sob e el mismo co e, lo cual se ía ca as ó ico pa a nues o
p opósi o de dis ibui la ca ga los más e icien emen e posible. Pa a soluciona es o hemos de
añadi la a iable de en o no “MV2_ENABLE_AFFINITY=0” en el comando de ejecución de
MPI (más in o mación en pg 16 ->
h p://chpc.wus l.edu/asse s/ iles/pd /WashU_7_m apich.pd ):
$ mpiexec -en MV2_ENABLE_AFFINITY 0 -np 2 --hos ile h _mpi miApp
Pa a de ec a si se es á dis ibuyendo bien la ca ga en e los co es podemos ayuda nos
o a ez de la o den “ op”; si po ejemplo es amos en un nodo con 8 co es y lo hemos p epa ado
odo pa a que se ejecu en 8 hilos en dicho nodo, debe íamos e que exis e una única ins ancia
del p og ama pe o que iene un po cen aje de consumo de CPU ce cano al 800%. Si po el
con a io, el po cen aje se man iene en o no al 100%, sab emos que MPI es á se ializando la
ejecución de odos los hilos en un mismo co e.
Po o o lado, la o ma de inicializa MPI en un p og ama híb ido es dis in a que al
u iliza MPI en soli a io. Cuando es amos abajando con hilos la o ma de inicializa
co ec amen e se ía:
MPI_Ini _ h ead (&a gc, &a g , MPI_THREAD_FUNNELED, &p o ided);
i (p o ided < MPI_THREAD_FUNNELED){
p in (" eques : %d, p o ided: %d",MPI_THREAD_FUNNELED, p o ided );
MPI_Abo (MPI_COMM_WORLD, 1);
}
Donde con “MPI_THREAD_FUNNELED” le indicamos a MPI el ni el mínimo de
“ h ead sa e y le el” con el que que emos abaja , en es e caso la a iable indica ni el 1 (más
in o mación en pg 17 -> h p://www.mcs.anl.go /~balaji/ alks/ u o ials/2013/2013-06-16-isc-
mpi.pp x) y en la a iable “p o ided” MPI nos de uel e el ni el e ec i o con el que se a a
ejecu a .
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
66
Impo an e: Si el ni el que nos de uel e “p o ided” es in e io al ni el que eque imos
y el p og ama abo a puede se debido a que no hemos u ilizado la a iable de en o no
“MV2_ENABLE_AFFINITY=0” a la ho a de ejecu a y se es án se ializando los p ocesos con
lo que MPI no nos puede da el ni el de segu idad que necesi amos.
Po úl imo, hemos de ene en cuen a que el a chi o “hos ile” ha de indica que en cada
nodo solo se puede ejecu a un p oceso, así el con enido de nues o a chi o “h _mpi” se ia po
ejemplo:
nodo1:1
nodo2:1
3.1 MPI + OMP
Podemos compila un p og ama híb ido de MPI y OMP añadiendo el lag “- openmp”:
$ mpicc - openmp -o mpi_hello_wo ld mpi_hello_wo ld.c
Además, hemos de in oduci en odos los nodos la a iable de en o no
“OMP_NUM_THREADS=X” donde X es el núme o de hilos que que emos que se c een den o
de cada nodo en pa icula . Po ejemplo, pa a indica que que emos que se ejecu en 8 hilos en el
nodo “nodo1” debe íamos en a a dicho nodo ía SSH y esc ibi :
$ expo OMP_NUM_THREADS=8
Si de ec amos que los hilos se ejecu an se ializados en un co e pese a habe con igu ado
la a inidad de MPI pa a que los hilos se dis ibuyan en e odos los co es, pod emos ayuda nos
de la a iable de en o no especí ica pa a OMP “GOMP_CPU_AFFINITY=X-Y”, donde X e Y
son los índices de los co es que indican el ango en e los cuales se an a dis ibui los hilos. Po
ejemplo, pa a indica que que emos que se dis ibuyan en e los co es del 0 al 7 esc ibi íamos
en cada nodo:
$ expo GOMP_CPU_AFFINITY=0-7
Finalmen e pa a ejecu a nues o algo i mo lo ha íamos de la o ma usual pa a
p og amas híb idos, indicando con “-np” que que emos an os p ocesos como nodos de que
disponemos:
$ mpiexec -np 2 --hos ile h _mpi -en MV2_ENABLE_AFFINITY 0
mpi_hello_wo ld
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
67
3.2 MPI + PTHREADS
En es e caso no enemos que ene an as conside aciones como con OMP. Podemos
compila no malmen e y ejecu a el p og ama al como indicamos en el p incipio del apa ado
de p og amas híb idos.
$ mpicc -o mpi_hello_wo ld mpi_hello_wo ld.c
$ mpiexec -np 2 --hos ile h _mpi -en MV2_ENABLE_AFFINITY 0
mpi_hello_wo ld
4 MPI + CUDA
Pa a ealiza pesados cálculos ma iciales puede esul a muy in e esan e u iliza MPI
pa a dis ibui la ca ga en e odos los nodos y CUDA pa a hace los cálculos sob e las GPU de
cada nodo.
Pa a que en iempo de ejecución sea isible la lib e ía CUBLAS en odos los nodos es necesa io
expo a la a iable de en o no LD_LIBRARY_PATH con la u a a dicha lib e ía:
$ expo LD_LIBRARY_PATH=$LD_LIBRARY_PATH: /us /local/cuda-5.5/lib64
Si as a u iliza el compilado n cc debes añadi ambién su u a a la a iable PATH:
$ expo PATH=$PATH:/us /local/cuda-5.5/bin/
Si po el con a io as a compila u ilizando mpicc has de indica los siguien es lags y u as:
$ mpicc s c/mpi_cublas.c -lcublas -lcuda _s a ic -I /us /local/cuda-5.5/include -L
/us /local/cuda-5.5/lib64 -s d=c99 -o bin/myCublasApp
5 MPI + COPROCESADOR VECTORIAL
Mejo a el iempo de ejecución de nues os p og amas siemp e es un obje i o
impo an e y más aún si es amos abajando sob e un Clus e dado que es os suelen es a muy
solici ados y usualmen e enemos un iempo limi ado de uso del mismo. Una buena p ác ica de
op imización es ap o echa los cop ocesado es ec o iales que ienen las CPU ejecu a
cómpu os en pa alelo. Con ello podemos ob ene speed –ups muy in e esan es.
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
68
Pa a ap o echa nos de la elocidad del cop ocesado enemos dos opciones. La p ime a
es implemen a noso os las ope aciones ec o iales en nues o código, lo cual no es i ial de
hace , consegui íamos una mejo a de endimien o que paga íamos con la complejidad de la
implemen ación. La segunda es ap o echa nos del au o ec o izado del que disponen las
e siones mode nas del compilado “gcc”. Simplemen e añadiendo el lag “-O3” el compilado
in en a a ec o iza odas las ope aciones y bucles que sea capaz. Po ejemplo:
$ mpicc -o mpi_hello_wo ld mpi_hello_wo ld.c –O3
La ejecución es comple amen e igual que la que ha íamos si no u ilizá amos el
cop ocesado .
$ mpiexec -np 2 --hos ile h _mpi -en MV2_ENABLE_AFFINITY 0
mpi_hello_wo ld
Además, podemos añadi di ec i as en nues o código que acili en al au o ec o izado
su abajo de op imización y pode saca asi mejo es endimien os (mas in o en ->
h p://locklessinc.com/a icles/ ec o ize/).
Si has op ado po hace una implemen ación median e unciones in ínsecas de GCC lo
único que debes añadi al comando de compilación es el lag –ma x si es ás abajando en los
nodos XEON o –msse2 si es ás abajando con los nodos ATOM (di e en es a qui ec u as de
p ocesado ienen di e en es juegos de ins ucciones ec o iales):
$ mpicc -o mpi_hello_wo ld mpi_hello_wo ld.c –ma x
$ mpicc -o mpi_hello_wo ld mpi_hello_wo ld.c –msse2
Es udio compa a i o de las p es aciones de di e en es modelos de p og amación pa alela
69
6 LINKS DE INTERÉS
MPICH:
! h p://www.mpich.o g/documen a ion/guides/
MVAPICH:
! h p://m apich.cse.ohio-s a e.edu/use guide/
! h p://chpc.wus l.edu/asse s/ iles/pd /WashU_7_m apich.pd
CUDA:
! h p://docs.n idia.com/cuda/index.h ml#axzz3Yu9xIJHA
! h p://docs.n idia.com/cuda/cublas/index.h ml#axzz3XmUq51mU
GCC:
! h p://locklessinc.com/a icles/ ec o ize/