Bucles de plantillas iterativos

Los bucles iterativos de plantilla (ISL) o cálculos de plantilla son una clase de solución de procesamiento numérico de datos ^{[ 1 ]} que actualizan los elementos de una matriz según un patrón fijo, llamado plantilla. ^{[ 2 ]} Se encuentran con mayor frecuencia en simulaciones por computadora , por ejemplo, para dinámica de fluidos computacional en el contexto de aplicaciones científicas y de ingeniería. Otros ejemplos notables incluyen la resolución de ecuaciones diferenciales parciales , ^{[ 1 ]} el núcleo de Jacobi , el método de Gauss-Seidel , ^{[ 2 ]} el procesamiento de imágenes ^{[ 1 ]} y los autómatas celulares . ^{[ 3 ]} La estructura regular de las matrices distingue a las técnicas de plantilla de otros métodos de modelado como el método de elementos finitos . La mayoría de los códigos de diferencias finitas que operan en cuadrículas regulares pueden formularse como ISL.

Los ISL realizan una secuencia de barridos (llamados pasos de tiempo) a través de una matriz dada. ^{[ 2 ]} Generalmente, se trata de una cuadrícula regular bidimensional o tridimensional. ^{[ 3 ]} Los elementos de las matrices suelen denominarse celdas. En cada paso de tiempo, todos los elementos de la matriz se actualizan. ^{[ 2 ]} Utilizando elementos vecinos de la matriz en un patrón fijo (la plantilla), se calcula el nuevo valor de cada celda. En la mayoría de los casos, los valores límite permanecen sin cambios, pero en algunos casos (por ejemplo, códigos LBM ) también es necesario ajustarlos durante el cálculo. Dado que la plantilla es la misma para cada elemento, el patrón de accesos a los datos se repite. ^{[ 4 ]}

De manera más formal, podemos definir los ISL como una 5-tupla.${\displaystyle (I,S,S_{0},s,T)}$con el siguiente significado: ^{[ 3 ]}

• ${\displaystyle I=\prod _{i=1}^{k}[0,\ldots ,n_{i}]}$es el conjunto de índices. Define la topología del arreglo.
• ${\displaystyle S}$es el conjunto (no necesariamente finito) de estados, uno de los cuales cada célula puede adoptar en cualquier paso de tiempo dado.
• ${\displaystyle S_{0}\colon \mathbb {Z} ^{k}\to S}$define el estado inicial del sistema en el tiempo 0.
• ${\displaystyle s\in \prod _{i=1}^{l}\mathbb {Z} ^{k}}$es la plantilla en sí y describe la forma real del vecindario. Hay${\displaystyle l}$elementos en la plantilla.
• ${\displaystyle T\colon S^{l}\to S}$es la función de transición que se utiliza para determinar el nuevo estado de una célula, dependiendo de sus vecinas.

Dado que I es un intervalo entero k -dimensional, la matriz siempre tendrá la topología de una cuadrícula regular finita. La matriz también se denomina espacio de simulación y las celdas individuales se identifican por su índice.${\displaystyle c\in I}$. La plantilla es un conjunto ordenado de${\displaystyle l}$coordenadas relativas. Ahora podemos obtener para cada celda${\displaystyle c}$la tupla de los índices de sus vecinos${\displaystyle I_{c}}$

${\displaystyle I_{c}=\{j\mid \exists x\in s:j=c+x\}\,}$

Sus estados se dan mediante el mapeo de la tupla.${\displaystyle I_{c}}$a la tupla de estados correspondiente${\displaystyle N_{i}(c)}$, dónde${\displaystyle N_{i}\colon I\to S^{l}}$se define de la siguiente manera:

${\displaystyle N_{i}(c)=(s_{1},\ldots ,s_{l}){\text{ con }}s_{j}=S_{i}(I_{c}(j))\,}$

Esto es todo lo que necesitamos para definir el estado del sistema para los siguientes pasos de tiempo.${\displaystyle S_{i+1}\colon \mathbb {Z} ^{k}\to S}$con${\displaystyle i\in \mathbb {N} }$:

${\displaystyle S_{i+1}(c)={\begin{cases}T(N_{i}(c)),&c\in I\\S_{i}(c),&c\in \mathbb {Z} ^{k}\setminus I\end{cases}}}$

