Repositorio Institucional de Documentos

Proyeto Fin de Carrera Ingeniería en Informátia Estrategias de paralelizaión de un ó digo de simulaión hidráulia de ujos transitorios 2D en volúmenes nitos Asier Heradio Laasta Soto Diretor: Javier Burguete Tolosa 1 Ponente: Vitor Viñals Yúfera 2 (1) Departamento Suelo y Agua Estaión Exp erimental Aula Dei/CSIC (2) Departamento de Informátia e Ingeniería de Sistemas Centro Politénio Sup erior Universidad de Zaragoza Curso 2010/2011 Abril 2011 2 A Papá, Mamá, María(s), José Miguel, Eva, Celia, Pepe, Tita, Diego y Tati 4 Agradeimientos Quiero agradeer, en primer lugar, a Pilar Garía, Diretora del Grup o de Hidráulia Computaional, la onanza y atenión mostradas, así omo la p osibilidad de realizar este traba jo. En segundo lugar, al resto de omp onentes de este Grup o p or su inestimable olab oraión, muy esp eialmente a Mario Morales, Javier Murillo y Daniel Caviedes, p or hab er p o dido saar el segundo de atenión que mis dudas requerían. Agradezo también a Juan Antonio Garía, p or su buen trato y p or su interés. Mis agradeimientos a Javier Burguete y Vitor Viñals, p or hab er aeptado ser el diretor y p onente resp etivos, así omo p or su ayuda en la revisión y orreión del texto que se presenta. También a Darío Suárez, p or hab erme p o dido resp onder uantas dudas omputaionales iban surgiendo. Además, me gustaría agradeer de manera esp eial a Arturo Giner y Guillermo Losilla la olab oraión que han mantenido onmigo en to do momento preo upándose de ofreerme to do lo que estaba en su mano para p o der realizar los tests que en este traba jo se presentan. i ii Resumen En este proyeto se plantea la optimizaión de SFS2D, un ó digo ientío de simulaión hidráulia, seuenial y esrito en Fortran, on una gran arga omputaional. SFS2D sirve para mo delar situaiones muy diversas que van desde la simulaión de las onseuenias de una rotura de presa al estudio de una reida rep entina del audal de un río. SFS2D ha sido desarrollado p or el Grup o de Hidráulia Computaional de la Universidad de Zaragoza y se basa en un méto do de resoluión de ujos de sup erial libre que en la atualidad sirve omo sop orte para desarrollar nuevos mo delos numérios aoplados. Sin embargo, tras varios años de evoluión, el rendimiento de SFS2D es esaso y las simulaiones de interés se prolongan demasiado en el tiemp o. Esto es un problema a la hora de obtener resultados, siendo neesaria algún tip o de optimizaión que haga disminuir estos tiemp os lo máximo p osible. Para esto y omo veremos a lo largo del traba jo, se han estudiado distintas op iones de optimizaión, desde las prop orionadas p or el propio ompilador hasta el desarrollo de versiones adaptadas a diversas plataformas multipro esador. Para ello, se han onsiderado los dos mo delos prinipales de ejeuión paralela en álulos ientíos: memoria ompartida y paso de mensa jes. La versión paralela de memoria ompartida se ha o diado utilizando primitivas Op enMP y es apropiada para su ejeuión en máquinas multiore , que integran varios pro esadores de alto rendimiento en un hip. La versión paralela basada en memoria distribuída se ha programado usando primitivas MPI y es apropiada para su ejeuión de un número p otenialmente grande de no dos de álulo indep endientes p ero onetados mediante una red de alto rendimiento (máquinas de memoria distribuida). En la evaluaión exp erimental se observa que el esalado de la versión basada en paso de mensa jes es muy bueno también en máquinas de memoria ompartida p or lo que se onsidera la ap ortaión prinipal de este proyeto. Para araterizar el rendimiento de nuestras soluiones, usamos omo arga de traba jo tres simulaiones diferentes que ubren la asuístia general de las simulaiones que se haen a través del ámbito abarado p or SFS2D. La evaluaión del rendimiento se ha realizado además en máquina real, utilizando tres lúster 1 suientemente distintos omo para dar validez a nuestras onlusiones. El primero de ellos es un lúster onformado p or equip os de araterístias no destinado a este tip o de ejeuiones. El segundo equip o, denominado Terminus, está esp eializado en omputaión y onsigue una gran densidad de álulo mediante una organizaión en blades y una jerarquía de interonexión optimizada. Por último se utiliza también el no do de la Red Española de Sup eromputaión en Zaragoza, Caesaraugusta. Caesaraugusta es un sup eromputador destinado úniamente a álulo ientío de memoria distribuida on 512 pro esadores interonetados mediante una red de ba ja latenia (Myrinet). 1 Conjunto de no dos de álulo iii iv Índie general 1 Intro duión 1 1.1 Contexto del traba jo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 El Grup o de Hidráulia Computaional . . . . . . . . . . . . . . . . . . . 2 1.1.2 El Grup o de Arquiteturas de la Universidad de Zaragoza . . . . . . . . . 2 1.2 Estrutura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Coneptos prinipales 5 3 Paralelizaión de la apliaión 9 3.1 Paralelizaión en máquinas de memoria ompartida . . . . . . . . . . . . . . . . . 9 3.1.1 Cálulo del ∆W y ∆t ............................. 10 3.1.2 Atualizaión de la variable W . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.3 Resultados de la ejeuión en máquinas de memoria ompartida . . . . . . 11 3.2 Paralelizaión en máquinas de memoria distribuida . . . . . . . . . . . . . . . . . 12 3.3 Prepro eso y Postpro eso de las mallas de álulo . . . . . . . . . . . . . . . . . . 15 4 Resultados de la paralelizaión 19 4.1 Casos de prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Rendimiento en Tromb ón . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.3 Rendimiento en el luster Terminus . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.4 Rendimiento en el luster RES-Caesaraugusta . . . . . . . . . . . . . . . . . . . . 22 5 Conlusiones y Traba jo Futuro 25 5.1 Conlusión del traba jo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.2 Traba jo Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.3 Conlusión p ersonal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Bibliografía 27 A Análisis de ompilaión del ó digo 29 A.1 Análisis de la ompilaión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 A.2 Rendimiento de los ompiladores . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 B Mo delo 2D de ujo de lámina libre on promedio en la vertial 33 B.1 Euaiones generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 B.2 Euaiones promediadas en la vertial . . . . . . . . . . . . . . . . . . . . . . . . 35 B.2.1 Término de friión y mo delos de turbulenia . . . . . . . . . . . . . . . . 36 B.2.2 Versión omún de las euaiones de aguas p o o profundas . . . . . . . . . 37 B.3 Esquema numério . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 v 4 Capítulo 2 Coneptos prinipales Para p o der omprender el alane del proyeto, es neesario intro duir los oneptos en los que se sustenta el mismo. Por ello, se detallarán los fundamentos de paralelizaión y las herramientas en las que se ap oya el traba jo. La omputaión ientía en to dos sus ámbitos, suele requerir de una serie de apliaiones uyas neesidades de álulo suelen ser elevadas [7℄. En partiular, la apliaión en la que se basa este proyeto, realiza suesivos pasos temp orales y una elevada antidad de álulos en ada uno de ellos. Por ello es imp ortante enontrar la forma de realizar estos álulos de la manera más eiente p osible on la nalidad de alzanar una mayor pro dutividad en términos omputaionales. En este aso, la pro dutividad la busaremos a través de ténias de paralelizaión. La paralelizaión se puede llevar a ab o en distintos niveles, desde la paralelizaión de instru- iones a muy ba jo nivel on reursos SIMD (Single instrution Multiple Data) de pro esamiendo vetorial, hasta la paralelizaión de tareas u op eraiones on máquinas MIMD (Multiple Instru- tion Multiple Data) según la lasiaión de Flynn[3 ℄, siendo estas últimas las que ubren las arquiteturas basadas en p pro esadores destinados a ataar un problema divisible en k partes. Nosotros nos basaremos en arquiteturas MIMD, a p esar de que el pro esador IBM R  PowerPC 970FX disp onga de un rep ertorio de instruiones vetoriales ono ido omo VLX. Para valorar las soluiones paralelas utilizaremos dos guras de mérito. Por un lado utilizaremos el Sp eed-up Sp [9℄, que mide la ganania en terminos temp orales de una apliaión paralelizada ejeutada en p pro esadores en un tiemp o tp frente a la ejeuión de la misma apli- aión ejeutada en un pro esador en un tiemp o ts . Así, este fator se puede formular omo, Sp=ts tp (2.1) Este valor está aotado teóriamente en (0, p] y p or lo tanto, siempre p o dremos omparar nuestro Sp eed-Up frente al Sp eed-Up teório, Stheorical =p (2.2) Por otro lado tenemos otro fator, que es el fator de Eienia o Performane que mide la relaión existente entre el Sp eed-Up y el número de pro esadores utilizados, e=Sp p (2.3) El valor de la eienia está aotado en [0,1] . Idealmente, la eienia es 1, aunque realmente esta eienia es inalanzable dado que existe un tiemp o de omuniaión tc que implia que el 5 CAPÍTULO 2. CONCEPTOS PRINCIPALES tiemp o de ejeuión será omo muho 2.4 texec =ts p+tc (2.4) Esta formulaión es una ota máxima que tamp o o se suele alanzar habitualmente, dado que sup one una división equilibrada de traba jo en p pro esadores y esto no siempre es así. Si en la ejeuión para p pro esadores esogemos el máximo tiemp o de ejeuión, tM=MAX(t1, t2...tn) , se umplirá que: tM≥ts p (2.5) Con lo que el tiemp o de ejeuión total será texec =tM+tc≥ts p+tc (2.6) Además de to do lo ontemplado aquí, para alular de manera rigurosa el tiemp o de ejeuión habría que tener en uenta los fallos en los distintos niveles de ahe, que en general disminuirán según vayamos distribuyendo el espaio de datos entre las ahes de los diferentes pro esadores. To do lo anteriormente planteado sugiere que la eienia e será menor que uno aunque existen mo delos que explian otas del Sp eed-Up sup eriores a p y p or lo tanto eienias sup eriores a uno [8℄, además, visibles en este traba jo. Sobre la ganania teória que puede tener una apliaión, existen diferentes p ostulaiones. Una de ellas es la ley de Amdahl[1 ℄, que prop one el álulo del Sp eed-Up omo Sp=p p−α(p−1) (2.7) siendo p el número de pro esadores que interviene en el álulo y α la fraión de ó digo que se ejeuta en paralelo. El fator α disminuye on la ejeuión de ó digo seuenial o on la entrada/salida no paralela. Otra propuesta es la de Gustafson [6℄, la ual es más optimista y enunia el Sp eed-Up teório, on las mismas variables que antes salvo α que representa la parte no paralelizable, omo Sp=p−α(p−1) (2.8) Lo ierto es que la ganania real está entre la urva que aparee de la formulaión 2.7 y 2.8. El balaneo de arga que ya ha apareido es uno de los fatores determinantes en el ob jetivo de enontrar una paralelizaión efetiva. Este punto es omplejo en nuestro aso dado que el número de elementos sobre los que hay que haer los álulos es variable en el tiemp o y además, a priori, no se puede estableer ningún tip o de división p erfetamente equilibrada. En nuestro aso p o demos haer la sup osiión de que el volumen de ontrol oinide on el dominio de álulo y p or lo tanto que se va a haer álulos en to da la malla aunque en realidad esto sólo suede uando to das las eldas tienen alado durante to do el tiemp o. Estableer una partiión óptima para to da la simulaión es una tarea que no se ha llevado a ab o en este traba jo pues la diultad que entraña meree un proyeto separado. El último onepto uya veraidad ha sido omprobada, es la omúnmente ono ida omo regla 90-90 heha p opular p or Jon Bentley's en 1985 que die "The rst 90 % of the ode aounts for the rst 90 % of the development time. The remaining 10 of the ode aounts for the other 90 % of the development time" . Esta frase tiene la uriosidad de que los p orenta jes no suman 100 y hay quien die que es un error tip ográo, p ero existe otra orriente que piensa que ya 6 entones se presumía que la naturaleza de los proyetos de desarrollo de software es neesariamente no umplir los plazos predihos. Por ualquiera de las dos orrientes se ha visto afetado este proyeto. Por otro lado el mo delo numério del simulador es un desarrollo lo suientemente omplejo omo para que su expliaión detallada apareza en el anexo B. La evoluión que ha ido sufriendo año atrás (e inluso durante el desarrollo de este proyeto) ha sido una de las razones de que el análisis del mismo haya resultado muy ompleja. Como veremos en apítulos p osteriores, la estrategia de paralelizaión del ó digo no es ni muho menos trivial y su implementaión tamp o o. Es op ortuno desribir omo funiona el algoritmo a nivel omputaional. En el ap éndie H se puede ver el Diagrama de Flujo de la apliaión a lo largo de la simulaión. En este proyeto, sólo se analizará y paralelizará el méto do bloks1 orresp ondiente on el méto do de orden 1 sin sedimentos aunque bloks1sedimentos será relativamente senillo a partir del primero. De ahora en adelante, nos referiremos a bloks1 omo al núleo de álulo, es deir, la funión que desarrolla to do el méto do numério sobre un dominio de álulo que estará representado omputaionalmente p or una malla (Ver Anexo B). Así mismo, es onveniente expliar que el méto do es iterativo, lo que implia que la resoluión lleva implíita un paso de tiemp o aso iado. En este aso, este paso de tiemp o viene impuesto p or la ondiión de CFL [12 ℄. Este paso de tiemp o lo denominaremos ∆t y p or lo tanto ada iteraión se hae on un paso de tiemp o aso- iado para la resoluión de la variable de interés W . La variable W se omp one de Wn= (hn, un, vn) donde hn es el alado de la elda n , un, vn son las omp onente de la velo idad del ujo en la elda n y si,1, ..., si,n son los términos fuente de la euaión para la elda n . Es imp ortante tener en uenta que a lo largo de la ejeuión, puede hab er eldas que pasen de estar seas a estar mojadas , es deir, que tengan alado h > 0 . Esto sup ondrá que hay que ampliar el dominio de álulo, y esto lo india una funión externa a la de bloks1 , p ero que de manera implíita está paralelizada ya que ada dominio de álulo tendrá que ampliar úniamente las eldas de su dominio. 7 8 Capítulo 3 Paralelizaión de la apliaión La paralelizaión de la apliaión es el ob jetivo prinipal del proyeto desarrollado on la nalidad de disminuir el tiemp o de álulo. A partir de este proyeto ha naido una relaión on el BIFI que nos ha p ermitido utilizar sus infraestruturas para realizar nuestros álulos. Para las pruebas que a ontinuaión presentaré, se han utilizado tres luster de álulo. El primero es el luster Tromb ón que p ertene al grup o GHC; el segundo p ertenee al luster Terminus 1 omo parte del programa de Hosted Computing del BIFI de la Universidad de Zaragoza. El terero es Caesaraugusta 2 , no do de la Red Española de Sup eromputaión que está instalado en el ediio de Cienias de la Universidad de Zaragoza y es gestionado p or el BIFI. En este apítulo se trata además, la adaptaión de las tareas de prepro eso y p ostpro eso propias de la apliaión de álulo. 3.1 Paralelizaión en máquinas de memoria ompartida La paralelizaión en máquinas de memoria ompartida se ha implementado ba jo el estándar Op enMP [2℄ omo ejeriio de intro duión al ó digo SFS2D. Para la paralelizaión p or este méto do, la estrategia que se sigue es la de, a partir de las on- lusiones obtenidas del análisis de ompilaión y detalladas en el anexo A, estudiar las seiones rítias en tiemp o para p o der reba jarlo. La parte identiada orresp ondiente al álulo de W es bloks1 y se basa en bules que op eran sobre las eldas y las paredes del volumen de ontrol y son estos bules los que hay que analizar apliando ténias similares a las utilizadas en el análisis de dep endenias a ba jo nivel [14℄. Po demos estableer dos tareas basadas en bule dentro de esta funión: 1. Cálulo de ∆W y ∆t 2. Atualizaión de W En estos dos bules existen sendas dep endenias que es neesario analizar. 1 http://bi.es/infrastrutures/sup eromputing/terminus/index.php 2 http://bi.es/infrastrutures/aesaraugusta/index.php 9 CAPÍTULO 3. PARALELIZACIÓN DE LA APLICACIÓN 3.1.1 Cálulo del ∆W y ∆t El álulo de to das las variables se hae reorriendo las paredes de la malla de alulo, lo que implia que será un bule que barrerá to do el dominio de paredes inluídas en el álulo en el paso de tiemp o atual. En el aso del álulo de ∆W las dep endenias haen que la ab eera del bule Op enMP quede de la siguiente forma: 1 ! $OMP PARALLEL DEFAULT( PRIVATE) SHARED ( NPAREDINCLULLE , 2 ! $ O M P + N U M _ N P A R E D I N C L U L L E , P A R E D , W , T O L E R A , V O L C , N O R M A L P , L A D O P , P R I M I T I V A S , 3 ! $ O M P + P R I M I T I V A S R A I Z , R A I Z H G , F O N D O , R N , B _ F R I C C , V E C C E L L , P A R E D N V , 4 ! $ O M P + C E L L D P , P E R D I D A P A R E D P U E N T E , G A N A N C I A _ E N E R _ O R B A L , C H I , L A D O , 5 ! $ O M P + D W 2 , V E C C E L L 2 , N U M _ N L I S T A , N E Q , 6 ! $ O M P + A C T I V A T E _ R I E N M A N N , T I P O F , N V E R T , M O D E L _ F R I C T I O N , A C T I V E G A M M A , 7 ! $ O M P + N S O L U T O S , A C T I V E E N T R O P Y , 8 ! $ O M P + D T , N L I S T A , G , R A I Z G 9 ! $ O M P + ) 10 ! $ O M P D O El paso de tiemp o ∆t es una funión de la velo idad y del alado en una elda dada, en partiular, para to do el dominio de álulo, será el menor de ellos, p or lo que deb eremos añadir además esta linea detrás del !$OMP DO : 1 ! $ O M P + R E D U C T I O N ( M I N : D T ) Con esta diretiva lo que haemos es indiar a Op enMP que de to dos los menores ∆t esoga el menor. El bule lo hemos paralelizado diiendo que, p or defeto, las variables serán privadas, salvo las que indiamos de manera explíita, mientras que este bule p o dríamos haerlo de una forma equivalente 1 ! $ O M P P A R A L L E L D E F A U L T ( S H A R E D ) P R I V A T E ( K , N , N 1 , N 2 , H 1 , H 2 2 ! $ O M P + M O J A D O I J , A R E A , N X , N Y , N O R M , U 1 , U 2 , V 1 , V 2 , A U X 1 , A U X 2 , A U X 3 , H B A R 3 ! $ O M P + U B A R , V B A R , F I S O L B A R , C B A R , U N O R M A L , A B S U N O R M A L , F R O U D E , L A N D A , 4 ! $ O M P + D I F Q X , D I F Q Y , A U X 4 , E , B E T A , L A N D A L , L A N D A R , B E T A A U X , L A N D A A U X , C 1 , 5 ! $ O M P + C 3 , Z 2 , Z 1 , P S 1 , P S 2 , D Z , A B S D Z , P S , P S M A X , F R I C T I O N , F R I C T I O N 2 , F R I C T I O N 3 , 6 ! $ O M P + M A X H , M O D U L 1 , M O D U L 2 , M I N U , B _ F R I C M E D I A , A C T I V A _ P A R E D , N C N , N V , A U X 1 0 7 ! $ O M P + M I N R A T I O , H Q I 1 , H Q I 2 , H S T A R , H L S , H L R , D T 3 , D T 2 , D T 4 , D T S M A L L , P A R E D _ S O L I D A 8 ! $ O M P + , H R S , D W 2 A U X , L , J , C O N D 1 , C O N D 2 , C O N D 3 , Q L , Q R , F R , F L , D F J 1 , D F J 2 ) 9 ! $ O M P D O 10 ! $ O M P + R E D U C T I O N ( M I N : D T ) 3.1.2 Atualizaión de la variable W La atualizaión de la variable W en el paso de tiemp o n es un bule que reorre en i to do el dominio de álulo omo: Wn i=Wn−1 i+ ∆Wn−1 i∗∆t (3.1) obteniendo de (3.1) el resultado de los nuevos valores de ∆W 10 3.1. PARALELIZACIÓN EN MÁQUINAS DE MEMORIA COMPARTIDA 3.1.3 Resultados de la ejeuión en máquinas de memoria ompartida Los resultados que aquí apareen son para la arquitetura F.3 on el aso de la gura 3.5 on un alado onstante. El binario pro ede del ompilador gFortran 4.4 sin ninguna optimizaión. 0 100 200 300 400 500 600 0 50 100 150 200 250 300 350 400 Execution time (s) Executed time (s) OpenMP - 1 Thread OpenMP - 2 Thread OpenMP - 3 Thread OpenMP - 4 Thread OpenMP - 5 Thread OpenMP - 6 Thread OpenMP - 7 Thread OpenMP - 8 Thread (a) Tiemp os de ejeuión (y) frente a tiemp o eje- utado (x) 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 Speed-Up # Threads Speed-Up Theorical Speed-Up (b) Sp eedUp vs. Theorial Sp eedUp Figura 3.1: Tiemp os de ejeuión (a) y Sp eed-Up (b) de Op enMP para el aso de prueba Los datos reogidos en la gura 3.1 muestran una diferenia notable resp eto a rendimiento teório. El sp eedUp está alulado de la forma: Sp=ts tp (3.2) Para p o der entender estos resultados, es neesario analizar qué está suediendo a ba jo nivel. Para esto vamos a utilizar la herramienta Valgrind 3 . Con esta herramienta, veremos los fallos de ahe en los distintos niveles. Cab e destaar que sólo apareen los niveles L1 y L2 de la ahe de datos mientras que la arquitetura disp one también de nivel L3. Por algún motivo desono ido, estos datos no apareen en la ejeuión de Valgrind. (a) Análisis de la funión prinipal (b) Análisis del bule prinipal de la funión Figura 3.2: Fallos de ahe en el programa prinipal (a) y fallos de ahe en bloks1 (b) para la apliaión on 1 thread En la gura 3.1 vemos que el Sp eed-Up es más o menos lineal p ero la p endiente de la urva es notablemente inferior a la de la teória. Analizando estos datos on los de los resultados del análisis de ahe 3.2, 3.3 y 3.4, p o demos ver que la ganania que teóriamente deb eríamos tener al dividir en el número de threads, se ve elipsado p or el número de fallos en ahé que inurre el 3 http://valgrind.org/ 11 CAPÍTULO 3. PARALELIZACIÓN DE LA APLICACIÓN (a) Análisis de la funión prinipal (b) Análisis del bule prinipal de la funión Figura 3.3: Fallos de ahe en el programa prinipal (a) y fallos de ahe en bloks1 (b) para la apliaión on 8 threads (a) Análisis de la funión prinipal (b) Análisis del bule prinipal de la funión Figura 3.4: Fallos de ahe en el programa prinipal (a) y fallos de ahe en bloks1 (b) para la apliaión on 4 threads programa prinipal. Tengamos en uenta que se disminuyen notablemente estos fallos en bloks1 p ero no en las funiones restantes en las que de heho, pasa lo ontrario. 3.2 Paralelizaión en máquinas de memoria distribuida A la vista de los resultados de la paralelizaión en máquinas de memoria ompartida, paree neesario ab ordar una estrategia de paralelizaión más esp eía para el ó digo. Esta paraleliza- ión se llevará a ab o ba jo el estándar MPI [5℄. Las estrategias que p o dríamos llevar a ab o son: 1. Paralelizar tareas 2. Paralelizar op eraiones Las diferenias entre ambas radian en la forma de implementar el ó digo y p or supuesto en el rendimiento que teóriamente nos puede ofreer una op ión u otra. En el aso de paralelizar tareas y apliado a nuestro aso, esta implementaión se basaría en que p pro esadores hiieran p tareas distintas e indep endientes on la nalidad de aumentar el rendimiento aumentando la pro dutividad. Ejemplos de esta forma de paralelizar se enuentran en simulaiones de Monte Carlo en la ual ada uno prueba on diferentes valores y a lo largo del tiemp o van omuniándose las aproximaiones. Paralelizar op eraiones desomp one una tarea en op eraiones dep endientes de manera distribuída. En nuestro aso esto será repartir el dominio de álulo en p partes, y asignarle ada parte a ada no do de álulo. La estrategia que aquí se prop one es la de paralelizar tareas, es deir, dejar a ada no do de álulo que ejeute sus op eraiones sobre un sub dominio. Esto es que ada no do alule un sub dominio de los mostrados en la gura 3.5. Está ténia se 12 3.2. PARALELIZACIÓN EN MÁQUINAS DE MEMORIA DISTRIBUIDA Figura 3.5: partiion de la malla en 8 subdominios ( grupo ) y altura top ográa z resp eto al 0 (Nivel de salida) send(),recv() send(),recv() send(),recv() send(),recv() Figura 3.6: esquema de omuniaión 1-D basa pues en rear varios sub dominios de álulo y onetarlos de manera onseutiva, es deir, implementar un esquema de omuniaión 1-Dimensional la ual sólo se hae on, omo mu- ho, dos no dos omo vemos en la gura 3.6. Para rear estos sub dominios y omo veremos en la siguiente seión, hemos de haer umplir alguna ondiión para que la paralelizaión sea efetiva. En este mo delo ada elda dep ende de sus veinas y en partiular, en el límite entre dos sub dominio de álulo, las eldas limítrofes dep enderán también de las eldas veinas. Por lo tanto neesitamos, para ada paso de tiemp o, transferir los valores de las eldas veinas de los sub dominios Ds−1 y Ds+1 que neesita el sub dominio Ds omo vemos en la gura 3.6. La parte ompleja de la paralelizaión es elegir la estrategia de omuniaión de estas variables omunes para ada sub dominio de entre las dos disp onibles: 1. Elegir un no do diretor que vaya reopilando las variables neesarias en ada paso de tiemp o y redistribuyéndolas. 13 CAPÍTULO 4. RESULTADOS DE LA PARALELIZACIÓN Además, para saar el Sp eed-up y el Rendimiento, se utilizará el tiemp o de ejeuión de 400 s. simulados. 4.2 Rendimiento en Tromb ón Los resultados que hemos obtenido en este luster son imp ortantes, dado que esta es la plataforma de la que disp one el grup o para haer sus simulaiones. Los rendimientos que se obtienen son bastante aeptables aunque hemos de tener en uenta que esta infraestrutura no se reó p ensando en lanzar apliaiones paralelas. Esto es algo que deb erá ser revisado en el futuro para obtener un mejor rendimiento de la instalaión. 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 0 50 100 150 200 250 300 350 400 Execution time (s) Executed time (s) MPI - 1 nodes MPI - 2 nodes MPI - 4 nodes MPI - 8 nodes MPI - 16 nodes MPI - 28 nodes (a) Tiemp os de ejeuión frente a tiemp os ejeutados 0 5 10 15 20 25 30 5 10 15 20 25 Speed-Up # Threads Speed-Up Theorical Speed-Up (b) Sp eed-up en 400 s. de simulaión 0 0.2 0.4 0.6 0.8 1 5 10 15 20 25 Performance # Nodes 1-performance Performance () Performane en 400 s. de simulaión Figura 4.1: Tiemp os de ejeuión (a), sp eed-ud (b) y rendimiento () del aso C.1 en Trombón Aún así se ve en 4.1 que esala de manera lineal hasta 16. Esta diferenia entre 8 y 16 se deb e a que los resultados on 8 no dos son fruto de la ejeuión en 2 no dos físios, ada uno on 4 ores en el pro esador, es deir, el fator de omuniaión intra-no do solo inuye una vez en tanto que sólo existe una frontera entre un no do y otro, mientras que a partir de 8, p or ejemplo on 16, ya existe una máquina que tiene que omuniarse on otras dos. 20 4.3. RENDIMIENTO EN EL CLUSTER TERMINUS Si tuvieramos más no dos, sería esp erable que el rendimiento ba jase en este aso partiular según aumentásemos los no dos omo onseuenia de lo que veremos en la ejeuión de Caesaraugusta, que es que la relaion de eldas aluladas frente a eldas omuniadas se va haiendo ada vez sustanialmente mas p equeña. 4.3 Rendimiento en el luster Terminus En este luster , las pruebas se han heho ba jo una ompilaión altamente optimizada para la arquitetura a través del luster . Además es imp ortante notar que la ejeuión en menos de 4 no dos se hae on-hip, para 8 se hae on-b oard y para 16 intra-no do. 0 500 1000 1500 2000 2500 3000 3500 4000 0 50 100 150 200 250 300 350 400 Execution time (s) Executed time (s) MPI - 1 nodes MPI - 2 nodes MPI - 4 nodes MPI - 8 nodes MPI - 16 nodes (a) Tiemp os de ejeuión frente a tiemp os ejeutados 0 2 4 6 8 10 12 14 16 2 4 6 8 10 12 14 16 Speed-Up # Threads Speed-Up Theorical Speed-Up (b) Sp eed-up en 400 s. de simulaión 0 0.2 0.4 0.6 0.8 1 2 4 6 8 10 12 14 16 Performance # Nodes 1-performance Performance () Performane en 400 s. de simulaión Figura 4.2: Tiemp os de ejeuión (a), sp eed-ud (b) y rendimiento () del aso C.1 en Terminus Si bien es ierto que la optimizaión a la hora de la ompilaión es muy imp ortante, lo destaable de estos resultados es el rendimiento 4.2() que saa la paralelizaión. El heho de que aumente según aumentamos los no dos (hasta 8) es p orque se priman los aiertos en ahe, mientras que p or el lado ontrario, aumentando fuera del no do, se p enaliza la omuniaión intra-no do. De estos resultados también hay que resaltar que el tiemp o de ejeuión, ya sólo la ejeuión del ó digo sin optimizar, es algo inferior a 2 vees más rápida que en Trombon y algo más de 6 21 CAPÍTULO 4. RESULTADOS DE LA PARALELIZACIÓN vees más que en Caesaraugusta . Igual que suede en la máquina Trombon , a partir de 8 no dos el rendimiento se redue ligeramente debido a la misma razón. Aquí en ambio la onguraión es ligeramente distinta lo que implia onlusiones distintas: Terminus tiene 2 no dos físios, ada uno de ellos on una plaa dual y ada una de ellas on dos pro esadores; esta onguraión implia que a partir de uatro no dos no sale de la plaa p ero sí sale del pro esador. Es a partir de 8 uando sale del no do y se omunia on el otro no do. jémonos que la tendenia del sp eed-up es muy similar en amb os, aunque el p erformane sea algo sup erior en esta máquina. 4.4 Rendimiento en el luster RES-Caesaraugusta Caesaraugusta tiene una onguraión mejor preparada para esta paralelizaión que el resto de omputadoras donde se han heho pruebas y los resultados que salen son muy interesantes en este sentido. En este aso hemos p o dido haer pruebas on hasta 128 no dos de álulo aunque este número no sea el que mejor rendimiento ofree omo vemos en la gura 4.3. 0 5000 10000 15000 20000 25000 30000 0 50 100 150 200 250 300 350 400 Execution time (s) Executed time (s) MPI - 1 nodes MPI - 2 nodes MPI - 4 nodes MPI - 8 nodes MPI - 16 nodes MPI - 32 nodes MPI - 64 nodes MPI - 96 nodes MPI - 128 nodes (a) Tiemp os de ejeuión frente a tiemp os ejeutados 0 20 40 60 80 100 120 140 20 40 60 80 100 120 Speed-Up # Threads Speed-Up Theorical Speed-Up (b) Sp eed-up en 400 s. de simulaión 0 0.2 0.4 0.6 0.8 1 20 40 60 80 100 120 Performance # Nodes 1-performance Performance () Performane en 400 s. de simulaión Figura 4.3: Tiemp os de ejeuión (a), sp eed-ud (b) y rendimiento () del aso C.1 en Caesaraugusta 22 4.4. RENDIMIENTO EN EL CLUSTER RES-CAESARAUGUSTA De estos resultados se desprende la onlusión de que a partir de 40 partiiones, en este aso, la ganania empieza a ser menor. Una de las onlusiones más imp ortantes que p o demos saar, no sólo de esta ejeuión si no de to do el traba jo y que será desarrollada en más profundidad, es la resultante de que a la vista de los resultados, el tiemp o de ejeuión en 128 no dos de Caesaraugusta ompilado on gFortran, es muy similar al de 16 no dos en una máquina de más reiente onstruión omo es Terminus. El heho de utilizar esta máquina es la futura adaptaión a simulaiones de gran esala que nos p ermite esta máquina. De heho, su araterizaión y omo se ve en la siguiente seión, será una parte fundamental a analizar antes de ejeutar ualquier simulaión on el n de determinar la duraión de la misma. 23 24 Capítulo 5 Conlusiones y Traba jo Futuro 5.1 Conlusión del traba jo La ejeuión de apliaiones paralelas en sistemas que lo sop ortan es una muy buena forma de disminuir el tiemp o de ejeuión de éstas, p ero es imp ortante ono er las araterístias propias del sistema en el que se va a ejeutar. Igualmente, la paralelizaión de una apliaión es una tarea ompleja p ero que en asos en los que este tip o de estrategia puede funionar y donde los tiemp os de ejeuión son largos, da unos resultados muy p ositivos. Además el heho de que la evoluión atual de las arquiteturas pase de la evoluión que seguía según la Ley de Mo ore [10℄ a arquiteturas multi-pro esador [11℄ requiere de una adaptaión en la forma de implementar nuestras apliaiones on el n de explotar al máximo las apaidades que éstas p oseen. No ab e duda de que este paradigma de programaión es uno de los que más futuro tiene en adelante. Es imp ortante además tener en uenta de que en España, disp onemos de una infraestrutura muy buena para el álulo de apliaiones ientías, que pasa p or la RES 1 y a nivel Europ eo ontamos on otras omo la EGEE 2 que favoreen el uso de instalaiones dirigidas a álulos masivos que requieren de la omputaión paralela. 5.2 Traba jo Futuro La paralelizaión de la apliaión es sólo el prinipio de la optimizaión de la herramienta. El heho de explotar la infraestrutura de manera paralela no es lo únio que p o demos haer en esta apliaión para saar más rendimiento. Una de las mejoras que se prop onen para la implementaión paralelizada y para la seuenial es reorganizar las estruturas de datos para adaptalas a la jerarquía de ahes, aumentando su lo alidad y mejorando la esalabilidad en memoria ompartida. To dos los lúster que se han usado en este traba jo disp onen de pro esadores que uentan on unidades de álulo vetorial, el ual nos daría algo más de rendimiento en seiones muy onretas del ó digo y on una reorganizaión del mismo, p o dríamos obtener muho más utili- 1 http://www.bs.es 2 http://www.eu-egee.org/ 25 CAPÍTULO 5. CONCLUSIONES Y TRABAJO FUTURO zando estas unidades. En esta misma linea, las GPGPUs 3 están muy preparadas para este tip o de álulos y queda omo traba jo futuro el adaptar la apliaión a este tip o de arquitetura. Otra tarea deseable para ompletar el traba jo desrito, es el estudio en profundidad de métodos de partiión y la onseuente adaptaión del ó digo a partiiones de tip o 2-D, esto sup ondría rendimientos sup eriores a altos números de no dos de álulo y también enontrar nuevas formulaiones del tiemp o de álulo. Otra alternativa que hemos planteado ha sido la partiión según el gradiente de p endientes, que p or lógia hidráulia, determinaría la direión preferente del aue. En [15℄ explian formas de disernir estas direiones prefereniales. Ademas, es interesante aoplar al algoritmo de partiión el mo delo matemátio desarrollado para alular el tiemp o de ejeuión p or dos razones: dejar al usuario la lib ertad de elegir el tiemp o que le interesa que dure la simulaión, prop orionándole siempre una ota mínima del mismo, y p or el heho de que en infraestruturas diseñadas para este tip o de ejeuiones, es neesario indiar el tiemp o aproximado de la duraión de la ejeuión, on la nalidad de que el sheduler otorgue una prioridad u otra. 5.3 Conlusión p ersonal Para mí este traba jo, además de un enorme esfuerzo, ha supuesto un reto tanto aadémio omo p ersonal. El primer ontato on la apliaión me hizo p ensar en la diultad que entrañaría la paralelizaión de la misma, p ero igualmente el onvenimiento de que se obtendrían unos muy buenos resultados. Efetivamente y omo desde un momento se p ensó, la paralelizaión de una apliaión de estas araterístias es ompleja, p ero realmente es la únia forma de p o der onseguir unos tiemp os de ejeuión razonables. Como hemos visto, estos tiemp os de ejeuión se han reduido muhísimo resp eto a los tiemp os que había hasta el momento. Esto ha sido muy bien aogido dentro del Grup o de Investigaión de tal manera que en un futuro próximo se pueda replantear el soliitar de nuevo horas de álulo en infraestruturas de la RES o la ompra de algún equip o más para las simulaiones. Además de to do esto he enontrado muy neesario la omprensión físia del problema y la p ersp etiva de la implementaión del méto do para p o der avanzar en el traba jo; ha sido fundamental quitarme las gafas de informátio y p onerme desde el punto de vista del mo delo para ver más allá de asignaiones o bules. Desde luego, to do lo aprendido a lo largo de la arrera me ha sido altamente útil, desde el Cálulo o el Álgebra, hasta la Ingeniería del Software o los Fundamentos de Arquiteturas Paralelas. Estoy muy orgulloso de los resultados del traba jo y onsidero que el esfuerzo volado no sólo en este traba jo, sino durante to da la arrera, ha tenido su reomp ensa. 3 General Purp ose Graphi Pro essing Unit 26 Bibliografía [1℄ G. M. Amdahl. Validity of the single pro essor approah to ahieving large sale omputing apabilities. In Proeedings of the April 18-20, 1967, spring joint omputer onferene , AFIPS '67 (Spring), pages 483485, New York, NY, USA, 1967. ACM. [2℄ B. Chapman, G. Jost, and R. v. d. Pas. Using OpenMP: Portable Shared Memory Paral lel Programming (Sienti and Engineering Computation) . The MIT Press, 2007. [3℄ M. J. Flynn and K. W. Rudd. Parallel arhitetures. ACM Comput. Surv. , 28:6770, Marh 1996. [4℄ P. Garía-Navarro, P. Brufau, J. Murillo, and J. Burguete. Volúmenes nitos para euaiones hiperbólias . 2009. [5℄ W. Gropp, R. Thakur, and E. Lusk. Using MPI-2: Advaned Features of the Message Passing Interfae . MIT Press, Cambridge, MA, USA, 2nd edition, 1999. [6℄ J. L. Gustafson. Reevaluating amdahl's law. Commun. ACM , 31:532533, May 1988. [7℄ M. T. Health. Sienti Computing . MGraw Hill, 1997. [8℄ D. Helmb old and C. MDowell. Mo delling sp eedup (n) greater than n. Paral lel and Distributed Systems, IEEE Transations on , 1(2):250 256, Apr. 1990. [9℄ A. H. Karp and H. P. Flatt. Measuring parallel pro essor p erformane. Commun. ACM , 33:539543, May 1990. [10℄ G. E. Mo ore. Cramming more omp onents onto integrated iruits. Eletronis, Volume 38, Number 8 , April 1965. [11℄ G. E. Mo ore. No exp onential is forever. International Solid State Ciruits Conferene, February 2003. [12℄ J. Murillo and P. Garia-Navarro. Weak solutions for partial dierential equations with sour- e terms: Appliation to the shallow water equations. JOURNAL OF COMPUTATIONAL PHYSICS Volume: 229 Issue: 11 Pages: 4327-4368 , 2010. [13℄ J. Murillo, P. Garía-Navarro, J. Burguete, and P. Brufau. The inuene of soure terms on stability, auray and onservation in two-dimensional shallow ow simulation using triangular nite volumes. International Journal for Numerial Methods in Fluids , 54(5):543 590, 2007. [14℄ W. J. P. Silvia M Mueller. On the orretness of hardware sheduling mehanisms for out-of-order exeution. Journal of Ciruits, systems and Computers, Volume 8, No. 2 , 1998. 27 BIBLIOGRAFÍA [15℄ G. M. Stefano Orlandini and M. Franhini. Path-metho ds for the determination of nondisp ersive drainage diretions in grid-based digital elevation mo dels. Water Resoures Researh, VOL. 39, NO. 6, 1144 , June 2003. 28 Ap éndie A Análisis de ompilaión del ó digo La ompilaión de la apliaión es una parte fundamental en el estudio del rendimiento iniial que p o demos obtener sin haer ninguna optimizaión en el ó digo, p or lo que es interesante prestarle atenión a este paso del análisis iniial de la apliaión. Atualmente, el GHC desarrolla su apliaión en sistemas Windows y Linux on diferentes ompiladores para ada Sistema Op erativo. En linux, el ompilador utilizado hasta el momento es gFortran 1 en su versión 4.4. Éste ompilador forma parte de la iniiativa GNU y aparee en los rep ositorios oiales de los sistemas op erativos utilizados en el grup o (Debian ó Ubuntu). En Windows, el ompilador que se utiliza es Lahey Fortran 90 2 en su versión v.4.5 para 32 bits. Esta versión están en desuso p ero el preio de la herramienta y su amigable entorno de programaión hae que esta herramienta to davía tenga un p eso imp ortante dentro de los usuario de Windows del grup o. Los equip os que se utilizan a nivel usuario, son to dos Intel Core 2 Duo en diferentes variantes, p or lo que sab emos que la familia es la Intel R  Core 2 que funionan en 64 bits. Se onsidera p or tanto, que es interesante analizar el rendimiento del ompilador de Intel R  3 on diferentes optimizaiones. A.1 Análisis de la ompilaión En una primera aproximaión al estudio del programa es interesante ono er dónde está p erdiendo tiemp o el ó digo y ver qué se puede haer on ello. Para esto vamos a utilizar una herramienta omerial, Intel R  vTune Amplifer XE for Linux. Es imp ortante alarar que p or ser para una lab or aadémia no remunerada, me voy a aoger a la lienia non-ommerial 4 . Además de la itada herramienta, utilizaremos el ompilador de Intel R  para este pro edimiento. El análisis se hará on el aso C.2 simulando 100 s. para evitar que la sobrearga iniial de prepro esamiento de la malla falsee los resultados. Esta premisa la mantendremos a lo largo del traba jo ya que esa sobrearga iniial se puede reduir optimizando esa seión y p or que entre otras osas, esa tarea no es paralelizable y p or lo tanto, no va a p o der reduirse on las estrategias 1 http://g.gnu.org/fortran/ 2 http://www.lahey.om/ 3 http://software.intel.om/en-us/artiles/intel-omposer-xe/ 4 http://software.intel.om/en-us/artiles/non-ommerial-software-development/ 29 APÉNDICE B. MODELO 2D DE FLUJO DE LÁMINA LIBRE CON PROMEDIO EN LA VERTICAL del movimiento en la direión vertial z se promedian las euaiones en esta direión haiendo uso de las deniiones de los promedios de las variables. ¯u=1 hZH zb udz (B.13) ¯v=1 hZH zb vdz (B.14) El pro eso de promediar en la vertial las euaiones onvierte el problema tridimensional en uno bidimensional de grosor variable h donde los ontornos ya no están en la sup erie libre y el fondo sino en el p erímetro. El promedio en la vertial de las euaiones del ujo de sup erie libre ba jo las hip ótesis del mo delo de aguas p o o profundas ondue a una versión muy omún del sistema de euaiones en 2D que rep etimos aquí: ∂h ∂t +∂(hu) ∂x +∂(hv) ∂y = 0 ∂(hu) ∂t +∂(hu2) ∂x +∂(huv) ∂y =−gh∂H ∂x +cfupu2+v2+hνT∇2u ∂(hv) ∂t +∂(huv) ∂x +∂(hv2) ∂y =−gh∂H ∂y +cfvpu2+v2+hνT∇2v B.2.1 Término de friión y mo delos de turbulenia El o eiente cf que aparee en el término de friión se expresa habitualmente en términos del o eiente de rugosidad de Manning n o de Chézy, cfupu2+v2=n2u√u2+v2 h4 3 (B.15) cfvpu2+v2=n2v√u2+v2 h4 3 (B.16) El o eiente de rugosidad n en la prátia se determina a partir de medidas exp erimentales o se estima a partir de valores que ya han sido almaenados en tablas. La euaión de Manning aquí desrita es de naturaleza empíria y p or tanto es el resultado de un pro eso de a juste a una urva de datos exp erimentales. La primera diultad que surge a la hora de usar este o eiente de rugosidad es la preisión on la que ha sido estimado. El o eiente n dep ende en prinipio del número de Reynolds del ujo, de la rugosidad de los ontornos y de la forma geométria de la uena. La rugosidad de la sup erie del ontorno representa un valor rítio a la hora de estimar n , on valores p equeños si el material es no y valores altos en el aso ontrario. El valor de n también deb e de dar uenta de la vegetaión retardando el ujo y prop orionando valores altos de n , dep endiendo también de la altura de agua. El mo delo de friión dado p or (B.15) y (B.16) se basa en la teoría de apa límite estaionaria sobre pared rugosa. Con el ob jeto de alular las variables hidro dinámias, es neesario jar el valor del o e- iente de Manning, omo ya hemos diho, y el valor de la visosidad inemátia de remolino. La visosidad turbulenta νT dep ende de las araterístias del ujo y puede variar de un punto a otro del dominio. Por tanto, es neesario plantear un mo delo de turbulenia que nos p ermita evaluar el valor de νT en ada punto del dominio. 36 B.2. ECUACIONES PROMEDIADAS EN LA VERTICAL B.2.2 Versión omún de las euaiones de aguas p o o profundas El término que proviene de promediar en la vertial el gradiente de presión ha dado lugar a los términos g∂H/∂x , g∂H/∂y , que a su vez se pueden desomp oner, teniendo en uenta que H=h+zb en g∂H ∂x =g∂h ∂x +g∂zb ∂x (B.17) g∂H ∂y =g∂h ∂y +g∂zb ∂y (B.18) Los términos ∂h/∂x , ∂h/∂y se agrupan junto a las otras derivadas del mismo tip o (términos onvetivos). Las variaiones del fondo se expresan en forma de p endiente S0x=−∂zb ∂x (B.19) S0y=−∂zb ∂y (B.20) Los términos de friión del agua on el fondo del aue se representan p or Sf , p endiente de la línea de energía en ada direión Sfx =cfu√u2+v2 gh (B.21) Sfy =cfv√u2+v2 gh (B.22) dando lugar al siguiente sistema de euaiones que es la forma más ono ida de representaión del mo delo de aguas p o o profundas ∂h ∂t +∂hu ∂x +∂hv ∂y = 0 (B.23) ∂hu ∂t +∂hu2 ∂x +gh∂h ∂x +∂huv ∂y =gh(S0x−Sfx) (B.24) ∂hv ∂t +∂huv ∂x +∂hv2 ∂y +gh∂h ∂y =gh(S0y−Sfy) (B.25) Este sistema de euaiones en su forma onservativa es deir, esritas las euaiones de la forma más erana p osible a un sistema de leyes de onservaión de masa y antidad de movimiento, es ∂U ∂t +∇E=S⇒∂U ∂t +∇·(F,G) = S (B.26) on U=  h hu hv  ,F=  hu hu2+gh2 2 huv  ,G=  hv huv hv2+gh2 2  , S=  0 gh (S0x−Sfx) gh (S0y−Sfy)   (B.27) 37 APÉNDICE B. MODELO 2D DE FLUJO DE LÁMINA LIBRE CON PROMEDIO EN LA VERTICAL U representa el vetor de variables onservadas ( h profundidad del agua (Fig. B.1), hu y hv audales unitarios a lo largo de las direiones o ordenadas x , y resp etivamente), F y G son los ujos de las variables onservadas a través de los lados de un volumen de ontrol, y ontienen el ujo onvetivo y los gradientes de presión hidrostátia. La parte dereha de la igualdad en el sistema de euaiones, S , ontiene las fuentes y sumideros de la antidad de movimiento a lo largo de las dos direiones o ordenadas, provenientes de las variaiones del fondo del aue y de las p érdidas p or friión que deb en estar relaionadas on el amp o de velo idades. De esta manera, (B.26) representa un sistema hip erb ólio de euaiones difereniales en derivadas pariales aopladas y no lineales. Si esribimos el sistema de euaiones en formulaión no onservativa ∂U ∂t + (A,B)·∇U=S (B.28) las matries Jaobianas de los vetores de ujo son A=∂F ∂U=  0 1 0 c2−u22u0 −uv v u  ,B=∂G ∂U=  0 0 1 −uv v u c2−v20 2v   (B.29) y la matriz Jaobiana del ujo normal a una direión dada p or ˆ n se puede esribir omo A=Aˆnx+Bˆny=  0 ˆnxˆny −u(u·ˆ n) + c2ˆnxu·ˆ n+uˆnxuˆny −v(u·ˆ n) + c2ˆnyvˆnxu·ˆ n+uˆny   (B.30) Los valores propios del Jaobiano Jn son a1=u·ˆ n+c a2=u·ˆ n a3=u·ˆ n−c (B.31) y sus vetores propios e1=  1 u+cˆnx v+cˆny  ,e2=  0 −cˆny cˆnx  ,e3=  1 u−cˆnx v−cˆny   (B.32) B.3 Esquema numério El dominio donde se mueve el ujo, se sub divide, en un onjunto de eldas para su resoluión numéria. En el mo delo presentado hay lib ertad a la hora de elegir el tip o de eldas: hexágonos, uadriláteros, triángulos, et... y además pueden formar parte de una malla estruturada o de una malla no estruturada. La eleión de la malla es un fator imp ortante en la simulaión numéria. Resp eto a la ténia de resoluión de las euaiones, se ha usado un méto do de volúmenes nitos p orque ombina lo mejor de los méto dos de elementos nitos y su exibilidad geométria, on lo mejor de los méto dos en diferenias nitas, su exibilidad en la deniión del ujo disreto (valores disretos de las variables dep endientes y sus ujos aso iados). El primer paso es esribir (B.28) en la forma ∂U ∂t +−→ ∇E=S (B.33) donde E= (F,G)T . 38 B.3. ESQUEMA NUMÉRICO Apliando el teorema de Gauss sobre la elda de álulo Ωi ja en el tiemp o, (B.33) se esrib e omo: ∂ ∂t ZΩi UdΩi+I∂Ωi Endl =I∂Ωi Tndl (B.34) donde Tn es un vetor que expresa el término fuente a través de la sup erie ∂Ω , l denota la variable de integraión de la sup erie alrededor del volumen Ωi y n es el vetor exterior normal unitario. Una vez formulado el problema en volúmenes nitos se ha de elab orar una estrategia adeuada para alular el ujo numério a través de la sup erie. La forma hip erb ólia del sistema de euaiones hae que este problema sea resuelto adeuadamente utilizando un esquema numério p erteneiente a la familia de los méto dos de Go dunov. Este tip o de méto do alula el ujo numério que atualiza el valor de ada elda de álulo i promediando el valor de las diferentes soluiones aproximadas que apareen al denir un problema de Riemann en la sup erie entre el volumen y ada uno de los volúmenes veinos j . Dentro las p osibles op iones que p ermiten generar una soluión aproximada, en este traba jo se utiliza la aproximaión propuesta p or Ro e, que a diferenia de otras onsidera to das las velo idades de propagaión de informaión ontenidas en el Jaobiano de la matriz. Cuando apareen términos fuente formularlos a través de una matriz en la pared, omo en (B.35) , p ermite desarrollar soluiones aproximadas más omplejas adeuadamente. De esta manera, el ujo normal En y su jaobiano obran protagonismo. Se evalúa la matriz jaobiana del ujo normal y se diagonaliza, p ermitiendo que el esquema numério se base en vetores y valores propios. La matriz Jaobiana Jn será la base para llevar a ab o la disretizaión numéria que se presenta en este traba jo. Para omenzar la ténia de volúmenes nitos, el sistema (B.28) se integra en el volumen o malla de eldas, Ω : ∂ ∂t ZΩ UdΩ + ZΩ (−→ ∇E)dΩ = ZΩ SdΩ (B.35) se asume que la terera integral se puede formular de la siguiente manera: ZΩ SdΩ = I∂Ω (Tn)dl (B.36) donde T es una matriz adeuada. Esto lleva a la siguiente formulaión: ∂ ∂t ZΩ UdΩ + I∂Ω Endl =I∂Ω Tndl (B.37) Cuando el dominio se sub divide en eldas Ωi en una malla ja en el tiemp o, Figura B.2, la euaión (B.37) también se puede apliar a ada elda. ∂ ∂t ZΩ UidΩi+ NE X k=1 Zek+1 ek Ejnklk= NE X k=1 Zek+1 ek Tnklk (B.38) En el primer orden las antidades vetoriales son uniformes en ada elda y la euaión (B.37) queda reduida a: (Un+1 i−Un i) ∆tAi+ NE X k=1 (δE−T)knklk= 0 (B.39) donde δE=Ej−Ei , on Ej y Ei el valor de la funión E en la elda veina j y en la elda i resp etivamente y onetadas a través del lado k , nk es el vetor normal haia afuera del b orde 39 APÉNDICE B. MODELO 2D DE FLUJO DE LÁMINA LIBRE CON PROMEDIO EN LA VERTICAL Figura B.2: Representaión onstante de las varaibles en ada elda. de la elda k , lk es la longitud orresp ondiente a diho b orde, NE es el número de b ordes que neesita para denir la elda y Tk es término fuente evaluado en la pared. Debido al aráter no lineal del ujo E , el Jaobiano aproximado, e Jn,k p ermite una linealizaión lo al δ(En) = e Jn,k δU (B.40) dando lugar a un sistema on 3 valores propios reales e λm k y vetores propios e em k , que se onstruyen on las siguientes variables promedio euk=ui√hi+ujphj √hi+phjevk=vi√hi+vjphj √hi+phjeck=rghi+hj 2 (B.41) dando lugar a e λ1 k= (e un +ec)ke λ2 k= (e un)ke λ3 k= (e un −ec)k (B.42) y e e1 k=  1 eu+ecnx ev+ecny  ke e2 k=  1 −ecny −ecnx  ke e3 k=  1 eu−ecnx ev−ecny  k (B.43) Las matries e Pk y e P−1 k , se pueden onstruir a partir de los vetores propios e em k de e Jn,k de forma que la diagonalien e Jn,k = (e PΛe P−1)ke Pk=e e1 ke e2 ke e3 k (B.44) donde e λm k son los valores propios de la matriz diagonal Λ . También, a partir de la matriz Jaobiana aproximada e Jn,ke em k=e λm ke em km= 1,2,3 (B.45) El problema se redue a un problema unidimensional proyetado sobre la direión n en ada b orde de elda. Además, la diferenia del vetor δU a través de ada lado de la elda se proyeta sobre la base de vetores propios δUk= 3 X m=1 (αe e)m k (B.46) 40 B.3. ESQUEMA NUMÉRICO Donde las expresiones que dan los o eientes αk son: α1,3 k=δhk 2±1 2eck (δqk−e ukδhk)nkα2 k=1 2eck (δqk−e ukδhk)nT,k (B.47) on nT,k = (−ny, nx) . La ontribuión de δ(En)k en una elda k se puede esribir omo: δ(En)k= 3 X m=1 (e λαe e)m klk (B.48) Siguiendo la disretizaión uniada, los términos fuente (Tn)k se esrib en de la siguiente manera: (Tn)k=0−ge h(δz +dnSf)nx−ge h(δz +dnSf)nyT k (B.49) donde siguiendo Sf,k =n2e un|e u|dn m´ax(hi, hj)4/3k (B.50) siendo dn es la distania entre los entroides de las eldas que omparten el lado k proyetado sobre la direión n . La p endiente del fondo y el término de friión se pueden desomp oner en la base de los vetores propios on el ob jetivo de asegurar el equilibrio disreto on los términos de ujo (B.48), de tal manera que se asegura en los asos estaionarios on velo idad nula y no nula: (Tn)k=e PkBk= 3 X m=1 (βme em)k (B.51) on Bk=β1β2β3T k . Los o eientes son β1,3 k=∓eck 2(δz +dnSf)kβ2 k= 0 (B.52) El esquema desentrado explíito de primer orden toma la forma Un+1 i=Un i+ ∆t NE X k=1 Ψn i,k (B.53) donde la ontribuión de ada lado de la elda, Ψi,k , sólo reoge la informaión en la direión entrante, Figura (B.3): Ψi,k = 3 X m=1 ((e λ−α−β−)e e)m klk/Ai (B.54) donde e λ−=1 2(e λ−|e λ|) y β−=1 2(β−|β|) . Para nuestro algoritmo y omo nos hemos referido en to do el traba jo, la variable W es Wn i= [Wn i,1, W n i,2, W n i,3] (B.55) Donde Wn i,1=Un i,1, W n i,2=Un i,2/Un i,1, W n i,3=Un i,3/Un i,1 (B.56) 41 APÉNDICE B. MODELO 2D DE FLUJO DE LÁMINA LIBRE CON PROMEDIO EN LA VERTICAL Figura B.3: Seleión de la informaión neesaria en el méto do desentrado. 42 Ap éndie C Gestión del proyeto software La traza temp oral del desarrollo del traba jo ha sido algo variable en el tiemp o. En un iniio, se planteó el desarrollo del Proyeto desde el día 15 de Septiembre de 2010, on intenión de que para abril estuviera terminado. En medio de este tiemp o, tuve que realizar una parada del traba jo desde el 20 de diiembre hasta el 12 de febrero on motivo de los último exámenes de los estudios de Ingeniería Informátia. A partir del día 12 de febrero, volví a inorp orarme al desarrollo del proyeto, on el inonveniente de que esos asi 2 meses de "parón", supusieron una p erdida de adherenia en uanto a la soltura de desarrollo del ó digo se reere. Con esta distribuión temp oral pues, me referiré a dos tramos bien difereniados del PFC: el primero que va desde el 15 de septiembre hasta el 20 de diiembre de 2010 y el que va desde el 12 de febrero hasta el 30 de abril. Si bien es ierto que para el primer p erio do tenía terminado una buena parte del PFC, quedaba to davía lo más ompliado, que onernía a la paralelizaión en máquinas de memoria distribuida. Durante ese primer p erio do, se desarrollaron las tareas de análisis de ó digo, análisis de ompilaión y desarrollo de la estrategia de paralelizaión en máquinas de memoria ompartida además de la inorp oraión de una herramienta de gestión de versiones y un seminario a los miembros de GHC para expliarle el uso del mismo. Durante el segundo, estuvo dediado prátiamente al desarrollo del ó digo adaptado a paralelizaión en máquinas de memoria distribuida y al desarrollo del texto del PFC que ha onsistido en fusionar los sub do umentos que iba haiendo según desarrollaba las distintas tareas y revisarlos en su onjunto. Esto queda reejado en la gura C.1. Figura C.1: Diagrama de Gantt del Proyeto 43 APÉNDICE C. GESTIÓN DEL PROYECTO SOFTWARE Además de las tareas esp eiadas en el diagrama, se han ido haiendo otras paralelas omo el desarrollo de herramientas de prepro esado de las mallas y p ostpro esado, o sripts útiles para el estudio de los rendimientos. Así mismo, no están inluídos los aprendiza jes que han onllevado el uso de to das las herramientas que se han usado durante el traba jo. Durante to do el proyeto han apareido ompliaiones a distintas esalas, de las uales hay dos muy destaables. La primera la ompliaión que apareió en un momento determiniado p or el mal funionamiento de la apliaión paralelizada on MPI. Llevó 2 días depurar el mal funionamiento para determinar que era p or un fallo en una iniializaión que no había apareido hasta ahora p or el ompilador que se utilizaba. El segundo gran obstáulo fue la adaptaión al uso de la infraestrutura en Caesaraugusta. Hasta ahora nuna había traba jado on olas de ejeuión ni on el ompilador XLF ni las optimizaiones que se utilizan. Ni muho menos me onsidero ahora un exp erto en ello, p ero sí he ogido solutura on esta forma de ejeutar apliaiones. La dediaión al proyeto ha sido de una media diaria de 9 horas reales, que teniendo en uenta un fator de uso del 90 % hae un total de 822 horas reales ó 739 horas efetivas. Para la mejor omprensión del méto do y de la meánia de uídos, he asistido (y sigo ha- iéndolo) omo oyente a la asignatura Fundamentos de Fluidos y Pro esos Fluido dinámios de 2 o urso de Ingeniería Industrial on un montante de 4 horas semanales desde el 18 de febrero de 2011. 44 Ap éndie D Casos de análisis En este anexo se desrib e on más profundidad los asos que se han elegido para estudiar el rendimiento de la paralelizaión así omo los motivos de su eleión. Aquí se puede enontrar p or lo tanto, una oleión de resultados referentes al traba jo desarrollado. D.1 Caso C.1 - Dos dep ósitos Este aso llamado así p or su geometría, resuelve la evoluión de un uido que iniialmente está en un dep ósito C1 onetado p or un anal a un segundo dep ósito C2 . La geometría exata del aso es omo se esp eia en la gura D.1. Se ha elegido este aso p orque tiene una evoluión temp oral en el tiemp o en la arga omputaional, ya que iniialmente el 50 % de las eldas están mo jadas, pasando en un tiemp o determinado (20 s.) a estar el 100 % de las eldas mo jadas on lo que se pretende ver la impliaión que tiene este desequilibrado iniial en el tiemp o de ejeuión on la paralelizaión. Cuando se emp ezó a diseñar este aso se p ensó que sería bueno, para mo diar las ondiiones de omuniaión, variar la anhura del anal p or el que se omunian las dos ub etas. Lo que no se esp eraba era que esto iba a haer ambiar las ondiiones del problema dado que, al disminuir la anhura del anal, aumentan las velo idades a las que pasa el agua (ver gura D.2 y esto hae ondiionar el paso de tiemp o, lo que mo dia totalmente el problema y los resultados pasan a no ser omparables. Como se ve en la gura D.2, el aso que mas velo idad lleva es el que tiene una anhura de anal más p equeña, p ero el que más tarda es el que tiene una anhura intermedia (de 30 m.) p or lo que es ese el que elegiremos omo aso para probar los rendimientos. En la misma gura se ve el tiemp o de ejeuión del aso que se utilizó para medir lo que se está expliando. Es imp ortante notar que los tiemp os que ahí apareen no son on las mismas ondiiones on las que se desarrollará el aso. En partiular, la simulaión la haremos de 400 s. on un volado de tiemp o ada 200 pasos de tiemp o. Además se ha utilizado un CFL=0.9 y un o eiente de Manning m= 0,03 . Los resultados de esta simulaión son los utilizados en el análisis del traba jo, así que están ya suientemente expliados. De ellos se dedue, para to dos los asos que la evoluión que se sufre en la arga sí rep erute en los tiemp os de ejeuión. Como p o demos ver en la gura D.3 el 45 APÉNDICE D. CASOS DE ANÁLISIS 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 10000 15000 20000 25000 30000 35000 Execution time (s) Executed time (s) MPI - 1 nodes MPI - 2 nodes MPI - 4 nodes MPI - 8 nodes MPI - 16 nodes (a) Tiemp os de ejeuión frente a tiemp os ejeutados 2 4 6 8 10 12 14 16 2 4 6 8 10 12 14 16 Speed-Up # Threads Speed-Up Theorical Speed-Up (b) Sp eed-up en 36500 s. de simulaión 0 0.2 0.4 0.6 0.8 1 2 4 6 8 10 12 14 16 Performance # Nodes 1-performance Performance () Performane en 36500 s. de simulaión Figura D.8: Resultados de ejeuión del aso C.2 en Terminus Este es un buen ejemplo del rendimiento que nos ofree la ejeuion uando iniialmente sab emos que se van a haer álulos en to das las eldas. Este ejemplo puede servir para saar un rendimiento límite para este problema. Simularemos durante 1000 s. El primer análisis lo vamos a efetuar sobre la simulaión en Trombón . En este luster , el rendimiento es bastante aeptable según vemos en las gráas de la gura D.12. En ellas nos enontramos que el Rendimiento deree de manera notoria a partir de 16 no dos. Hay que tener en uenta que aquí hemos heho una simulión on 32 no dos. Estos no dos son virtuales en el sentido de que ada pro esador de Tromb ón disp one de 4 ores y 8 threads, en partiular, hemos heho traba jar a 4 de los pro esadores on 5 threads para ver omo iba el rendimiento y omo vemos deree rápidamente on ejeuiones de este estilo. Sigue ganando algo, p ero el reimiento es muho menor. Esto nos reuerda a los resultados que presentamos en seiones anteriores para la implementaión Op enMP, en los uales nos enontrábamos que a partir de 4 threads en esta máquina, el reimiento del Sp eed-up era menor que el pro duido hasta 4 threads. En la ejeuión en el luster terminus los resultados son sup eriores, igual que en el aso anterior, a los de Trombón . En este aso el rendimiento que saa la apliaión es sup erior al 90 % . 52 D.3. CASO C.3 - CROSS 0 5000 10000 15000 20000 25000 30000 35000 40000 5000 10000 15000 20000 25000 30000 35000 Execution time (s) Executed time (s) MPI - 1 nodes MPI - 2 nodes MPI - 4 nodes MPI - 8 nodes MPI - 16 nodes MPI - 24 nodes (a) Tiemp os de ejeuión frente a tiemp os ejeutados 0 5 10 15 20 25 30 5 10 15 20 Speed-Up # Threads Speed-Up Theorical Speed-Up (b) Sp eed-up en 36500 s. de simulaión 0 0.2 0.4 0.6 0.8 1 5 10 15 20 Performance # Nodes 1-performance Performance () Performane en 36500 s. de simulaión Figura D.9: Resultados de ejeuión del aso C.2 en Caesaraugusta Figura D.10: Geometría del problema C.3 53 APÉNDICE D. CASOS DE ANÁLISIS Figura D.11: 64-partiion de la malla del problema C.3. 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0 100 200 300 400 500 600 700 800 900 1000 Execution time (s) Executed time (s) MPI - 1 nodes MPI - 2 nodes MPI - 4 nodes MPI - 8 nodes MPI - 16 nodes MPI - 32 nodes (a) Tiemp os de ejeuión frente a tiemp os ejeutados 0 5 10 15 20 25 30 35 5 10 15 20 25 30 Speed-Up # Threads Speed-Up Theorical Speed-Up (b) Sp eed-up en 1000 s. de simulaión 0 0.2 0.4 0.6 0.8 1 5 10 15 20 25 30 Performance # Nodes 1-performance Performance () Performane en 1000 s. de simulaión Figura D.12: Resultados de ejeuión del aso C.3 en Trombón 54 D.3. CASO C.3 - CROSS Como vemos en la gura, el Sp eed-Up es muy erano al teório sobrepasándolo, igual que en el aso anterior, en la ejeuión en 8 ores. 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 0 100 200 300 400 500 600 700 800 900 1000 Execution time (s) Executed time (s) MPI - 1 nodes MPI - 2 nodes MPI - 4 nodes MPI - 8 nodes MPI - 16 nodes (a) Tiemp os de ejeuión frente a tiemp os ejeutados 0 2 4 6 8 10 12 14 16 2 4 6 8 10 12 14 16 Speed-Up # Threads Speed-Up Theorical Speed-Up (b) Sp eed-up en 1000 s. de simulaión 0 0.2 0.4 0.6 0.8 1 2 4 6 8 10 12 14 16 Performance # Nodes 1-performance Performance () Performane en 1000 s. de simulaión Figura D.13: Resultados de ejeuión del aso C.3 en Terminus Como onlusión general y vistos los tres asos en Terminus on la onguraión en la que atualmente está dispuesto, la ejeuión on 8 ores saa los mejores rendimientos en general, lo que nos hae p ensar que la onguraión de hips-on-b oard es muy adeuada para este tip o de ejeuiones. Si bien está onguraión es más ara que onetar los no dos en red, para simulaiones en las que queramos un buen rendimiento sin ser tiemp os de ejeuión exesivamente largos, esta onguraión funiona realmente bien. El último luster en el que hemos realizado las pruebas de rendimiento es en Caesaraugusta . En la gura D.14 p o demos omprobar lo onstante que es el rendimiento. En este aso se hae muy p o o aeso a memoria ya que éste sólo tiene relevania en la preparaión del aso (fator t0 ) que es donde se haen álulos de preparaión de dominio. A diferenia de otros asos el fator ahe no inuye de manera drástia y los fatores que van a determinar el tiemp o de álulo van a ser el tiemp o de álulo y el tiemp o de omuniaión. El segundo fator es onstante en to dos los asos, ya que en el aso en el que la partiión sea 2, la frontera que más paredes sop orta on muha diferenia es la entral, igual que en el resto de los asos, luego el fator que variará según 55 APÉNDICE D. CASOS DE ANÁLISIS ampliemos el dominio, será uniamente el tiemp o de álulo. el heho de que la infraestrutura sea tan homogenea, nos lleva a expliar ese rendimiento onstante. 0 5000 10000 15000 20000 25000 30000 35000 0 100 200 300 400 500 600 700 800 900 1000 Execution time (s) Executed time (s) MPI - 1 nodes MPI - 2 nodes MPI - 4 nodes MPI - 8 nodes MPI - 16 nodes MPI - 32 nodes (a) Tiemp os de ejeuión frente a tiemp os ejeutados 0 5 10 15 20 25 30 35 5 10 15 20 25 30 Speed-Up # Nodos Speed-Up Theorical Speed-Up (b) Sp eed-up en 1000 s. de simulaión 0 0.2 0.4 0.6 0.8 1 5 10 15 20 25 30 Rendimiento # Nodos 1-performance Performance () Performane en 1000 s. de simulaión Figura D.14: Resultados de ejeuión del aso C.3 en Caesaraugusta Como onlusión de este aso, se ve que las velo idades de pro esamiento y de omuniaión haen variar muho los rendimientos de una máquina a otra. Los resultados obtenidos son muy buenos en to dos los asos on los maties anteriormente omentados. 56 Ap éndie E Regresion de la euaion tx en Caesaraugusta En el apítulo anterior hemos intro duido la fórmula del tiemp o de ejeuión de la forma texec =t0+ (texec1∗ncells) + ((tcomm1∗Nf,s)∗3) (E.1) y omo hemos expliado en éste, p o demos aproximarla a texec = 0 t0+ (texec1∗ncells) + ((tcomm1∗Nf,s)∗3) (E.2) Es un ejeriio interesante ver, lo bien que se a justa esta funión a la realidad, para p o der así predeir a priori el tiemp o de ejeuión aproximado que nos tomará una simulaión on nuestro mo delo de paralelizaión. (a) alado iniial h9 del aso de estudio (b) Distribuión de dominios do, d1 Figura E.1: Diseño del exp erimento de regresión Para haer éste análisis, lo que haremos será tomar el aso C.3 mo diado on una h0= 5m y vamos a dejar que evoluione durante 17s. , tiemp o que requiere llegar al segundo dominio. Esta mo diaión además implia que iniialmente hay un 12 % de eldas mo jadas en el dominio d0 y ninguna en el dominio d1 . Por último saaremos tiemp os de ejeuión en ada paso de 57 APÉNDICE E. REGRESION DE LA ECUACION TX EN CAESARAUGUSTA tiemp o, haiendo una relaión celdasmojadas −tx y apliaremos una regresión lineal de la funión. 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 20000 30000 40000 50000 60000 70000 Tiempo de ejecucion Celdas Mojadas Experimental times Regression Figura E.2: Diseño del exp erimento de regresión Los resultados se a justan muy bien a esta funión omo vemos en la gura E.2 y omo se observa, existen valores que destaan en tiemp os no determinados. Estos valores se orresp onden al jitter anteriormente nombrado que igualmente, no altera demasiado el resultado. Los resultados del a juste a una funion f(x) = ax +b son a= 4,11272e−06, b = 0,00242021, RMS = 0,0080191 (E.3) Ajustamos a esta funion dado que la funion E tiene el elemento ((tcomm1∗Nf,s)∗3) onstante en el tiemp o (similar al término b ) y en nuestro aso el término a∗x es el término (texec1∗ncells) . Lo que si es urioso es el desa juste del origen de ordenadas. Esto puede ser p or que on p o as eldas, los tiemp os de ejeuion son muy p equeños y p or lo tanto la mediion de los mismos es ms suseptible de error. Caraterizando la euaión a nuestros términos y para el aso de estudio y teniendo en uenta que b= 2 ∗n0,1∗tcomm ∗3 siendo n0,1 número de paredes en la interseión (0,1) que en nuestro aso es n0,1= 82 , se dedue que el tiemp o de omuniaión de un elemento es, tcomm =0,00242021 2∗3∗82 = 0,000004919s. (E.4) Con lo que la euaión queda tx= 4,11272 ∗10−6∗ncell + (4,919 ∗10−6∗3∗2∗n0,1) (E.5) En general, para los asos en los que tenemos más seiones y además estas seiones no están totalmente equilibradas, el tiemp o de ejeuión de una iteraión on esta fórmula se reesrib e omo, tx= 4,11272 ∗10−6∗(MAX(ncell) + (4,919 ∗10−6∗3∗2∗V∗MAX(ni,j))) (E.6) Siendo MAX(ncell) el máximo número de eldas impliadas y MAX(ni,j) la seión que más paredes omparte on sus veinas. Nótese que áparee un término V en la euaión. Este término es el número de veinos de la seión, que para el aso anterior era V= 1 , p ero que en general, 58 esto sólo se umple en la primera seión y en la última, el resto de sub dominios tienen 2 veinos. Sin p o der extenderlo para to dos los asos, salvo para aquél en el que to do el tiemp o to das las eldas tengan alado h > 0 , p o demos deduir el término general omo tXtotal =I∗(4,11272e−06 ∗(MAX(ncell) + (4,919 ∗10−6∗3∗2∗V∗MAX(ni,j)))) (E.7) donde I es el número total de iteraiones neesarias para alanzar el tiemp o de simulaión. 59 60 Ap éndie F Equip os de simulaión F.1 Caraterístias de Caesaraugusta En este equip o, las simulaiones se han heho sin aprovehar to das las araterístias espaiales que la infraestrutura nos p ermitía, obligándole a utilizar un pro esador, de los dos disp onibles, p or no do. Por tanto, en esta onguraión uando nos reramos a no do, nos referimos a no do físio, y hemos de tener en uenta que ada no do está onetado p or red. 1. Pro essor: 512 pro essors PowerPC 970FX 2.2 GHz 2. Memory: 1TB RAM memory 3. Network: Interonnetion networks Myrinet 4. System: Linux 5. Total No des: 256 No des F.2 Caraterístias de Terminus Dos pro esadores p or blade. Nuestro luster está formado p or dos Blades onetados p or Gigabit, y la omuniaión intra-blade es en plaa a través de una plaa base dual. En este equip o se utilizarán primero los ores del pro esador omo no dos de álulo (4), pasando a los ores totales p or blade (8) esalando p or último a los ores totales en nuestro luster (16). 1. Pro essor: 4 778I Xeon Quad ore 2. Memory: 4 Mbytes/pro essor 3. Network: Interonnetion networks Gigabit 4. System: Linux 5. Total No des: 2 No des Los parámetros de ompilaión ongurados p or los ténios del luster son los siguientes: 61 APÉNDICE I. MANUAL DE SUBVERSION desarrolla gran parte del ó digo fuente y de forma esp orádia apareen mo diaiones de otros, mediante las uales se prop onen funionalidades nuevas readas de forma paralela. Este tip o de desarrollos deb en haerse ba jo dos pautas: • Do umentar ualquier ambio pro duido en el ó digo prinipal y en los sub ó digos en desarrollo • Mantener un orden ba jo el amparo de un árb ol de proyeto. La primera ha de ser estableida p or el autor prinipal del ó digo debiendo ser seguido p or to dos los desarrolladores mientras que para la segunda será para la que es neesaria utilizar herramientas de ontrol de versiones. I.2.1 Estrutura de proyetos software en ámbitos ientíos Para denir la estrutura de este tip o de proyetos, antes deb emos indiar qué elementos omp onen el proyeto y de que manera. Para ello p o demos basarnos en MÉTRICA, una meto dología promovida p or el Ministerio de Administraiones Públias del Gobierno de España para la elab oraión y sistematizaión de atividades propias del ilo de vida de los proyetos software, esp eialmente para el ámbito de las administraiones públias, p ero válidas y reomendables para ualquier otro. Según la meto dología MÉTRICA v.3, los elementos de onguraión inluyen: • Ejeutables • Có digo Fuente • Mo delos de Datos • Pruebas • ... To das ellas almaenando: • Nombre • Versión • Estado • Lo alizaión To do esto, deb e estar onjuntado en el proyeto de una manera organizada según la estabilidad de los heros ontenidos, pudiendo estableer esta lasiaión: • Prinipal (SVN Trunk): Rama de desarrollo prinipal • Congelaión (SVN Tags): Rep ositorio on las versiones prinipales erradas • Evlouión (SVN Branhes): Rama de evoluiones del desarrollo prinipal 68 I.3. USO DE SVN I.2.2 Estrutura de proyetos software en SVN A partir de la deniión de la estrutura genéria mínima que deb ería tener to do proyeto software, la traduión a SVN, on mo delo de arp etas, sigue omo en la siguiente gura: Para que este esquema se mantenga onsistente, se reomiendan las siguientes prátias: • Atualizar al entorno lo al las últimas mo diaiones que se hayan p o dido pro duir en el ó digo. Es imp ortante tener en uenta que hemos de tener el proyeto ya desargado en lo al. Este omando es update • Subir al servidor SVN los ambios del entorno lo al. SVN sólo p ermitirá estas mo diaiones si no existen onitos on el ó digo ya existente en el rep ositorio, es deir, no p ermitira la mo diaión de un ó digo si otro miembro del equip o ha mo diado el mismo elemento de forma paralela desde la última sinronizaión de ó digo. El omando es Commit. Dado que este último requisito, puede plantear problemas, se prop one el siguiente proto olo: • Antes de omenzar la resoluión de una tarea, se deb erá asegurar la sinronizaión del ó digo via Update . • Una vez resuelta la tarea, se deb erá haer otro Update para traer al entorno lo al los ambios que hayan p o dido ser realizados en paralelo, teniendo en uenta que SVN sabrá integrar los ambios en la mayoría de los asos, siendo en otros neesaria la integraión manual (p.e. un ambio en el mismo bule). Estos asos deb erían no existir en tanto que dos p ersonas no deb erían estar to ando la misma seión de ó digo. • Finalmente haemos ommit para haer públio el ó digo desarrollado. El alanze del ommit deb e limitarse al ó digo relevante a la resoluión de la tarea, y no mezlar desarrollos de distintas tareas en un mismo Commit. IMPORTANTE: Para ompletar el sentido de este tip o de gestiones, ab e destaar que SVN disp one de herramientas para umplir on los requisitos antes itados mediante Logs. Esto es que ada vez que haemos ommit , se deb e de inluir un p equeño omentario on los ambios aonteidos. I.3 Uso de SVN A través de SVN p o demos p oner en prátia las pautas anteriormente itadas para la gestión de proyetos. Por esta razón se va a disernir de dos usos de SVN en gestores y desarrolladores. Esto es que el Gestor (p ersona únia) ha de ser el resp onsable de errar versiones y rear nuevas ramiaiones del proyeto, siendo igualmente interesante que to do el mundo onoza el proto- olo p or si pudiese ser interesante prop oner un ambio al proyeto. I.3.1 Instalaión del liente SVN La eleión del liente SVN es libre en tanto que existen multiud de ellos, aunque aquí se reomendará RapidSVN p or la existenia de éste tanto para distribuiones Linux, omo para Windows o MaOS. Si bien es ierto que las expliaiones que aquí se adjuntan están p ensadas para el entorno gráo, es p osible para los usuarios de Linux igual para aquellos que están aostumbrados a traba jar on la onsola, el manejo de SVN mediante omandos en onsola. 69 APÉNDICE I. MANUAL DE SUBVERSION I.3.1.1 Instalaión en entornos Windows 1. Ir a www.rapìdsvn.org/download/release/ 2. Elegir la última versión disp onible 3. Desargar RapidSVN-x.x.xx.xxxx.exe 4. Seguir instruiones de instalaión I.3.1.2 Instalaión en Linux (Debian) 1. Aeder omo Single-User 2. Ejeutar el omando apt-get instal l rapidsvn I.3.2 SVN para gestores La seión que sigue está reomendada sea heha p or el administrador del equip o en el que vaya a instalarse el servidor. Nótese que la expliaión está heha para distribuiones Debian p or el aso que nos o upa. I.3.2.1 Instalaión del servidor SVN Los pasos que se presentan son los básios para la onguraión de SVN. Es imp ortante ono er el heho de que to da la instalaión se hará en Single-User. Cab e destaar que está inluido en los paquetes de Debian. 1. Aeder a Single User: su 2. Ejeutar el siguiente omando: #apt-get instal l subversion subversion-tools 3. Añadimos el grup o para el demonio aso iado al serviio. #groupadd -g 99 svnd 4. Y el usuario del grup o: #useradd svnd -d /srv/svn -g svnd -s /bin/false -m -k /dev/nul l - Úsuario svnServe'-u 99 5. Creamos la arp eta donde alo jaremos los rep ositorios, p or ejemplo /svn on mkdir /svn 6. Creamos un sript, alo jado en /et/init.d/ llamado svnserve, en el que se inluya lo siguiente. (Ver ó digo) 7. Añadimos al nal los enlaes simb ólios on #update-r.d svnserve defaults 1 \# ! / b i n / s h 2 \# 3 \# s t a r t / s t o p s v n ( S u b v e r s i o n ) s e r v e r . 4 set -e 5 N A M E = s v n s e r v e 6 DESC =\ textquotedbl {} Subversion server \ textquotedbl{} 7 D A E M O N = / u s r / b i n / \ $ N A M E 8 P A R A M S = \ t e x t q u o t e d b l { } - d - T - r / s v n \ t e x t q u o t e d b l { } 9 D A E M O N U S E R = s v n d 70 I.3. USO DE SVN 10 t e s t - x \ $ D A E M O N | | e x i t 0 11 . / l i b / l s b / i n i t - f u n  t i o n s 12 s t a r t \ _ i t \ _ u p ( ) 13 \ { 14 l o g \ _ d a e m o n \ _ m s g \ t e x t q u o t e d b l { } S t a r t i n g \ $ D E S C \ t e x t q u o t e d b l { } \ textquotedbl {}\ $NAME \ textquotedbl{} 15 s t a r t - s t o p - d a e m o n - - s t a r t - - q u i e t - -  h u i d \ $ D A E M O N U S E R : \ $ D A E M O N U S E R 16 - - e x e  \ $ D A E M O N - - \ $ P A R A M S 17 l o g \ _ e n d \ _ m s g \ $ ? 18 \ } 19 s h u t \ _ i t \ _ d o w n ( ) 20 \ { 21 l o g \ _ d a e m o n \ _ m s g \ t e x t q u o t e d b l { } S t o p p i n g \ $ D E S C \ t e x t q u o t e d b l { } \ textquotedbl {}\ $NAME \ textquotedbl{} 22 s t a r t - s t o p - d a e m o n - - s t o p - - r e t r y 6 0 - - q u i e t - - o k n o d o - - e x e  \ $ D A E M O N 23 l o g \ _ e n d \ _ m s g \ $ ? 24 \ } 25 ase \ textquotedbl {}\ $1\ textquotedbl {} in 26 s t a r t ) 27 s t a r t \ _ i t \ _ u p 28 ; ; 29 s t o p ) 30 s h u t \ _ i t \ _ d o w n 31 ; ; 32 r e s t a r t ) 33 s h u t \ _ i t \ _ d o w n 34 s t a r t \ _ i t \ _ u p 35 ; ; 36 { * } ) 37 e  h o \ t e x t q u o t e d b l { } U s a g e : / e t  / i n i t . d / \ $ N A M E \ { s t a r t | s t o p | r e s t a r t \ } \ textquotedbl{} 38 > \ & 2 39 e x i t 1 40 ; ; 41 e s a  42 e x i t 0 % I.3.2.2 Creaión del rep ositorio La reaión del rep ositorio se realizará mediante el omando svnadmin  reate /svn/nombre- Proyeto siendo nombreProyeto el nombre del rep ositorio. Esta op eraión se realizará sólo en Single-User. Para realizar la estrutura de arp etas propuesta anteriormente, p o demos realizar la siguiente op eraión: 1. Creamos en lo al la arp eta nombreProyeto 2. Dentro de ella reamos trunk, branhes y tags 3. Utilizamos el siguiente omando: 1 s v n i m p o r t / n o m b r e P r o y e  t o s v n : / / s h r e k .  p s . u n i z a r . e s / n o m b r e P r o y e  t o - m ' C r e a  i o n d e e s t r u  t u r a d e l p r o y e  t o ' 71 APÉNDICE I. MANUAL DE SUBVERSION I.3.2.3 Creaión y gestión de Usuarios Es imp ortante sab er que es p osible estableer p ermisos para los usuarios de los rep ositorios, luego lo que se reomienda es estableer p ermisos SÓLO de esritura para los usuarios autorizados. Esto es: 1. Ir a svn/nombreProyeto/onf 2. Editar el hero svnserve.onf añadiendo las lineas auth-aess=write anon-aess=none password-db=passwd 3. En el hero passwd ontenido en la misma arp eta, añadir la relaión de usuarios ontraseñas on el siguiente formato usuario1=on1 usuario2=on2 usuarioN=onN 4. NOTA IMPORTANTE: en el hero svnserve.onf es imp ortante que exista una linea (generalmente omentada p or defeto, si es así desomentarla) en la que p onga lo siguiente anon-aess=none ya que de no ser así ualquier p ersona p o dría ver el ontenido de lo que existe en el rep ositorio. I.3.3 SVN para desarrolladores I.3.3.1 Ajustes preliminares Para p o der ompletar las funionalidades de VisualSVN vamos a realizar estos a justes: 1. Para integrar la funionalidad del editor de textos, vamos a ir al menú Preferenes, y ahí inluiremos el editor que utlizamos (p or ejemplo, para gedit utilizar /usr/bin/gedit ) 2. Para la funionalidad Di y Merge p o demos utilizar Meld, inludo en los paquetes Debian. Lo instalamos mediante apt-get instal l meld I.3.3.2 Cierre de versiones En iertos momentos del proyeto, puede ser interesante el estabilizar un ierre de una versión y en onseuenia, puede ser interesante regresar a una versión anterior en el aso, p or ejemplo, de que se desubra un bug tras una entrega, donde se deb ería retomar el ó digo desde la versión previa a la entrega, en lugar de ontinuar en la versión en desarrollo. En lengua je SVN, el ierre de una versión se denomina tag de la versión desarrol lada. SVN maneja opias para este tip o de ramiaión en el que sólo guarda una referenia a la rama y versión que se desea opiar, siendo el oste de ésta ba jo en tiemp o y en espaio, además de onstante. La reomendaión es realizar estos ierres on ada hito del proyeto. Lo interesante de estos tag es tener la erteza de la estabilidad de la versión, lo que implia que NUNCA se deb e mo diar un tag tras su reaión. SVN no p one restriiones sobre esta op eraión luego es resp onsabilidad de los desarrolladores el seguir esta buena prátia. Una vez reado el tag, el desarrollo deb e ontinuar bien en trunk o en branh. No deb emos olvidar que el tag no es más que una anotaión o referenia a un punto del desarrollo en el nivel físio, aunque sí a nivel lógio es el ierre de la versión. 72 I.3. USO DE SVN El omando para realizar esto, es svn opy y se realizará haiendo una opia arrastrando la arp eta al destino deseado, e indiándole opy para la op eraión. I.3.3.3 Ramiaión del ó digo El uso de los branhes es útil para rear una rama indep endiente de desarrollo para traba jar en alguna funionalidad nueva de un proyeto que to davía no se quiere inorp orar a la linea prinipal. Al rear una nueva ramiaión en branhes el programador ambiará su working-opy a este nuevo branh y traba jará sobre él. Las op eraiones de ommit serán sobre su branh, sin afetar al desarrollo prinipal. Cuando estos ambios estén listos se realizará la op eraión merge. Se ha de tener en uenta que la ramiaión del proyeto sup one ompliar la estrutura del mismo, lo que implia que sólo se deb en abrir las neesarias, siendo útil la aprobaión de ésta p or el diretor o resp onsable del proyeto. I.3.3.4 Fusión de ambios La op eraión Merge antes itada hae referenia a este punto, en el ual ab e destaar la existenia del omando Path on diferenias en uanto a lo que fusiona; El primero fusiona ambios en diretorios inlusive, mientras que el segundo sólo lo hae de heros. Es imp ortante el uso de estos omando dado que la apliaión manual de la mo diaión puede ser suseptible del error humano al trasribir los ambios realizados. I.3.3.5 Mo diaión de ó digo fuente La mo diaión del ó digo fuente reqiere de ser auto en los pasos a seguir. En primer lugar efetuamos doble lik sobre el hero a mo diar en el rep ositorio lo al que hemos desargado en el b o okmark. Una vez nalizada la mo diaión volvemos a la ventana de RapidSVN. Veremos que está marado en ro jo on el status modied siendo neesario subir los ambios al servidor. Esto es realizar Update presionando sobre el b otón dereho del ratón para despues ejeutar Commit on el b otón dereho tambien. Deb emos inluir la mo diaión que hemos realizado para ompletar la utilidad de la herramienta. Esta op eraión es imp ortante realizarla ada vez que aabamos la funionalidad que estamos desarrollando omo máximo, y omo mínimo ada día o p erio do de elab oraión de ó digo. I.3.3.6 Control de Log's Seleionando un hero, p o demos ir, mediante el menú ontextual Query>Log para ver los ambios que hemos ido realizando revisión a revisión, visualizando además el omentario que habíamos inluido (de ahí la imp ortania de realizarlos) e inluso visualizar el hero en ese estado on view. I.3.3.7 Di La herramienta di es el ap oyo fundamental para el ontrol de ambios. En el menú ontextual del Log, p o demos presionar ese omando para visualizar las diferenias entre el arhivo que tenemos atualmente en nuestro equip o. 73 74 Ap éndie J Ejemplo de malla partiionada Figura J.1: Malla de álulo original 75 APÉNDICE J. EJEMPLO DE MALLA PARTICIONADA Figura J.2: Malla de álulo apliando 2-partiión (Nótese la desomp osiión en la indexaión de las eldas) 76