Hispanopedia Wiki
Articulo de referencia

Programa único, múltiples datos

En informática , el término "programa único, datos múltiples" ( SPMD , por sus siglas en inglés) se utiliza para referirse a modelos computacionales que aprovechan el paralelism...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , el término "programa único, datos múltiples" ( SPMD , por sus siglas en inglés) se utiliza para referirse a modelos computacionales que aprovechan el paralelismo , mediante el cual múltiples procesadores cooperan en la ejecución de un programa para obtener resultados más rápidamente.

El término SPMD se introdujo en 1983 y se utilizó para designar dos modelos computacionales diferentes:

  1. por Michel Auguin (Universidad de Niza Sophia-Antipolis) y François Larbey (Thomson/Sintra), [ 1 ] [ 2 ] [ 3 ] como un enfoque de " bifurcación y unión " y de paralelismo de datos donde las tareas paralelas ("programa único") se dividen y se ejecutan simultáneamente en sincronía en múltiples procesadores SIMD con diferentes entradas, y
  2. por Frederica Darema (IBM), [ 4 ] [ 5 ] [ 6 ] donde " todos los procesos (de los procesadores)  comienzan a ejecutar el mismo programa... pero a través de directivas de sincronización... se autoprograman para ejecutar diferentes instrucciones y actuar sobre diferentes datos " y habilitando la paralelización MIMD de un programa dado, y es un enfoque más general que el paralelismo de datos y más eficiente que el fork-and-join para la ejecución paralela en multiprocesadores de propósito general.

El (IBM) SPMD es el estilo más común de programación paralela y puede considerarse una subcategoría de MIMD, ya que se refiere a la ejecución MIMD de un programa dado ("único"). [ 7 ] También es un requisito previo para conceptos de investigación como mensajes activos y memoria compartida distribuida .

SPMD frente a SIMD

En la ejecución paralela SPMD, varios procesadores autónomos ejecutan simultáneamente el mismo programa en puntos independientes, en lugar de hacerlo de forma sincronizada como lo hacen SIMD o SIMT con datos diferentes. En SIMD, la misma operación (instrucción) se aplica a múltiples datos para manipular flujos de datos (una versión de SIMD es el procesamiento vectorial, donde los datos se organizan como vectores).

A diferencia de SIMD, SPMD no requiere soporte especial del procesador en el que se ejecuta, ya sean CPU o GPU .

SPMD y SIMD no son mutuamente excluyentes: cada programa SPMD puede incluir subprocesamiento SIMD, vectorial o de GPU. Muchas CPU incluyen varios núcleos compatibles con SIMD, cada uno de los cuales puede participar en SPMD; lo mismo ocurre con muchas GPU que contienen varios flujos SIMD. SPMD se ha utilizado para la programación paralela tanto en arquitecturas de máquinas de paso de mensajes como de memoria compartida.

Operación

Memoria distribuida

En arquitecturas de computadoras con memoria distribuida , las implementaciones de SPMD suelen emplear programación por paso de mensajes . Una computadora con memoria distribuida consta de un conjunto de computadoras independientes interconectadas, llamadas nodos. Para la ejecución paralela, cada nodo inicia su propio programa y se comunica con los demás nodos enviando y recibiendo mensajes, para lo cual se utilizan rutinas de envío/recepción. Otras directivas de paralelización, como la sincronización de barrera , también pueden implementarse mediante mensajes. Estos mensajes pueden enviarse a través de diversos mecanismos de comunicación, como TCP/IP sobre Ethernet , o interconexiones especializadas de alta velocidad como InfiniBand u Omni-Path . En entornos de memoria distribuida, las secciones seriales del programa pueden implementarse mediante el cálculo idéntico de la sección serial en todos los nodos, en lugar de calcular el resultado en un nodo y enviarlo a los demás, si esto mejora el rendimiento al reducir la sobrecarga de comunicación.

Actualmente, el programador está aislado de los detalles del paso de mensajes mediante interfaces estándar, como PVM y MPI .

