Ημερολόγιο Εκδηλώσεων

Περιγραφή:
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών Πρόγραμμα Προπτυχιακών Σπουδών ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ Δημήτριου Μποζίκα με θέμα Σχεδίαση και Yλοποίηση Συστήματος Πολλαπλών FPGA για την Επιτάχυνση Μεγάλης Κλίμακας Αναλύσεων Πληθυσμιακής Γενομικής βασιζόμενες σε Ανισορροπία Σύνδεσης Design and Implementation of a Multi-FPGA Acceleration System for Large-Scale Population Genomics Analyses based on Linkage Disequilibrium Εξεταστική Επιτροπή Καθηγητής Απόστολος Δόλλας (επιβλέπων) Καθηγητής Διονύσιος Πνευματικάτος Αναπληρωτής Καθηγητής Γιάννης Παπαευσταθίου Περίληψη Σύγχρονες τεχνολογίες sequencing έχουν συμβάλλει στη δημιουργία και τη διεύρυνση βάσεων δεδομένων DNA, οι οποίες απαριθμούν ήδη χιλιάδες ολόκληρα γονιδιώματα. Ο ρυθμός με τον οποίο γενομικά δεδομένα συλλέγονται, σε συνδυασμό με το γεγονός ότι έχει ξεπεράσει το νόμο του Moore, εδραιώνει την ανάγκη για την ανάπτυξη νέων εργαλείων, ικανών να διενερούν γενομικές αναλύσεις μεγάλης κλίμακας αποδοτικά. Η παρούσα δουλειά εστιάζει στις υπολογιστικές προκλήσεις που συνοδεύουν την ανάλυση των επιπέδων ανισορροπίας σύνδεσης (LD) σε μεγάλα set δεδομένων. Το LD είναι μία στατιστική που προσδιορίζει τη μη τυχαία συσχέτιση μεταξύ αλληλόμορφων γονιδίων σε διαφορετικές γενομικές τοποθεσίες. Ενώ χρησιμοποιέιται σε μεγάλο εύρος γενομικών και γενετικών αναλύσεων, η εξάρτιση του υπολογισμού του από την απαρίθμηση των set bits (population count) σε μεγάλα vectors δεν επιτρέπει την αποδοτική χρήση των σύχρονων CPUs για τέτοιου είδους αναλύσεις, κυρίως λόγω της έλλειψης ενός vectorized population counter. Σαν απάντηση, παρουσιάζουμε μία καινοτόμα αρχιτεκτονική για τον υπολογισμό του LD ανά ζεύγη με τη χρήση αναδιατασσόμενης λογικής. Το προτεινόμενο σύστημα εκμεταλλεύεται την ικανότητα των αναδιατασσόμενων μηχανών να προγραμματίζονται σε επίπεδο υλικού. Η χρήση πολλαπλών επιπέδων παραλληλισμού, σε συνδυασμό με την αποδοτική διαχείριση των δομών δεδομένων στη μνήμη μέσα από το μετασχηματισμό του memory layout, προσφέρουν υψηλό throughput για την εκτίμηση του LD σε μεγάλα set δεδομένων. Η αρχιτεκτονική υλοποιείται σε μία ετερογενή υπολογιστική πλατφόρμα, η οποία διαθέτει ένα memory interface μεγάλου εύρους ζώνης και επιτρέπει την παράλληλη συνεργασία τεσσάρων FPGA. Το υλοποιημένο σύστημα αξιολογείται για την ανάλυση τεχνητών γενομικών δεδομένων μεταβαλλόμενου μεγέθους μέσω της σύγκρισης με αντίστοιχες παράλληλες υλοποιήσεις σε software, πετυχαίνοντας επιτχύνσεις μεταξύ 6.35Χ και 134.93Χ, ανάλογα με το μέγεθος του δείγματος. Σε πιθανές πραγματικές αναλύσεις, όπως η σάρωση του 22ου χρωμοσώματος του ανθρώπινου γονιδιώματος για ίχνη δετικής επιλογής, το σύστημα είναι είναι ικανό να αποδώσει πενταπλάσιο throughput σε σχέση με αντίστοιχες βέλτιστες υλοποιήσεις σε software που εκτελούνται σε πολλαπλούς πυρήνες. Abstract Modern sequencing technologies have contributed to the creation and rapid expansion of DNA databases, already numbering thousands of whole genomes. The astonishing rate at which genomic data are being collected, combined with the fact that it has outpaced Moore’s law, establishes the necessity of the development of novel tools, capable of conducting large-scale genomics analyses efficiently. This work addresses the computational challenges inherent to the analysis of linkage disequilibrium (LD) levels in large-scale datasets. LD is a statistic that quantifies the non-random association between alleles at different genomic locations. While it contributes to a wide variety of genomics and genetics analyses, the compute- and memory-intensive operation of counting set-bits (population count) in large vectors, required for the estimation of LD, hinders the efficient use of modern CPUs for such analyses, mainly due to the lack of a vectorized population counter. To overcome this obstacle, we present a novel hardware architecture for the calculation of pairwise LD scores based on reconfigurable logic. The proposed accelerator exploits the ability of reconfigurable machines to be programmed at the hardware level. The effective use of multiple levels of parallelism, combined with the efficient manipulation of the data structures on memory through the transformation of the memory layout, result in high throughput capabilities for the estimation of LD in arbitrarily large datasets. The architecture is, subsequently, mapped onto a high-performance heterogeneous computing platform that enables the parallel cooperation of 4 reconfigurable devices, while, simultaneously, providing a high-speed memory interface. The implemented accelerator is evaluated for analyses of simulated genomic data of varying sizes, through its comparison with corresponding state-of-the-art parallel software implementations, achieving speedups between 6.35X and 134.93X, depending on the dataset size. Concerning real-world analyses, such as scanning the 22nd chromosome of the human genome for traces of positive selection, the accelerator is capable of potentially achieving quintupled throughput when compared to highly optimized reference software running on multiple cores.