Domande e risposte esame Calcolo parallelo

Analisi delle fasi di lavoro

Individuiamo le fasi, in questo caso vogliamo trovare QUANTI PROCESSORIlavorano per OGNI FASE.

1 fase (è la stessa della 1 strategia)

Si tratta di una fase tutta parallela, in quanto ogni unità processanteeffettuerà le proprie somme. In particolare, ogni p farà nloc-1 somme,cioè 4-1= 3 somme. Siccome ogni processore effettua 3 somme, edabbiamo 8 processori, nella prima fase effettuiamo 3x8=24 somme delle31 totali. Dunque, la parte parallela a8 = 24/31. Possiamo già calcolareap/p = a8/8 = 3/31. nb: con la legge di WAG la parte parallela non vienepiù indicata come (1-a) ma come ap. Infatti, non indica tutte le operazioniparallele ma solo quelle eseguite con parallelismo totale. nb: non c’ènessuna fase in cui lavorano contemporaneamente 7, 6, o 5processor/core. Quindi possiamo porre i loro valori a 0.

2 fase

Si tratta di una fase che avviene parzialmente in parallelo. Infatti comeben ricordiamo, al passo

Successivamente solo metà dei processori del passo precedente lavorano alle somme parziali, e così fino alla fine. In questo caso, se prima hanno lavorato 8 processori contemporaneamente, ora ne avremo 4. Ogni processore si occuperà di effettuare 1 somma.

Siccome ogni processore effettua 1 somma, ed abbiamo 4 processori, nella seconda fase effettuiamo 1x4=4 somme delle 31 totali. Dunque, la parte parallela a4 = 4/31. Quindi a4/4 = 1/31.

NB: non c'è nessuna fase in cui lavorano contemporaneamente 3 processori/core. Quindi possiamo porre il suo valore a 0. Infatti avremo:

3 fase

Anche questa è una fase che avviene parzialmente in parallelo. Prima avevamo 4 processori che lavoravano contemporaneamente, dunque ora ne avremo 2. Siccome ogni processore effettua 1 somma, ed abbiamo 2 processori, nella terza fase effettuiamo 1x2=2 somme delle 31 totali. Dunque, la parte parallela a2 = 2/31. Quindi a2/2 = 1/31.

4 fase (ultima)

Si tratta di una fase tutta sequenziale.

Quanto il processore Master si occupa di effettuare la somma totale. Nello specifico, il processore Master si occuperà di effettuare l'ultima somma. Dunque, la parte sequenziale a1 = 1/31. È importante che dalla somma della parte sequenziale e delle parti parallele otteniamo 1. Dunque: a8 + a7 + a6 + a5 + a4 + a3 + a2 + a1 deve essere = 1. Sapendo che a7, a6, a5, a3 = 0, possiamo tener conto solo di a8, a4, a2, a1, dunque: 24/31 + 4/31 + 2/31 + 1/31 = 31/31 = 1. Dunque abbiamo fatto bene i conti. Adesso ci rimane da calcolare lo Speed Up con WAG: - Classificazione di Flynn ? Nel corso del tempo si sono diffusi vari tipi di parallelismo, la cui implementazione avviene a livello hardware. Flynn dunque distinse varie architetture di calcolo, individuati dalla tassonomia di Flynn. Distinguiamo 3 tipologie principali di parallelismo: temporale, spaziale e asincrono. Inoltre, distinguiamo due tipi di parallelismo on-chip, in base a se il parallelismo è effettuato su unico chip (temporale, spaziale) o su più chip (asincrono).

Parallelismo temporale: Il parallelismo temporale è realizzato attraverso la tecnica della catena di montaggio, detto anche parallelismo pipeline. Consiste nel suddividere un lavoro in più fasi semplici ed affidare ogni fase ad una specifica unità, come se si trattasse di una catena di montaggio. Questa tipologia di architetture prende il nome di MISD (Multiple Instruction Single Data).

Parallelismo spaziale: Il parallelismo spaziale consiste nel fare seguire contemporaneamente a più unità la stessa azione ma su parti diverse. Questa tipologia di architetture prende il nome di SIMD (Single Instruction Multiple Data).

Parallelismo asincrono: Il parallelismo asincrono consiste nel fare seguire contemporaneamente a più unità azioni diverse su parti diverse. Questa tipologia di architetture prende il nome di MIMD (Multiple Instruction Multiple Data). In particolar modo, possiamo distinguere due

tipologie di calcolatori MIMD: Distributed Memory e Shared Memory.

1. DM (Distributed Memory): I calcolatori DM sono costituiti da più CPU ognuna delle quali ha una propria memoria. Si parla di "cluster" di processori. Distinguiamo due categorie di MIMD DM:
   • MMP (Massive Parallel Processors): architettura con CPU in PC indipendenti che lavorano in parallelo.
   • DSM (Distributed Shared Memory): architettura con CPU in PC indipendenti che lavorano in parallelo, ma dove uno dei PC ha una memoria condivisa virtuale.
2. SM (Shared Memory): I calcolatori SM sono costituiti da più CPU connesse ad una singola memoria principale in un'unica macchina. Ne distinguiamo due categorie:
   • SMP (Symmetric Multi processor): tutti i microprocessori sono identici, in quanto tutti i core hanno la stessa funzione (multicore Intel).
   • ASMP (Asymettric Multi processor): i microprocessori sono diversi, in quanto NON tutti i core hanno la stessa funzione (PS5).

