¿Cuáles son las ventajas y desventajas de la descomposición de partículas y los algoritmos de paralelización de descomposición de dominio?

Estoy ejecutando simulaciones de dinámica molecular (MD) usando varios paquetes de software, como Gromacs y DL_POLY.

Gromacs ahora admite los algoritmos de descomposición de partículas y de descomposición de dominio. Por defecto, las simulaciones de Gromacs utilizan la descomposición de dominio, aunque durante muchos años, hasta hace poco, la descomposición de partículas era el único método implementado en Gromacs. En uno de los documentos de Gromacs (DOI 10.1002 / jcc.20291), los autores dan una razón para su elección inicial de descomposición de partículas:

"Una decisión de diseño temprana fue la elección de trabajar con descomposición de partículas en lugar de descomposición de dominio para distribuir el trabajo entre los procesadores. En este último caso, los dominios espaciales se asignan a los procesadores, lo que permite encontrar vecinos espaciales rápidamente solo por comunicación local, pero las complicaciones se deben las partículas que se mueven sobre los límites espaciales son considerables. La descomposición del dominio es una mejor opción solo cuando el tamaño del sistema lineal excede considerablemente el rango de interacción, lo que rara vez ocurre en la dinámica molecular. Con la descomposición de partículas, cada procesador calcula las fuerzas y las actualizaciones de coordenadas / velocidad para una fracción asignada de las partículas, utilizando una lista de vecinos precalculada distribuida uniformemente sobre los procesadores.$F_{ij}$ surge de la interacción del par entre las partículas y , que es necesaria para la actualización de la velocidad de ambas partículas y jj i $i$$j$$i$$j$, se calcula solo una vez y se comunica a otros procesadores. Cada procesador mantiene en su memoria local el conjunto completo de coordenadas del sistema en lugar de restringir el almacenamiento a las coordenadas que necesita. Esto es más simple y ahorra gastos generales de comunicación, mientras que el reclamo de memoria generalmente no es un factor limitante, incluso para millones de partículas. La lista de vecinos, por otro lado, que puede contener hasta 1000 veces el número de partículas, se distribuye entre los procesadores. La comunicación está esencialmente restringida al envío de coordenadas y fuerzas una vez por vez alrededor del anillo del procesador. Estas opciones han demostrado ser robustas con el tiempo y fácilmente aplicables a los clústeres de procesadores modernos ".

¿Qué quieren decir con "tamaño del sistema lineal" en la oración "La descomposición del dominio es una mejor opción solo cuando el tamaño del sistema lineal excede considerablemente el rango de interacción, que rara vez ocurre en la dinámica molecular"? Del párrafo anterior, tengo la idea de que la descomposición de partículas tiene la ventaja de que uno no tiene que lidiar con partículas que se mueven a través de los límites del dominio; más bien, solo tiene que tener suficiente memoria para que cada procesador almacene la configuración total del sistema. Por lo tanto, la descomposición de partículas se ve muy favorable, mientras que la descomposición del dominio se ve muy desfavorable.

Estoy seguro de que esta es una pregunta muy complicada (y probablemente el tema de muchos libros), pero básicamente, si la descomposición de partículas parece tan favorable, ¿por qué alguien necesitaría usar la descomposición de dominio? ¿La descomposición del dominio es favorable si el tamaño del sistema es muy grande (lo que hace que sea difícil o imposible almacenar la configuración total en cada procesador)? Basado en el párrafo citado arriba, no estoy seguro de por qué la descomposición del dominio es ahora, recientemente, el algoritmo de paralelización predeterminado en Gromacs.

Parece que DL_POLY ahora (versión 4) también usa la descomposición del dominio. Del manual de la versión 4:

"La división de los datos de conguración de esta manera se basa en la ubicación de los átomos en la celda de simulación, tal asignación geométrica de los datos del sistema es el sello distintivo de los algoritmos DD. Tenga en cuenta que para que esta estrategia funcione de manera eficiente, el simulado el sistema debe poseer una densidad razonablemente uniforme, de modo que a cada procesador se le asigne casi una porción igual de datos de átomos (tanto como sea posible). Mediante este enfoque, el cálculo de las fuerzas y la integración de las ecuaciones de movimiento se comparten (razonablemente) por igual entre los procesadores y en gran medida se puede calcular de forma independiente en cada procesador. El método es conceptualmente simple aunque difícil de programar y es particularmente adecuado para simulaciones a gran escala, donde la eficiencia es más alta.

