Παραλληλοποίηση της τοποθέτησης FPGA με βάση τον Simulated Annealing
| dc.contributor.advisor | Ψαράκης, Μιχαήλ | |
| dc.contributor.author | Αθανασόπουλος, Γεώργιος | |
| dc.date.accessioned | 2016-12-13T10:26:38Z | |
| dc.date.available | 2016-12-13T10:26:38Z | |
| dc.date.issued | 2016-10 | |
| dc.identifier.uri | https://dione.lib.unipi.gr/xmlui/handle/unipi/9290 | |
| dc.description.abstract | υλοποίηση λογικών κυκλωμάτων και αποτελούν μια ευρέως αποδεκτή μέθοδο σχεδιασμού κυκλωμάτων εδώ και αρκετές δεκαετίες. Η ραγδαία αύξηση της κλίμακας ολοκλήρωσης παρέχει την δυνατότητα να αυξηθεί η λογική που μπορεί να προγραμματιστεί σε μια FPGA, γεγονός που αυξάνει τις απαιτήσεις για εύρεση αλγορίθμων που θα είναι ταχύτεροι από αυτούς του παρελθόντος. Οι ερευνητικές προσπάθειες εστιάζουν στο στάδιο της τοποθέτησης (placement), το οποίο παίρνει έως και 50% του υπολογιστικού χρόνου με σκοπό να διατηρηθεί το πλεονέκτημα που παρουσιάζει αυτή η τεχνολογία να μπορεί να προγραμματιστεί γρήγορα και άμεσα. Τα περισσότερα εργαλεία CAD που εκτελούν την διαδικασία της τοποθέτησης στις FPGA είναι βασισμένα στην σειριακή εκτέλεση του αλγορίθμου Προσομοιωμένης Ανόπτησης (Simulated Annealing). Ο χρόνος εκτέλεσης του συγκεκριμένου αλγορίθμου αυξάνει εκθετικά όσο αυξάνεται η λογική στο κύκλωμα ενώ με τον ρυθμό αύξησης της εξομοιούμενης λογικής, αν δεν βρεθεί κάποια εναλλακτική θα καταστεί ασύμφορος. Γι αυτό, η έρευνα για εύρεση κατάλληλης λύσης που θα εκμεταλλεύεται την παράλληλη επεξεργασία παραμένει κρίσιμή. Δυστυχώς οι περισσότερες προτάσεις που έχουν γίνει πάνω στην παράλληλη επεξεργασία, παρουσιάζουν μικρές τιμές επιτάχυνσης και η αποτελεσματικότητά τους εξαρτάται σε μεγάλο βαθμό από τμήματα τα οποία συνεχίζουν να εκτελούνται σειριακά. Σε αυτό το έγγραφο προτείνεται μια μέθοδος η οποία μπορεί να εκτελεστεί σε οποιοδήποτε πολυπύρηνο σύστημα αν και είναι αποδοτικότερη σε SIMD συστήματα ενώ παρέχονται παραδείγματα με χρήση CUDA C και της βιβλιοθήκης της NVidia για C++, Thrust. Στόχος της εργασίας είναι να εκμεταλλευτεί την δυνατότητα να εκτελείται ανά πάσα στιγμή ένας μεγάλος αριθμός νημάτων (threads) και των παράλληλων σχημάτων προγραμματισμού χωρίς να θυσιάζει μέρος της ποιότητας του τελικού κυκλώματος. | el |
| dc.format.extent | 50 | el |
| dc.language.iso | el | el |
| dc.publisher | Πανεπιστήμιο Πειραιώς | el |
| dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
| dc.title | Παραλληλοποίηση της τοποθέτησης FPGA με βάση τον Simulated Annealing | el |
| dc.title.alternative | Parallelizing FPGA placement based on Simulated Annealing | el |
| dc.type | Master Thesis | el |
| dc.contributor.department | Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Πληροφορικής | el |
| dc.description.abstractEN | Field Programmable Gate Arrays (FPGAs) allow fast and cheap implementation of logic circuits and they consist a widely used method for design of electronic circuits for the past few decades. The growing market demands that more logic can potentially be packed into them especially now that the integration scale becomes smaller every few years. This unavoidably lead to the pursuit of a better programming method for the FPGAs as it is evident that the more the logic that is packed into them the more computational time is required in order to compile the hardware description program. The research trend at the moment is searching for a new algorithm that can potentially speed the process of placement of the logic blocks on the FPGA since that part of the program flow can take up to 50% of the total time spent in compilation. Most of the CAD programs responsible for the compilation process, implement a serial version of Simulated Annealing algorithm. The execution time of this algorithm increases exponentially the more logic is required to be implemented on the FPGA which threatens to take away some of the advantages of using an FPGA over an ASIC in the future. Fortunately the evolution of computational systems appears to be systems that rely on multiple processors that allow large throughput and that can work independently. Thus it is crucial that research focuses on parallel processing. Unfortunately, most papers posted on this subject to day, show either underwhelming speedups or sacrifice quality for speed resulting in subpar implementations. This thesis proposes a method of Simulated Annealing parallelization that can be applied to any multicore/manycore system albeit optimized for SIMD systems. Examples are given that use NVidia's GPUs to serve as the means to increase the throughput using CUDA C language extension and the C++ library Thrust. Our goal is to propose an alternative version of the Simulated Annealing algorithm that takes advantage of parallel programming concepts without sacrificing much of the final product quality if any at all. | el |
| dc.contributor.master | Προηγμένα Συστήματα Πληροφορικής | el |
| dc.subject.keyword | Κυκλώματα | el |
| dc.subject.keyword | Αλγόριθμοι | el |
Αρχεία σε αυτό το τεκμήριο
Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές
-
Τμήμα Πληροφορικής
Department of Informatics
Εκτός από όπου διευκρινίζεται διαφορετικά, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές
Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές