multicore - programming - ¿Qué modelo de programación paralelo recomienda hoy para aprovechar los procesadores de muchos puntajes del mañana?

parallel programming book (22)

Apuesto a comunicar bucles de eventos con promesas, tal como se realiza en sistemas como Twisted , E , AmbientTalk y otros. Conservan la capacidad de escribir código con los mismos supuestos del modelo de ejecución que las aplicaciones no concurrentes / paralelas, pero escalando a sistemas distribuidos y paralelos. (Es por eso que estoy trabajando en Ecru ).

Si estuvieras escribiendo una nueva aplicación desde cero hoy, y quisieras que escalara a todos los núcleos que podrías usar mañana, ¿qué modelo / sistema / idioma / biblioteca de programación en paralelo elegirías? ¿Por qué?

Estoy particularmente interesado en respuestas a lo largo de estos ejes:

Productividad / facilidad de uso del programador (¿pueden los mortales utilizarla con éxito?)
Dominio de aplicación de destino (¿en qué problemas (no) está bien?)
Estilo de concurrencia (¿admite tareas, interconexiones, paralelismo de datos, mensajes ...?)
Mantenibilidad / a prueba de futuro (¿Alguien aún lo estará usando en 20 años?)
Rendimiento (¿cómo se escala en qué tipo de hardware?)

Estoy deliberadamente vago sobre la naturaleza de la aplicación, anticipándome a que las buenas respuestas generales sean útiles para una variedad de aplicaciones.

Como se mencionó, los lenguajes puramente funcionales son inherentemente paralelizables. Sin embargo, los lenguajes imperativos son mucho más intuitivos para muchas personas, y estamos profundamente arraigados en el código de legado imperativo. El problema fundamental es que los lenguajes funcionales puros expresan efectos secundarios explícitamente, mientras que los efectos secundarios se expresan implícitamente en los lenguajes imperativos por el orden de los enunciados.

Creo que las técnicas para expresar de forma declarativa los efectos secundarios (por ejemplo, en un marco orientado a objetos) permitirán a los compiladores descomponer declaraciones imperativas en sus relaciones funcionales. Esto debería permitir que el código se paralelice automáticamente de la misma manera que el código funcional puro.

Por supuesto, al igual que hoy en día todavía es deseable escribir cierto código crítico para el rendimiento en lenguaje ensamblador, aún será necesario escribir mañana el código explícitamente paralelo de rendimiento crítico. Sin embargo, técnicas como las delineadas deberían ayudar a aprovechar automáticamente muchas arquitecturas de núcleo con el mínimo esfuerzo invertido por el desarrollador.

