SPMD
| Instrucció Simple |
Múltiples Instruccions | |
|---|---|---|
| Dada Simple |
SISD | MISD |
| Múltiples Dades |
SIMD | MIMD |
En ciències de la computació, SPMD (acrònim de single program, multiple data, en anglès) és la tècnica més emprada per aconseguir paral·lelisme. SPMD és una subcategoria de MIMD (Multiple Instruction Stream, Multiple Data Stream).
SPMD està format per dues característiques que es poden estudiar per separat, la primera és Single Program (SP) el que determina que només es pot assignar un programa o procés a cada node que executi l'aplicació. La segona característica és Multiple Data (MD), que es refereix a la quantitat d'espai (cel·les) que es poden assignar a cada un dels nodes perquè siguin computades. El conjunt de cel·les a assignar per node depèn de l'aplicació, de la quantitat de cel·les i de l'estratègia de subdivisió per assignar-les. Finalment, obtenim que el concepte SPMD és l'assignació d'un conjunt de cel·les de còmput a cada un dels nodes, que executarà el mateix procés.[1]
Aquesta tècnica suposa que tots els processos executen el mateix codi, però les dades processades són diferents, és a dir, les tasques són dividides i executades simultàniament en els múltiples processadors disponibles amb diferents seccions de dades (entrades) amb l'objectiu de tenir resultats més ràpids.
L'estructura bàsica del SPMD és geomètrica regular amb interacció limitada espacialment. Aquesta estructura permet que les dades es distribueixin uniformement entre els processos on cadascun serà responsable de l'àrea de dades assignada del total de les dades d'entrada.[2]
SPMD acostuma a ser eficient si les dades estan ben distribuïdes en els processos, és a dir, si la càrrega de treball o la capacitat de còmput entre els diferents processos és heterogènia, llavors el paradigma necessita estratègies de load balancing (balanceig de càrrega), que permet adaptar la distribució de les dades durant l'execució.
Comparativa SPMD i SIMD
[modifica]En SPMD, múltiples processadors autònoms executen simultàniament el mateix programa en punts independents del conjunt de dades a processar. Amb SPMD, les tasques es poden executar amb processadors estàndards; SIMD requereix utilitzar processadors vectorials per a manipular les dades.
SPMD permet que les dades es distribueixin de forma uniforme entre els processadors, per tant, cada un es fa càrrec d'una àrea de dades definida. En SPMD els threads executen bàsicament el mateix programa amb diferents dades. Aquest paradigma ens permet executar un determinat nombre de dades simultàneament, tenint en compte la dependència d'aquestes i utilitzant tècniques de sincronització per assolir els resultats desitjats.[2]
En canvi, SIMD (acrònim de Single Instuction Multiple Data) es basa en càlculs simultanis, en paral·lel, però només en una única instrucció. S'utilitza en computadors amb múltiples elements de processament que realitzen la mateixa operació en diversos punts de dades simultàneament. Aquesta arquitectura neix degut a la necessitat d'aplicar repetidament una mateixa operació en grups de dades diferents.[3]
En SIMD la vectorizació és a nivell d'instrucció: cada instrucció de la CPU processa múltiples elements de dades. En SPMD el nivell és molt més alt on els processos o programes es divideixen en diferents processadors i operen amb múltiples conjunts de dades.
Memòria distribuïda
[modifica]SPMD, normalment, fa referència a la programació que passa missatges en arquitectures d'ordinadors de memòria distribuïda.
Una arquitectura de memòria distribuïda és una col·lecció d'ordinadors independents, anomenats nodes, on cada un d'ells té una interfície de xarxa (NI), inicia el seu propi programa, i es comunica amb els altres nodes a través de rutines d'enviament/recepció, és a dir, enviant i rebent missatges. Tota la comunicació i sincronització entre processadors es fa a través de missatges que passen per la NI (la sincronització de ‘barriers’ també es pot implementar per missatges). Tots els processadors d'un node estan connectats directament a la seva propia memòria i a la memòria cache, però qualsevol processador no pot accedir directament a la memòria d'un altre processador.[4]
Els missatges poden ser enviats per diversos mecanismes de comunicació. En són dos exemples, TCP/IP a través d'Ethernet, o interconnexions d'alta velocitat especialitzades, com Myrinet i Supercomputer Interconnect. Les seccions en sèrie del programa, en lloc de calcular el resultat en un node i enviar-lo cap als altres, implementen un càlcul idèntic per a tots.
Avui en dia, el programador no té cap influència sobre els detalls dels missatges que passen per interfícies estàndard, com són PVM i MPI.
Aquesta arquitectura pertany al model de programació MIMD (Multiple Instruction Stream, Multiple Data Stream). La memòria distribuïda és un estil de programació, majoritàriament, utilitzat en supercomputadors paral·lels, anant des de clústers casolans com el Beowulf, fins a clústers més grans de la Teragrid.
Memòria compartida
[modifica]En una màquina de memòria compartida (una màquina amb molts CPU que accedeixen al mateix espai de memòria), els missatges poden ser enviats posant els seus continguts sobre l'àrea de memòria compartida. Això significa que tot l'adreçament de la memòria principal és únic i els processadors poden accedir a totes les posicions de memòria. Aquesta molts cops és la manera més eficient per programar màquines amb memòria compartida amb un gran número de processadors, especialment sobre la màquina NUMA. El temps d'accés que tenen els processadors d'aquestes màquines a la memòria depèn de la ubicació de memòria, la mateixa direcció física en dos processadors fa referència a la mateixa ubicació en memòria.[5]
A diferència del SPMD, el multiprocessament de la memòria compartida (tant el multiprocessament simètric, SMP, com l'accés no uniforme a la memòria, NUMA) presenta al programador un espai de memòria comú i la possibilitat de paral·lelitzar l'execució al fer que el programa prengui diferents camins en diferents processadors.
El programa comença a executar-se en un processador i l'execució es divideix en una regió paral·lela la qual s'inicia quan les directives paral·leles es troben actives. En una regió paral·lela, els processadors executen un sol programa amb diferentes dades. Un exemple és el bucle DO (la directiva PARALLEL DO permet especificar quins bucles ha de paral·lelitzar el compilador). En aquest bucle hi ha diferents processadors treballant en parts separades de les matrius involucrades en el bucle. Al final del cicle, l'execució es sincronitza, només un processador continua i els altres esperen. La interfície estàndard actual pel multiprocessament de memòria compartida és OpenMP.[6]
Combinació de nivells de paral·lelisme
[modifica]Els computadors actuals permeten l'explotació de diversos modes paral·lels al mateix temps per obtenir un màxim efecte combinat. Un programa de memòria distribuïda utilitzant MPI es pot executar sobre un conjunt de nodes. Cada node deu ser un ordinador de memòria compartida que executa en paral·lel sobre múltiples CPU utilitzant OpenMP. Dins de cada CPU, les instruccions vectorials SIMD (normalment generades automàticament pel compilador) i l'execució de les instruccions superescalar (generalment de forma transparent controlat pel mateix CPU), com el pipelining i l'ús de múltiples unitats funcionals paral·leles, s'utilitzen per arribar a una velocitat màxima del CPU.
Història
[modifica]SPMD (Single Program, Multiple Data) va ser proposat originàriament el 1983 per Michael Auguin (Universitat de Niza Sophia-Antipolis) i François Larbey (Thomson / Sintra) en l'ordinador paral·lel OPSILA.
El següent cop va ser el 1984 per Frederica Darema de l'IBM (International Business Machines Corporation) per màquines altament paral·leles com el RP3 (la investigació del prototip del procesador paral·lel de IBM), en una nota publicada de IBM.
A finals dels anys 80, hi havia molts ordinadors distribuïts amb biblioteques pròpies pel traspàs de missatges. El primer estàndard de SPMD va ser el PVM (Parallel Virtual Machine), tot i això actualment és el MPI (Message Passing Interface).
MPI, defineix la sintaxi i la semàntica de les funcions contingudes a una biblioteca de traspàs de missatges dissenyada per ser utilitzada en programes que exploren l'existència de múltiples processadors.
Les directrius paral·leles de Cray (fabricant nord-americà de supercomputadors) van ser un predecessor directe del OpenMP (Open Multi-Processing).
OpenMP és una interfície de programació d'aplicacions (API) que suporta programació multiprocés amb memòria compartida multi-plataforma en C/C++ i Fortran a moltes arquitectures, incloent les plataformes Unix i Microsoft Windows.
Referències
[modifica]- ↑ «Aplicaciones Single Program Multiple Data (SPMD) en ambientes distribuidos».
- ↑ 2,0 2,1 «Factores de Rendimiento Asociados a SPMD».
- ↑ «Arquitectura SIMD». Arxivat de l'original el 2015-10-10. [Consulta: 31 març 2020].
- ↑ «Distributed Memory Architecture». Arxivat de l'original el 2020-02-03. [Consulta: 30 març 2020].
- ↑ «Sistemas Multiprocesador de Memoria Compartida Comerciales».
- ↑ «Introducción a las arquitecturas paralelas». Arxivat de l'original el 2020-09-29. [Consulta: 30 març 2020].
Enllaços externs
[modifica]- OPSILA https://ieeexplore.ieee.org/document/192215
- Article del Michael Auguin al 1987 https://www.researchgate.net/publication/256413978_Experience_using_a_SIMDSPMD_multiprocessor_architecture