La memoria distribuida es el estilo de programación utilizado en supercomputadoras paralelas, desde los clústeres Beowulf de fabricación propia hasta los clústeres más grandes de Teragrid , así como en las supercomputadoras actuales basadas en GPU .

Memoria compartida

En una máquina de memoria compartida (un ordenador con varias CPU interconectadas que acceden al mismo espacio de memoria), el uso compartido puede implementarse en el contexto de memoria compartida físicamente o memoria compartida lógicamente (pero distribuida físicamente); además de la memoria compartida, las CPU del sistema informático también pueden incluir memoria local (o privada). Para cualquiera de estos contextos, la sincronización se puede habilitar con primitivas habilitadas por hardware (como compare-and-swap o fetch-and-add) . Para máquinas que no tienen dicho soporte de hardware, se pueden usar bloqueos y los datos se pueden "intercambiar" entre procesadores (o, más generalmente, procesos o hilos ) depositando los datos compartibles en un área de memoria compartida. Cuando el hardware no admite memoria compartida, empaquetar los datos como un "mensaje" suele ser la forma más eficiente de programar computadoras de memoria compartida (lógicamente) con un gran número de procesadores, donde la memoria física es local a los procesadores y el acceso a la memoria de otro procesador lleva más tiempo. SPMD en una máquina de memoria compartida se puede implementar mediante procesos estándar (pesados) o hilos (ligeros).

El procesamiento paralelo de memoria compartida (tanto el procesamiento paralelo simétrico , SMP, como el acceso a memoria no uniforme , NUMA) ofrece al programador un espacio de memoria común y la posibilidad de paralelizar la ejecución. Con el modelo SPMD (de IBM), los procesadores (o procesos) que cooperan siguen diferentes rutas a través del programa, utilizando directivas paralelas ( directivas de paralelización y sincronización , que pueden utilizar operaciones de comparación e intercambio y de búsqueda y adición en variables de sincronización de memoria compartida), y realizan operaciones sobre datos en la memoria compartida ("datos compartidos"); los procesadores (o procesos) también pueden acceder y realizar operaciones sobre datos en su memoria local ("datos privados"). En cambio, con los enfoques de bifurcación y unión, el programa comienza a ejecutarse en un procesador y la ejecución se divide en una región paralela, que se inicia cuando se encuentran directivas paralelas; en una región paralela, los procesadores ejecutan una tarea paralela sobre datos diferentes. Un ejemplo típico es el bucle DO paralelo, donde diferentes procesadores trabajan en partes separadas de los arreglos involucrados en el bucle. Al final del bucle, la ejecución se sincroniza (con barreras suaves o duras [ 6 ] ), y los procesadores (procesos) continúan a la siguiente sección disponible del programa para ejecutar. El SPMD (de IBM) se ha implementado en la interfaz estándar actual para el multiprocesamiento de memoria compartida, OpenMP , que utiliza multihilo, generalmente implementado por procesos ligeros, llamados hilos .

Combinación de niveles de paralelismo

Los ordenadores actuales permiten aprovechar múltiples modos de procesamiento paralelo simultáneamente para obtener el máximo efecto combinado. Un programa de memoria distribuida que utiliza MPI puede ejecutarse en un conjunto de nodos. Cada nodo puede ser un ordenador de memoria compartida y ejecutarse en paralelo en múltiples CPU mediante OpenMP. Dentro de cada CPU, se utilizan instrucciones vectoriales SIMD (generalmente generadas automáticamente por el compilador) y la ejecución de instrucciones superescalares (generalmente gestionada de forma transparente por la propia CPU), como la segmentación y el uso de múltiples unidades funcionales paralelas, para maximizar la velocidad de cada CPU.

Implementaciones

MPI se usa comúnmente para implementar SPMD. Como se mencionó anteriormente, es adecuado para sistemas de memoria distribuida (varias máquinas), pero también funciona en escenarios de memoria compartida (varios núcleos). [ 9 ]

GPU y otros aceleradores

