Επιτάχυνση του αλγορίθμου Smith-Waterman για ανίχνευση ηχητικών εφέ με χρήση GPU

Abstract

Η αναγνώριση προτύπων σε ένα μεγάλο πλήθος δεδομένων αποτελεί έναν από τους σημαντικότερους τομείς στην σύγχρονη πληροφορική. Ένα τέτοιο πρόβλημα στο χώρο της βιοπληροφορικής είναι η ευθυγράμμιση μοριακών ακολουθιών, δηλαδή η εύρεση παρόμοιων υποακολουθιών ανάμεσα σε δύο ακολουθίες πρωτεϊνών. Ένας αλγόριθμος που χρησιμοποιείται για την ευθυγράμμιση μοριακών ακολουθιών είναι ο δυναμικός αλγόριθμος Smith-Waterman. Η ακρίβεια του αλγόριθμου αυτού είναι πολύ μεγάλη, αλλά αντισταθμίζεται από τις μεγάλες υπολογιστικές απαιτήσεις του. Η εξυπηρέτηση των μεγάλων υπολογιστικών απαιτήσεων του αλγόριθμου Smith-Waterman, μπορεί να πραγματοποιηθεί με την χρήση υλικού παράλληλης αρχιτεκτονικής, όπως οι κάρτες γραφικών του υπολογιστικού μοντέλου της CUDA. Οι κάρτες γραφικών μας δίνουν την δυνατότητα να εκτελέσουμε χιλιάδες νήματα, τα οποία μπορούν να πραγματοποιήσουν χιλιάδες υπολογισμούς παράλληλα. Σκοπός της παρούσας διπλωματικής είναι η επιτάχυνση του αλγόριθμου Smith - Waterman για την ανίχνευση ηχητικών εφέ σε μία ροή ηχητικών δεδομένων. Για να ικανοποιηθούν οι μεγάλες υπολογιστικές απαιτήσεις, ο αλγόριθμος υλοποιείται πάνω στο προγραμματιστικό μοντέλο της CUDA, για να εκμεταλλευτούμε τις μεγάλες δυνατότητες παραλληλίας που μας παρέχουν οι κάρτες γραφικών. Το προγραμματιστικό μοντέλο της CUDA αποτελείται από δύο κομμάτια: το κομμάτι που εκτελείται από την CPU και το κομμάτι που εκτελείται από την GPU. Στην συγκεκριμένη εφαρμογή το κομμάτι της CPU αναλαμβάνει κυρίως το φόρτωμα των αρχείων στο σύστημα και την μεταφορά των απαραίτητων δεδομένων στην GPU. Το κομμάτι της GPU αναλαμβάνει τον υπολογισμό του πίνακας κόστους αντικατάστασης και την εκτέλεση του αλγόριθμου Smith – Waterman. Τα ηχητικά αρχεία μορφοποιούνται πάνω στην μορφή ASE, ώστε να έχουμε μια ακολουθία διανυσμάτων 62 διαστάσεων. Ο πίνακας κόστους αντικατάστασης που χρησιμοποιούμε σε αναλογία με τον αντίστοιχο της βιοπληροφορικής, είναι ένας πίνακας που μας δίνει το συνημίτονο μεταξύ δύο συγκρινόμενων διανυσμάτων. Το μεγάλο μειονέκτημα της κάρτας γραφικών είναι ο περιορισμός των επιδόσεων σε εφαρμογές που υπάρχει συχνά επικοινωνία μεταξύ επεξεργαστή και μνήμη. Ο αλγόριθμος Smith – Waterman απαιτεί πολλές προσπελάσεις στην μνήμη και αυτό περιορίζει τις επιδόσεις της εφαρμογής. Παρ’ όλους τους περιορισμούς που έχουμε λόγω της συχνής επικοινωνίας με την μνήμη, η χρήση της κάρτας γραφικών μας δίνει σημαντικά βελτιωμένους χρόνους σε σχέση με τις επιδώσεις της CPU.