polito.it
Politecnico di Torino (logo)

Cross Architecture Edit Similarity Join for DNA Data Storage Using oneAPI

Eugenio Marinelli

Cross Architecture Edit Similarity Join for DNA Data Storage Using oneAPI.

Rel. Paolo Garza. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2021

[img]
Preview
PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (2MB) | Preview
Abstract:

La quantità di dati prodotti è destinato ad aumentare in modo significativo nei prossimi anni. Il problema principale legato alla crescita dei dati è rappresentato dal costo di archiviazione di tali dati. Ciò è dovuto alla limitazione fisica rappresentata dai supporti magnetici attualmente utilizzati per l'archiviazione. Un'alternativa ai supporti magnetici contemporanei è rappresentata dal DNA sintetico, ancora poco studiato, ma che presenta alcune proprietà interessanti - in termini di durata e alta densità - che lo rendono molto promettente. Tuttavia, il processo di recupero dei dati dal DNA è limitato da una procedura chiamata "consenso". L'obiettivo di questa procedura è identificare milioni di stringhe univoche tra centinaia di milioni di copie contenenti errori. Ciò coinvolge algoritmi di "similarity join" che tuttavia non sono in grado di scalare su tali dataset a causa sia della complessità della metrica utilizzata - edit distance - sia per il loro design single-thread. In questa tesi, viene presentato OneJoin, un algoritmo di similarity join che può sfruttare CPU multicore, GPU integrate e GPU discrete utilizzando la stessa base di codice. OneJoin è implementato con oneAPI, un modello di programmazione progettato per aumentare la portabilità del codice su diverse architetture. In questo lavoro presentiamo gli aspetti principali di oneAPI e descriviamo le scelte progettuali del nostro algoritmo. Inoltre, presentiamo una pipeline di decodifica dei dati del DNA end-to-end basata su OneJoin e la valutazione sperimentale del nostro algoritmo rispetto alle soluzioni esistenti. Mostreremo che OneJoin può raggiungere una velocità fino a 21 volte superiore rispetto allo state-of-the-art, riducendo il tempo di decodifica dei dati dal DNA da diverse ore a pochi minuti.

Relators: Paolo Garza
Academic year: 2020/21
Publication type: Electronic
Number of Pages: 71
Subjects:
Corso di laurea: Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering)
Classe di laurea: New organization > Master science > LM-32 - COMPUTER SYSTEMS ENGINEERING
Ente in cotutela: TELECOM ParisTech - EURECOM (FRANCIA)
Aziende collaboratrici: Eurecom
URI: http://webthesis.biblio.polito.it/id/eprint/18106
Modify record (reserved for operators) Modify record (reserved for operators)