Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17254
Τίτλος: Accelerating Connected Components Graph Algorithms in Reconfigurable Logic
Συγγραφείς: Κουρής, Αλέξανδρος
Σούντρης Δημήτριος
Λέξεις κλειδιά: Θεωρία Γράφων
Shiloach-Vishkin
Διασυνδεδεμένα Στοιχεία
FPGA
Επεξεργαστής υλικού
επιτάχυνση αλγορίθμου
Ημερομηνία έκδοσης: 4-Απρ-2019
Περίληψη: Ένα από τα πιο χρήσιμα αντικείμενα στη σύγχρονη επιστήμη των υπολογιστών και το οποίο έχει επανέλθει στην επικαιρότητα λόγω της διάδοσης και ανάγκης ανάλυσης μεγάλου όγκου δεδομένων (Big Data) είναι η θεωρία των γράφων. Η έρευνα έχει πλέον στραφεί στην εύρεση νέων αποδοτικότερων αλγορίθμων και στη βελτιστοποίηση των υπαρχόντων, ειδικότερα αυτών που επικεντρώνονται στην επίλυση προβλημάτων και ανάλυση γράφων. Οι γράφοι αναλαμβάνουν να αναπαραστήσουν τις σχέσεις μεταξύ των στοιχείων ενός συνόλου. Γύρω μας οι γράφοι διέπουν μεγάλο μέρος της καθημερινότητας μας χωρίς να το αντιλαμβανόμαστε, καθώς γράφος μπορεί να είναι ένα δίκτυο υπολογιστών, μία αλυσίδα καταστημάτων, ένα κοινωνικό δίκτυο ή όποιας μορφής δίκτυο δημιουργείται μέσω μιας σχέσης σε ένα σύνολο. Χαρακτηριστικά των γράφων είναι κυρίως το μεγάλο τους μέγεθος και η τυχαιότητα που διέπει της διασυνδέσεις τους. Λόγω των παραπάνω, ο χρόνος επίλυσης και ο υπολογιστικός φόρτος που απαιτείται για την επίλυση αλγορίθμων αυξάνεται εκθετικά κάθε χρόνο. Πλέον, για να επεξεργαστούμε τα δεδομένα και για να εξάγουμε πληροφορίες από γράφους που αναπαριστούν παραδείγματος χάρη, μέσα κοινωνικής δικτύωσης, απαιτείται τεράστια υπολογιστική ισχύ, που πριν από μερικά χρόνια δεν θα μπορούσαμε να το φανταστούμε. Αυτό το φαινόμενο και η συνεχής ροή και παραγωγή δεδομένων δεν πρόκειται να σταματήσουν, οπότε χρειαζόμαστε νέες μεθόδους και τρόπους ανάλυσης των γράφων. Η πολυπλοκότητα πλέον των αλγορίθμων γράφων καθιστούν μη αποδοτική την εκτέλεση τους από επεξεργαστές γενικού σκοπού. Σε αυτή τη διπλωματική διερευνούμε τη δυνατότητα και την αποδοτικότητα υλοποίησης τους από υλικό ειδικού σκοπού, FPGAs. Πιο συγκεκριμένα, θα ασχοληθούμε με τον αλγόριθμο των Shiloach-Vishkin για την εύρεση του αριθμού των διασυνδεμένων στοιχείων ενός γράφου. Για την υλοποίηση του αλγορίθμου θα χρησιμοποιήσουμε FPGA της εταιρίας Xilinx και συγκεκριμένα το ZYNQ ZC702. Θα διερευνήσουμε διάφορες μορφές του αλγορίθμου αλλά και τη χρήση του FPGA. Στόχος μας είναι η επιτάχυνσή του με όσο το δυνατό μικρότερη χρήση πόρων του συστήματος.
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/17254
Εμφανίζεται στις συλλογές:Διπλωματικές Εργασίες - Theses

Αρχεία σε αυτό το τεκμήριο:
Αρχείο Περιγραφή ΜέγεθοςΜορφότυπος 
πτυχιακή.pdf3.15 MBAdobe PDFΕμφάνιση/Άνοιγμα


Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.