Sviluppo di algoritmi paralleli per l’analisi di ”storie” simulative

In fase implementativa è stato opportuno rispettare alcuni requisiti:
• il linguaggio prescelto è il Fortran77 per motivi di coerenza con il codice
originale.
• per la parallelizzazione del codice sono state scelte le librerie MPI nella
versione MPICH in quanto compatibile con vari moduli del pacchetto AM-
BER, scelto per condurre le simulazioni su piattaforma Linux (il sistema
operativo installato sui PC).
• il cluster è gestito con openMosix che fornisce ottimi strumenti per una
agevole amministrazione del sistema e si è rivelato utile anche per la realiz-
zazione del progetto.
La parallelizzazione di uno di tali programmi (quello che analizza la mobilità del
solvente) è stata realizzata secondo tre diversi approcci o ”modelli” per quanto
concerne la distribuzione del lavoro sui nodi del cluster. L’efficienza di ciascuna
delle tre versioni è stata misurata attraverso numerose prove condotte sul cluster.
I risultati dei test indicano che il modello più efficiente è quello che trae vantaggio
dalla presenza del filesystem di openMosix, benchè sia stata disabilitata la feature
più interessante messa a disposizione da questo software, ossia la ”migrazione
dei processi”. Ciò si è reso necessario in quanto essa interferiva con il normale
funzionamento del programma usato per eseguire la simulazione (cioè il modulo
SANDER del pacchetto AMBER).
Il guadagno derivante dalla parallelizzazione, in termini di tempo e di ottimiz-
zazione dell’uso delle risorse, si è rivelato rilevante. Inoltre lo schema può essere
considerato paradigmatico in quanto è adottabile per parallelizzare tutta una se-
rie di altri programmi aventi analoga struttura ma con richieste computazionali
anche più elevate.
L’esperienza accumulata indica anche che probabilmente è possibile ottenere ul-
teriori miglioramenti, analizzando più approfonditamente l’interazione fra i vari
software coinvolti e risolvendo eventuali reciproche incompatibilità.
Capitolo 1
Introduzione
La branca dell’Informatica nota come High Performance Computing (HPC) sta
acquisendo giorno dopo giorno sempre maggior importanza e, di riflesso, nuovi
approcci computazionali appaiono all’orizzonte. Assistiamo quindi al continuo
affinamento di algoritmi per il calcolo parallelo e distribuito che ci permettono di
ottimizzare e gestire in maniera più efficiente le risorse a disposizione, per esempio
ripartendo meglio i carichi di lavoro. Da questo sforzo sono scaturiti numerosissi-
mi miglioramenti software tra cui librerie per il calcolo parallelo, software per la
gestione di clusters , programmi predisposti ed ottimizzati per il calcolo distribui-
to, grid computing. Nel frattempo miglioramenti tecnologici a livello hardware
hanno consentito vistosi aumenti delle potenze di calcolo pur con un netto calo
dei costi.
I vantaggi più evidenti che ne sono derivati sono:
• significativi aumenti dell’affidabilità dei sistemi di calcolo e della loro sem-
plicità di utilizzo, che consente ai ricercatori di concentrarsi sulle proprie
ricerche e non su una continua opera di gestione e manutenzione delle risorse
impiegate
• drastiche diminuzioni dei tempi necessari per effettuare, per esempio, espe-
rimenti al computer nell’ambito della Bionformatica Simulativa che richiede
notoriamente richieste elaborative molto consistenti
• aumenti significativi della quantità e della qualità dei dati sia negli esperi-
menti reali che in quelli simulati
1
CAPITOLO 1. INTRODUZIONE 2
Nell’ambito dell’HPC si colloca anche il lavoro svolto per la preparazione di questa
tesi, che riguarda la parallelizzazione di un programma per effettuare l’analisi
statistica di ”storie simulative” allo scopo di renderne più efficiente l’utilizzo su
un cluster di PC. Come verrà discusso nel proseguo lo schema di parallelizzazione
adottato è applicabile a tutta una serie di altri programmi di analisi altrettanto
se non maggiormento onerosi in termini di tempo di elaborazione.
L’esposizione di questa tesi si articolerà come segue:
• nel Cap. 2 si presentano cenni essenziali sulle esigenze computazionali della
Bioinformatica Simulativa
• nel Cap. 3 sono introdotte le librerie MPI per il il cacolo parallelo
• nel Cap. 4 è introdotto il software per la gestione di cluster di PC openMosix
• nel Cap. 5 viene discusso lo scopo del progetto
• nel Cap. 6 viene presentato il codice di un programma seriale per l’analisi
statistica della diffusione
• nel Cap. 7 vengono presentate diverse implementazioni parallele dello stesso
programma
• nel Cap. 8 vengono esposti i risultati dei test delle prestazioni di queste
implementazioni
• nel Cap. 9 si riportano conclusioni ed indicazioni per sviluppi futuri
Capitolo 2
Bioinformatica Simulativa
Nella Bioinformatica Simulativa si utilizzano metodi informatici e sistemi com-
putazionali per realizzare ed analizzare simulazioni di sistemi fisici rilevanti dal
punto di vista biologico.
Le simulazioni di sistemi biomolecolari forniscono risultati che possono integrare
quelli ottenibili con esperimenti di laboratorio, facilitandone l’interpretazione a
livello di modelli miscroscopici.
Uno dei problemi per lo studio dei quali la Bionformatica Simulativa affianca
proficuamente la ricerca sperimentale è il folding delle proteine. Tale fenomeno
rappresenta il passaggio cruciale delle proteine dalla forma lineare, risultante dalla
trascrizione del messaggio genomico, alla struttura 3D che è la forma proteica
funzionale.
Nella simulazione di Dinamica Molecolare (MD) di un fenomeno, l’evoluzione di
un sistema molecolare viene realizzata sul computer secondo un passo temporale
tanto più piccolo quanto più fine è il dettaglio fisico con cui si vuole analizzare
il fenomeno. Questa esigenza si traduce spesso (in particolare quando sono coin-
volte macromolecole) in tempi di elaborazione molto grandi e in quantità di dati
rilevanti. Questi costituiscono la cosiddetta ”storia simulativa” che deve essere
analizzata statisticamente, quasi sempre off-line rispetto alla simulazione.
Quindi, tanto la fase di simulazione quanto quella di analisi dei dati prodotti
può richiedere grandi potenze elaborative intese come computer particolarmente
performanti o addirittura insiemi (anche vasti) di computer che lavorano con-
temporaneamente su un dato problema. Normalmente la potenza elaborativa
3
CAPITOLO 2. BIOINFORMATICA SIMULATIVA 4
richiesta è proporzionale tanto alla quantità di dati quanto alla qualità degli
stessi: strumenti migliori comportano più dati e più precisione su questi ultimi.
Come accennato nell’Introduzione, accanto all’aspetto hardware, bisogna consi-
derare anche l’impatto del software. Il progresso nel campo degli algoritmi per il
calcolo parallelo e distribuito hanno portato alla vasta disponibilità di software
adatto allo scopo, tra i quali vale la pena ricordare:
• appositi programmi e suite di programmi (come le suite AMBER, CHARMM,
GROMOS) che consentono di progettare simulazioni ed analizzarne i risul-
tati
• librerie per il calcolo parallelo e distribuito (es. le librerie MPI, PVM,...)
che supportano svariati linguaggi di programmazione (Fortran, C, C++,
Java in primis) e che consentono di sviluppare rapidamente programmi per
distribuire e gestire i carichi di lavoro.
• software per la gestione di cluster di computer (es.: openMosix, Beowulf),
per ”sommare” le potenze elaborative di singole macchine per ottenere
ragguardevoli potenze di calcolo complessive.
• grid computing che permette di distribuire i carichi di lavoro su macchine
anche molto distanti geograficamente fra loro.
• distributed computing : riguarda, per esempio, progetti SETI@Home e Fol-
ding@Home (per lo studio massivo del folding delle proteine, vedi Fig. 2.1)
consentono di distribuire il lavoro su scala globale sfruttando i tempi morti
di macchine altrimenti non utilizzate.
Allo scopo di effettuare la parallelizzazione del codice accennato nell’Introduzione
verranno usate features offerte dalle librerie MPI e dal pacchetto openMosix. Nei
capitoli che seguono vengono richiamate le loro caratteristiche salienti.
CAPITOLO 2. BIOINFORMATICA SIMULATIVA 5
Figura 2.1: Distribuzione su scala globale degli utenti di Folding@Home
Capitolo 3
Elementi essenziali di MPI
3.1 Il paradigma
Lo scambio di messaggi (message passing) è uno dei paradigmi di programmazio-
ne più usati nell’ambito del calcolo parallelo specialmente sui cosiddetti Computer
Paralleli Scalabili (Scalable Parallel Computers, SPC ) con memoria distribuita
(distributed memory) e su Reti di Calcolatori (Networks of Workstations, NOW ).
Il concetto chiave è, come si può capire dal nome del paradigma, un continuo
scambio di informazioni (sotto forma di messaggi) fra più entità elaborative in-
dipendenti, solitamente riconducibili a processi o thread del Sistema Operativo
sottostante.
3.2 Breve storia di MPI
Nel 1992 un gruppo di istituzioni accademiche e membri del mondo dell’industria
diede origine ad un interest group, l’MPI Forum. Scopo di tale gruppo di lavoro
era la produzione di uno standard comune, basato sul paradigma message pas-
sing , che permettesse lo sviluppo di software efficiente e, soprattutto, portabile
(all’epoca esistevano infatti numerose librerie proprietarie per il calcolo parallelo
e distribuito, incompatibili fra loro).
I membri del Forum (80 persone provenienti da 40 fra istituzioni accademiche e
companies) ratificarono nel 1994 una prima edizione dello standard denominato
Message Passing Interfaces (MPI) 1.0. L’approccio nella scelta delle features da
6
CAPITOLO 3. ELEMENTI ESSENZIALI DI MPI 7
includere nello standard fu molto libertario: relativamente a ciascun contesto, si
preferì includere più opzioni diverse piuttosto di sceglierne una sola. Il risultato
di questa prassi è uno standard ricco di soluzioni e, per tanto, molto versatile
e completo. Nel corso degli anni, dopo una serie di correzioni confluite nella
revisione 1.1 dello standard, nel Luglio del 1997 fu ratificata l’attuale edizione, la
2.0 [21] e [15].
3.3 Le due edizioni dello Standard
Lo standard MPI 1.0 include:
• funzioni locali e non locali:
1. local : il completamento dipende solo dall’esecuzione del processo loca-
le. Tali operazioni (es: la funzione che recupera il nome della macchina
su cui è in esecuzione il processo) non necessitano di una comunica-
zione esplicita con un altro processo. Secondo le specifiche, tutte le
chiamate MPI che riguardano oggetti locali, sono locali.
2. non-local : il completamento può richiedere l’esecuzione di qualche
procedura MPI su un altro processo (es: sincronizzazione dei trasferi-
menti). Molte chiamate di comunicazione MPI sono di tipo non-locale.
• comunicazione point-to-point: lo standard definisce apposite funzioni,
costanti e tipi per la comunicazione ed il trasferimento di dati fra le va-
rie entità elaborative. In particolare sono supportate i seguenti tipi di
operazione:
1. blocking : il completamento implica la possibilità da parte dell’uten-
te di riutilizzare le risorse (es: buffer di invio o ricezione) utilizzate
durante la chiamata.
2. non-blocking : la procedura può ritornare prima che l’operazione ini-
ziata dalla chiamata termini (es: invii multipli di dati con possibili
sovrascritture dei buffer di trasmissione).
CAPITOLO 3. ELEMENTI ESSENZIALI DI MPI 8
3. cooperative: i dati sono esplicitamente inviati e ricevuti, ossia tutti i
processi coinvolti nella comunicazione devono dare il consenso al tra-
sferimento. Un vantaggio è che ogni scrittura di dati avviene con la
partecipazione del processo ricevente.
• gruppi di processi: MPI permette il raggruppamento logico di processi,
aumentando così la flessibilità della distribuzione di lavoro (es: i processi
con un rank pari possono svolgere una porzione di lavoro distinta da quella
eseguita dai processi con rank dispari)
• domini di comunicazione fra i processi: un messaggio può essere in-
viato e ricevuto nell’ambito di un intero gruppo di processi. Un dominio
è quindi uno spazio di comunicazione ristretto e definito nel quale solo
i processi ”membri” possono scambiarsi messaggi. Ogni processo MPI in
esecuzione, per default, appartiene al dominio MPI_COMM_WORLD. Lo
standard permette la creazione di nuovi domini.
• interfaccia per il profiling dei programmi: lo standard definisce ap-
posite interfacce e funzioni per aiutare i programmatori in fase di profiling
delle applicazioni basate su MPI. Tale tecnica si rivela molto utile in fase di
ottimizzazione di un programma in quanto permette di ottenerne un rappor-
to dettagliato e completo (”profilo”) delle prestazioni di ciascuna funzione
invocata o meccanismo logico interno (subsystem). A tale scopo, per ogni
funzione MPI ne esiste una corrispondente con profiling attivo, solitamente
presente in un’apposita libreria esterna.
• supporto (bindings) per Fortran e C: la prima versione dello standard
definisce esattamente i nomi delle funzioni, delle costanti, dei tipi e delle
strutture MPI per questi due diffusi linguaggi di programmazione.
Lo standard MPI 2.0 aggiunge:
• gestione dinamica dei processi: è possibile intervenire sullo stato di
un processo MPI direttamente in fase di esecuzione (es: fermarlo e farlo
ripartire).
• gestione estesa dell’Input/Output (I/O): vengono definite nuove fun-
zioni per le operazioni di Input/Output (es: una vasta collezione di funzioni
per l’accesso condiviso da parte di più processi di un file)