¿Estrategia para implementar el algoritmo de desplazamiento de árbol en paralelo?

Question

He implementado un algoritmo iterativo, donde cada iteración implica un recorrido de árbol de prepedido (a veces llamado acumulación descendente) seguido de un recorrido de árbol posterior al pedido (acumulación ascendente). Cada visita a cada nodo implica calcular y almacenar la información que se utilizará para la próxima visita (ya sea en el posterior recorrido posterior al pedido o en la iteración siguiente).

Durante el recorrido de preorden, cada nodo se puede procesar independientemente siempre que todos los nodos entre él y la raíz ya se hayan procesado. Después del procesamiento, cada nodo necesita pasar una tupla (específicamente, dos flotadores) a cada uno de sus hijos. En el recorrido posterior a la orden, cada nodo se puede procesar de forma independiente siempre que todos sus subárboles (si los hay) ya se hayan procesado. Después del procesamiento, cada nodo necesita pasar un solo float a su primario.

La estructura de los árboles es estática y no cambia durante el algoritmo. Sin embargo, durante el curso del recorrido descendente, si los dos flotantes que pasan son cero, no es necesario procesar todo el subárbol bajo este nodo y puede comenzar el recorrido hacia arriba para este nodo. (El subárbol debe conservarse, porque los flotantes pasados ​​en iteraciones posteriores pueden ser diferentes de cero en este nodo y se reanudarán los recorridos).

La intensidad del cálculo en cada nodo es la misma en todo el árbol. El cálculo en cada nodo es trivial: solo unas pocas sumas y multiplicaciones/divisiones en una lista de números con una longitud igual a la cantidad de hijos en el nodo.

Los árboles que se están procesando están desequilibrados: un nodo típico tendría 2 hojas más 0-6 nodos secundarios adicionales. Entonces, simplemente particionar el árbol en un conjunto de subárboles relativamente equilibrados no es obvio (para mí). Además, los árboles están diseñados para consumir toda la RAM disponible: el árbol más grande que puedo procesar, mejor.

Mi implementación en serie alcanza el orden de 1000 iteraciones por segundo solo en mis pequeños árboles de prueba; con los árboles "reales", espero que pueda disminuir en un orden de magnitud (¿o más?). Dado que el algoritmo requiere al menos 100 millones de iteraciones (posiblemente hasta mil millones) para alcanzar un resultado aceptable, me gustaría paralelizar el algoritmo para aprovechar los múltiples núcleos. Tengo cero experiencia con programación paralela.

¿Cuál es el patrón recomendado para la paralelización dada la naturaleza de mi algoritmo?

Answer 1

Intente reescribir su algoritmo para que esté compuesto por pure functions. Eso significa que cada fragmento de código es esencialmente una función estática (pequeña) sin dependencia de las variables globales o estáticas, y que todos los datos se tratan como inmutables --- los cambios solo se realizan en las copias --- y todas las funciones solo manipulan estado (en un sentido amplio de la palabra "manipular") devolviendo (nuevos) datos.

--- si cada función es referentially transparent --- solo depende de su entrada (y no estado oculto) para calcular su salida, y cada llamada de función con la misma entrada siempre produce la misma salida --- entonces usted está en una buena posición para paralelizar el algoritmo: ya que su código nunca muta variables globales (o archivos, servidores, etc.)) el trabajo que realiza una función puede repetirse con seguridad (para recalcular el resultado de la función) o ignorarse por completo (ningún código futuro depende de los efectos secundarios de esta función, por lo que omitir una llamada por completo no romperá nada). Luego, cuando se ejecuta el conjunto de funciones (por ejemplo, en alguna implementación de MapReduce, hadoop, etc.) de la cadena de funciones provocará una cascada mágica de dependencias basándose únicamente en la salida de una función y la entrada de otra función, y qué que está tratando de calcular (a través de funciones puras) estará completamente separado del ORDEN en el que está tratando de calcularlo (una pregunta respondida por la implementación de un planificador para un marco como MapReduce).

