Συντάχθηκε 10-03-2017 09:15
από Esthir Gelasaki
Email συντάκτη: egelasaki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΕΥΑΓΓΕΛΟΥ ΜΑΓΕΙΡΟΠΟΥΛΟΥ
με θέμα
Μία Προσέγγιση με τη Χρήση HLS για την Επιτάχυνση του Αλγορίθμου Δυναμικού Προγραμματισμού Needleman-Wunsch
An HLS Approach to Accelerating the Needleman-Wunsch Dynamic Programming Algorithm
Εξεταστική Επιτροπή
Καθηγητής Διονύσιος Πνευματικάτος (επιβλέπων)
Καθηγητής Απόστολος Δόλλας
Αναπληρωτής Καθηγητής Ιωάννης Παπαευσταθίου
Περίληψη
Τα τελευταία χρόνια, το λογισμικό High Level Synthesis (HLS) έχει παρουσιαστεί ως ένα εργαλείο ανάπτυξης εφαρμογών για τις Συστοιχίες Επιτόπια Προγραμματιζόμενων Πυλών (FPGAs). Αυτό το λογισμικό παρέχει μεγαλύτερο επίπεδο αφαίρεσης σε σχέση με προγραμματιστικές μεθόδους που χρησιμοποιούνται για να περιγράψουν απ’ ευθείας το σχέδιο Register-Transfer Level (RTL) που πρόκειται να υλοποιηθεί σε FPGA. Η Xilinx, η τρέχουσα μεγαλύτερη εταιρεία πώλησης FPGA, έχει παρουσιάσει πρόσφατα το Vivado HLS, ως μέρος της σουίτας σχεδίασης Vivado.
Σε αυτή τη διπλωματική, παρουσιάζουμε την προσέγγισή μας στην υλοποίηση του αλγορίθμου δυναμικού προγραμματισμού Needleman-Wunsch για την ευθυγράμμιση πρωτεϊνικών ακολουθιών στο Vivado HLS, με κύριο στόχο να επιδιώξουμε το μέγιστο δυνατό βαθμό παραλληλισμού και επιτάχυνσης. Η εργασία αυτή προσφέρει μία ανάλυση του αλγορίθμου υπό το πρίσμα του παραλληλισμού, των εξαρτήσεων δεδομένων του και τους περιορισμούς που θέτουν, καθώς και της τοπικότητας δεδομένων, για τη ολοκλήρωση της οποίας αναπτύξαμε ένα προσομοιωτή κρυφής μνήμης σε Java. Επίσης, παρέχει μία ανάλυση του εργαλείου Vivado HLS ως προς την αποδοτικότητά του στην επιτάχυνση του αλγορίθμου και παρουσιάζει μια σύγκριση των μεθοδολογιών που προσφέρει το εργαλείο αυτό για τη βελτιστοποίηση της υλοποίησης.
Αρχικά, παρουσιάζουμε σύντομα τον αλγόριθμο Needleman-Wunsch και περιγράφουμε τη λειτουργία του. Στη συνέχεια, τον αναλύουμε ως προς το μέγιστο βαθμό παραλληλισμού που μπορούμε να πετύχουμε βάσει των περιορισμών του και προχωράμε στην περαιτέρω ανάλυση των μεθόδων που προέκυψαν για τη διάσχιση του πίνακα δυναμικού προγραμματισμού του ως προς την απόδοσή τους σε επίπεδο τοπικότητας δεδομένων. Εδώ παρουσιάζουμε τον προσομοιωτή κρυφής μνήμης, τα αποτελέσματα του οποίου μας είναι χρήσιμα στη σύγκριση της αποδοτικότητας των μεθόδων όσο αφορά το πλήθος ευστοχιών και αστοχιών στην προσπέλαση της κρυφής μνήμης. Ακολούθως, εμφανίζουμε δύο διακριτές υλοποιήσεις του αλγορίθμου στο Vivado HLS: Μία με τη χρήση κώδικα που προήλθε από την υλοποίηση του αλγορίθμου σε λογισμικό και μία με κώδικα που αναπτύξαμε βάσει των ευρημάτων που συλλέξαμε από την ανάλυσή του. Στην πρώτη περίπτωση, χρησιμοποιήσαμε ένα σύνολο από directives που παρέχει το Vivado HLS, ώστε να βελτιώσουμε την απόδοση της υλοποίησης, χωρίς ωστόσο να πετύχουμε παραλληλισμό. Στη δεύτερη, η οποία περιγράφει μία παράλληλη υλοποίηση του αλγορίθμου, παρατηρήσαμε την αδυναμία του Vivado HLS να παράγει την προσδοκώμενη επιτάχυνση της σχεδίασης. Τέλος, παρουσιάζουμε τα συμπεράσματα στα οποία καταλήξαμε και τα οποία αποτελούν έναυσμα για μελλοντική εργασία πάνω στη βελτιστοποίηση της υλοποίησης του αλγορίθμου και τη σύγκρισή του με άλλες υλοποιήσεις.
Abstract
In recent years, High Level Synthesis (HLS) software has been introduced as a tool for developing on Field Programmable Gate Arrays (FPGAs). This software brings a higher level of abstraction compared to traditional programming methods that are used to directly describe the Register-Transfer Level (RTL) design to be implemented on an FPGA. Xilinx, the current largest FPGA vendor has recently introduced Vivado HLS, as a part of the Vivado design suite.
In this thesis, we present our approach at implementing the Needleman-Wunsch dynamic programming algorithm for protein sequence alignment on Vivado HLS, with the main goal to achieve the highest level of parallelism and acceleration. This study contributes an analysis of the algorithm under the scope of parallelism, its data dependencies and the limitations they set, as well as data locality, for which we developed a cache simulator in Java. Additionally, it provides an analysis of Vivado HLS regarding its performance on accelerating the algorithm and presents a comparison of the methods offered by the tool for optimizing the implementation.
Initially, we briefly present the Needleman-Wunsch algorithm and describe its function. Subsequently, we analyze it in regard to the maximum level of parallelism that can be achieved in respect to the limitations of the algorithm and proceed to further examine the available methods of parsing its dynamic programming matrix under the scope of data locality. Here we present the cache simulator, the results of which are important for the comparison of the efficiency of the aforementioned methods regarding their hit/miss rates when accessing the cache memory. Afterwards, we present two discrete implementations of the algorithm on Vivado HLS: One using the code of a software implementation of the algorithm and one with code we developed considering the results of the analysis of the algorithm. In the former case, we used a set of directives offered by Vivado HLS, in order to optimize the performance of our implementation; without however achieving parallelism on the design. In the latter one, which describes a parallel implementation of the algorithm, we observed the inability of Vivado HLS to achieve the expected acceleration of the design. Finally, we present the conclusions of our study, which provide input for further work on optimizing the implementation of the algorithm and comparing it with alternative implementations.
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 2042
Έναρξη: 13/03/2017 14:00
Λήξη: 13/03/2017 15:00
