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

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