Un buen lugar para aprender este modo de pensar es escribir su algoritmo en el lenguaje de programación Haskell (o algo F # u Ocaml) que tiene un gran soporte para programación paralelo/multinúcleo, listo para usar. Haskell obliga a que su código sea puro, de modo que si su algoritmo funciona, probablemente sea fácilmente paralelizable.

Answer 2

El método habitual es utilizar algún tipo de división de trabajo en profundidad. Empiezas con una cantidad de trabajadores esperando en una cola inactiva y un trabajador iniciando un recorrido en la raíz. Un trabajador con trabajo atraviesa primero la profundidad, y siempre que se encuentre en un nodo con más de un niño por hacer, verifica la cola de trabajo inactiva y, si no está vacía, cultiva un subárbol (secundario) en otro trabajador. Hay algunas complicaciones al manejar la unión cuando un trabajador termina un subárbol, pero en general esto puede funcionar bien para una variedad de estructuras de árbol (equilibradas o desequilibradas)

Answer 3

Esta respuesta se describe la forma que lo haría con el lenguaje paralelo y sistema de ejecución que trabajo en el día a día, Charm++. Tenga en cuenta que el lenguaje utilizado para el código secuencial dentro de este marco es C o C++, por lo que tendría que esforzarse en portar el código computacional. Charm ++ tiene algunos mecanismos para interoperar con el código Python, aunque estoy menos familiarizado con esos aspectos. Es posible que pueda mantener el código del controlador y la interfaz en Python y simplemente colocar el código computacional pesado en C++. De todos modos, el esfuerzo de portabilidad en el código secuencial probablemente te proporcionará un buen incremento de rendimiento.

Diseño:

Crear una matriz de objetos paralelos (llamados Cares en nuestro entorno), y asignar a cada una lista de trabajo de los nodos del árbol interior a partir de una raíz subárbol y se extienden hacia abajo partways. Cualquier hoja unida a esos nodos también pertenecería a esa chare.

Cada objeto paralelo necesitaría dos métodos remotamente invocable asíncronos, conocidos como métodos de introducción de , passDown(float a, float b) y passUp(int nodeID, float f), que serían los puntos de comunicación entre ellos. passDown llamarían método de nodo se utiliza para hacer el cálculo pre-orden, y los nodos que tienen fuera del objeto hijos llamarían passDown en esos objetos descendientes.

Una vez que todo el trabajo se realiza a la baja, el objeto sería calcular el trabajo al alza sobre sus hojas y esperar a sus descendientes. Las invocaciones de passUp calcularían lo más arriba posible en el árbol del objeto de recepción hasta que llegue a un elemento primario que no haya recibido datos de todos sus elementos secundarios. Cuando el nodo raíz del objeto se completa con el trabajo hacia arriba, llamaría al passUp en el objeto que contiene el nodo padre. Cuando finaliza la raíz de todo el árbol, sabrá que se ha completado una iteración.

resultados

tiempo de ejecución:

Una vez que esto se ha implementado, el sistema de ejecución se encarga de la ejecución en paralelo para usted. Distribuirá los objetos entre los procesadores e incluso a través de diferentes nodos de cómputo (por lo tanto, aumentará dramáticamente el techo de su tamaño de árbol, ya que su memoria disponible puede escalar mucho más). La comunicación entre procesadores y nodos se parece a la comunicación en proceso: llamadas a métodos asíncronos. El tiempo de ejecución puede equilibrar la carga de los objetos para mantener todos sus procesadores ocupados durante la mayor parte de cada iteración posible.

sintonización:

Si vas de esta manera y llegar al punto de actuación paralela de sintonía, también puede establecer prioridades en los mensajes para mantener longitud del camino crítico corto. De la parte superior de mi cabeza, la priorización me gustaría sugerir que haría el trabajo en este orden

1. trabaje hacia abajo eso es distinto de cero
   • Más cerca de la raíz va más pronto
2. trabajo ascendente
   • Más cerca de las hojas ocurre más pronto

Charm ++ funciona con una herramienta de análisis de rendimiento conocida como Proyecciones para obtener más información sobre el rendimiento de su programa.