Somma tra vettori con resto?

input viene dato N non divisibile per t, è necessario calcolare il resto di questa divisione.

Se il resto non è zero, tutti i core con identificativo strettamente minore del resto devono occuparsi di calcolare un elemento in più del vettore soluzione c.

La variabile step consente ad ogni core di sapere di quali elementi, dei vettori a e b, si deve occupare.

Rappresentazione grafica di MIMD ?

Somma N numeri, 2° strategia ?

II Strategia

Ad ogni passo, la metà dei core (rispetto al passo precedente) calcola un contributo alla somma parziale.

La somma finale (sumtot) sarà data dalla somma degli ultimi due contributi (ovviamente se NP è potenza di 2).

Prodotto matrice per matrice e complessità?

La complessità sarà sempre NxM sia per prodotto che somma.

Il prodotto matrice per matrice si ottiene moltiplicando due matrici.

cherispettano il criterio di congruenza delle dimensioni (il numero di colonne della prima matrice = numero righe della seconda). nb: basta ricordare mx n * n x p, dove i numeri interni devono essere uguali. Effettuiamo il prodotto scalare della i-esima riga di A per la j-esima colonna di B. Il risultato sarà una nuova matrice C che avrà m*p componenti.

- Direttive al compilatore ?

Le direttive si usano per creare un team e stabilire quali istruzioni devono essere eseguite in parallelo e come queste devono essere distribuite tra i thread. Tali direttive saranno inserite nelle zone concorrenti, con le relative clausole.

Le direttive sono identificate da “#pragma omp …”.

Per formare il team di thread e avviare l’esecuzione parallela si deve usare il costrutto parallel.

#pragma omp parallel [clause], [clause]..{structured_block}

Alla fine del blocco di istruzioni è sottintesa una barriera di sincronizzazione: tutti i thread si fermano ad aspettare che gli

altriabbiano completato l'esecuzione, prima di ritornare ad un'esecuzionesequenziale.

Esempio di clausole:

• default: mi permette di impostare automaticamente tutte le variabili ashared (shared), oppure specifico che dovrò essere io ad impostaremanualmente se una variabile è shared o private (none). Di default, laclausola defaulti è none.
• private: gli argomenti contenuti in list sono privati per ogni thread che liutilizza. Ciò significa che ogni thread avrà la propria copia delle variabiliprivate, che saranno tutte inizializzate a 0;
• shared: gli argomenti contenuti in list sono condivisi tra i thread delteam;
• firstprivate: come private, ma le variabili mantengono il valore cheavevano prima di entrare nella regione parallela (solo per parallel).
• lastprivate: come private, ma il valore delle variabili verrà aggiornato unavolta usciti dalla regione parallela (solo per for).
• reduction: gli argomenti contenuti in list verranno

combinati utilizzando l'operativo associativo specificato.

num_threads: imposta il numero dei thread che lavoreranno della direttiva.

Nello specifico, reduction si occupa di creare una copia private della variabile (var) per ogni thread. Terminata la regione parallela, la variabile var è ridotta ad una operazione atomica.

In altre parole, la variabile che viene esposta è un aggregato di tutte le var contenute in ogni thread. È utile perché evita il verificarsi di race condition sulla variabile.

Sottogruppi di MIMD, cosa sono e perché c'è necessità del sottogruppo DSM ?

DM (Distributed Memory)

I calcolatori DM sono costituiti da più CPU ognuna delle quali ha una propria memoria. Si parla di "cluster" di processori.

Distinguiamo due categorie di MIMD DM:

• MMP (Massive Parallel Processors): architettura con CPU in PC indipendenti che lavorano in parallelo;
• DSM (Distributed Shared Memory): architettura con CPU in

PC indipendenti che lavorano in parallelo, ma dove uno dei PC ha una memoria condivisa virtuale. C'è necessità del sottogruppo DSM per evitare l'overhead dello scambio delle informazioni. - Numero dei core ottimali per eseguire un algoritmo in parallelo, e perché? Il numero dei core ottimali per eseguire un algoritmo in parallelo è 2 e 4 core, perché all'aumentare dei core la dimensione deve aumentare di molto per avere una buona efficienza. È sconveniente. - Reti di interconnessione? Nelle macchine MIMD, CPU e memorie possono essere collegate in diverso modo a seconda del tipo di problema e applicazione della macchina. In un calcolatore MIMD SM, la memoria e le CPU possono essere collegate con un bus singolo, con bus multipli oppure in modo indiretto. In un calcolatore MIMD DM, la memoria e le CPU possono essere collegate anche con schemi di connessione più complessi, come: - Analisi di speed up ed efficienza scalata ? Calcolo dello speed up e dell'efficienza scalata.Speed up scalata: Sp = T1/Tp ed è ideale quando Sp = p Calcolo dell'efficienza scalata: Ep = Sp/p Per effettuare un analisi, verifica se lo speed-up scalato aumenta con l'aumentare del numero di risorse di calcolo, e se l'efficienza scalata si avvicina a 1. Un algoritmo si dice scalabile se l'efficienza rimane costante al crescere del numero dei processori e della dimensione del problema, in un rapporto costante pari a: * la i in maiuscolo sta per Isoefficienza Tempo di esecuzione di un software ? In generale, il tempo richiesto per l'esecuzione di un software τ (tau) è: dove: - k: r