Tenga en cuenta que${\displaystyle S_{i}}$se define en${\displaystyle \mathbb {Z} ^{k}}$y no solo en${\displaystyle I}$ya que también es necesario establecer las condiciones de contorno. A veces, los elementos de${\displaystyle I_{c}}$puede definirse mediante una suma vectorial módulo la dimensión del espacio de simulación para realizar topologías toroidales:

${\displaystyle I_{c}=\{j\mid \exists x\in s:j=((c+x)\mod (n_{1},\ldots ,n_{k}))\}}$

Esto puede resultar útil para implementar condiciones de contorno periódicas , lo que simplifica ciertos modelos físicos.

Ejemplo: Iteración de Jacobi en 2D

Para ilustrar la definición formal, veremos cómo se define una iteración de Jacobi bidimensional . La función de actualización calcula la media aritmética de los cuatro vecinos de una celda. En este caso, partimos de una solución inicial de 0. Los límites izquierdo y derecho se fijan en 1, mientras que los límites superior e inferior se establecen en 0. Tras un número suficiente de iteraciones, el sistema converge hacia una forma de silla de montar.

${\displaystyle {\begin{aligned}I&=[0,\ldots ,99]^{2}\\S&=\mathbb {R} \\S_{0}&:\mathbb {Z} ^{2}\to \mathbb {R} \\S_{0}((x,y))&={\begin{cases}1,&x<0\\0,&0\leq x<100\\1,&x\geq 100\end{cases}}\\s&=((0,-1),(-1,0),(1,0),(0,1))\\T&\colon \mathbb {R} ^{4}\to \mathbb {R} \\T((x_{1},x_{2},x_{3},x_{4}))&=0.25\cdot (x_{1}+x_{2}+x_{3}+x_{4})\end{aligned}}}$

${\displaystyle S_{0}}$

${\displaystyle S_{200}}$

${\displaystyle S_{400}}$

${\displaystyle S_{600}}$

${\displaystyle S_{800}}$

${\displaystyle S_{1000}}$

Iteración de Jacobi 2D en un${\displaystyle 100^{2}}$Formación

La forma del vecindario utilizado durante las actualizaciones depende de la propia aplicación. Las plantillas más comunes son las versiones 2D o 3D del vecindario de von Neumann y del vecindario de Moore . El ejemplo anterior utiliza una plantilla de von Neumann 2D, mientras que los códigos LBM generalmente utilizan su variante 3D. El Juego de la Vida de Conway utiliza el vecindario de Moore 2D. Dicho esto, también se pueden encontrar otras plantillas, como una plantilla de 25 puntos para la propagación de ondas sísmicas ^{[ 5 ] .}

Plantilla 2D de 9 puntos

Plantilla 2D de 5 puntos

Plantilla 3D de 7 puntos

Plantilla 3D de 25 puntos

Una selección de plantillas utilizadas en diversas aplicaciones científicas.

Muchos códigos de simulación pueden formularse naturalmente como ISL. Dado que el tiempo de computación y el consumo de memoria crecen linealmente con el número de elementos de la matriz, las implementaciones paralelas de ISL son de suma importancia para la investigación. ^{[ 6 ]} Esto es un desafío ya que los cálculos están estrechamente acoplados (debido a que las actualizaciones de las celdas dependen de las celdas vecinas) y la mayoría de los ISL están limitados por la memoria (es decir, la relación entre los accesos a la memoria y los cálculos es alta). ^{[ 7 ]} Prácticamente todas las arquitecturas paralelas actuales se han explorado para ejecutar ISL de manera eficiente; ^{[ 8 ]} en este momento las GPGPU han demostrado ser las más eficientes. ^{[ 9 ]}

Debido a la importancia de los lenguajes de simulación intersistemas (ISL) para las simulaciones por computadora y a sus elevados requisitos computacionales, existen numerosos esfuerzos para crear bibliotecas reutilizables que ayuden a los científicos a realizar cálculos basados ​​en plantillas. Estas bibliotecas se centran principalmente en la paralelización, pero también pueden abordar otros desafíos, como la entrada/salida, la gestión de recursos y los puntos de control . Se pueden clasificar según sus API.

• Física
• LibGeoDecomp archivado el 25/06/2022 en Wayback Machine .
• waLBerla