...

En el caso de la estrategia DD, el algoritmo SHAKE (RATTLE) es más simple que para el método de datos replicados de DL_POLY Classic), donde se requieren actualizaciones globales de las posiciones de los átomos (fusión y empalme) ".

Esto hace que parezca que la descomposición del dominio es buena porque puede ser más eficiente, aunque quizás sea más difícil de implementar.

Por otro lado, una versión anterior (DL_POLY Classic) utilizaba la paralelización de datos replicados, que parece ser otro nombre para la descomposición de partículas. Del manual de esa versión:

La estrategia de datos replicados (RD) es una de varias formas de lograr la paralelización en MD. Su nombre deriva de la replicación de los datos de configuración en cada nodo de una computadora paralela (es decir, las matrices que definen las coordenadas atómicas , velocidades y fuerzas , para todov i f i$\textbf{r}_i$$\textbf{v}_i$$\textbf{f}_i$$N$átomos en el sistema simulado, se reproducen en cada nodo de procesamiento). En esta estrategia, la mayoría del cálculo de las fuerzas y la integración de las ecuaciones de movimiento se pueden compartir fácilmente y por igual entre los nodos y, en gran medida, se pueden procesar de forma independiente en cada nodo. El método es relativamente simple de programar y es razonablemente eficiente. Además, puede "colapsarse" para ejecutarse en un único procesador con mucha facilidad. Sin embargo, la estrategia puede ser costosa en memoria y tener altos costos de comunicación, pero en general ha demostrado ser exitosa en una amplia gama de aplicaciones.

Este párrafo parece generalmente consistente con el primer párrafo de esta pregunta, excepto que dice que la descomposición de datos / partículas replicadas tiene "altos costos de comunicación". El párrafo del artículo de Gromacs parece decir lo contrario: esa descomposición de partículas es preferible porque tiene una sobrecarga de comunicación menor que la descomposición del dominio.

¿Que piensas?

La descomposición de partículas y dominios está directamente conectada a los dos métodos principales para acelerar los cálculos de fuerza para sistemas con interacciones de rango limitado: listas vecinas de Verlet y listas vinculadas a celdas. Si desea entrar en detalles, hay un buen libro de Allen y Tildesley, llamado Computer Simulation of Liquids , considerado por muchos como la "biblia" de los estudios Molecular Dynamics y Monte Carlo. Luego está la Simulación Numérica en Dinámica Molecular de Griebel, Knapek y Zumbusch, que profundiza en las diversas técnicas para la implementación paralela de MD.