La mayoría de los sombreadores gráficos se escriben en un modelo de programación SPMD: el código describe una operación en un solo elemento. El compilador de sombreadores convierte el código en código paralelo utilizando las capacidades de paralelismo que ofrece el hardware (múltiples unidades SIMD en el caso de la mayoría de las GPU, múltiples unidades SIMT en el caso de las GPU de Nvidia). CUDA también sigue un modelo SPMD/SIMT. [ 10 ] Al dirigirse a hardware SIMD, el flujo de control se asigna normalmente a las operaciones SIMD mediante predicado , que restringe qué partes de un registro vectorial se modifican utilizando una máscara . [ 11 ] [ 12 ] Las GPU generalmente no tienen un espacio de direcciones unificado ; en cambio, hay varios niveles de memoria disponibles, de los cuales solo algunos se comparten entre los programas de sombreado. [ 13 ]

En las bibliotecas de aprendizaje automático Jax y PyTorch, SPMD se utiliza para distribuir el trabajo ( fragmento ) entre múltiples dispositivos, ya sea de forma automática o manual. [ 14 ] [ 15 ] Al hacer que todos los dispositivos ejecuten lo que es funcionalmente el mismo programa, la distribución automática del trabajo se vuelve mucho más fácil y se reduce la necesidad de comunicación entre dispositivos. [ 16 ]

Clang ofrece un modo de generación de código SPMD para su soporte de descarga OpenMP además del modo regular. [ 17 ] [ 18 ] La parte OpenCL de Clang considera que un objetivo es SPMD si el hardware puede generar múltiples elementos de trabajo sobre la marcha. [ 19 ]

Núcleo de CPU único (SPMD en SIMD)

Intel IPSC (Implicit SPMD Program Compiler) es un compilador de código abierto para programas SPMD escritos en un dialecto de C. Convierte programas de entrada, escritos en un modelo SPMD aparentemente de un solo hilo, en código SIMD eficiente para x86 (SSE2 a AVX512) o ARM (NEON), o código SIMD para GPU Intel. [ 11 ] La mayor parte de IPSC fue escrita por Matt Pharr. Según él, IPSC fue diseñado para producir un compilador que generara buen código de vector amplio para arquitecturas tipo Larrabee . La vectorización automática resultó demasiado frágil para un uso fiable, por lo que se buscó una solución similar a un sombreador. [ 10 ] [ 12 ]

La biblioteca NSIMD ofrece una interfaz SPMD, similar en concepto a la de IPSC. Está dirigida a SIMD escalar, x86 (SSE2 a AVX-512), ARM (NEON o SVE), POWERPC VMX/VSX, CUDA, ROCm y OneAPI. [ 20 ]

SPMD-on-SIMD (similar a IPSC) se ha demostrado académicamente en LLVM , [ 21 ] [ 22 ] pero ninguno ha sido aceptado en LLVM oficial hasta marzo de 2026.

Historia

El acrónimo SPMD, que significa "Single-Program Multiple-Data" (Programa Único, Datos Múltiples), se ha utilizado para describir dos modelos computacionales diferentes para aprovechar la computación paralela, debido a que ambos términos son extensiones naturales de la taxonomía de Flynn. [ 7 ] Los dos grupos de investigadores desconocían que el otro utilizara el término SPMD para describir de forma independiente diferentes modelos de programación paralela.

El término SPMD fue propuesto por primera vez en 1983 por Michel Auguin (Universidad de Niza Sophia-Antipolis) y François Larbey (Thomson/Sintra) en el contexto de la computadora paralela OPSILA y en el contexto de un enfoque de modelo computacional de datos paralelos de bifurcación y unión. [ 1 ] Esta computadora constaba de un maestro (procesador controlador) y procesadores SIMD (o modo de procesador vectorial, como propuso Flynn). En el modelo SPMD de Auguin, la misma tarea (paralela) (" mismo programa ") se ejecuta en diferentes procesadores (SIMD) (" operando en modo de sincronización ") [ 1 ] que actúan sobre una parte ("segmento") del vector de datos. Específicamente, su artículo de 1985 [ 2 ] y otros [ 3 ] [ 1 ] afirmaron:

