Estudio comparativo de las prestaciones de diferentes modelos de programación paralela

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/