MIMD

MIMD (acrònim de multiple instruction, multiple data), en ciències de la computació, és una tècnica emprada per a aconseguir el paral·lelisme. Els ordinadors amb capacitat MIMD tenen una col·lecció de N-processadors individuals que funcionen asíncronament i estan estretament acoblats entre ells. L'arquitectura paral·lela MIMD és el tipus de processador més bàsic i més familiar. Aquesta arquitectura té diverses aplicacions a diverses àrees, es poden utilitzar en el disseny assistit per ordinador, el modelatge, la simulació, commutadors de comunicació, etc. En un moment donat, diferents processadors poden executar diferents instruccions amb diferents dades, és a dir, es poden utilitzar tantes instruccions i dades com processadors hi hagi.

Fig.1 Esquema MIMD

Michael J. Flynn és un informàtic que va proposar un mecanisme per classificar els ordinadors a l'any 1966. Va afirmar l'existència de 4 màquines depenent del paral·lelisme de cada una, el programa i les dades que utilitza. Les va separar en SISD, SIMD, MISD i MIMD. Aquests sistemes es van començar a utilitzar a principis dels anys 80.^{[1][2][3][4][5]}

Taxonomia de Flynn

	Instrucció Simple	Múltiples Instruccions
Dada Simple	SISD	MISD
Múltiples Dades	SIMD	MIMD
Aquesta caixa:

Característiques[6]

• Permeten executar diferents processos simultàniament.
• Es tracta de sistemes asíncrons. No tenen completa correspondència temporal amb el procés que els ha produït.
• No tenen rellotge central.
• Quan les unitats de procés reben dades d'una memòria no compartida reben el nom de Múltiple SISD o MSISD.
• Diferents elements d'informació s'assignen a diferents processadors.
• Cada processador MIMD treballa quasi intependentment de la resta.
• Poden ser utilitzats en aplicacions amb informació en paral·lel o amb tasques que s'executen en paral·lel.
• Cada processador té la seva pròpia unitat de control i la seva pròpia unitat funcional.

Models de memòria

Les màquines MIMD poden ser de memòria compartida, memòria distribuïda o distribuïda compartida, això depèn de com accedeixin a memòria.^[7][8]

Memòria compartida

Els processadors estan tots connectats a una memòria disponible globalment, és a dir, hi ha un espai d'adreçament compartit. Exemples són UMA (uniform memory access), COMA (cache only memory access).

Les computadores MIMD amb memòria compartida son sistemes coneguts com a SMP (symmetrical multi processing) on els múltiples processadors comparteixen un mateix sistema operatiu i memòria.

Esquema general de les arquitectures de memòria compartida

Memòria compartida basada en busos

Tots els processadors estan connectats a un bus que els connecta a la memòria. Aquesta configuració s'anomena memòria compartida basada en busos. Les màquines basades en busos poden tenir un altre bus que els permet comunicar-se directament. Aquest bus addicional s'utilitza per a la sincronització entre els processadors. Les màquines MIMD de memòria compartida basades en busos només poden donar suport a un petit nombre de processadors. Hi ha contenció entre els processadors per accedir a la memòria compartida, i aquest motiu les limita.

Memòria compartida ampliada

Les màquines MIMD amb memòria compartida amplia intenten evitar o reduir la contenció entre els processadors per a la memòria compartida mitjançant la subdivisió de la memòria en diverses unitats de memòria independents. Aquestes unitats de memòria estan connectades als processadors mitjançant una xarxa d'interconnexió. Les unitats de memòria es tracten com una memòria central unificada. Un tipus de xarxa d'interconnexió d'aquest tipus d'arquitectura és una xarxa de commutació de barres creuades (crossbar switching network). Una xarxa de commutació de barres creuades que uneix N processadors amb M unitats de memòria necessita N vegades M commutacions. No es tracta d'una configuració econòmicament factible per connectar un gran nombre de processadors.

Memòria compartida jeràrquica

Les màquines MIMD amb memòria compartida jeràrquica utilitzen una jerarquia de busos per proporcionar accés als processadors a la memòria dels altres. Els processadors de diferents taulers poden comunicar-se mitjançant busos. Els busos donen suport a la comunicació entre taulers. Amb aquest tipus d'arquitectura, la màquina pot suportar una gran quantitat de taulers. En informàtica, la memòria compartida és memòria a la qual es poden accedir simultàniament diversos programes amb la intenció de proporcionar comunicació entre ells o evitar còpies redundants. Segons el context, els programes es poden executar en un mateix processador o en diversos processadors separats.