Consideramos el modo de operación SPMD (Programa Único, Datos Múltiples). Este modo permite la ejecución simultánea de la misma tarea (una por procesador), pero impide el intercambio de datos entre procesadores. El intercambio de datos solo se realiza en el modo SIMD mediante asignaciones vectoriales. Suponemos que las sincronizaciones se suman a las conmutaciones entre los modos de operación SIMD y SPMD utilizando primitivas globales de bifurcación y unión.

A partir de la misma época (finales de 1983 - principios de 1984), Frederica Darema (en IBM en ese momento, y parte del grupo RP3) propuso el término SPMD para definir un modelo computacional SPMD diferente que ella propuso, [ 6 ] [ 5 ] [ 4 ] como un modelo de programación que en los años intermedios se ha aplicado a una amplia gama de computadoras de alto rendimiento de propósito general (incluido RP3 - el prototipo de procesador paralelo de investigación de IBM de 512 procesadores) y ha dado lugar a los estándares actuales de computación paralela. El modelo de programación SPMD (de IBM) asume una multiplicidad de procesadores que operan de forma cooperativa, todos ejecutando el mismo programa pero pueden tomar diferentes rutas a través del programa en función de las directivas de paralelización integradas en el programa: [ 6 ] [ 5 ] [ 4 ] [ 23 ] [ 24 ]

Todos los procesos que participan en la computación paralela se crean al inicio de la ejecución y permanecen en existencia hasta el final... [los procesadores/procesos] ejecutan diferentes instrucciones y actúan sobre diferentes datos... la tarea [(trabajo)] que debe realizar cada proceso se asigna dinámicamente... [es decir, los procesos] se autoprograman para ejecutar diferentes instrucciones y actuar sobre diferentes datos [así que se autoasignan para cooperar en la ejecución de tareas seriales y paralelas (así como tareas de replicación) en el programa].

El concepto de proceso generalizó el término procesador en el sentido de que múltiples procesos pueden ejecutarse en un procesador (para, por ejemplo, explotar mayores grados de paralelismo para mayor eficiencia y equilibrio de carga). El modelo (IBM) SPMD fue propuesto por Darema como un enfoque diferente y más eficiente que el fork-and-join que seguían todos los demás en la comunidad en ese momento; también es más general que un simple modelo computacional de "paralelo de datos" y puede abarcar fork-and-join (como una implementación de subcategoría). El contexto original del (IBM) SPMD fue la computadora RP3 (el prototipo de procesador paralelo de investigación de IBM de 512 procesadores), que admitía computación de propósito general, con memoria distribuida y (lógicamente) compartida. [ 23 ] El modelo (IBM) SPMD fue implementado por Darema y colegas de IBM en EPEX (Environment for Parallel Execution), uno de los primeros entornos de programación prototipo. [ 6 ] [ 5 ] [ 4 ] [ 23 ] [ 24 ] [ 25 ] La efectividad del (IBM) SPMD se demostró para una amplia clase de aplicaciones, [ 23 ] [ 4 ] y se implementó en IBM FORTRAN en 1988, [ 26 ] el primer producto de proveedor en programación paralela; y en MPI (1991 en adelante), OpenMP (1997 en adelante) y otros entornos que han adoptado y citan el modelo computacional (IBM) SPMD.

A finales de la década de 1980, existían muchos ordenadores distribuidos con bibliotecas de paso de mensajes propietarias. El primer estándar SPMD fue PVM . El estándar de facto actual es MPI .

Las directivas paralelas de Cray fueron un predecesor directo de OpenMP .

