Αρχιτεκτονικές και FPGA υλοποιήσεις αλγορίθμου για εφαρμογές βιοτεχνολογίας
Loading...
Date
2024-02-27
Authors
Θανοπούλου, Κωνσταντίνα
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Στην παρούσα διπλωματική εργασία εξετάζεται ο αλγόριθμος Smith-Waterman, ο οποίος
είναι ένας από τους βασικούς αλγορίθμους της Βιοπληροφορικής. Η Βιοπληροφορική είναι
ένας επιστημονικός κλάδος που συνδυάζει την επιστήμη της μοριακής βιολογίας με την
επιστήμη των υπολογιστών και θεωρώντας τα βιολογικά δεδομένα (DNA, RNA, πρωτεΐνες)
ως ψηφιακή πληροφορία – ακολουθίες συμβόλων, μπορεί να εφαρμόσει σε αυτά
αλγορίθμους για την επεξεργασία τους και να προκύψουν χρήσιμα συμπεράσματα. Ο
αλγόριθμος Smith-Waterman είναι ένας από τους βασικούς αλγορίθμους στοίχισης δυο
ακολουθιών βιολογικών δεδομένων και βρίσκει με βεβαιότητα πάντα τη βέλτιστη τοπική
στοίχιση τους. Με αυτό τον τρόπο προκύπτει πόσο όμοιες είναι αυτές οι δυο ακολουθίες,
κάτι πολύ χρήσιμο για διάφορες εφαρμογές της Βιολογίας.
H υλοποίηση αυτού του αλγορίθμου έγινε με το εργαλείο Σύνθεσης Υψηλού Επιπέδου,
Vivado HLS, το οποίο βοηθά στο σχεδιασμό ψηφιακών κυκλωμάτων καθώς προσφέρει τη
δυνατότητα μετάφρασης γλωσσών προγραμματισμού υψηλού επιπέδου, όπως C/C++ και
System C σε επίπεδο καταχωρητών (RTL). Η πρώτη αρχιτεκτονική που αναπτύχθηκε ήταν η
αρχιτεκτονική αναφοράς (baseline), η οποία δεν είχε κάποια βελτιστοποίηση στον κώδικα
της (BWOB). Στη συνέχεια, στην αρχιτεκτονική αυτή έγινε προσθήκη μιας προσωρινής
μνήμης για να βοηθήσει με τις προσπελάσεις στον πίνακα βαθμολογιών (BWIB). Οι επόμενες
δυο αρχιτεκτονικές που αναπτύχθηκαν χρησιμοποίησαν τις τεχνικές του Loop Skewing και
Loop Tiling για την παραλληλοποίηση του υπολογισμού των στοιχείων του πίνακα
βαθμολογιών. Η πρώτη εκ των δυο δεν λαμβάνει υπόψιν κάποιες εξαιρέσεις που ήταν
απαραίτητες για τον παράλληλο υπολογισμό όλων των στοιχείων ενός tile (LSTWOEX), ενώ η
δεύτερη λαμβάνει υπόψιν αυτές εξαιρέσεις (LSTWIEX).
Για τις πειραματικές μετρήσεις χρησιμοποιήθηκαν οι συσκευές Zynq UltraScale+ ZCU102
Evaluation Board (xczu9eg-ffvb1156-2-e) και Virtex-7 VC709 Evaluation Platform
(xc7vx690tffg1761-2) από την AMD Xilinx. Μέσα από τα αποτελέσματα της σύνθεσης
προέκυψε ότι η αρχιτεκτονική LSTWIEX1 (LSTWIEX με loop skew factor=1) ήταν η πιο γρήγορη
αρχιτεκτονική. Μια ισορροπία στις απαιτήσεις σε πόρους και την καθυστέρηση έδωσε η
αρχιτεκτονική LSTWOEX1. Η αρχιτεκτονική BWIB πέτυχε τη μικρότερη χρήση πόρων και
ταυτόχρονα μείωνε αρκετά την καθυστέρηση σε σχέση με τη μη βελτιστοποιημένη
αρχιτεκτονική αναφοράς.
Description
Keywords
Σύνθεση υψηλού επιπέδου, Στοίχιση ακολουθιών, Βιοπληροφορική