Υλοποίηση του αλγόριθμου ευθυγράμμισης ακολουθίας Smith-Waterman σε ενσωματωμένη πλατφόρμα FPGA

Abstract

Η ευθυγράμμιση αλληλουχίας (sequence alignment), όρος που προέρχεται από τον κλάδο της βιοπληροφορικής, ασχολείται με την εύρεση κοινών ή παρόμοιων περιοχών ομοιότητας μεταξύ δύο αλληλουχιών DNA ή πρωτεϊνών. Για την υλοποιήση της διαδικασίας της ευθυγράμμισης ακολουθίας έχουν προταθεί πολλαπλοί αλγόριθμοι με την πάροδο των χρόνων, ωστόσο ο μεγάλος όγκος των δεδομένων υπο επεξεργασία και η αδυναμία εκματάλλευσης της παράλληλης επεξεργασίας των δεδομένων αυτών, καθιστούν τις μεθόδους αυτές εξαιρετικά χρονοβόρες αν εκτελεστούν αποκλειστικά με τη χρήση λογισμικού. Για τους λόγους αυτούς, δημιουργείται η ανάγκη επιτάχυνσης αυτών των αλγορίθμων με χρήση υλικού και συγκεκριμένα, μέσω της τεχνολογίας των FPGAs (Field Programmable Gate Arrays) και των ενσωματωμένων συστημάτων. Τα FPGAs, όντας επαναπρογραμματιζόμενες μονάδες λογικής, μας δίνουν τη δυνατότητα να μετατρέψουμε ένα πολύπλοκο πρόβλημα σε ένα ηλεκτρονικό κύκλωμα εύκολα και χωρίς κόστη πρωτοτύπου, εκμεταλλευόμενοι οποία δυνατότητα παραλληλίας δεδομένων δεν μπορούσε να εκμεταλλευτεί το λογισμικό. Με αυτόν τον τρόπο, μπορεί να κατασκευαστεί ένας επιταχυντής υπολογισμών για την υλοποίηση του αλγορίθμου δυναμικού προγραμματισμού, ο οποίος σε συνδυασμό με άλλα πλεονεκτήματα των ενσωματωμένων συστημάτων, επιταχύνει αισθητά το χρόνο εκτέλεσης του αλγορίθμου. Στην παρούσα διπλωματική εργασία καλούμαστε να υλοποιήσουμε έναν συγκεκριμένο αλγόριθμο ευθυγράμμισης ακολουθίας, τον αλγόριθμο Smith-Waterman σε ένα ολοκληρωμένο ενσωματωμένο σύστημα. Μελετώντας τα χαρακτηριστικά του αλγορίθμου, επιλέγουμε να υλοποιήσουμε έναν επιταχυντή υπολογισμών στο υλικό με τη μέθοδο του συστολικού πίνακα, ο οποίος προστίθεται στο ενσωματωμένο σύστημα σαν επιπλέον περιφερειακό και αλληλεπιδρά με τον ενσωματωμένο επεξεργαστή που εκτελεί την υπόλοιπη εφαρμογή. Στόχος μας είναι η δημιουργία μίας ενσωματωμένης και κατ’ επέκταση φορητής, αποδοτικής μηχανής ανίχνευσης ηχητικών εφέ μέσα σε ροές ηχητικών δεδομένων, όπως είναι μία ταινία. Το σύστημα ανίχνευσης ηχητικών εφέ αποτελείται, αρχικά, από μια εφαρμογή, που εκτελείται στον ενσωματωμένο επεξεργαστή και διαχειρίζεται την προ-επεξεργασία των αρχείων που αποτελούν την ταινία και το προς ανίχνευση ηχητικό εφέ. Επιπρόσθετα, το σύστημα αποτελείται από το περιφερειακό που αποτελεί τον επιταχυντή των υπολογισμών, καθώς και τη μεταξύ τους διασύνδεση μέσω κοινών μνημών και καταχωρητών. Συγκεκριμένα, η γραμμένη σε γλώσσα προγραμματισμού C εφαρμογή, που εκτελείται στον ενσωματωμένο επεξεργαστή, αναλαμβάνει την εξαγωγή των χαρακτηριστικών από τα αρχεία εισόδου, ενημερώνει τις μνήμες του επιταχυντή με τα χαρακτηριστικά αυτά, ενώ παράλληλα μέσω εγγραφής σε κοινούς καταχωρητές τον θέτει σε εκκίνηση. Ο επιταχυντής, αυτός, αναπτύσσεται μετατρέποντας τον S-W αλγόριθμο σε μία συστολική συστοιχία από λογικά στοιχεία (systolic array), όπου το καθένα λειτουργεί όμοια, ανεξάρτητα και παράλληλα, μέσα σε μία αρχιτεκτονική σχεδίασης εκμεταλλευόμενη την παραλληλία των δεδομένων. Με τον τρόπο αυτό, το υλικό, εκμεταλλευόμενο την παραλληλία επεξεργασίας, επιτυγχάνει να επιταχύνει τους χρόνους εκτέλεσης κατά ένα σημαντικό ποσοστό, σε σύγκριση με άλλες υλοποιήσεις του ίδιου αλγορίθμου εκτελεσμένες μόνο σε λογισμικό.