ed è liberamente a disposizione dei ricercatori come pacchetto open sour- ce [72], scritto sia in linguaggio C sia in Java. La versione C è il punto di partenza di questa analisi; il codice sorgente è stato analizzato al fine di ca- pire quale partizionamento hardware/software consente di ottimizzare le prestazioni dei tempi di esecuzione.
L’analisi è stata compiuta inizialmente tramite profiling del codice sorgente, quindi identificando le dipendenze tra le varie funzioni e, infine, model- lando l’intero sistema assumendo che ogni funzione possa essere realizzata
sia come codice software che come modulo hardware. Il modello ottenu- to è stato utilizzato per decidere quale sia il più efficiente partizionamento hardware/software.
Il profiling dei dati(vedi sottosezione 4.1.1) dell’algoritmo MDR è stato rea- lizzato utilizzando strumenti specifici come il GNU profiling tool: Gprof [73] [74]. L’algoritmo è stato profilato utilizzando differenti insieme di dati (dataset), tuttavia i risultati ottenuti sono pressoché identici. La tecnica di profiling utilizzata ha consentito l’estrazione di una serie di informazioni relative al numero di chiamate e al tempo di esecuzione per ogni funzione dell’algoritmo (vedi tabella 4.1 ).
Tabella 4.1: Insieme di tutte le procedure che costituiscono l’algoritmo MDR
ID Nome Funzione 1b MDR_model_construct_attribute 2b MDR_model_build_cell_counts 3b MDR_PRIVATE_model_construct_attribute_instance 4b MDR_PRIVATE_model_build_cells_instance 5b MDR_multiindex_encode 6b MDR_PRIVATE_model_init_cells 1e balanced_accuracy 2e MDR_model_compute_confusion_matrix 3e MDR_model_release 1d MDR_dataset_read 2d MDR_dataset_release 3d MDR_PRIVATE_dataset_finish_row 4d MDR_vector_detach 5d MDR_vector_add_array 6d MDR_vector_init 7d MDR_vector_release 8d MDR_vector_resize 9d MDR_vector_ensure_capacity 1r Main 2r MDR_model_build_cell_statuses 3r MDR_model_init 4r MDR_model_set_attr 5r print_combo 6r MDR_dataset_init 7r MDR_multiindex_init 8r MDR_model_clear_cells 9r MDR_multiindex_release
CAPITOLO 4. ANALISI DELL’ALGORITMO MDR 48
90% 10%
Istruzioni totali
blocco principale restanti
36,08% 25,25% 22,10% 3,62% 0,15% 2,57% 10,23%
Istruzioni per ogni funzione
5b 4b 3b 1b 6b 2b restanti Funzioni Funzioni
Figura 4.1: Distribuzione di tutte le istruzioni chiamate dall’algoritmo MDR, analizzando un dataset costituito da 1.000 attributi per 1.600 pazienti diversi
te tramite la tecnica di profiling è stata effettuata sia in relazione al tempo di esecuzione sia al numero di chiamate effettuate per ogni funzione. Il risultato di tale analisi è stato l’identificazione di alcune funzioni che con- tribuiscono maggiormente al tempo di esecuzione totale e al numero di istruzioni eseguite dell’algoritmo. Dall’analisi delle istruzioni eseguite si evidenzia che il 90% delle istruzioni vengono eseguite da 6 funzioni (fa- centi parte della partizione model building functions) mentre le restanti 21 procedure eseguono il 10% delle istruzioni (vedi figura 4.1).
Dall’analisi dei tempi di esecuzioni si evidenzia che 85% del tempo di esecuzione è relativo alle stesse 6 funzioni (facenti parte delle model building functions) sopra individuate, mentre il 15% rimanente è relativo alle restanti 21 funzioni (vedi figura 4.2).
Dai risultati ottenuti e rappresentati nelle figure 4.1 e 4.2, si indivi- dua un blocco di 6 funzioni con un alto carico computazionale (90% istru- zioni eseguite e 85% tempo di esecuzione) su cui focalizzare l’analisi di partizionamento hw/sw.
La tabella 4.2 riporta i risultati di profiling relativi alle funzioni più si- gnificative. Il dataset utilizzato come input è costituito da: N = 3 con una
30,46% 29,11% 20,21% 3,42% 0,00% 2,05% 14,75%
Tempo di esecuzione per ogni
funzione
5b 4b 3b 1b 6b 2b restanti 85% 15%Tempo di esecuzione totale
blocco principale restanti
Funzioni
Funzioni
Figura 4.2: Tempi di esecuzione dell’algoritmo MDR, analizzando un dataset costituito da 1.000 attributi per 1.600 pazienti diversi
lista di attributi pari a 1.000 e una lista di pazienti pari a 1.600.
Tabella 4.2: Dati di profiling dell’algoritmo MDR, analizzando un dataset costituito da 1.000 at- tributi per 1.600 pazienti diversi. Sono riportati i dati relativi alle funzioni più significative (model
building functions)
ID Istruzioni totali Numero di chiamate Tempo di esecuzione (sec.)
Totale 303,360,518 18,999,115,020 28,363 1b 10,986,180 166,167,000 1,005 2b 7,803,300 166,167,000 731 3b 67,032,000 4,040,361,944 8,195 4b 76,608,000 4,040,361,944 9,264 5b 109,440,000 8,080,723,888 8,709 6b 444,600 166,167,000 123
Per stabilire le dipendenze tra le funzioni è stato realizzato il grafo del- le chiamate. Dall’analisi del grafico si individuano i seguenti blocchi di funzioni:
model building blocco principale, formato principalmente dalle 6 procedu- re sopra identificate
CAPITOLO 4. ANALISI DELL’ALGORITMO MDR 50
model evaluation blocco secondario, composto dalle funzioni che valuta- no il modello
manage dataset blocco che gestisce il dataset in input all’algoritmo
Dall’analisi dipendenze tra funzioni (vedi sottosezione 4.1.3) appare evi- dente concentrare il partizionamento hw/sw sul blocco model building poi- ché i benefici che se ne traggono risultano decisamente superiori rispet- to a quelli dei restanti blocchi (90% istruzioni eseguite e 85% tempo di esecuzione rispetto 10% istruzioni eseguite e 15% tempo di esecuzione).
Un’analisi del grafo delle dipendenze consente di rivelare le dipenden- ze dei dati. Identificare le dipendenze dato è un compito essenziale perché i trasferimenti di dati sono uno dei fattori principali che influenzano le pre- stazioni di un sistema hardware/software. L’obiettivo è quello di capire quali sono i dati necessari per ogni funzione e quali sono le funzioni o bloc- chi di funzioni che producono tali dati. Questo obiettivo è stato raggiunto studiando il grafico delle chiamate che evidenzia le relazioni tra funzio- ni: per ogni relazione è stata stimata la quantità di dati trasferita analiz- zando il codice sorgente dell’algoritmo MDR, queste informazioni saranno parte del modello del sistema finale. Il grafico di chiamata, insieme con le dipendenze dei dati tra le funzioni, è mostrato in figura 4.3.
Con i dati ottenenti è possibile passare alla fase di creazione modello (vedi sottosezione 4.1.4) in grado di simulare il comportamento dell’algorit- mo MDR. Il modello consente di stimare il tempo di esecuzione dell’algorit- mo MDR, considerando i nodi in hardware oppure in software, la velocità di trasferimento dei dati da un nodo software ad un modulo hardware e viceversa e lo speed-up del modulo hardware rispetto alla funzione soft- ware. Il modello prende in esame la quantità di dati trasmessi tra funzione chiamante e funzione chiamata in modo da valutare l’incidenza del tempo di trasferimento dati tra un nodo software e un nodo hardware. La simu- lazione del modello, applicando differenti soluzioni di partizionamento re-
1r 8r 2r 3r 4r 9r 5r 6r 7r 1b 2b 3b 4b 5b 6b 1d 2d 3d 4d 5d 6d 7d 8d 9d 1e 3e Li ve llo d i ch iamata 0 Model Building Model Evaluation Gestione Dataset Dipendenza Dato Dipendenza di Funzione 2e Li ve llo d i ch iamata 1 Li ve llo d i ch iamata 2 Li ve llo d i ch iamata 3 Li ve llo d i ch iamata 4
Figura 4.3: Grafo delle chiamate - mostra le dipendenze temporali e di dato
lative al blocco principale, ha evidenziato differenti risultati. Attraverso il modello è possibile simulare le performance dell’algoritmo in relazione ad un partizionamento hardware/software selezionato. Tale processo rientra nella fase di analisi prestazione (vedi sottosezione 4.1.5).
La tabella 4.3 mostra i risultati medi ottenuti simulando differenti soluzio- ni di partizionamento, speed-up e velocità di trasferimento dati. La prima riga riporta l’esecuzione puramente software (il parametro N è impostato a 3) utilizzando un dataset composto da 1.000 attributi relativi a 1.600 pa- zienti diversi. Le altre righe mostrano come il tempo cambia in funzione al partizionamento adottato. Le simulazioni sono state effettuate prendendo in considerazione diversi hw speed-up (da 10x a 1.000x) e diverse velocità di trasferimento dati tra nodo hardware e nodo software (da 10MB/s fino a 120MB/s); tale intervallo è stato determinato analizzando i datasheet dei bus di comunicazione [75] [76], concludendo che esperimenti con velocità di trasferimento superiore a 120MB/s non comportano un significativo au- mento nelle prestazioni. Dalla tabella si può vedere che il miglior risultato si ottiene quando tutte le funzioni model building e tutti i nodi aventi con
CAPITOLO 4. ANALISI DELL’ALGORITMO MDR 52
esse dipendenze di dato, vengono implementati come moduli hardware.
Tabella 4.3: Dati ottenuti dalla simulazione del modello considerando una velocità di trasferimento dei dati da un nodo software a un nodo hardware di 65MB/s e una velocità di elaborazione del nodo hardware di 100 volte più veloce rispetto allo stesso nodo implementato in software. La tabella mostra come il tempo di esecuzione camba quando viene utilizzato un differente partizionamento hw/sw
Tempo di esecuzione (sec.) Moduli hardware Speed-up
28.363 None 1,00x 20.611 5b 1,38x 15.244 1b,3b,5b 1,86x 10.095 1b,2b,3b,4b,5b 2,81x 6.021 1b,2b,3b,4b,5b,6b 4,71x 406 1b,2b,3b,4b,5b,6b,1e,2e,3e,2r,3r,4r 68,78x
Dalla tabella 4.3 sopra riportata si nota che analizzando esclusivamente le procedure principali (1b,2b,3b,4b,5b) del partizionamento model building si ottiene un miglioramento di circa 3 volte rispetto alla implementazio- ne puramente software. Considerando le procedure che presentano delle dipendenze con il blocco principale e analizzando i dati trasferiti, si nota che implementando tutti i nodi del blocco principale (1b,2b,3b,4b,5b,6b) in hardware si ottiene un miglioramento di 5 volte. Considerando invece tutte le procedure che hanno dipendenze di dato con il blocco principale e implementandole tutte in hw (blocco principale e i nodi1e,2e,3e,2r,3r,4r) si ottengono notevoli miglioramenti, si riduce il tempo di esecuzione di circa 68 volte rispetto all’implementazione puramente software.
Nella figura 4.4 sono mostrati, tramite istogrammi, tutti i risultati rela- tivi al tempo di esecuzione e al miglioramento (speed-up) dell’algoritmo in base al tipo di partizionamento adottato. Sull’asse delle ordinate vengo- no riportati i tempi di esecuzione, espressi in secondi oppure lo speed-up, mentre sull’asse delle ascisse è riportato il tipo di partizionamento conside-
rato, evidenziato nella tabella 4.4.
Tabella 4.4: Indici che identificano il tipo di partizionamento hardware/software adottato
ID Procedure realizzate in hardware
1 none 2 5b 3 4b,5b 4 3b,5b 5 1b,4b,5b 6 1b,3b,4b,5b 7 1b,2b,3b,4b,5b 8 1b,2b,3b,4b,5b,6b 9 1b,2b,3b,4b,5b,6b,7r 10 1b,2b,3b,4b,5b,6b,1e,2e,3e,2r,3r,4r
Ogni valutazione delle prestazioni dell’algoritmo, in relazione ad un partizionamento, è stata effettuata considerando 4 differenti speed-up del modulo hardware rispetto alla funzione softwar: 10x, 100x, 200x, 1.000x.
Dai grafici risulta che le tipologie di partizionamento 3,4 e 6 ottengono risultati peggiori rispetto all’implementazione puramente software aven- do una velocità di trasferimento dati hw/sw inferiori o uguale a 80MB/s, questo perchè la quantità di dati da trasmettere tra nodo hardware e nodo software è elevata; questo comporta tempi di trasmissione notevoli rispetto alla trasmissione da una funzione software ad un’altra funzione software. E’ quindi fondamentale considerare le dipendenze di dato e la quantità di dati trasmessi tra le funzioni padre-figlio, per ottenere un miglior partizio- namento. La tipologia 10 soddisfa le principali dipendenze di dato relative al blocco principale, ottenendo risultati importanti.
CAPITOLO 4. ANALISI DELL’ALGORITMO MDR 54
Figura 4.4: Dati relativi alla simulazione del modello, impostando una velocità di trasferimento dei dati, tra nodo hardware e software, pari a 40, 65, 80 e 120MB/s
L’analisi relativa ai tempi di esecuzione dell’algoritmo ha permesso di creare un insieme di possibili tipi di partizionamento hw/sw che garanti- scono i migliori risultati in termini di prestazione. Si passa ora ad analizzare come questi partizionamenti influenzano i costi di sistema relativi al dispo- sitivo utilizzato. Attraverso questa analisi è possibile scegliere i dispositivi più vantaggiosi per implementare i moduli hardware al fine di sviluppare un sistema con il migliore partizionamento hw/sw, garantendo sia le mi- gliori prestazioni sia i più bassi costi.
L’analisi viene effettuata considerando come device per l’implementazione dei moduli hardware, le Field Programmable Gate Array (FPGA) prodot- te da Xilinx (vedi sottosezione 3.6.2). Sono state scelte queste categorie di dispositivi poiché presentano caratteristiche intermedie rispetto ai dispo- sitivi Application Specific Integrated Circuit (ASIC) da un lato e a quelli con architettura Programmable Array Logic (PAL) dall’altro. Le FPGA so- no programmate direttamente dall’utente finale, consentendo la diminu- zione dei tempi di progettazione, di verifica mediante simulazioni e di pro- va sul campo dell’applicazione. Il grande vantaggio rispetto agli ASIC è che permettono di apportare eventuali modifiche o correggere errori semplice- mente riprogrammando il dispositivo in qualsiasi momento. Di contro, per applicazioni su grandi numeri sono poco economiche perché il prezzo uni- tario del dispositivo è superiore a quello degli ASIC (che al contrario hanno elevati costi di progettazione).
Per contenere i costi è necessario trovare un dispositivo che offra esat- tamente il numero di risorse richieste dal sistema. Questo problema è diffi- cilmente risolvibile se si ricerca la soluzione ottimale nei dispositivi FPGA, poiché tali device nascono con un numero di risorse standard e risulta mol- to improbabile la coincidenza tra risorse offerte dalla FPGA e risorse richie- ste dal sistema; la soluzione ottimale si trova realizzando un sistema ad hoc, questo comporta ottime prestazioni e unit cost bassi, ma Non Recurring
CAPITOLO 4. ANALISI DELL’ALGORITMO MDR 56
Engineering (NRE) costmolto elevati. E’ quindi necessario conoscere il nu- mero di sistemi da produrre e il time-to-market, per poter stabilire se la scelta migliore è utilizzare una FPGA con NRE cost bassi e tempi di progettazione inferiori (ad un sistema ad hoc) ma unit cost elevati oppure un sistema ad hoc con NRE cost elevati ma unit cost bassi e tempi di progettazioni elevati.