Skip to content Skip to navigation Skip to collection information
Inside Collection (Textbook): Cómputo de Alto Rendimiento
Based on: Language Support for Performance - Data-Parallel Problem: Heat Flow by Charles Severance, Kevin Dowd
Un problema clásico que explota el procesamiento paralelo escalable, es la simulación de un flujo calórico. La física tras este fenómeno descansa en una ecuación diferencial en derivadas parciales.
Comenzaremos con una placa de metal unidimensional (también conocida como una barra), y avanzaremos hacia una placa bidimensional en los ejemplos posteriores. Al arranque, la barra se encuentra a cero grados Celsius. Luego metemos uno de sus extremos en vapor a 100 grados, y el otro extremo en hielo a cero grados. Queremos simular cómo es el flujo calórico de un extremo al otro, y observar las temperaturas resultantes a lo largo de los distintos puntos de la barra de metal, hasta que dichas temperaturas se estabilicen.
Para lograrlo, dividiremos la barra en 10 segmentos, y seguiremos la pista a la temperatura de cada segmento a lo largo del tiempo. Podemos ver intuitivamente que, en cada ciclo de la simulación, la temperatura que adquirirá cada porción de la barra será el promedio de las temperaturas a su alrededor. Dado que hay temperaturas fijas en ciertos puntos de la barra, el resto eventualmente convergerán a un estado estable tras un número suficiente de ciclos. La Figure 1 muestra el estado al inicio de la simulación.
| Flujo Calórico en una Barra |
|---|
 |
Una implementación simplista de tal simulación es como sigue:
PROGRAM HEATROD
PARAMETER(MAXTIME=200)
INTEGER TICKS,I,MAXTIME
REAL*4 ROD(10)
ROD(1) = 100.0
DO I=2,9
ROD(I) = 0.0
ENDDO
ROD(10) = 0.0
DO TICKS=1,MAXTIME
IF ( MOD(TICKS,20) .EQ. 1 ) PRINT 100,TICKS,(ROD(I),I=1,10)
DO I=2,9
ROD(I) = (ROD(I-1) + ROD(I+1) ) / 2
ENDDO
ENDDO
100 FORMAT(I4,10F7.2)
END
La salida de este programa será la siguiente:
% f77 heatrod.f
heatrod.f:
MAIN heatrod:
% a.out
1 100.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
21 100.00 87.04 74.52 62.54 51.15 40.30 29.91 19.83 9.92 0.00
41 100.00 88.74 77.51 66.32 55.19 44.10 33.05 22.02 11.01 0.00
61 100.00 88.88 77.76 66.64 55.53 44.42 33.31 22.21 11.10 0.00
81 100.00 88.89 77.78 66.66 55.55 44.44 33.33 22.22 11.11 0.00
101 100.00 88.89 77.78 66.67 55.56 44.44 33.33 22.22 11.11 0.00
121 100.00 88.89 77.78 66.67 55.56 44.44 33.33 22.22 11.11 0.00
141 100.00 88.89 77.78 66.67 55.56 44.44 33.33 22.22 11.11 0.00
161 100.00 88.89 77.78 66.67 55.56 44.44 33.33 22.22 11.11 0.00
181 100.00 88.89 77.78 66.67 55.56 44.44 33.33 22.22 11.11 0.00
%
Claramente, para el ciclo de ejecución 101, la simulación converge con una precisión de dos decimales, conforme los números han dejado de cambiar. Debe tratarse de una aproximación a un estado de temperaturas estables al centro de cada segmento de la barra.
Ahora bien, para este momento los lectores más astutos estarán diciéndose: "Ey, por si no te has dado cuenta, este ciclo tiene una dependencia de flujo." Puede usted alegar que ello impedirá paralelizarlo siquiera un poquito. ¡Es tan grave que ni siquiera puede usted deshacer el bucle para lograr algo de paralelismo a nivel de instrucciones!
Una persona familiarizada con la teoría del flujo calórico también pudiera señalar que el ciclo anterior no implementa exactamente el modelo del flujo calórico. El problema es que los valores en el lado derecho de la asignación en el ciclo ROD, se supone que vienen del ciclo de ejecución anterior, y que el valor en el lado izquierdo es el que tendrá en el siguiente ciclo. Pero debido a la manera en que está escrito, el valor ROD(I-1) viene desde el siguiente ciclo, como se muestra en la Paragraph 10.
Este problema puede solucionarse usando una técnica conocida como rojo-negro, en la cual alternamos entre dos arreglos. La Figure 3 muestra cómo opera (usando dos arreglos para eliminar una dependencia) la versión rojo-negro del cálculo. ¡Mata dos pájaros de una sola pedrada! Ahora las matemáticas son precisamente correctas, y no hay recurrencia. Suena como una situación realmente de ganar-ganar.
| Calculando el nuevo valor de una celda. |
|---|
 |