Arquitectura

• Conjunt de processadors i mòduls de memòria.
• Qualsevol processador pot accedir directament a qualsevol mòdul de memòria mitjançant una xarxa d'interconnexió.
• El conjunt de mòduls de memòria defineix un espai d'adreces global que es comparteix entre els processadors.

Un avantatge clau d'aquest tipus d'arquitectura és que és molt fàcil de programar ja que no hi ha comunicacions explícites entre processadors amb comunicacions dirigides a través del magatzem de memòria global. Independentment de quants blocs de memòria s'utilitzin en ells i de com es connectin aquests blocs de memòria als processadors i els espais d'adreces d'aquests blocs de memòria, s'uneixen en un espai d'adreces global que és completament visible per a tots els processadors. del sistema de memòria compartida. L'emissió d'una certa adreça de memòria per part de qualsevol processador accedirà a la mateixa ubicació del bloc de memòria.

Memòria distribuïda

Tots els processadors tenen la seva memòria individual. Exemples són processador MPPA, COW (clúster d'ordinadors) i l'arquitectura NUMA. Aquests sistemes tenen la seva pròpia memòria local. Els processadors poden compartir informació només enviant missatges. Els ordinadors MIMD de memòria distribuïda són conegudes com a sistemes MPP (massively parallel processing) on múltiples processadors treballen en diferents parts d'un programa, amb el seu propi sistema operatiu i memòria.

Esquema general de les arquitectures de memòria distribuïda

Arquitectura

• Replica els parells de processador / memòria i els connecta mitjançant una xarxa d'interconnexió.
• El parell de processador / memòria s'anomena processament d'elements (PE).
• Cada processament d'elements (PE) pot interactuar entre ells mitjançant l'enviament de missatges.

Proporcionant a cada processador la seva pròpia memòria, l'arquitectura de memòria distribuïda evita els inconvenients de l'arquitectura de memòria compartida. Un processador només pot accedir a la memòria que hi està connectada directament. En cas que un processador requereixi dades que resideixen a la memòria del processador remot, el processador hauria d'enviar un missatge al processador remot, sol·licitant les dades necessàries. L'accés a la memòria local podria passar de manera més ràpida en contraposició a l'accés a les dades d'un processador remot. A més, si la distància física amb el processador remot és més gran, l'accés a les dades remotes requerirà més temps.

Memòria distribuïda compartida

És una partició de processadors que tenen accés a una memòria compartida comuna o sense canal compartit. Físicament cada processador es planteja la seva memòria local i s'interconecta amb altres processadors per mitjà d'un sistema d'alta velocitat, i veu totes les memòries de cada un com un espai de direccions globals.

Comparació SIMD[9]

Sigles	Single Instruction Multiple Data	Multiple Instruction Multiple Data
Facilitat de programació i depuració	Un únic programa	Múltiples comunicacions de programes
Rendiment	Menys eficient	Més eficient
Processament d'Elements (PE)	Operen sincrònicament	Operen de manera asíncrona
Requeriments de memòria del programa	Es guarda una còpia del programa	Cada PE guarda la seva còpia en el seu programa
Cost d'instrucció	Un descodificador en la unitat de control	Un descodificador en cada PE
Complexitat de les arquitectures	Simple	Complexa
Cost	Baix	Mitjà
Mida i rendiment	Escalable	Complex en mida i bo en rendiment
Declaracions condicionals	Depèn de les dades locals als processadors, totes les instruccions del bloc then s'han demetre, seguides de tot el bloc else	El flux d'instruccions múltiple permet una execució més eficaç d'instruccions condicionals (per exemple, if-else) perquè cada processador pot seguir de manera independent les dues rutes de decisions
Despeses generals de sincronització baixes	Implícites al programa	Explícites a les estructures de dades i operacions requerides
Despeses generals de sincronització de PE a PE baixes	Sincronització automàtica de totes les operacions “enviar” i “rebre”	Sincronització explícita i necessitat d'identificació de protocols