Macchine parallele ad accesso casuale

Parallel Random Access Machines (PRAM)è un modello, che è considerato per la maggior parte degli algoritmi paralleli. Qui, più processori sono collegati a un singolo blocco di memoria. Un modello PRAM contiene:

  • Un insieme di processori di tipo simile.

  • Tutti i processori condividono un'unità di memoria comune. I processori possono comunicare tra di loro solo attraverso la memoria condivisa.

  • Un'unità di accesso alla memoria (MAU) collega i processori con la singola memoria condivisa.

Qui, n numero di processori su cui è possibile eseguire operazioni indipendenti nnumero di dati in una particolare unità di tempo. Ciò può comportare l'accesso simultaneo alla stessa posizione di memoria da parte di processori diversi.

Per risolvere questo problema, i seguenti vincoli sono stati applicati al modello PRAM:

  • Exclusive Read Exclusive Write (EREW) - Qui non è consentito a due processori di leggere o scrivere nella stessa posizione di memoria contemporaneamente.

  • Exclusive Read Concurrent Write (ERCW) - Qui non è consentito a due processori di leggere dalla stessa posizione di memoria allo stesso tempo, ma possono scrivere nella stessa posizione di memoria allo stesso tempo.

  • Concurrent Read Exclusive Write (CREW) - Qui tutti i processori possono leggere dalla stessa posizione di memoria allo stesso tempo, ma non sono autorizzati a scrivere nella stessa posizione di memoria allo stesso tempo.

  • Concurrent Read Concurrent Write (CRCW) - Tutti i processori possono leggere o scrivere nella stessa posizione di memoria contemporaneamente.

Esistono molti metodi per implementare il modello PRAM, ma i più importanti sono:

  • Modello di memoria condivisa
  • Modello di passaggio del messaggio
  • Modello parallelo dei dati

Modello di memoria condivisa

La memoria condivisa enfatizza control parallelism che su data parallelism. Nel modello di memoria condivisa, più processi vengono eseguiti su processori diversi in modo indipendente, ma condividono uno spazio di memoria comune. A causa di qualsiasi attività del processore, se c'è qualche cambiamento in una posizione di memoria, è visibile al resto dei processori.

Poiché più processori accedono alla stessa posizione di memoria, può accadere che in un determinato momento, più di un processore acceda alla stessa posizione di memoria. Supponiamo che uno stia leggendo quella posizione e l'altro stia scrivendo in quella posizione. Può creare confusione. Per evitare ciò, alcuni meccanismi di controllo, comelock / semaphore, è implementato per garantire l'esclusione reciproca.

La programmazione della memoria condivisa è stata implementata nel seguente:

  • Thread libraries- La libreria di thread consente più thread di controllo che vengono eseguiti contemporaneamente nella stessa posizione di memoria. La libreria di thread fornisce un'interfaccia che supporta il multithreading tramite una libreria di subroutine. Contiene subroutine per

    • Creazione e distruzione di thread
    • Pianificazione dell'esecuzione del thread
    • passaggio di dati e messaggi tra i thread
    • salvataggio e ripristino dei contesti dei thread

Esempi di librerie di thread includono: thread SolarisTM per Solaris, thread POSIX come implementati in Linux, thread Win32 disponibili in Windows NT e Windows 2000 e thread JavaTM come parte del JavaTM Development Kit (JDK) standard.

  • Distributed Shared Memory (DSM) Systems- I sistemi DSM creano un'astrazione della memoria condivisa su un'architettura debolmente accoppiata al fine di implementare la programmazione della memoria condivisa senza supporto hardware. Implementano librerie standard e utilizzano le funzionalità avanzate di gestione della memoria a livello utente presenti nei sistemi operativi moderni. Gli esempi includono Tread Marks System, Munin, IVY, Shasta, Brazos e Cashmere.

  • Program Annotation Packages- Questo è implementato sulle architetture che hanno caratteristiche di accesso alla memoria uniformi. L'esempio più notevole di pacchetti di annotazioni di programmi è OpenMP. OpenMP implementa il parallelismo funzionale. Si concentra principalmente sulla parallelizzazione dei cicli.

Il concetto di memoria condivisa fornisce un controllo di basso livello del sistema di memoria condivisa, ma tende ad essere noioso ed errato. È più applicabile alla programmazione del sistema che alla programmazione dell'applicazione.

Meriti della programmazione con memoria condivisa

  • Lo spazio degli indirizzi globale offre un approccio di programmazione intuitivo alla memoria.

  • A causa della vicinanza della memoria alla CPU, la condivisione dei dati tra i processi è veloce e uniforme.

  • Non è necessario specificare distintamente la comunicazione dei dati tra i processi.

  • Il sovraccarico della comunicazione di processo è trascurabile.

  • È molto facile da imparare.

Demeriti della programmazione della memoria condivisa

  • Non è portatile.
  • La gestione della località dei dati è molto difficile.

Modello di passaggio del messaggio

Il passaggio dei messaggi è l'approccio di programmazione parallela più comunemente utilizzato nei sistemi di memoria distribuita. Qui, il programmatore deve determinare il parallelismo. In questo modello, tutti i processori hanno una propria unità di memoria locale e scambiano dati attraverso una rete di comunicazione.

I processori utilizzano librerie di passaggio di messaggi per la comunicazione tra di loro. Insieme ai dati inviati, il messaggio contiene i seguenti componenti:

  • L'indirizzo del processore da cui viene inviato il messaggio;

  • Indirizzo iniziale della posizione di memoria dei dati nel processore mittente;

  • Tipo di dati dei dati di invio;

  • Dimensioni dei dati di invio;

  • L'indirizzo del processore a cui viene inviato il messaggio;

  • Indirizzo iniziale della posizione di memoria per i dati nel processore ricevente.

