Università degli Studi di Napoli Federico II
Scuola Politecnica e delle Scienze di Base
Area Didattica Scienze MM.FF.NN.
Master di I° Livello in Tecnologie per il CAlcolo
Scientifico ad Alte Prestazioni - CASAP
Tesi di Master
Valutazione delle prestazioni di algoritmi paralleli
per il calcolo scientifico in ambienti con CPU
multi-core: Presentazione di un caso di studio
Relatori
Prof. Marco Lapegna
Anno Accademico 2012-2013
Candidato
Dott. Luigi Perillo
matr. Z62/000007
Indice Generale
Introduzione...............................................................................................................5
1 Parallelismo...........................................................................................................7
1.1 Architettura di Memoria.................................................................................8
1.2 Organizzazione della Memoria.....................................................................15
1.3 Modelli di programmazione parallela...........................................................20
1.4 Valutare algoritmi paralleli...........................................................................23
2 Problema affrontato.............................................................................................27
2.1 Descrizione Algoritmo..................................................................................30
2.2 Strategia di distribuzione dei dati.................................................................31
2.3 Test performance e stima errori....................................................................33
2.3.1 Test efficienza algoritmo.......................................................................34
2.3.2 Test stima errore....................................................................................40
3 Conclusioni.........................................................................................................43
Bibliografia..............................................................................................................45
Luigi Perillo Z62/000007
Pagina 2 di 45
Indice delle illustrazioni
Illustrazione 1: Schema Tassonomia di Flynn............................................................9
Illustrazione 2: Schema architettura SISD...............................................................10
Illustrazione 3: Schema architettura SIMD..............................................................12
Illustrazione 4: Schema architettura MISD..............................................................13
Illustrazione 5: Schema architettura MIMD............................................................14
Illustrazione 6: Architettura a memoria condivisa...................................................16
Illustrazione 7: Architettura a memoria distribuita...................................................17
Illustrazione 8: Architettura di Memoria Ibrida Condivisa-Distribuita....................19
Illustrazione 9: Griglia di comunicazione tra nodi...................................................29
Illustrazione 10: Grafico Speed Up, Redist 0...........................................................35
Illustrazione 11: Grafico Speed Up, Redist 1...........................................................36
Illustrazione 12: Grafico Efficienza Media, Redist 0...............................................38
Illustrazione 13: Grafico Efficienza Media, Redist 1...............................................39
Illustrazione 14: Grafico Errore stimato. Redist 0 (scala logaritmica).....................41
Illustrazione 15: Grafico Errore stimato. Redist 1 (scala logaritmica).....................42
Luigi Perillo Z62/000007
Pagina 3 di 45
Indice delle tabelle
Tabella 1: Tempi di esecuzione. Redist 0.................................................................34
Tabella 2: Tempi di esecuzione. Redist 1.................................................................34
Tabella 3: Speed Up medio su 3 esecuzioni. Redist 0..............................................35
Tabella 4: Speed Up medio su 3 esecuzioni. Redist 1..............................................36
Tabella 5: Efficienza media su 3 esecuzioni. Redist 0.............................................37
Tabella 6: Efficienza media su 3 esecuzioni. Redist 1.............................................38
Tabella 7: Errori Elaborazione. Redist 0..................................................................40
Tabella 8: Errori elaborazione. Redist 1...................................................................41
Luigi Perillo Z62/000007
Pagina 4 di 45
Introduzione
La crescente potenza di calcolo messa a disposizione dai moderni calcolatori ha
permesso di fronteggiare problemi numerici dalla complessità sempre maggiore in
tempi relativamente brevi.
In precedenza si puntava a migliorare le prestazioni dei processori, aumentando la
frequenza di clock, portando però in questo caso ad un consumo eccessivo dei
processori.
Per questo motivo, l'attenzione si è spostata verso lo sviluppo di processori multicore i quali a frequenze di clock decisamente ridotte permettono di avere prestazioni
simili, in alcuni casi anche superiori, ai più potenti processori single-core.
Lo scopo del lavoro svolto, è stato quello di approfondire una metodologia di
valutazione di funzioni per il calcolo scientifico, in ambiente computazionale basato
su CPU multi-core.
Negli ultimi trent'anni, diverse routine efficienti sono stati sviluppati per la
soluzione del problema sulla CPU tradizionali.
La maggior parte di essi, si basano su algoritmi adattativi, che permettono
un'elevata precisione con un costo computazionale ragionevole.
Nelle pagine che seguiranno si è cercato di capire le differenze e i vantaggi
nell'utilizzare l'elaborazione di codice parallela (multi-threads) confrontando i tempi
di esecuzione (al variare delle dimensioni dei dati di input, della strategia di
distribuzione dei dati e il numero di threads interessati nell'esecuzione), effettuando
una stima degli errori sui dati ottenuti.
La tesi si snoda nei seguenti capitoli:
✔ Capitolo 1: Propone una panoramica generale, sulla concetto di
Parallelizzazione, nonché una descrizione esclusivamente teorica, delle
architetture e delle organizzazioni di memoria e delle differenti strategie di
Luigi Perillo Z62/000007
Pagina 5 di 45
parallelizzazione disponibili attualmente.
Si riportano inoltre esempi di architetture parallele e gli indici di
classificazione per gli algoritmi paralleli.
✔ Capitolo 2: Descrive nel dettaglio il problema affrontato, e la metodologia
adoperata per la risoluzione. Descrive la classe di algoritmo, le strategie
utilizzate e l'harware predisposto per l'esecuzione e la verifica.
Si passa ad una visione dettagliata delle solo architetture. Viene posta una
differenziazione sulle funzioni sviluppate, specificando nel dettaglio, la
strategia di parallelizzazione, la modalità di esecuzione ed i risultati attesi e
poi ottenuti durante la fase di Testing del codice.
Luigi Perillo Z62/000007
Pagina 6 di 45
1 Parallelismo
Nella definizione più semplice di parallelismo, si intende, l'uso simultaneo di molte
risorse di calcolo per l'esecuzione di un programma. Nell'ambito dell'elaborazione
di grandi quantità di dati su terminali, risulta molto utile la suddivisione del carico
di lavoro; poiché l'approccio con metodi statici tradizionali risulta dispendioso sia in
termini di gestione di memoria che in tempi elaborazione.
Nell'ultimo periodo si sta offrendo la possibilità di implementare soluzioni
alternative per l'elaborazione sequenziale dei dati, sfruttando le caratteristiche del
calcolo parallelo.
La strategia si basa sulle evoluzione hardware, in pratica sviluppando un algoritmo
parallelo che suddivide il carico di lavoro su più processori, portando un vantaggio
significativo nel caso di lavoro su grandi moli di dati.
Non si ottiene un calcolo parallelo efficiente semplicemente aumentando il numero
di processori, eseguendo una connessione ad alta velocità.
Nella pratica, è molto difficile ottenere uno speedup lineare, cioè prestazioni
direttamente proporzionali al numero di processori presenti nel sistema, poiché
molti algoritmi sono di natura sequenziale.
Nella maggior parte degli algoritmi quindi occorre una riscrittura per poter sfruttare
l'hardware parallelo.
Un programma che viene svolto correttamente da una singola CPU potrebbe
presentare problemi se svolto in parallelo, poiché più copie dello stesso blocco di
istruzioni, potrebbero interferire tra loro, accedendo ad esempio ad una stessa area
di memoria contemporaneamente. Da qui nasce quindi la necessità di una attenta
programmazione per sfruttare questo tipo di sistemi.
Luigi Perillo Z62/000007
Pagina 7 di 45
1.1 Architettura di Memoria
I sistemi di calcolatori a seconda della molteplicità del flusso di istruzioni e del
flusso dei dati che possono gestire, possono essere classificati secondo uno standard
ben definito.
La classificazione più utilizzata è la Tassonomia di Flynn, introdotta nel 1966.
Questa classificazione, cataloga i computer in paralleli e seriali, nel caso in cui i
processori eseguano la stessa istruzione contemporaneamente (SIMD, Single
Instruction Multiple data) o istruzioni diverse (MIMD, multiple Instructions
Multiple data).
I sistemi paralleli sono anche classificati come simmetrici o asimmetrici, secondo le
abilità possedute o ai compiti assegnati alle CPU (capacità di far girare tutto il
codice del sistema operativo o solo una parte; accesso alla memoria e ai dispositivi
di I/O).
Di conseguenza ogni sistema di calcolo attuale, rientra in una delle seguenti
categorie:
➢ SISD (Single Instruction Single Data)
➢ SIMD (Single Instruction Multiple Data)
 Processori vettoriali
 Array processor
 Array sistolici
➢ MISD (Multiple Instruction Single Data)
➢ MIMD (Multiple Instruction Multiple Data)
 Sistemi a memoria distribuita
 MPP Massively Parallel Processing
 COW Cluster Of Workstations
Luigi Perillo Z62/000007
Pagina 8 di 45
 Sistemi a memoria condivisa
 UMA Uniform Memory Access
 NUMA NonUniform Memory Access
•
NC-NUMA No Cache – NUMA
•
CC-NUMA Cache Coherent – NUMA
 NORMA NO Remote Memory Access
 COMA Cache only memory Access
 Macchine dataflow
 Macchine a riduzione
Come è possibile notare dallo schema precedente, le quattro categorie principali
(SISD,SIMD,MISD,MIMD), sono strutturare in sotto categorie, infatti categorie
differenti saranno propense ad utilizzare organizzazioni di memoria di tipo diverso.
Illustrazione 1: Schema Tassonomia di Flynn
Luigi Perillo Z62/000007
Pagina 9 di 45
➢ Architettura SISD
L'architettura SISD è rappresentata dalla struttura della macchina di Von Neumann.
Questo computer comprende una sola unità di elaborazione (ALU), che lavora su un
unico flusso di istruzioni e opera su un solo flusso dati.
Ad ogni ciclo di Clock, le istruzioni per l'elaborazione delle istruzioni vengono
eseguite in sequenza.
Durante la fase di Fetch, viene prelevata dalla memoria centrale, l'istruzione per
elaborazione del comando da eseguire.
Segue la fase di Decode, in cui viene interpretata l'istruzione da eseguire, durante la
fase di Execute, in cui viene eseguita l'istruzione precedentemente stabilita.
Illustrazione 2: Schema architettura SISD
Possiamo semplificare, tale architettura dicendo, che è composta da: unità di
controllo, unità di elaborazione e memoria.
Luigi Perillo Z62/000007
Pagina 10 di 45
Un esempio di quest'architettura sono i processori tradizionali single-core, utilizzata
in quasi tutti i personal computer, anche se ora risulta obsoleta.
➢ Architettura SIMD
Questa architettura, rappresenta un multi-processore; cioè una struttura composta da
un numero definito di processori identici.
Tutti i processori, in modalità sincrona, eseguono la stessa istruzione su dati diversi.
In questa architettura l'unità di controllo delle CPU organizza e distribuisce le
istruzioni da inviare alle differenti unità di elaborazione logico aritmetica.
L'architettura SIMD è spesso usata dai super-computer con alcune varianti anche
nei moderni microprocessori.
Gli algoritmi da parallelizzare su questo tipo di architettura, devono essere suddivisi
in sotto problemi identici, poiché le istruzioni da eseguire sono le stesse per ogni
processore.
Uno dei vantaggio delle architetture SIMD è la capacità di manipolare tutti i dati
caricati contemporaneamente; quindi se per esempio un processore SIMD risulta in
grado di caricare n dati differenti, quest'ultimo sarà anche in grado di processarli
contemporaneamente, ottenendo dei risultati buoni in termini di efficienza.
Luigi Perillo Z62/000007
Pagina 11 di 45
Illustrazione 3: Schema architettura SIMD
Questo tipo di architettura trova, applicazione nella realizzazione delle GPU, dove
diversi stream, lavorano tutte sottoposte ad uno stesso controllo.
➢ Architettura MISD
Risulta l'architettura meno utilizzabile, infatti prevede che un singolo flusso di dati,
alimenti più unità di elaborazione contemporaneamente. Ogni singola unità lavora
su dati indipendenti con flusso di istruzione differenti. Questa architettura esiste
solo a livello sperimentale, ma non è mai stata commercializzata.
Ad ogni ciclo di Clock, il dato ricevuto nella memoria viene elaborato da processori
simultaneamente, utilizzando le istruzioni contenute nella propria unità di controllo.
La differenziazione dei risultati è dovuta alle istruzione differenti eseguite sui dati.
Luigi Perillo Z62/000007
Pagina 12 di 45
➢ Architettura MIMD
Attualmente risulta l'architettura più diffusa per il calcolo parallelo, poiché è molto
potente durante la fase di calcolo.
Questa architettura parallela è costituita da diverse unità che effettuano elaborazioni
su diversi dati.
Nell'architettura MIMD multiprocessore, questi condividono le strutture di dati in
una memoria comune ai processori. Lo scambio delle informazioni avviene
mediante la condivisione della memoria.
Per questo motivo i processori necessitano di alcuni meccanismi di controllo che
risolvano l'accesso simultaneo in fase di scrittura in memoria da parte di due o più
processori contemporaneamente. In questa architettura il calcolo è molto veloce in
Luigi Perillo Z62/000007
Pagina 13 di 45
quanto tutti i processori accedono simultaneamente alla memoria condivisa, però c'è
da dire che tale architettura è anche molto complessa in quanto devono essere
presenti numerosi circuiti di decodifica tra i processori.
Nell'architettura MIMD, multi computer, ogni processore ha una propria memoria.
I vari processori comunicano tra loro mediante uno scambio di messaggi definito
message passing. La comunicazione tra i vari processori è affidata a una rete di
interconnessione che consente a ciascun processore di trasmettere dati a qualunque
altro presente nella stessa rete. I processori possono anche essere fisicamente
lontani, come capita nei sistemi distribuiti.
Illustrazione 5: Schema architettura MIMD
Questa architettura è suddivisa in due differenti categorie, a seconda se viene
utilizzata Memoria distribuita, ad esempio utilizzando dei Cluster, oppure a
Memoria Condivisa, con la struttura a Multi-Core.
Luigi Perillo Z62/000007
Pagina 14 di 45
1.2 Organizzazione della Memoria
Uno degli aspetti più importanti della progettazione di un sistema di calcolo
parallelo, riguarda il metodo di organizzazione della memoria.
Questa risulta una parte fondamentale, per l'obbiettivo finale dell'aumento delle
prestazioni, da cui non si può solo prescindere dalla velocità di accesso alla
memoria per il recupero e l'elaborazione dei dati.
Le architetture sono suddivise principalmente in tre categorie principali: Memoria
condivisa, Memoria distribuita, ed una fusione tra le precedenti che prende il nome
di Memoria ibrida Condivisa-Distribuita.
➢ Memoria Condivisa
Nel modello a Memoria Condivisa, i processori interessati hanno accesso a tutta la
memoria, che viene vista come un unico spazio di indirizzamento globale.
I processori lavorano indipendentemente l'uno dall'altro, ma si ritrovano a
condividere la memoria; ed in questo caso le modifiche saranno accessibili a tutti i
processore collegati.
A sua volta ogni processore risulta in possesso di una piccola cache locale, in cui
memorizzare le informazioni, nella fase precedente alla modifica globale della
memoria condivisa.
Questa tecnica di indirizzamento globale, rende la programmazione parallela più
intuitiva, nella realizzazione di un algoritmo per la parallelizzazione.
Luigi Perillo Z62/000007
Pagina 15 di 45
Illustrazione 6: Architettura a memoria condivisa
Questa architettura presenta anche notevoli svantaggi, tra cui la limitata scalabilità.
Nel caso in cui si intendesse aumentare il numero di CPU, infatti ci sarebbe un
aumento del traffico per le comunicazione tra le CPU e la memoria.
➢ Memoria Distribuita
In un sistema con struttura a memoria distribuita, ogni processore risulta in possesso
di una propria area di memoria locale, non condivisibile con gli altri processori del
sistema. In questo caso i processori lavorano separatamente l'uno dall'altro e le
modifiche alla memoria che avvengono in un determinato processore non
influenzano la memoria locale degli altri.
Lo scambio di informazioni tra i processori, è deciso dal programmatore, che
Luigi Perillo Z62/000007
Pagina 16 di 45
gestisce i momenti e le modalità con cui deve avvenire lo scambio attraverso
direttive di sistema.
Questa tipologia di architettura di memoria è preferita per strutture di calcolo
composte da più sistemi collegati tra loro attraverso una rete.
Illustrazione 7: Architettura a memoria distribuita
Questa architettura, consente una maggiore scalabilità del sistema, senza un
aumento dei costi eccessivo. Infatti se in precedenza per la Memoria Condivisa,
l'inserimento di nuovi processori, comportava modifiche del software che era stato
implementato, in questo caso le modifiche risultano in prevalenza di tipo hardware,
in quanto occorre ampliare esclusivamente la rete di collegamento dei processori.
Le difficoltà come detto in precedenza si presentano nelle comunicazioni tra i
processori, che portano anche ad un rallentamento generale, per la comunicazione
dei pacchetti lungo la rete.
Luigi Perillo Z62/000007
Pagina 17 di 45
➢ Memoria Ibrida Distribuita-Condivisa
I calcolatori moderni più grandi e veloci utilizzano oggi in prevalenza questo tipo di
memoria. Questa architettura risulta una fusione delle precedenti; in pratica i
differenti sistemi di calcolo, lavorano indipendentemente con la propria memoria
condivisa e la connessione di rete viene utilizzata quando occorre muovere i dati da
un sistema all'altro.
Così come per le architetture a memoria condivisa, i sistemi in questo caso sono
cache-coerency, mentre la componente distribuita è posta sulla rete per le
connessione delle diverse componenti.
La cache-coerency in questi sistemi è un problema molto complesso da gestire, che
prevede l'utilizzo di interfacce di rete molto sofisticate.
In questo caso, i vantaggi dall'utilizzo di questa architettura così come gli svantaggi
sono una stretta fusione di quelli incontrati per le precedenti architetture. In
prevalenza questa conformazione permette un'alta efficienza con macchine multiprocessori, con possibilità di scalare unità elevate di processori.
Luigi Perillo Z62/000007
Pagina 18 di 45
Luigi Perillo Z62/000007
Pagina 19 di 45
1.3 Modelli di programmazione parallela
Gli algoritmi strutturati per sfruttare il parallelismo, si basano su una serie di
operazione che necessariamente devono essere svolte, al fine che un'operazione
possa compiere correttamente il lavoro, producendo risultati corretti e finali.
I modelli di programmazione parallela, sono sviluppati per essere multi-piattaforma,
e quindi essere implementati per qualsiasi tipo di macchina.
I modelli principalmente utilizzati per la programmazione parallela sono: Shared
Memory, Messsage Passing.
Non esiste un modello migliore in termini assoluti rispetto agli altri, la soluzione
migliore da applicare, dipende molto dal problema che si deve risolvere o dal tipo di
hardware a disposizione.
➢ Shared Memory
In questo modello i task condividono un'unica area di memoria, nella quale vengono
scritti in modalità asincrona le informazioni.
In alcuni sistemi può accadere che i processi in esecuzione condividano una risorsa
comune. Se si verifica che il risultato finale dell'esecuzione di più processi dipende
dall'ordine in cui essi vengono eseguite queste operazioni, ci troviamo in presenza
di una corsa critica (race-condition). Il problema delle "corse critiche" può essere
evitato impedendo che più di un processo per volta acceda a risorse condivise.
Uno dei metodi per ovviare ciò, è la mutua esclusione; in questo caso i sistemi
concorrenti mettono a disposizione delle primitive di comunicazione che
permettono di alternarsi (escludendosi a vicenda) nell'accesso ad una risorsa
condivisa oppure usando delle primitive di sincronizzazione che permettono di
intervenire sulla sequenza secondo la quale avverranno determinati eventi.
Ogni sistema mette a disposizione le proprie primitive, ma nonostante ciò i sistemi
Luigi Perillo Z62/000007
Pagina 20 di 45
si rifanno ad una teoria comune. Le più comuni vie di sincronizzazione e
comunicazione tra processi sono:
•
Mutex: variabili binarie che permettono di gestire l'accesso ad una risorsa
condivisa mediante accesso esclusivo di uno dei contendenti. Le operazioni
di blocco e di sblocco sono operazioni atomiche (eseguite in sequenza, senza
interruzione).
•
Semafori n-ari: variabili n-arie che possono essere incrementate e
decrementate. Il processo che decrementa il semaforo si bloccherà appena
raggiunto lo zero della variabile. Un processo che incrementa il semaforo
invece risveglia tutti i processi che si erano bloccati in fase di decremento.
Questa è una delle primitive base che consentono la sincronizzazione. Le
operazioni di incremento, decremento e controllo del semaforo sono
anch'esse atomiche.
•
Variabili di tipo condizione: conosciute anche come Condition Variables,
sono variabili con associate due primitive: wait e signal. Una procedura che
richiama la primitiva wait si pone in attesa indefinita, una procedura che
richiama la primitiva signal ne risveglia una in attesa su wait. Anche in
questo caso le operazioni sono atomiche.
•
Scambio di messaggi: due procedure, send (invia) e receive (ricevi),
permettono a due processi di scambiarsi messaggi. Lo scambio di messaggi è
solitamente usato in sistemi paralleli.
•
Barriere: un processo che ha terminato la sua fase chiama una primitiva
barrier e si blocca. Quando tutti i processi coinvolti hanno terminato il loro
stadio di esecuzione invocando anch'essi la primitiva barrier, il sistema li
sblocca tutti permettendo di passare ad uno stadio successivo.
Risulta molto semplice l'implementazione di questo tipo di programmazione, anche
Luigi Perillo Z62/000007
Pagina 21 di 45
nel caso in cui si passa da una versione seriale dell'algoritmo di interesse.
In questa categoria subentra la gestione multithreading, infatti il processo da
eseguire può avere percorsi multipli, alternando esecuzioni sequenziali a blocchi di
codice parallelo.
Alcune implementazioni principali di questo modello sono:
1. OpenMP
2. Posix Threads (Pthreads).
Questo è il modello utilizzato per l'algoritmo sviluppato, in quanto permette di
raggiungere gli obbiettivi fissati, sfruttando al meglio la struttura di calcolo a
disposizione.
➢ Message Passing
Il modello Message-Passing viene solitamente applicato in sistemi in cui
l'architettura di memoria è distribuita. Più task possono essere situati sulla stessa
macchina, oppure, su un numero di macchine random.
In questo caso il programmatore, è portato a determinare il parallelismo e lo
scambio dei dati, che avviene attraverso messaggi, richiamando una libreria da
inserire all'interno del codice.
Uno modello standard è MPI (Message Passing Interface), implementato per
architettura a memoria distribuita ma adattabili anche a macchine multi-piattaforma
a memoria condivisa.
Luigi Perillo Z62/000007
Pagina 22 di 45
1.4 Valutare algoritmi paralleli
Lo sviluppo della tecnologia di Calcolo Parallelo, ha portato alla necessità di avere
strumenti di valutazione per poter constatare le prestazioni, e gli effettivi vantaggi
nella parallelizzazione di algoritmi.
Come detto in precedenza, la parallelizzazione di algoritmi in precedenza eseguiti
sequenzialmente, ha come scopo prevalente quello di risolvere problemi di grandi
dimensioni in tempi relativamente brevi.
I fattori da avere sotto controllo per il raggiungimento di questo obbiettivo, sono
molteplici e vanno, come detto, dalla tecnologia hardware utilizzata, al modello di
parallelizzazione (ampiamente spiegati in precedenza) scelto, a seconda delle
caratteristiche strutturali su cui si basa l'algoritmo.
Per l'analisi delle prestazioni fornite dagli algoritmi paralleli, sono stati introdotti
dei concetti, che confrontano in prima istanza le prestazioni con la versione
originale dell'algoritmo, in modo da verificarne l'effettivo aumento di prestazioni, o
modificandone le caratteristiche, variandone il numero di processori e/o thread per
le singole esecuzioni.
Gli indici che permettono di analizzare questo valori sono: Speed Up, Efficienza e
Scalabilità.
➢ Speed Up
Uno degli strumenti per confrontare un algoritmo sequenziale con il suo
corrispettivo parallelo, è chiamato Speed Up.
Lo Speed Up è definito come:
S p=
T1
Tp
dove in dettaglio, “p” è il numero di processori, “T 1” è il tempo di esecuzione nella
Luigi Perillo Z62/000007
Pagina 23 di 45
versione sequenziale dell'algoritmo, “Tp” è il tempo di esecuzione della versione
parallela dell'algoritmo con “p” processori.
Nel caso in cui il nostro algoritmo risulti avere uno Speed Up Ideale (Sp=p), ci
troveremo nella condizione in cui, raddoppiando il numero di processori si
verificherà un raddoppio della velocità di esecuzione.
In presenza di questa caratteristica, l'algoritmo avrebbe la maggiore scalabilità, cioè
la massima versatilità al variare delle necessità o della disponibilità del problema.
➢ Efficienza
Nell'ambito delle analisi delle prestazioni, l'efficienza viene definita nel seguente
modo:
E p=
Sp
T1
=
p ( p∗T p )
Questo parametro compreso tra i valori zero ed uno, permette di effettuare una stima
di quanto i processori vengano sfruttati per la risoluzione del problema, rispetto alle
altre attività assegnate all'algoritmo, come la comunicazione tra i processori e la
sincronizzazione.
Sulla base di quanto appena detto definiamo con T(k,z) il tempo di elapsed (tempo
di esecuzione) totale per completare l'esecuzione, avendo dimensione del problema
z con k thread.
T ( k , z)=T s +
T c (z )
+T 0 (k )
K
Avremo quindi:
•
Ts, tempo di esecuzione per le sezioni seriali dell'algoritmo. Ts risulta
indipendente dalla dimensione del problema che indicheremo con z, e dal
numero di threads k interessati nell'elaborazione.
Luigi Perillo Z62/000007
Pagina 24 di 45
•
T c ( z)
K
indica il tempo di esecuzione per le sezione parallelizzabile
dell'algoritmo. Indica che la sezione di codice da parallelizzare può essere
decomposta ed eseguita in contemporanea k volte dai thread, avendo dei
tempi di esecuzioni uguali.
•
T0(k), tempo di comunicazione tra i thread, utilizzato per scambio di
informazioni e dei risultati parziali di elaborazione. Questa è una funzione
non decrescente, in funzione del numero di thread, per cui avremo che per
T0(1)=0, cioè nell'esecuzione ad un solo thread, l'Overhead di comunicazione
sarà 0, poiché non esistono comunicazione tra i vari thread.
L'efficienza R(N,z), sarà data da:
R( N , z)⩽
T (1, z )
⩽1
T ( 1, z )+T 0( N )
I differenti tempi di overhead che si possono riscontrare, per la sincronizzazione dei
risultati e per la comunicazione tra i thread, influiscono notevolmente sul calcolo
dell'efficienza, maggiore sarà l'Overhead, più le prestazioni dell'algoritmo saranno
meno accettabili.
Prendendo come esempio l'algoritmo che esegue una somma a cascata, a seconda
della strategia e della gestione di memoria utilizzata, possiamo trovarci in presenza
di fattori di overhead, che influiscono sull'efficienza dell'algoritmo.
Nel caso di una struttura MIMD, a memoria distribuita, il tempo di overhead risulta
pari a: T 0 ( p)=log 2 ( p) .
Utilizzando invece un'architettura a memoria condivisa, con attraversamento di una
regione critica, ci troveremo ad avere un overhead, dipendente dal numero di
Luigi Perillo Z62/000007
Pagina 25 di 45
processori interessati nell'elaborazione dei risultati, quindi pari a: T 0 ( p)= p , un
fattore molto influente in questo caso, se il numero di processori interessati
nell'elaborazione risulta elevato.
Nel caso in cui ci si trova in una completa assenza di comunicazione tra i
processori, ci troveremo in presenza di assenza di overhead, quindi per algoritmi
denominati Embarrassingly parallel avremo che: T 0 ( p)=1 .
Classifichiamo quindi l'Efficienza nel seguente modo:
Ep = 1 Caso Ideale
Ep < 1 Caso Reale.
➢ Scalabilità
La Scalabilità viene definita come la capacità di un algoritmo di essere efficiente su
una macchina parallela.
Identifica in breve, la possibilità di incremento della potenza di calcolo,
proporzionalmente all'aumento del numero di processori.
Quindi in presenza dell'aumento della dimensione del problema, e allo stesso tempo
effettuando un aumento del numero di processori nell'esecuzione, le prestazioni
restano stabili senza perdita di efficienza. Questo risulta essere l'obbiettivo
principale, per cui si progettano algoritmi paralleli.
Luigi Perillo Z62/000007
Pagina 26 di 45
2 Problema affrontato
L'algoritmo che si è analizzato, come accennato in precedenza, esegue il calcolo
della quadratura numerica per la risoluzione di un integrale definito in un dominio
[0,1]10 su una funzione a dieci variabili, utilizzando algoritmi adattativi
[1]
per la
quadratura in dieci dimensioni [2].
U =[0,1] d with d =10
f (x )=0 if x1> β 1 ∨ x 2> β 2 ;
f (x)= exp(
∑
i=1,..., d
ai x i )
Tale algoritmo dimezza successivamente l'ampiezza dei sotto intervalli, affinché una
stima dell'errore commesso, non risulta inferiore ad una fascia di tolleranza
assegnata tra i parametri di input.
In se questo risulta essere un problema semplice, nel caso in cui la funzione da
determinare è costituita da poche unità di variabili, mentre tende ad aumentare il
carico di lavoro, in presenza di un range di valori più ampio per le variabili della
funzione.
Nel caso in cui il comportamento della funzione non è lo stesso nell'intervallo di
integrazione, si cerca di adattare la distribuzione dei nodi alle proprietà della
funzione integrata.
Per la risoluzione si è usufruito del calcolo parallelo, su un architettura MIMD, con
memoria condivisa, utilizzando una strategia Multi-Threads, sfruttando la libreria
Pthread.
L'implementazione di questa strategia, consente nell'ambito della programmazione
parallela, di guadagnare tempo in modo molto rilevante, poiché lo switching tra
thread è molto più veloce che non quello tra processi.
Il problema generale da affrontato, è quello della suddivisione della parte
parallelizzabile dell'algoritmo, tra i diversi threads, in modo da avere un carico di
Luigi Perillo Z62/000007
Pagina 27 di 45
lavoro bilanciato tra i diversi threads, senza sovraccaricare di lavoro solo alcuni di
essi e rendere inattivi gli altri.
La strategia utilizzata, prevede la suddivisione del dominio in N thread parti, per poi
sfruttare la proprietà additiva degli integrali.
L'algoritmo adattativo, permette di raffinare gli intervalli dove l'errore di
elaborazione è più grande, dividendolo in aree più piccole, da distribuire ai thread in
cui la stima dell'errore risulta minima, cioè ai threads che si trovano ad esaminare
parti della funzione in cui l'andamento è di facile calcolo (lineare).
Le metodologie di ridistribuzione che si sono prese in esame sono in prevalenza
due:
•
Comunicazione globale. Ogni nodo ha dei sotto domini propri.
Il nodo identifica l'area con l'errore maggiore e comunica a tutti gli altri nodi
le informazioni per la ripetizione dell'esecuzione e per la riduzione
dell'errore. I punti negativi rilevanti in questa strategia, sono le eccessive
comunicazioni tra i thread, che comporta un elevato overhead , ma di
conseguenza comporta un accuratezza molto elevata dei risultati calcolati,
T 0 ( p)= p
•
.
Comunicazioni locali. Ogni nodo comunica solo con i nodi adiacenti.
Questo comporta
una
riduzione
drastica
dell'overhead,
in quanto
indipendentemente dal numero di nodi interessati nell'elaborazione, le
comunicazioni restano di numero costante,
T 0 ( p)=cost
.
Questa strategia comporta quindi una notevole scalabilità, che la rende
preferibile rispetto ad un algoritmo in cui le strategie di comunicazioni sono
globali.
La strategia scelta è la seconda, assegnando ad ogni nodo in esecuzione un
algoritmo iterativo, che in ogni passo di iterazione effettua una comunicazione in
Luigi Perillo Z62/000007
Pagina 28 di 45
senso orizzontale o verticale, riducendo ulteriormente il numero di comunicazioni
locali a 2 tra i 4 nodi adiacenti.
Luigi Perillo Z62/000007
Pagina 29 di 45
2.1 Descrizione Algoritmo
L'algoritmo consente la distribuzione dei dati di input sui diversi thread, utilizzando
due strategie di distribuzione differenti, in modo da ottimizzare oltre al tempo
effettivo di esecuzione della funzione sviluppata, anche la stima dell'errore per
determinare la risoluzione dell'integrale.
A seconda di come sono distribuiti i dati sui vari thread, sarà possibile ottenere una
stima dell'errore minore all'aumentare del numero di thread, e quindi una maggiore
accuratezza dei risultati ottenuti.
L'integrale da risolvere viene suddiviso in sub-regioni da assegnare ai vari thread ed
a seconda della suddivisione, sarà stimato l'errore.
L'errore stimato viene determinato in un confronto con il risultato ottenuto dalla
funzione che determina l'integrale noto, utilizzando il calcolo della primitiva nota
della funzione.
La suddivisione in sub-sezioni dipende dal numero di thread e dal numero di
valutazione di funzione.
Ai diversi thread (1, 2 o 4) impiegati nell'esecuzione, sono assegnate differenti
sezioni della funzione, nel caso in cui un thread si trova con un carico di lavoro
minore, dovuto ai risultati ottenuti che non appartengono al range di valori
accettabili, avviene un'ulteriore suddivisione, che consente di bilanciare il carico dei
dati e di ottimizzare esecuzione e l'errore di elaborazione.
Il progetto è stato compilato, in ambiente Linux, da riga di comando con la seguente
sintassi:
cc auxiliary.c c_timer.c environ.c pamihr.c main.c -o eseguibile -lm -lpthread
dove:
•
pamihr.c, la funzione sviluppata per la risoluzione dell'integrale.
•
main.c, funzione in cui sono contenute le chiamate alle varie procedure e
Luigi Perillo Z62/000007
Pagina 30 di 45
dove sono gestite le strutture per il salvataggio delle informazioni di output.
•
-lm, modulo per la gestione della libreria matematica.
•
-lpthread, modulo per la gestione della libreria Pthread.
2.2 Strategia di distribuzione dei dati
Le strategie adottate per la risoluzione del problema, sono sostanzialmente due.
Occorre quindi valutare in termini di efficienza e accuratezza quale approccio,
risulta il migliore da seguire, in quanto ognuna delle due strategie come sarà
possibile osservare dai test effettuati, ha delle caratteristiche che ne consente di
favorirne una rispetto l'altra, puntando ad avere una maggiore accuratezza dei
risultati ottenuti, o ad avere tempi di esecuzione inferiori.
La differenza sostanziale tra le due strategie si presenta nel modo in cui i dati (precaricati, e dati in input alla funzione PAMIHR)
[3]
vengono distribuiti ai thread e di
conseguenza se devono essere create e gestite le sub-sezioni, per la risoluzione e di
conseguenza le comunicazioni tra i vari thread impegnati nell'esecuzione.
Le due differenti strategie sono settate con l'ausilio di una variabile semaforo
chiamata REDIST, che può essere settata con valore rispettivamente 1 o 0.
•
Strategia di distribuzione: Redist 0
Questa strategia denominata Redist 0, non prevede la possibilità di
ridistribuire i dati e quindi di creare sotto sezioni, da assegnare ai thread, nel
caso in cui in una particolare area, sia presente un errore d'elaborazione
elevato.
Questa strategia, non è affidabile nel caso in cui si vuole puntare ad una
maggiore accuratezza dei risultati, poiché l'errore di elaborazione risulta
maggiore; in compenso, risulta essere una strategia utilizzabile nel caso in
Luigi Perillo Z62/000007
Pagina 31 di 45
cui si punta ad ottenere una maggiore efficienza in termini di tempi di
elaborazione.
•
Strategia di distribuzione: Redist 1
La strategia denominata Redist 1, permette di avere una maggiore
accuratezza dei risultati ottenuti, avendo una riduzione della errore stimato,
tra l'algoritmo parallelo, e la risoluzione con funzioni già note.
In questa strategia, i tempi di esecuzione, sono soggetti ad overhead di
comunicazione costante, tra i nodi adiacenti secondo la strategia spiegata in
precedenza nel paragrafo 2.
In presenza di aree in cui i thread riscontrano un errore elevato, avviene una
ridistribuzione di solo una parte di questa area, tra i thread adiacenti, che
consentiranno di ridurre l'errore di calcolo e di avere quindi risultati più
attendibili e prossimi a quello calcolati da funzioni note.
Le differenze tra le due strategie, nel caso in cui si prede in considerazione
l'efficienza dell'elaborazione, risulta essere di poco meno del 10%.
Una maggiore differenza, la si ottiene nel caso in cui si punta all'accuratezza dei
dati, in questo caso tra gli errori stimati sui risultati, sarà possibile riscontrare un
fattore ben più evidente, dimostrando l'efficacia della strategia di ridistribuzione
adottata.
Ciò è dovuto al fatto che le comunicazioni tra i thread sono ridotte, (ad ogni passo
iterativo, sono al massimo 2 per ogni nodo, e non N-1, come nel caso della strategia
globale descritta in precedenza).
Questa caratteristica sarà ben più visibile nel paragrafo successivo, in cui sono
riportati i test effettuati sia per efficienza e sia per stima dell'errore.
Luigi Perillo Z62/000007
Pagina 32 di 45
2.3 Test performance e stima errori
Nel capitolo precedente è stata fatta una panoramica sull'algoritmo.
In particolare è stata mostrata la metodologia adottata per la risoluzione, mostrando
le due differenti strategie per ridistribuire i dati sui thread predisposti per
l'elaborazione.
Si passa ora ad analizzare da un punto di vista più teorico le performance
dell'algoritmo, per la valutazione dei punti di forza della parallelizzazione sui
differenti casi riscontrati, per condizioni di input da noi definite.
Un primo test effettuato, si è basato sull'analisi dei tempi di esecuzione della
funzione Pamihr, per il calcolo dell'integrale posto in input, facendo variare, la
dimensione del problema ed il numero di thread.
Svolto questo test, si è passato all'analisi dei tempi, determinando in ogni caso, lo
Speed Up e l'Efficienza, così da poter valutare l'utilità della parallelizzazione del
codice e la Scalabilità della struttura progettata.
Il secondo test effettuato, si orienta sui risultati dell'elaborazione ottenuti.
Sono riportati i valori ottenuti dalla funzione sviluppata, in confronto ai risultati del
calcolo dell'integrale mediante primitive già note.
Di questi test, si è svolta una stima degli errori, verificando l'accuratezza dei dati,
nelle due diverse strategie implementate.
I tempi e le stime degli errori riportati nei paragrafi a seguito, sono il risultato della
media di tre differenti esecuzioni, in modo da ammortizzare le fluttuazioni a runtime.
I test sono stati svolti su di una macchina in dotazione del dipartimento di
matematica, che riporta le seguenti caratteristiche.
•
Processor 8-core Intel(R) Core(TM) i7 CPU, 950 @3.07GHz con 8192 KB
di cache-size.
Luigi Perillo Z62/000007
Pagina 33 di 45
2.3.1
Test efficienza algoritmo
Come detto in precedenza, il primo test effettuato è l'analisi delle performance della
funzione Pamihr, che determina il calcolo dell'integrale definito di una funzione a
dieci variabili.
Le prove sono effettuate sulle variazione di thread 1, 2 o 4 e su dimensioni di input
che vanno da 250.000 a 1.000.000 e al variare del tipo di ridistribuzione dei dati,
settando la variabile Redist.
Dimensioni
Threads
Valori
250000
500000
1
Elapsed Medio 0,013508 0,025782
2
Elapsed Medio 0,007446 0,012800
4
Elapsed Medio 0,005109 0,007798
750000
0,039444
0,020221
0,011841
1000000
0,051660
0,027679
0,015354
Tabella 1: Tempi di esecuzione. Redist 0
Threads
1
2
4
Valori
Elapsed Medio
Elapsed Medio
Elapsed Medio
Dimensioni
250000
0,014241
0,008482
0,005464
500000
0,025167
0,015012
0,009147
750000
0,038562
0,022616
0,012468
1000000
0,050412
0,029972
0,016506
Tabella 2: Tempi di esecuzione. Redist 1
Come si può notare dai tempi riportati nelle tabelle precedenti, all'aumentare del
numero di thread, impiegati nell'esecuzione, i tempi tendono a diminuire, andando
in alcuni casi, a dimezzarsi di circa il 50% rispetto al tempo di esecuzione nel caso
strettamente precedente di numero di thread.
È possibile riscontrare gli effettivi vantaggi della parallelizzazione nelle tabelle
successive, che riportano lo Speed Up e l'Efficienza media.
Luigi Perillo Z62/000007
Pagina 34 di 45
Threads
1
2
4
Valori
Speed Up
Speed Up
Speed Up
Dimensioni
250000
1
1,824952
2,817228
500000
1
2,016069
3,416137
750000
1
1,952758
3,416137
1000000
1
1,882525
3,519785
Tabella 3: Speed Up medio su 3 esecuzioni. Redist 0
3,5
3
Speed Up
2,5
2
250000
500000
750000
1000000
1,5
1
0,5
0
1
2
4
Threads
Illustrazione 10: Grafico Speed Up, Redist 0
Luigi Perillo Z62/000007
Pagina 35 di 45
Threads
1
2
4
Valori
Speed Up
Speed Up
Speed Up
Dimensioni
250000
500000
1
1
1,684318 1,673195
2,722445 2,800481
750000
1
1,702252
3,088452
1000000
1
1,679207
3,049022
Tabella 4: Speed Up medio su 3 esecuzioni. Redist 1
3,5
3
Speed Up
2,5
2
250000
500000
750000
1000000
1,5
1
0,5
0
1
2
4
Threads
Illustrazione 11: Grafico Speed Up, Redist 1
Luigi Perillo Z62/000007
Pagina 36 di 45
Dai calcoli effettuati per lo Speed Up su entrambe le strategie, si nota che le
prestazioni dell'algoritmo non risultano perfettamente conformi alla definizione di
Speed Up, questo dipende da alcuni fattori esterni alla parallelizzazione su thread,
come ad esempio i tempi di overhead di trasmissione dei dati e al tipo di strategia
utilizzata per la distribuzione.
Le prestazioni dell'algoritmo restano comunque molto apprezzabili, di fatto
all'aumentare delle dimensioni del problema ed all'aumentare del numero dei thread
impiegati per l'elaborazione, l'algoritmo risulta molto performante.
In particolare la strategia di ridistribuzione Redist 0, risulta molto più performante
rispetto all'altra strategia e quindi preferibile nel caso in cui si voglia puntare come
caratteristica prevalente, ad avere tempi di esecuzione migliori e quindi risposte in
tempi minori.
Le tabelle seguenti riportano per completezza l'Efficienza media, per entrambe le
strategie di distribuzione.
Threads
1
2
4
Valori
Efficienza
Efficienza
Efficienza
Dimensioni
250000
500000
1
1
0,912476 1,008034
0,704307 0,854034
750000
1
0,976379
0,862745
1000000
1
0,941262
0,879946
Tabella 5: Efficienza media su 3 esecuzioni. Redist 0
Luigi Perillo Z62/000007
Pagina 37 di 45
1,2
1
0,8
Efficienza
250000
0,6
500000
750000
0,4
1000000
0,2
0
1
2
4
Threads
Illustrazione 12: Grafico Efficienza Media, Redist 0
Threads
1
2
4
Valori
Efficienza
Efficienza
Efficienza
Dimensioni
250000
500000
1
1
0,842159 0,836598
0,680611 0,700120
750000
1
0,851126
0,772113
1000000
1
0,839604
0,762256
Tabella 6: Efficienza media su 3 esecuzioni. Redist 1
Luigi Perillo Z62/000007
Pagina 38 di 45
1
0,8
0,6
Efficienza
250000
500000
0,4
750000
1000000
0,2
0
1
2
4
Threads
Illustrazione 13: Grafico Efficienza Media, Redist 1
Come detto in precedenza, è possibile notare, dalle tabelle e dai grafici precedenti
come le prestazioni della strategia di distribuzione Redist 0, risultano preferibili,
rispetto all'altra strategia e dalle tabelle precedenti sull'Efficienza media, risulta più
evidente, in quanto l'efficienza tende ad avvicinarsi all'Efficienza Ideale, descritta
nel paragrafo 1.4.
Luigi Perillo Z62/000007
Pagina 39 di 45
2.3.2
Test stima errore
Il secondo test sviluppato sull'algoritmo, è quello che analizza i risultati delle
elaborazioni, confrontando i risultati ottenuti con i valori, riscontrati dal calcolo
dell'integrale con le funzioni note.
Di questi valori, è stato effettuata una stima dell'errore, per verificare gli effettivi
vantaggi, e la correttezza delle varie elaborazioni.
Le prove sono effettuate sulle variazione di thread 1, 2 o 4 e su dimensioni di input
che vanno da 250.000 a 1.000.000 e al variare del tipo di ridistribuzione dei dati,
settando la variabile Redist.
I grafici che seguiranno sono su scala logaritmica, per rendere visibile gli effettivi
vantaggi e le differenziazioni tra le due strategie di calcolo.
Thread
1
2
4
Valori
Act. Error
Est. Error
Act. Error
Est. Error
Act. Error
Est. Error
Dimensioni
250000
0,071017
0,004370
0,071364
0,017965
0,071170
0,029775
500000
0,071170
0,003610
0,070998
0,002639
0,070994
0,006546
750000
0,071035
0,000047
0,071031
0,000775
0,070992
0,002733
1000000
0,071035
0,000011
0,071036
0,000240
0,071036
0,001037
Tabella 7: Errori Elaborazione. Redist 0
Luigi Perillo Z62/000007
Pagina 40 di 45
0,050000
0,029775
0,017965
0,006546
0,004370
0,005000
0,003610
0,000500
0,002639
0,002733
0,000775
0,001037
0,000240
Errori
250000
500000
0,000047
0,000050
750000
0,000011
0,000005
1
Threads
2
4
Illustrazione 14: Grafico Errore stimato. Redist 0 (scala logaritmica)
Thread
Valori
1
Act. Error
Est. Error
2
Act. Error
Est. Error
4
Act. Error
Est. Error
Dimensioni
250000
0,071017
0,004370
0,071035
0,004374
0,071022
0,014005
500000
0,071038
0,000361
0,071037
0,000371
0,071032
0,000485
750000
0,071035
0,000047
0,071035
0,000048
0,071035
0,000066
1000000
0,071035
0,000011
0,071035
0,000011
0,071035
0,000013
Tabella 8: Errori elaborazione. Redist 1
Luigi Perillo Z62/000007
Pagina 41 di 45
0,050000
0,014005
0,004374
0,005000
0,004370
0,000371
0,000500
0,000361
Errori
0,000048
0,000485
0,000066
0,000050
0,000047
0,000011
0,000013
2
4
0,000011
0,000005
1
250000
500000
750000
1000000
Threads
Illustrazione 15: Grafico Errore stimato. Redist 1 (scala logaritmica)
Come si può osservare dai valori riportati nelle tabelle e sui grafici, si ottengono
notevoli vantaggi di accuratezza dati in presenza della strategia di ridistribuzione
denominata Redist 1. I dati riportati evidenziano che le prestazioni ottenute
dall'algoritmo all'aumentare della dimensione dell'input e del numero di thread,
tendono ad avere un errore stimato dell'ordine 10 -5 rispetto al valore dello stesso
integrale di partenza, determinato tramite funzioni di primitive note.
Dai test effettuati, si evidenzia maggiormente quanto la scelta della strategia da
applicare, dipenda dal tipo di riscontro che si vuole ottenere, cioè un vantaggio
esclusivamente temporale, a discapito dell'accuratezza dei dati di output, o
viceversa.
Luigi Perillo Z62/000007
Pagina 42 di 45
3 Conclusioni
Nell'ambito della analisi della risoluzione mediante quadratura di integrali definiti,
in un dominio [0,1]10 di funzioni complesse a dieci variabili, si è seguita la strada
della risoluzione mediante l'uso del calcolo parallelo, per ottenere vantaggi sia in
termini di tempi di esecuzione, sia per avere delle approssimazioni migliori dei
risultati di calcolo.
Lo scopo era quello di approfondire una metodologia di valutazione di funzioni per
il calcolo scientifico, in ambiente computazionali basati su CPU multicore. Come
caso di studio si è deciso di utilizzare una classe speciale di algoritmi per la
quadratura numerica; per poi applicare questa metodologia anche ad altri tipi di
problemi, come la manipolazione delle matrici, utilizzando funzioni test per
esaminare la strategia, oppure far eseguire più volte lo stesso problema e fare la
media in maniera tale da ammortizzare le variazioni a run-time.
La direzione adottata nella parallelizzazione dell'algoritmo è stata quella di
utilizzare l'architettura MIMD, con gestione multi-thread con l'ausilio della libreria
Pthread.
Ciò ha portato dapprima a svolgere dei test, per la valutazione dell'ambiente di
calcolo determinando l'effettivo vantaggio di questo approccio, valutando
l'efficienza prestazionale; per poi passare ad un'analisi accurata dei risultati ottenuti,
sulla loro corrispondenza ai valori determinati tramite lo studio della primitive note,
per la funzione conosciuta data in input.
Dalle analisi svolte, si è giunti alla conclusione che l'algoritmo sviluppato, pone il
programmatore di fronte ad una scelta, a seconda del risultato che si è prefissato di
ottenere.
Le due strategie denominate rispettivamente Redist 0 e Redist 1, permettono di
scegliere, se si desidera riscontrare un vantaggio in termini di tempi di esecuzione,
ciò però a discapito dell'accuratezza dei dati, o se puntare su una precisione
Luigi Perillo Z62/000007
Pagina 43 di 45
millesimale dei dati, con un errore stimato molto piccolo.
Le motivazioni di tale considerazione, risiedono principalmente, dal numero di
thread impiegati nell'elaborazione, e dalla possibilità di ridistribuire i dati di input
sui diversi threads, quindi adoperando un algoritmo adattativo, piuttosto che calcoli
separati, senza cooperazione tra i thread, che portano ad una minore qualità dei
risultati, (anche se non eccessiva), in termini di tempi minori di esecuzione, dovuti
soprattutto all'assenza dell'overhead di comunicazione e alla sincronizzazione delle
aree di memoria condivise tra i thread.
Luigi Perillo Z62/000007
Pagina 44 di 45
Bibliografia
1. Almerico Murli: Libro: “Matematica numerica: metodi, algoritmi e software
Parte Prima” – Liguori Editore; (2007) ; pp 508.
2. A. Genz and A. Malik; Articolo:“An embedded family of fully symmetric
numerical integration rules”; SIAM Journal on Numerical Analysis; 20
(1983); pp. 580-588.
3. Giuliano Laccetti, Marco Lapegna, Valeria Mele, Diego Romano: Articolo:
“A study on adaptive algorithms for numerical quadrature on heterogeneous
GPU and multicore based systems”.
Luigi Perillo Z62/000007
Pagina 45 di 45