Básicamente, las listas de Verlet crean una lista de todos los vecinos de un átomo / molécula (o partículas en general) dentro de un radio dado. Más tarde, cuando se examinan pares de átomos para calcular la fuerza, se consulta la lista. Una vez que tiene la lista construida, es obvio qué partículas están cerca de qué otras y se pueden distribuir entre diferentes procesadores para su evaluación. La lista se construye solo de vez en cuando con algunas técnicas inteligentes para mantenerla actualizada, ya que se necesita para construirla (se examinan todas las posibles partículas de partículas). La evaluación de la fuerza dada la lista ya construida toma .O ( N $O(N^2)$$O(N)$

Las listas vinculadas a celdas dividen el espacio en celdas de igual tamaño que son más grandes que la distancia de corte del potencial de interacción y luego cada partícula se coloca en una lista asociada con la celda en la que cae. Este proceso toma . Luego, los vecinos de una partícula dada solo se buscan en la misma celda o en sus celdas vecinas. Dado que cada celda tiene un número constante de vecinos (por ejemplo, 26 en el caso 3D), las fuerzas se evalúan en . Pero aquí el multiplicador constante podría ser lo suficientemente grande como para hacer que este algoritmo escale peor que el método de la lista Verlet. Pero por lo suficientemente grandeO ( N ) $O(N)$$O(N)$ $N$Se escala mejor. De ahí el argumento de tamaño lineal. El método de descomposición del dominio es una extensión directa del método de listas vinculadas a celdas: las celdas se dividen entre diferentes CPU.

El problema con la descomposición del dominio es que tiene que comunicarse cuando las partículas se mueven de una celda a otra de la que se ocupa otra CPU. Esto podría volverse problemático a temperaturas de simulación más altas donde las partículas tienden a alejarse más que su posición de equilibrio, o cuando hay un flujo de partículas. Además, la información de las celdas en el borde del dominio debe transferirse en cada iteración a los dominios vecinos. Pero todo esto es comunicación localmente sincrónica y podría hacerse de manera muy eficiente.

Los datos replicados son el enfoque más fácil, pero desafortunadamente requieren que en cada paso toda la información de posición y velocidad se sincronice globalmente. Esto realmente no escala bien y para un sistema muy grande, la cantidad global de memoria es el tamaño de la estructura de datos multiplicada por el número de CPU utilizadas, mientras que uno de los objetivos del procesamiento paralelo es la distribución de datos de manera que cada CPU tenga menos que la cantidad global de datos.

En resumen, no existe un método de "talla única", adecuado para todos los sistemas que se simulan. La mayoría de las veces, la mejor estrategia de paralelización se puede deducir de la geometría del sistema y, después de todo, se puede elegir el código MD apropiado: todos ellos implementan más o menos los mismos campos de fuerza e integradores subyacentes.

Por "La descomposición del dominio es una mejor opción solo cuando el tamaño del sistema lineal excede considerablemente el rango de interacción, que rara vez es el caso en la dinámica molecular", los autores de ese (muy antiguo) documento GROMACS quieren decir que si el tamaño espacial de la lista vecina es del orden de 1 nm, y la celda de simulación es solo de varios nanómetros, entonces la sobrecarga de descomposición del dominio es demasiado alta. También puede aceptar una distribución de información de todos en la descomposición de partículas, y no necesita perder tiempo en toda la contabilidad para la descomposición del dominio.

El problema con la descomposición de partículas cuando GROMACS lo implementó fue que con el tiempo las partículas asignadas a cada procesador se difunden a través del espacio. Dado que la responsabilidad de calcular cada interacción estaba fijada por su ubicación inicial, la difusión aumentó gradualmente el volumen del espacio total que cada procesador necesitaba saber para construir su lista de vecinos, incluso si el cálculo total descrito por la lista de vecinos era constante. En la práctica, reiniciaría periódicamente la simulación para restablecer la localidad de datos y comunicación.

Su suposición de que "la descomposición de partículas tiene la ventaja de que uno no tiene que lidiar con partículas que se mueven a través de los límites del dominio" no se cumple si la difusión es significativa en la escala de tiempo de la simulación.

La descomposición del dominio se ocupa de este "por adelantado" al migrar la responsabilidad de la interacción junto con la difusión, mejorando así la ubicación de los datos en cada procesador y minimizando el volumen de comunicación.

Descargo de responsabilidad: ayudo a desarrollar GROMACS, y probablemente arrancaré la implementación de descomposición de partículas la próxima semana ;-)

Me gustaría añadir a la respuesta de Hristo Iliev. Si bien su publicación habla principalmente de la complejidad computacional , cuando se trata de la paralelización, la complejidad de la comunicación es al menos igual de importante, y esa es la razón principal de la descomposición del dominio.

Las máquinas paralelas modernas generalmente tienen algún tipo de topología de toro. Esto significa que cada CPU tiene varias CPU "vecinas" con las que puede comunicarse muy rápidamente. Comunicarse con una CPU que no es un vecino es más costoso. Por lo tanto, siempre es favorable tener un algoritmo que solo necesite comunicarse con las CPU vecinas.

$P$$\mathcal{O}(P^2)$

$P$$\mathcal{O}(P)$

$\mathcal{O}(P)$

Sin embargo, tenga en cuenta que los sistemas no uniformes no son tan comunes como puede parecer, solo ocurren cuando se simula algo en el vacío o cuando se usa un solvente implícito. Las densidades de cristales y líquidos son lo suficientemente cercanas como para ejecutar la descomposición del dominio.