Accelerating Connected Components Graph Algorithms in Reconfigurable Logic

Abstract

Ένα από τα πιο χρήσιμα αντικείμενα στη σύγχρονη επιστήμη των υπολογιστών και το οποίο έχει επανέλθει στην επικαιρότητα λόγω της διάδοσης και ανάγκης ανάλυσης μεγάλου όγκου δεδομένων (Big Data) είναι η θεωρία των γράφων. Η έρευνα έχει πλέον στραφεί στην εύρεση νέων αποδοτικότερων αλγορίθμων και στη βελτιστοποίηση των υπαρχόντων, ειδικότερα αυτών που επικεντρώνονται στην επίλυση προβλημάτων και ανάλυση γράφων. Οι γράφοι αναλαμβάνουν να αναπαραστήσουν τις σχέσεις μεταξύ των στοιχείων ενός συνόλου. Γύρω μας οι γράφοι διέπουν μεγάλο μέρος της καθημερινότητας μας χωρίς να το αντιλαμβανόμαστε, καθώς γράφος μπορεί να είναι ένα δίκτυο υπολογιστών, μία αλυσίδα καταστημάτων, ένα κοινωνικό δίκτυο ή όποιας μορφής δίκτυο δημιουργείται μέσω μιας σχέσης σε ένα σύνολο. Χαρακτηριστικά των γράφων είναι κυρίως το μεγάλο τους μέγεθος και η τυχαιότητα που διέπει της διασυνδέσεις τους. Λόγω των παραπάνω, ο χρόνος επίλυσης και ο υπολογιστικός φόρτος που απαιτείται για την επίλυση αλγορίθμων αυξάνεται εκθετικά κάθε χρόνο. Πλέον, για να επεξεργαστούμε τα δεδομένα και για να εξάγουμε πληροφορίες από γράφους που αναπαριστούν παραδείγματος χάρη, μέσα κοινωνικής δικτύωσης, απαιτείται τεράστια υπολογιστική ισχύ, που πριν από μερικά χρόνια δεν θα μπορούσαμε να το φανταστούμε. Αυτό το φαινόμενο και η συνεχής ροή και παραγωγή δεδομένων δεν πρόκειται να σταματήσουν, οπότε χρειαζόμαστε νέες μεθόδους και τρόπους ανάλυσης των γράφων. Η πολυπλοκότητα πλέον των αλγορίθμων γράφων καθιστούν μη αποδοτική την εκτέλεση τους από επεξεργαστές γενικού σκοπού. Σε αυτή τη διπλωματική διερευνούμε τη δυνατότητα και την αποδοτικότητα υλοποίησης τους από υλικό ειδικού σκοπού, FPGAs. Πιο συγκεκριμένα, θα ασχοληθούμε με τον αλγόριθμο των Shiloach-Vishkin για την εύρεση του αριθμού των διασυνδεμένων στοιχείων ενός γράφου. Για την υλοποίηση του αλγορίθμου θα χρησιμοποιήσουμε FPGA της εταιρίας Xilinx και συγκεκριμένα το ZYNQ ZC702. Θα διερευνήσουμε διάφορες μορφές του αλγορίθμου αλλά και τη χρήση του FPGA. Στόχος μας είναι η επιτάχυνσή του με όσο το δυνατό μικρότερη χρήση πόρων του συστήματος.