c++ - programas - mpi que es

Programación Paralela y C++

Question

Recientemente he escrito mucho sobre programación y programación en paralelo y me doy cuenta de que hay muchos patrones que surgen cuando se trata de computación paralela. Observando que Microsoft ya lanzó una biblioteca junto con la Vista previa técnica de la comunidad de Microsoft Visual C ++ 2010 (denominada Parallel Patterns Library) me pregunto cuáles son los patrones comunes de programación en paralelo que ha estado usando y encontrando que puede valer la pena recordar. ¿Tienes algún modismo que sigas y patrones que pareces seguir apareciendo mientras escribes programas paralelos con C ++?

Answer 1

En primer lugar, debe elegir entre informática de memoria compartida y informática compartida. La memoria compartida es más fácil, pero no se escala tan bien: no usarás nada compartido si tú tampoco

a) tener un clúster, en lugar de un sistema multiprocesador, o

b) si tiene muchas CPU (por ejemplo,> 60) y un alto grado de memoria no uniforme

Para la memoria compartida, la solución común es usar hilos; son fáciles de entender como concepto y fáciles de usar en la API (pero difíciles de depurar).

Para compartir-nada, usa algún tipo de mensaje. En informática de alto rendimiento, MPI se establece como el middleware de mensajería.

También debe diseñar una arquitectura para las actividades paralelas. El enfoque más común (nuevamente porque es fácil de entender) es el patrón agricultor-trabajador (también conocido como maestro-esclavo).

Answer 2

Patrones:

• Producto / Consumidor

  • One Thread produce datos
  • One Thread consume los datos

• Paralelismo de bucle

  • Si puede mostrar que cada ciclo es independiente
    cada iteración se puede hacer en un hilo sperate

• Re-Draw Thread

  • Otros subprocesos funcionan y actualizan las estructuras de datos, pero un hilo vuelve a dibujar la pantalla.

• Tema principal

  • Múltiples hilos pueden estar generando eventos
  • Un hilo tiene que procesar los eventos (ya que el orden es importante)
  • Debería intentar separar el subproceso del evento / volver a dibujar el subproceso
    Esto (ayuda) evita que la IU se congele
    Pero puede causar extra-draws excesivos si no se hace con cuidado.

• Grupo de trabajo

  • Un conjunto de subprocesos espera trabajos en una que.
  • El hilo extrae un elemento de trabajo de la cola (esperando si no hay ninguno disponible).
    El hilo funciona en un elemento de trabajo hasta que se complete
    Una vez completado, el hilo vuelve a la cola.

Answer 3

Patrones de ejecución paralela

La programación paralela estructurada con patrones deterministas es un enfoque de alto nivel basado principalmente en una colección de patrones de ejecución paralelos recurrentes, a menudo denominados esqueletos algorítmicos o construcciones paralelas, que resumen la descripción del programa y ocultan detalles de subprocesamiento de bajo nivel y muchas complejidades inherentes al paralelismo de los programadores.

Estos patrones reutilizables automatizan muchas rutinas paralelas relacionadas con el paradigma, como sincronización, comunicación, partición de datos o programación de tareas y las manejan internamente. Este enfoque de alto nivel intenta el modelo tradicional de bajo nivel de bloqueo de hilos con más abstracción y una forma más fácil de expresar el paralelismo y enfocar la productividad y la programabilidad en lugar del rendimiento.

Hay muchos patrones comúnmente utilizados, tales como: Map-Reduce, Fork-Join, Pipeline o Parallel Loop ...

Papeles

La "Programación paralela estructurada con patrones determinísticos" es un documento que analiza estos patrones. También puede ver "MHPM: Modelo de Programación Híbrido Multi-Escala: Una Metodología de Parallelización Flexible" que describe una implementación en C ++ de este enfoque llamado XPU.

Biblioteca

XPU es una biblioteca de C ++ basada en tareas compuesta a partir de un conjunto de patrones de ejecución reutilizables. Permite la expresión de varios tipos de paralelismo en varios niveles de granularidad dentro de un único modelo de programación homogéneo. Es fácil de usar e ilustra el interés en el uso de patrones para diseñar programas paralelos.