| Usando dos arreglos para eliminar una dependencia |
|---|
 |
La única desventaja de este enfoque, es que toma el doble de almacenamiento en memoria, y el doble de ancho de banda de memoria. 1 El código código modificado es como sigue:
PROGRAM HEATRED
PARAMETER(MAXTIME=200)
INTEGER TICKS,I,MAXTIME
REAL*4 RED(10),BLACK(10)
RED(1) = 100.0
BLACK(1) = 100.0
DO I=2,9
RED(I) = 0.0
ENDDO
RED(10) = 0.0
BLACK(10) = 0.0
DO TICKS=1,MAXTIME,2
IF ( MOD(TICKS,20) .EQ. 1 ) PRINT 100,TICKS,(RED(I),I=1,10)
DO I=2,9
BLACK(I) = (RED(I-1) + RED(I+1) ) / 2
ENDDO
DO I=2,9
RED(I) = (BLACK(I-1) + BLACK(I+1) ) / 2
ENDDO
ENDDO
100 FORMAT(I4,10F7.2)
END
La salida del programa modificado es como sigue:
% f77 heatred.f
heatred.f:
MAIN heatred:
% a.out
1 100.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
21 100.00 82.38 66.34 50.30 38.18 26.06 18.20 10.35 5.18 0.00
41 100.00 87.04 74.52 61.99 50.56 39.13 28.94 18.75 9.38 0.00
61 100.00 88.36 76.84 65.32 54.12 42.91 32.07 21.22 10.61 0.00
81 100.00 88.74 77.51 66.28 55.14 44.00 32.97 21.93 10.97 0.00
101 100.00 88.84 77.70 66.55 55.44 44.32 33.23 22.14 11.07 0.00
121 100.00 88.88 77.76 66.63 55.52 44.41 33.30 22.20 11.10 0.00
141 100.00 88.89 77.77 66.66 55.55 44.43 33.32 22.22 11.11 0.00
161 100.00 88.89 77.78 66.66 55.55 44.44 33.33 22.22 11.11 0.00
181 100.00 88.89 77.78 66.67 55.55 44.44 33.33 22.22 11.11 0.00
%
Resulta interesante notar que el programa modificado requiere de más tiempo de convergencia que la primera versión. Converge hasta la iteración 181, en vez de en la 101. Si observa usted la primera versión, notará que debido a la recurrencia, el calor terminaba fluyendo más rápido de izquierda a derecha, dado que el elemento izquierdo de cada promedio era el valor del siguiente ciclo de ejecución. Puede parecer ágil, pero está mal. 2 Generalmente, en este problema, cualquier enfoque converge a los mismos valores eventuales dentro de los límites de la representación de punto flotante.
El problema de flujo calórico es extremadamente simple, y en su forma rojo-negro, resulta inherentemente muy paralelizable con interacciones muy simples de datos. Resulta un buen modelo para una amplia variedad de problemas en los cuales discretizamos espacios bidimensionales y tridimensionales, y realizamos alguna simulación sencilla en tales espacios.
Este problema usualmente puede escalarse creando una malla más fina. A menudo, el beneficio de usar procesadores escalables viene de permitir crear dichas mallas más finas, y no de obtener soluciones en tiempos más cortos. Por ejemplo, puede que usted sea capaz de realizar una simulación climática a nivel mundial, usando una malla con una separación de 200 millas, con un solo procesador en cuatro horas. Usando 100 procesadores, puede que sea capaz de ejecutar la misma simulación usando un tamaño de malla de 20 millas, también en cuatro horas, pero con resultados mucho más precisos. O, utilizando 400 procesadores, puede hacer una simulación de malla aún más fina en una hora.
More about this module: Metadata | Downloads | Version History
This work is licensed by José Enrique Alvarez Estrada under a Creative Commons Attribution License (CC-BY 3.0), and is an Open Educational Resource.
Last edited by José Enrique Alvarez Estrada on May 13, 2011 7:54 am -0500.