I processori possono comunicare tra loro tramite uno dei seguenti metodi:

  • Comunicazione punto a punto
  • Comunicazione collettiva
  • Interfaccia di passaggio dei messaggi

Comunicazione punto a punto

La comunicazione punto a punto è la forma più semplice di trasmissione di messaggi. Qui, un messaggio può essere inviato dal processore mittente a un processore ricevente mediante una delle seguenti modalità di trasferimento:

  • Synchronous mode - Il messaggio successivo viene inviato solo dopo aver ricevuto una conferma che il suo messaggio precedente è stato consegnato, per mantenere la sequenza del messaggio.

  • Asynchronous mode - Per inviare il messaggio successivo, non è richiesta la ricezione della conferma di consegna del messaggio precedente.

Comunicazione collettiva

La comunicazione collettiva coinvolge più di due processori per il passaggio dei messaggi. Le seguenti modalità consentono comunicazioni collettive:

  • Barrier - La modalità barriera è possibile se tutti i processori inclusi nelle comunicazioni eseguono un particolare bock (noto come barrier block) per il passaggio dei messaggi.

  • Broadcast - La trasmissione è di due tipi:

    • One-to-all - Qui, un processore con una singola operazione invia lo stesso messaggio a tutti gli altri processori.

    • All-to-all - Qui, tutti i processori inviano un messaggio a tutti gli altri processori.

I messaggi trasmessi possono essere di tre tipi:

  • Personalized - I messaggi univoci vengono inviati a tutti gli altri processori di destinazione.

  • Non-personalized - Tutti i processori di destinazione ricevono lo stesso messaggio.

  • Reduction - Nella trasmissione di riduzione, un processore del gruppo raccoglie tutti i messaggi da tutti gli altri processori del gruppo e li combina in un unico messaggio a cui possono accedere tutti gli altri processori del gruppo.

Meriti del passaggio del messaggio

  • Fornisce un controllo di basso livello del parallelismo;
  • È portatile;
  • Meno soggetto a errori;
  • Meno overhead nella sincronizzazione parallela e nella distribuzione dei dati.

Demeriti del passaggio di messaggi

  • Rispetto al codice di memoria condivisa parallelo, il codice di passaggio dei messaggi generalmente richiede un sovraccarico software maggiore.

Librerie di passaggio di messaggi

Esistono molte librerie di passaggio di messaggi. Qui, discuteremo due delle librerie di passaggio di messaggi più utilizzate:

  • Message Passing Interface (MPI)
  • Macchina virtuale parallela (PVM)

Message Passing Interface (MPI)

È uno standard universale per fornire la comunicazione tra tutti i processi simultanei in un sistema di memoria distribuita. La maggior parte delle piattaforme di calcolo parallelo comunemente utilizzate fornisce almeno un'implementazione dell'interfaccia di passaggio dei messaggi. È stato implementato come raccolta di funzioni predefinite chiamatelibrary e possono essere richiamati da linguaggi come C, C ++, Fortran, ecc. Le MPI sono sia veloci che portatili rispetto alle altre librerie di passaggio di messaggi.

Merits of Message Passing Interface

  • Funziona solo su architetture di memoria condivisa o architetture di memoria distribuita;

  • Ogni processore ha le proprie variabili locali;

  • Rispetto ai computer con memoria condivisa di grandi dimensioni, i computer con memoria distribuita sono meno costosi.

Demerits of Message Passing Interface

  • Sono necessarie ulteriori modifiche alla programmazione per l'algoritmo parallelo;
  • A volte è difficile eseguire il debug; e
  • Non funziona bene nella rete di comunicazione tra i nodi.

Macchina virtuale parallela (PVM)

PVM è un sistema di trasmissione di messaggi portatile, progettato per connettere macchine host eterogenee separate per formare un'unica macchina virtuale. È una singola risorsa di calcolo parallelo gestibile. Grandi problemi computazionali come studi di superconduttività, simulazioni di dinamica molecolare e algoritmi di matrice possono essere risolti in modo più economico utilizzando la memoria e la potenza aggregata di molti computer. Gestisce tutto il routing dei messaggi, la conversione dei dati, la pianificazione delle attività nella rete di architetture di computer incompatibili.

Features of PVM

  • Molto facile da installare e configurare;
  • Più utenti possono utilizzare PVM contemporaneamente;
  • Un utente può eseguire più applicazioni;
  • È un piccolo pacchetto;
  • Supporta C, C ++, Fortran;
  • Per una data esecuzione di un programma PVM, gli utenti possono selezionare il gruppo di macchine;
  • È un modello di trasmissione di messaggi,
  • Calcolo basato sul processo;
  • Supporta un'architettura eterogenea.

Programmazione parallela dei dati

L'obiettivo principale del modello di programmazione parallela dei dati è l'esecuzione simultanea di operazioni su un set di dati. Il set di dati è organizzato in una struttura come un array, un ipercubo, ecc. I processori eseguono operazioni collettivamente sulla stessa struttura di dati. Ogni attività viene eseguita su una partizione diversa della stessa struttura dati.

È restrittivo, poiché non tutti gli algoritmi possono essere specificati in termini di parallelismo dei dati. Questo è il motivo per cui il parallelismo dei dati non è universale.

I linguaggi paralleli dei dati aiutano a specificare la scomposizione dei dati e la mappatura ai processori. Include anche istruzioni di distribuzione dei dati che consentono al programmatore di avere il controllo sui dati, ad esempio quali dati andranno su quale processore, per ridurre la quantità di comunicazione all'interno dei processori.