Referencias

  1. 1 2 3 4 M. Auguin; F. Larbey (1983). "OPSILA: un SIMD avanzado para análisis numérico y procesamiento de señales". Microprocesamiento y microprogramación: EUROMICRO  ; Actas del simposio  ; Microcomputadoras: desarrollos en la industria, los negocios y la educación. 13-16 de septiembre de 1983. Ámsterdam: North-Holland. ISBN 0-444-86742-2.
  2. 1 2 M. Auguin; F. Labrey (1985). "Una máquina SIMD multiprocesador: OPSILA". En K. Waldschmidt; B. Myhrhaug (eds.). Microcomputadoras, uso y diseño . Ámsterdam: North-Holland. ISBN 0-444-87835-1.
  3. 1 2 Auguin, M.; Boeri, F.; Dalban, JP; Vincent-Carrefour, A. (1987). "Experiencia con una arquitectura multiprocesador SIMD/SPMD". Multiprocessing and Microprogramming . 21 ( 1– 5): 171– 178. doi : 10.1016/0165-6074(87)90034-2 .
  4. 1 2 3 4 5 Darema, Frederica (2001). "El modelo SPMD: pasado, presente y futuro". Avances recientes en máquinas virtuales paralelas e interfaz de paso de mensajes . Notas de clase en ciencias de la computación. Vol. 2131. pág. 1. doi : 10.1007/3-540-45417-9_1 . ISBN   978-3-540-42609-7.
  5. 1 2 3 4 F. Darema-Rogers; DA George; VA Norton; GF Pfister (23 de enero de 1985). "Un entorno paralelo de VM". Informe de investigación de IBM RC 11225 (Informe). Centro de investigación IBM TJ Watson.
  6. 1 2 3 4 5 Darema, F.; George, DA; Norton, VA; Pfister, GF (1988). "Un modelo computacional de un solo programa y múltiples datos para EPEX/FORTRAN". Journal of Parallel Computing . 7 : 11– 24. doi : 10.1016/0167-8191(88)90094-4 .
  7. 1 2 Flynn, Michael (1972). "Algunas organizaciones informáticas y su eficacia" (PDF) . IEEE Transactions on Computers . C-21 (9): 948– 960. doi : 10.1109/TC.1972.5009071 . S2CID 18573685 . 
  8. ↑ Flynn, Michael J. (septiembre de 1972). "Algunas organizaciones informáticas y su eficacia" (PDF) . IEEE Transactions on Computers . C-21 (9): 948–960 . doi : 10.1109/TC.1972.5009071 .
  9. ↑ Strout, MM; Kreaseck, B.; Hovland, PD (2006). "Análisis del flujo de datos para programas MPI": 175– 184. doi : 10.1109/ICPP.2006.32 .{{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  10. 1 2 "La historia de ISPC: orígenes (parte 1)" . pharr.org . 2018.
  11. 1 2 "Guía del usuario de Intel® ISPC § El modelo de ejecución paralela de ISPC" . ispc.github.io .
  12. 1 2 Pharr, Matt; Mark, William R. (mayo de 2012). ispc: Un compilador SPMD para programación de CPU de alto rendimiento (PDF) . 2012 Innovative Parallel Computing (InPar). pp. 1– 13. doi : 10.1109/InPar.2012.6339601 . 
  13. ↑ "Lenguaje de sombreado WebGPU" . www.w3.org .
  14. ↑ "Guía del usuario de PyTorch/XLA SPMD — Documentación maestra de PyTorch/XLA" . docs.pytorch.org .
  15. ↑ "Introducción a la programación paralela — Documentación de JAX" . docs.jax.dev .
  16. ^ Xu, Yuanzhong; Lee, Hyouk Joong; Chen, Dehao; Hechtman, Blake; Huang, Yanping; Joshi, Rahul; Krikún, Maxim; Lepikhin, Dmitry; Ly, Andy; Maggioni, Marcello; Pang, Ruoming; Shazeer, Noam; Wang, Shibo; Wang, Tao; Wu, Yonghui; Chen, Zhifeng (23 de diciembre de 2021), GSPMD: paralelización general y escalable para gráficos de computación de aprendizaje automático , arXiv, doi : 10.48550/arXiv.2105.04663
  17. ↑ "Soporte para OpenMP — Documentación de Clang 14.0.0" . releases.llvm.org .
  18. ↑ "LLVM/OpenMP Runtimes" . GitHub .
  19. ↑ "Manual del usuario del compilador Clang" . Para destinos "no SPMD" que no pueden generar múltiples elementos de trabajo sobre la marcha utilizando hardware, lo que cubre prácticamente todos los dispositivos que no son GPU, como CPU y DSP.
  20. ↑ "Documentación de NSIMD" . agenium-scale.github.io .
  21. ↑ Kandiah, Vijay; Lustig, Daniel; Villa, Oreste; Nellans, David; Hardavellas, Nikos (17 de febrero de 2023). Parsimonia: Habilitación de la programación SIMD/Vectorial en flujos de compiladores estándar . CGO 2023: Actas del 21.º Simposio Internacional ACM/IEEE sobre Generación y Optimización de Código. págs. 186–198 . doi : 10.1145/3579990.3580019 . 
  22. ↑ Kruppe, Robin; Oppermann, Julian; Sommer, Lukas; Koch, Andreas (febrero de 2019). Extendiendo LLVM para vectorización SPMD ligera: uso sencillo de instrucciones SIMD y vectoriales desde cualquier lenguaje . Simposio internacional IEEE/ACM de 2019 sobre generación y optimización de código (CGO). págs. 278–279 . doi : 10.1109/CGO.2019.8661165 . 
  23. 1 2 3 4 Darema, Frederica (1988). "Entorno de aplicaciones para el prototipo de procesador paralelo de investigación de IBM (RP3)". Supercomputing . Lecture Notes in Computer Science. Vol. 297. pp. 80–95 . doi : 10.1007/3-540-18991-2_6 . ISBN   978-3-540-18991-6.
  24. 1 2 Darema, Frederica (1986). "Desarrollo de aplicaciones paralelas para sistemas de memoria compartida". Informe de investigación de IBM RC12229 (Informe). Yorktown Heights, NY: Centro de investigación IBM TJ Watson.
  25. ↑ JM Stone; F. Darema-Rogers; VA Norton; GF Pfister (30 de septiembre de 1985). "Introducción al preprocesador Fortran VM/EPEX". Informe de investigación de IBM RC11407 (Informe). Yorktown Heights, NY: Centro de investigación IBM TJ Watson.
  26. ↑ Toomey, LJ; Plachy, EC; Scarborough, RG; Sahulka, RJ; Shaw, JF; Shannon, AW (1988). "IBM Parallel FORTRAN". IBM Systems Journal . 27 (4): 416– 435. doi : 10.1147/sj.274.0416 .
  • Gestión de trabajos en paralelo y paso de mensajes
  • Programa único, flujo de datos múltiples. Archivado el 4 de junio de 2004 en Wayback Machine.
  • SPMD
  • Programación de memoria distribuida. Archivado el 13 de diciembre de 2013 en Wayback Machine.
Lecturas relacionadas
6 articulos
Simulación por computadoraComputaciónLa informática es cualquier actividad orientada a objetivos que requiera, se beneficie o cree maquinaria informática . [1] Incluye el estudio y la ...Computación paralelaComputación paralelaLa computación paralela es un tipo de computación en el que muchos cálculos o procesos se llevan a cabo simultáneamente. [1] Los problemas grandes ...Proceso (informática)Proceso (informática)En informática , un proceso es la instancia de un programa informático que se ejecuta mediante uno o varios subprocesos . Existen muchos modelos de...Múltiples instrucciones, múltiples datosMúltiples instrucciones, múltiples datosEn informática , la técnica de múltiples instrucciones, múltiples datos ( MIMD ) se emplea para lograr paralelismo. Las máquinas que utilizan MIMD ...Paralelismo de datosParalelismo de datosEl paralelismo de datos es la paralelización entre múltiples procesadores en entornos de computación paralela . Se centra en la distribución de los...Memoria compartida distribuidaMemoria compartida distribuidaEn informática , la memoria compartida distribuida ( DSM ) es una forma de arquitectura de memoria donde las memorias separadas físicamente pueden ...