Insegnare la programmazione parallela attraverso l'allineamento delle sequenze DNA

Quest'articolo descrive un compito incentrato sull'allineamento delle sequenze di DNA, pensato per un corso di Calcolo Parallelo. L'assegnazione ha l'obiettivo di aiutare gli studenti a imparare e applicare diverse tecniche di programmazione utilizzando OpenMP, MPI e CUDA/OpenCL. Il problema affrontato riguarda la ricerca di corrispondenze esatte di brevi schemi di DNA all'interno di una sequenza di DNA più lunga.

#Contesto dell'Assegnazione

Dal 2017, ogni anno viene introdotto un nuovo problema per dimostrare come affrontare lo stesso problema computazionale usando vari metodi di programmazione parallela. Gli studenti acquisiscono esperienza con la programmazione in memoria condivisa tramite OpenMP, la programmazione in memoria distribuita con MPI e la programmazione GPU con CUDA o OpenCL. Quest'anno, gli studenti hanno affrontato un metodo di forza bruta per identificare corrispondenze esatte di più stringhe di nucleotidi in una sequenza di DNA.

La versione sequenziale del programma è facile da seguire, rendendola accessibile per gli studenti, mentre offre opportunità di parallelizzazione e ottimizzazione. L'assegnazione affronta anche concetti sfidanti come le condizioni di competizione, le riduzioni e le comunicazioni punto a punto, che spesso sono difficili da comprendere per gli studenti in situazioni pratiche.

#L'Importanza della Parallelizzazione

La programmazione parallela utilizza più processi per completare i compiti più velocemente, suddividendo il lavoro tra le risorse disponibili. Questa assegnazione introduce concetti essenziali nella programmazione parallela, permettendo agli studenti di familiarizzare con varie strategie per migliorare le prestazioni.

All'Università, un corso di Programmazione Parallela viene offerto nel terzo anno del programma di Ingegneria Informatica. Questo corso insegna idee fondamentali riguardanti Modelli di memoria condivisa e distribuita, insieme alla programmazione GPU. Le passate assegnazioni hanno dimostrato che questi approcci possono insegnare agli studenti come trasmettere concetti attraverso diversi metodi di programmazione.

#Il Problema dell'Allineamento delle Sequenze di DNA

Le sequenze di DNA sono rappresentate come stringhe di caratteri, ciascun simbolo che simboleggia un tipo di nucleotide. L'obiettivo dell'assegnazione è identificare corrispondenze esatte di schemi di nucleotidi all'interno di una sequenza di DNA più lunga. Gli schemi possono essere sequenze casuali o copie esatte di parti della sequenza principale.

Sono stati sviluppati diversi algoritmi avanzati per questo problema, ma è stato scelto un approccio di forza bruta semplice. Questo metodo controlla ogni schema da ogni possibile posizione di partenza nella sequenza di DNA, con opportunità di facile parallelizzazione esaminando sia gli schemi che le posizioni di partenza. Il programma registra solo la prima occorrenza di qualsiasi schema trovato.

#Concetti Chiave Trattati nell'Assegnazione

Ogni assegnazione mira a insegnare un ampio raggio di concetti del corso. Questa particolare assegnazione ruota attorno a due cicli annidati, che possono essere parallelizzati indipendentemente o congiuntamente. Gli studenti devono identificare quali variabili sono condivise o private, affrontando le condizioni di competizione quando gestiscono i contatori di corrispondenza e un array condiviso.

L'assegnazione include anche il calcolo delle somme di controllo delle impronte delle posizioni di partenza e il monitoraggio di quante posizioni corrispondono a più di uno schema. Questi controlli aiutano a confermare l'accuratezza quando si modifica il codice per migliorarne le prestazioni. Gli studenti devono analizzare quando è meglio utilizzare operazioni atomiche o riduzioni per compiti specifici.