Dos soluciones que realmente me gustan son el cálculo de unión ( JoCaml , Polyphonic C # , Cω ) y el modelo de actor ( Erlang , Scala , E , Io ).

No estoy particularmente impresionado con Software Transactional Memory . Simplemente parece que está ahí solo para permitir que los hilos se aferren a la vida un poco más, a pesar de que deberían haber muerto hace décadas. Sin embargo, tiene tres ventajas principales:

La gente entiende las transacciones en las bases de datos
Ya se habla de hardware RAM transaccional
Por mucho que todos deseamos que se vayan, los hilos probablemente serán el modelo dominante de simultaneidad para las próximas dos décadas, por triste que sea. STM podría reducir significativamente el dolor.

Echa un vistazo a Erlang . Busque Google y vea las diversas presentaciones y videos. Muchos de los programadores y arquitectos que respeto están bastante tomados con su escalabilidad. Lo estamos usando donde trabajo bastante ...

El paradigma mapreduce / hadoop es útil y relevante. Especialmente para las personas que están acostumbradas a lenguajes como Perl, la idea de mapear una matriz y hacer alguna acción en cada elemento debería ser bastante fluida y natural, y mapreduce / hadoop simplemente lo lleva a la siguiente etapa y dice que no hay razón para que cada elemento de la matriz necesita procesarse en la misma máquina.

En cierto sentido, está más probado en la batalla, porque Google usa mapreduce y mucha gente ha estado usando hadoop, y ha demostrado que funciona bien para escalar aplicaciones en múltiples máquinas a través de la red. Y si puede escalar en varias máquinas a través de la red, puede escalar múltiples núcleos en una sola máquina.

La programación multi-core en realidad puede requerir más de un paradigma. Algunos contendientes actuales son:

MapReduce . Esto funciona bien donde un problema puede descomponerse fácilmente en trozos paralelos.
Paralelismo de Datos Anidados . Esto es similar a MapReduce, pero en realidad admite la descomposición recursiva de un problema, incluso cuando los fragmentos recursivos son de tamaño irregular. Busque NDP para ser una gran ganancia en lenguajes puramente funcionales que se ejecutan en hardware masivamente paralelo pero limitado (como GPU).
Memoria transaccional de software . Si necesita hilos tradicionales, STM los hace soportables. Paga un 50% de rendimiento en secciones críticas, pero puede escalar complejos esquemas de bloqueo a cientos de procesadores sin ningún problema. Sin embargo, esto no funcionará para los sistemas distribuidos.
En paralelo hilos de objeto con mensajes . Este modelo realmente inteligente es utilizado por Erlang. Cada "objeto" se convierte en un hilo ligero, y los objetos se comunican mediante mensajes asincrónicos y coincidencia de patrones. Es básicamente verdadero OO paralelo. Esto ha tenido éxito en varias aplicaciones del mundo real, y funciona muy bien para sistemas distribuidos no confiables.

Algunos de estos paradigmas le brindan el máximo rendimiento, pero solo funcionan si el problema se descompone limpiamente. Otros sacrifican algo de rendimiento, pero permiten una variedad más amplia de algoritmos. Sospecho que alguna combinación de lo anterior finalmente se convertirá en un conjunto de herramientas estándar.

Para cálculos pesados y similares, los lenguajes puramente funcionales como Haskell son fácilmente paralelizables sin ningún esfuerzo por parte del programador. Además de aprender Haskell, eso es.

Sin embargo, no creo que esta sea la forma del futuro (próximo), simplemente porque demasiados programadores están demasiado acostumbrados al paradigma de programación imperativa.

Para la aplicación .NET elijo " .NET Parallel Extensions (PLINQ) " es extremadamente fácil de usar y me permite paralelizar el código existente en minutos.

Es simple de aprender
Se utiliza para realizar operaciones complejas en grandes conjuntos de objetos, por lo que no puedo comentar sobre otras aplicaciones
Admite tareas y piplines
Debería ser apoyado por un par de años, pero ¿quién sabe con certeza?
La versión CTP tiene algunos problemas de rendimiento, pero parece muy prometedor.

Es probable que Mono obtenga soporte para PLINQ, por lo que podría ser una solución multiplataforma también.

Qt concurrent ofrece una implementación de MapReduce para multinúcleo que es realmente fácil de usar. Es multiOS.

Si su dominio problemático lo permite, intente pensar en un modelo de compartir nada. Cuanto menos compartas entre los procesos y los hilos, menos tienes que diseñar modelos de concurrencia complejos.

Usaría Java, es portátil, por lo que los procesadores futuros no serán un problema. También codificaría mi aplicación con capas separando interfaz / lógica y datos (más como aplicación web de 3 niveles) con rutinas mutex estándar como una biblioteca (menos depuración del código paralelo). Recuerde que los servidores web se adaptan muy bien a muchos procesadores y son el camino menos doloroso para el multinúcleo. O eso o mira el viejo modelo de Machine Connection con un procesador virtual vinculado a los datos.

Erlang es la solución más "madura" y es portátil y de código abierto. Jugueté con Polyphonic C #, no sé cómo sería programar todos los días en él.

Hay bibliotecas y extensiones para casi todos los idiomas / sistemas operativos bajo el sol, la memoria transaccional de Google. Es un enfoque interesante de MS.

Me sorprende que nadie haya sugerido MPI (Message Passing Interface). Aunque están diseñados para la memoria distribuida, se ha demostrado que los programas MPI con acoplamiento global esencial y frecuente (resolución de ecuaciones lineales y no lineales con miles de millones de incógnitas) se escalan a 200k núcleos.

Esta pregunta parece seguir apareciendo con diferentes términos: tal vez haya diferentes grupos dentro de . La Programación basada en flujo (Flow-Based Programming, FBP) es un concepto / metodología que existe desde hace más de 30 años y se utiliza para procesar la mayor parte del procesamiento por lotes en un importante banco canadiense. Tiene implementaciones basadas en subprocesos en Java y C #, aunque las implementaciones anteriores se basaban en fibra (C ++ y Ensamblador de mainframe, el que se usaba en el banco). La mayoría de las aproximaciones al problema de aprovechar las multinúcleo implican intentar tomar un programa de subproceso convencional y determinar qué partes se pueden ejecutar en paralelo. FBP tiene un enfoque diferente: la aplicación está diseñada desde el principio en términos de múltiples componentes de "caja negra" que se ejecutan de forma asíncrona (piense en una línea de ensamblaje de fabricación). Dado que la interfaz entre los componentes es flujos de datos, FBP es esencialmente independiente del lenguaje y, por lo tanto, es compatible con aplicaciones de lenguaje mixto y lenguajes específicos de dominio. Por la misma razón, los efectos secundarios se reducen al mínimo. También podría describirse como un modelo de "compartir nada" y un MOM (middleware orientado a mensajes). MapReduce parece ser un caso especial de FBP. FBP difiere de Erlang principalmente en que Erlang opera en términos de muchos hilos de corta duración, por lo que los hilos verdes son más apropiados allí, mientras que FBP usa menos hilos (normalmente de unos 10 a unos cientos) de mayor duración. Para una parte de una red por lotes que ha estado en uso diario durante más de 30 años, vea parte de la red por lotes . Para un diseño de alto nivel de una aplicación interactiva, consulte el diseño de alto nivel de la aplicación Brokerage . Se ha encontrado que FBP da como resultado aplicaciones mucho más fáciles de mantener y tiempos transcurridos mejorados, ¡incluso en máquinas de un solo núcleo!

Una cola de trabajos con sistema de trabajadores múltiples (¿no está seguro de la terminología correcta - cola de mensajes?)

¿Por qué?

Principalmente, porque es un concepto absurdamente simple. Usted tiene una lista de cosas que necesita procesamiento, luego un montón de procesos que obtienen trabajos y los procesan.

Además, a diferencia de las razones, por ejemplo, Haskell o Erlang son tan concurrentes / paralelas (?), Es totalmente independiente del lenguaje, puedes implementar trivialmente dicho sistema en C, Python o cualquier otro lenguaje (incluso usando scripts de shell), mientras que dudo que bash obtenga memoria transaccional de software o cálculo de unión pronto.

Me gusta mucho el modelo que Clojure ha elegido. Clojure usa una combinación de estructuras de datos inmutables y memoria transaccional de software.

Las estructuras de datos inmutables son las que nunca cambian. Se pueden crear nuevas versiones de las estructuras con datos modificados, pero si tiene un "puntero" a una estructura de datos, nunca cambiará debajo de usted. Esto es bueno porque puede acceder a esos datos sin preocuparse por problemas de simultaneidad.

La memoria transaccional de software se analiza en otra parte de estas respuestas, pero basta decir que es un mecanismo por el cual varios subprocesos pueden actuar sobre algunos datos y, si colisionan, uno de los subprocesos se revierte para volver a intentarlo. Esto permite una velocidad mucho más rápida cuando el riesgo de colisión está presente pero poco probable.

Hay un video del autor Rich Hickey que entra en muchos más detalles.

Una ruta valiosa podría ser OpenCL , que proporciona un medio para distribuir ciertos tipos de cargas de cómputo a través de recursos computacionales heterogéneos, IE el mismo código se ejecutará en una CPU multinúcleo y también en GPUs básicas. ATI lanzó recientemente una cadena de herramientas de este tipo . La cadena de herramientas CUDA de NVidia es similar, aunque algo más restringida. También parece que Nvidia tiene un SDK OpenCL en las obras

Cabe señalar que esto probablemente no ayude mucho cuando las cargas de trabajo no son de naturaleza paralela a los datos, por ejemplo, no ayudará mucho con el procesamiento de transacciones típico. OpenCL está principalmente orientado a los tipos de computación que son intensivos en matemáticas, como la simulación científica / de ingeniería o el modelado financiero.

Si estuvieras escribiendo una nueva aplicación desde cero hoy, y quisieras que escalara a todos los núcleos que podrías usar mañana, ¿qué modelo / sistema / idioma / biblioteca de programación en paralelo elegirías?

Tal vez la más aplicable actualmente sea la cola de tareas estilo Cilk (ahora disponible en .NET 4). Son ideales para problemas que pueden resolverse utilizando divide y vencerás con complejidad predecible para subtareas (como el map paralelo y la reduce matrices donde se conoce la complejidad de los argumentos de función, así como algoritmos como quicksort) y que cubre muchos problemas reales.

Además, esto solo se aplica a las arquitecturas de memoria compartida como las multinúcleas actuales. Aunque no creo que esta arquitectura básica desaparezca pronto, sí creo que debe combinarse con el paralelismo distribuido en algún momento. Esto tendrá la forma de un clúster de multinúcleos en una CPU de muchos núcleos con mensajes que pasan entre multinúcleos, o en forma de una jerarquía de núcleos con tiempos de comunicación predecibles entre ellos. Estos requerirán modelos de programación sustancialmente diferentes para obtener la máxima eficiencia y no creo que se sepa mucho de ellos.

Hay tres partes en la programación paralela de la OMI: identifique el paralelismo y especifique el paralelismo. Identificar = Desglosar el algoritmo en trozos de trabajo concurrentes, especificar = haciendo la codificación / depuración real. Identify es independiente de qué marco usará para especificar el paralelismo y no creo que un framework pueda ayudar mucho. Viene con una buena comprensión de su aplicación, plataforma de destino, compensaciones comunes de programación en paralelo (latencias de hardware, etc.) y, lo que es más importante, experiencia. Sin embargo, especifique lo que puede discutirse y esto es lo que trato de responder a continuación:

He intentado muchos marcos (en la escuela y el trabajo). Como usted preguntó por las multinúcleas, que son todas memorias compartidas, me quedaré con tres marcos de memoria compartida que he usado.

Pthreads (no es realmente un marco, pero definitivamente aplicable):

Pro: -Pthreads es extremadamente general. Para mí, pthreads son como el ensamblaje de programación paralela. Puedes codificar cualquier paradigma en pthreads. - Es flexible para que pueda obtener el alto rendimiento que desee. No hay limitaciones inherentes para frenarlo. Puede escribir sus propias construcciones y primitivas y obtener la mayor velocidad posible.

Con: -Necesita que usted haga todas las cañerías, como administrar las colas de trabajo, la distribución de tareas, usted mismo. -La sintaxis real es fea y tu aplicación a menudo tiene un montón de código adicional que hace que el código sea difícil de escribir y luego difícil de leer.

OpenMP:

Pros: -El código parece limpio, la plomería y la división de tareas se realizan principalmente bajo el capó -Semi-flexible. Le da varias opciones interesantes para programar el trabajo

Contras: -Me refiero al paralelismo simple para bucle. (La nueva versión de Intel también admite tareas pero las tareas son las mismas que Cilk). -Las estructuras subyacentes pueden o no estar bien escritas para el rendimiento. La implementación de GNU está bien. La ICC de Intel funcionó mejor para mí, pero prefiero escribir algunas cosas para un mayor rendimiento.

Cilk, Intel TBB, Apple GCD:

Pros: -Problemas subyacentes óptimos para el paralelismo a nivel de tarea -Decontrol decente de tareas en serie / paralelas -TBB también tiene un marco de paralelismo de tuberías que utilicé (no es lo mejor para ser sincero) -Elimina la tarea de escribir mucho de código para sistemas basados en tareas que puede ser una gran ventaja si no tienes suficiente

Contras: -Menos control del rendimiento de las estructuras subyacentes. Sé que Intel TBB tiene estructuras de datos subyacentes que funcionan muy mal, por ejemplo, la cola de trabajo era mala (en 2008 cuando la vi). -El código se ve horrible algunas veces con todas las palabras clave y las palabras de moda que desean que use -Necesita leer muchas referencias para comprender sus API "flexibles"

Hemos estado utilizando PARLANSE , un lenguaje de programación paralelo con especificación explícita de orden parcial de simultaneidad durante la última década, para implementar un sistema escalable de análisis y transformación de programas ( DMS Software Reengineering Toolkit ) que principalmente hace cálculos simbólicos en lugar de numéricos. PARLANSE es un lenguaje compilado en forma de C con caracteres de datos escalares tradicionales, entero, flotante, cadena de tipos de datos dinámicos y matriz, estructura y unión de tipos de datos compuestos, y funciones de ámbito léxico. Si bien la mayoría del lenguaje es vainilla (expresiones aritméticas sobre operandos, declaraciones if-then-else, hacer bucles, llamadas a funciones), el paralelismo no lo es. El paralelismo se expresa definiendo una relación "precede" sobre bloques de código (p. Ej., A antes de b, a antes de c, d antes de c) escrito como

(|; a (... a''s computation) (<< a) b ( ... b''s computation ... ) (<< a) c ( ....c''s computation ...) (>> c) d ( ... d''s computation...) )|;

donde los operadores << y >> se refieren a "orden en el tiempo". El compilador PARLANSE puede ver estos cálculos paralelos y preasignar todas las estructuras necesarias para los granos de cálculo a, b, c, d, y generar código personalizado para iniciar / detener cada uno, lo que minimiza la sobrecarga para iniciar y detener estos granos paralelos.

Vea este enlace para la búsqueda paralela iterativa iterativa de soluciones óptimas para el rompecabezas de 15 , que es el hermano mayor de 4x4 del rompecabezas 8. Solo utiliza el potencial paralelo como una construcción de paralelismo (|| abcd) que dice que no hay restricciones de orden parcial en los cálculos a b c d , pero también utiliza la especulación y anula asíncronamente las tareas que no encontrarán soluciones. Son muchas ideas en un código bastante pequeño.

PARLANSE funciona en PC multinúcleo. Un gran programa PARLANSE (hemos creado muchos con 1 millón de líneas o más) tendrá miles de estos pedidos parciales, algunos de los cuales llaman funciones que contienen otros. Hasta ahora hemos tenido buenos resultados con hasta 8 CPUs y pagos modestos con hasta 16, y todavía estamos ajustando el sistema. (Creemos que un problema real con un mayor número de núcleos en las PC actuales es el ancho de banda de la memoria: 16 núcleos golpeando un subsistema de memoria crea una gran demanda de ancho de banda).

La mayoría de los otros lenguajes no exponen el paralelismo por lo que es difícil de encontrar, y los sistemas de tiempo de ejecución pagan un alto precio por programar los granos de cálculo mediante el uso de primitivas de programación de propósito general. Creemos que es una receta para el desastre o al menos un rendimiento deficiente debido a la ley de Amhdahl: si el número de instrucciones de la máquina para programar un grano es grande en comparación con el trabajo, no puede ser eficiente. OTOH, si insistes en los granos de cálculo con muchas instrucciones de máquina para mantener los costos de programación relativamente bajos, no puedes encontrar granos de cálculo que sean independientes y por lo tanto no tienes ningún paralelismo útil para programar. Entonces, la idea clave detrás de PARLANSE es minimizar el costo de programar granos, de modo que los granos puedan ser pequeños, de modo que puede haber muchos de ellos en código real. La idea de esta compensación proviene de la falla absoluta del paradigma de flujo de datos puro, que hizo todo en paralelo con pequeños trozos paralelos (por ejemplo, el operador de agregar).

Hemos estado trabajando en esto de forma intermitente durante una década. Es difícil hacer esto bien. No veo cómo la gente que no ha estado construyendo idiomas paralelos y usándolos / afinando para este marco de tiempo tiene alguna posibilidad seria de construir sistemas paralelos efectivos.

Véase también la pregunta Multi-Core y Concurrency - Idiomas, Bibliotecas y Técnicas de Desarrollo

kamaelia es un framework Python para construir aplicaciones con muchos procesos de comunicación.

http://www.kamaelia.org/cat-trans-medium.png Kamaelia - Concurrencia útil, divertida
En Kamaelia construyes sistemas a partir de componentes simples que se comunican entre sí . Esto acelera el desarrollo, ayuda de forma masiva al mantenimiento y también significa que crea software concurrente de forma natural . Está destinado a ser accesible por cualquier desarrollador, incluidos los principiantes. También lo hace divertido :)
¿Qué tipo de sistemas? Servidores de red, clientes, aplicaciones de escritorio, juegos basados en pygame, sistemas y tuberías de transcodificación, sistemas de televisión digital, borradoras de correo no deseado, herramientas de enseñanza, y mucho más :)

Ver también la pregunta Multi-Core y Concurrency - Idiomas, Bibliotecas y Técnicas de Desarrollo