Por ejemplo, permite la expresión de:

1. Patrón de paralelismo de tareas:

   Simple / Hierarchical Fork / Join patrón de ejecución con algunas características como detección automática y protección de datos compartidos.

2. Parallelismo de datos:

   Patrón de bucle paralelo con partición de datos escalables.

3. Paralelismo temporal:

   Patrón de ejecución de canalización

Answer 4

Tienes los conceptos básicos que conectan el paralelismo con partes de un programa. C ++ 17 está obteniendo muchos de ellos (por ejemplo, versiones paralelas de foreach, sort, find y friends, map_reduce, map, reduce, prefix_sum ...) ver Extensiones de C ++ para el Paralelismo

Luego tienes los elementos como continuaciones. Piensa en std :: future pero with continúa. Hay pocas maneras de implementar esto ( boost tiene uno bueno ahora ya que el estándar no tiene un próximo (...) o luego (...) método, pero el gran beneficio es que uno no tiene que esperar es para hacer la próxima tarea

auto fut = async([]( ){..some work...} ).then( [](result_of_prev ){...more work} ).then... ;
fut.wait( );

La falta de sincronización entre las tareas posteriores es importante ya que la comunicación entre tareas / hilos / ... es lo que ralentiza los programas paralelos.

Entonces, con ese paralelismo basado en tareas es realmente agradable. Con un planificador de tareas, simplemente pasa las tareas y se va. Pueden tener métodos, como un semáforo, para comunicarse, pero eso no es obligatorio. Tanto Intel Thread Building Blocks como Microsoft Parallel Pattern Library tienen instalaciones para esto.

Después de eso tenemos el patrón de tenedor / unión. No implica crear N hilos para cada tarea. Solo que tienes estas N, cosas idealmente independientes, para hacer (fork) y cuando terminan tienen un punto de sincronización en algún lugar (join).

auto semaphore = make_semaphore( num_tasks );
add_task( [&semaphore]( ) {...task1...; semaphore.notify( ); } );
add_task( [&semaphore]( ) {...task2...; semaphore.notify( ); } );
...
add_task( [&semaphore]( ) {...taskN...; semaphore.notify( ); } );
semaphore.wait( );

Desde arriba, puede comenzar a ver el patrón de que se trata de un diagrama de flujo. El futuro es (A >> B >> C >> D) y Fork Join es (A | B | C | D). Con eso puedes combinarlos para formar un gráfico. (A1 >> A2 | B1 >> B2 >> B3 | C1 | D1 >> D2 >> (E1 >> E2 | F1)) Donde A1 >> A2 significa que A1 debe preceder a A2 y A | B significa que A y B puede correr concurrentemente Las partes lentas se encuentran al final de los gráficos / subgrafos donde las cosas se juntan.

El objetivo es encontrar partes independientes del sistema que no necesiten comunicarse. Los algoritmos paralelos, como se señaló anteriormente, son en casi todos los casos más lentos que sus contrapartes secuenciales hasta que la carga de trabajo sea lo suficientemente alta o el tamaño sea lo suficientemente grande (suponiendo que la comunicación no sea demasiado parlanchina). Por ejemplo, ordenar. En una computadora de 4 núcleos obtendrás alrededor de 2.5X el rendimiento dado o recibido porque la fusión es hablante y requiere mucha sincronización y no funciona todos los núcleos después de la primera ronda de fusión. En una GPU con una N que es muy grande, se puede usar una clase menos eficiente, como Bitonic, y termina siendo muy rápida porque tienes muchos trabajadores para potenciar el trabajo y todos están tranquilos haciendo sus cosas.

Algunos trucos para reducir la comunicación incluyen, usar una matriz de resultados para que cada tarea no intente bloquear un objeto para empujar un valor. A menudo, la reducción de estos resultados puede ser muy rápida.

Pero con todos los tipos de paralelismo, la lentitud proviene de la comunicación. Reducirlo.