Le soluzioni sviluppate dagli studenti saranno convertite tra OpenMP e CUDA/OpenCL. In CUDA/OpenCL, lavoreranno con blocchi di thread e accessi alla memoria. Per MPI, gli studenti devono suddividere la sequenza di DNA tra più processi, permettendo ad alcune ricerche di iniziare su un processore e finire su un altro, incorporando un modello a pipeline con comunicazioni.

La flessibilità delle assegnazioni consente agli studenti di generare schemi con diverse lunghezze e posizioni, utilizzando strategie di bilanciamento del carico per migliori prestazioni tra diversi modelli di programmazione. Il codice aiuta gli studenti a evitare la gestione complessa della memoria utilizzando array unidimensionali per la sequenza di DNA e gli schemi.

#Contesto Didattico e Coinvolgimento degli Studenti

Prima di affrontare questa assegnazione, gli studenti apprendono sistemi operativi, concorrenza e il linguaggio di programmazione C. In un recente corso, 44 studenti hanno partecipato, lavorando in coppie ai loro progetti. La partecipazione è stata forte, con 40 studenti attivamente coinvolti.

Si tiene una sessione introduttiva per presentare il problema dell'allineamento delle sequenze di DNA e la sua implementazione attraverso esempi pratici. Gli studenti ricevono un documento informativo che delinea i loro compiti insieme a un codice di partenza che evidenzia le parti che possono modificare. Vengono forniti esempi per generare varie sequenze principali e schemi.

Gli studenti partecipano a lezioni e sessioni di laboratorio per tre settimane, apprendendo concetti fondamentali prima di passare una settimana sull'assegnazione. Segue un esame che valuta quanto bene hanno risolto questioni specifiche nel loro lavoro presentato.

È richiesto solo un compilatore C moderno compatibile con OpenMP, una libreria MPI e un toolkit CUDA o OpenCL. OpenMP e MPI possono essere sviluppati su qualsiasi computer multicore, ma è necessaria una scheda GPU per CUDA. Un'esperienza ottimale si trova in un cluster condiviso dove gli studenti possono confrontare i risultati delle prestazioni.

#Feedback ed Esperienze degli Studenti

Alla fine del corso, gli studenti compilano un sondaggio e 26 studenti hanno risposto. Su una scala da 1 a 5, la loro soddisfazione per l'esperienza complessiva ha avuto una media di 3.77, con un punteggio mediano di 4. Alcuni studenti hanno espresso preoccupazioni riguardo al peso degli esami pratici nelle loro votazioni finali, ma hanno concordato che l'assegnazione illustra efficacemente i concetti del corso.

In alcuni casi, gli studenti sono riusciti a ottimizzare i loro codici CUDA per funzionare significativamente più veloce rispetto alla versione base. Il compito OpenMP è stato percepito come il più semplice perché gli studenti potevano ottenere versioni parallele iniziali con una comprensione minima del codice sottostante. D'altra parte, il compito MPI si è rivelato il più difficile a causa delle modifiche al codice richieste.

Il compito CUDA ha portato la maggior soddisfazione, poiché ha permesso transizioni più fluide dalle soluzioni OpenMP, specialmente quando si affrontano le condizioni di competizione. Complessivamente, il livello di coinvolgimento è stato alto, con quasi 9.000 invii effettuati dagli studenti al cluster.

#Conclusione

L'assegnazione sull'allineamento delle sequenze di DNA si rivela uno strumento didattico prezioso nel corso di Calcolo Parallelo. Fornisce agli studenti competenze pratiche nella programmazione parallela attraverso tecniche diverse, migliorando le loro conoscenze sull'argomento. Le sfide affrontate durante questa assegnazione preparano gli studenti a temi più complessi nel calcolo parallelo, contribuendo in modo significativo alla loro esperienza educativa nell'ingegneria informatica.

Con il supporto di strumenti moderni e un ambiente di apprendimento collaborativo, gli studenti possono affrontare problemi del mondo reale in modo efficace sviluppando abilità di programmazione critiche. I risultati di vari concorsi di programmazione forniscono un feedback prezioso sulle prestazioni, incoraggiando un miglioramento continuo e l'esplorazione di diverse metodologie nel campo del calcolo parallelo.