Παραλληλοποίηση της τοποθέτησης FPGA με βάση τον Simulated Annealing

Abstract

υλοποίηση λογικών κυκλωμάτων και αποτελούν μια ευρέως αποδεκτή μέθοδο σχεδιασμού κυκλωμάτων εδώ και αρκετές δεκαετίες. Η ραγδαία αύξηση της κλίμακας ολοκλήρωσης παρέχει την δυνατότητα να αυξηθεί η λογική που μπορεί να προγραμματιστεί σε μια FPGA, γεγονός που αυξάνει τις απαιτήσεις για εύρεση αλγορίθμων που θα είναι ταχύτεροι από αυτούς του παρελθόντος. Οι ερευνητικές προσπάθειες εστιάζουν στο στάδιο της τοποθέτησης (placement), το οποίο παίρνει έως και 50% του υπολογιστικού χρόνου με σκοπό να διατηρηθεί το πλεονέκτημα που παρουσιάζει αυτή η τεχνολογία να μπορεί να προγραμματιστεί γρήγορα και άμεσα. Τα περισσότερα εργαλεία CAD που εκτελούν την διαδικασία της τοποθέτησης στις FPGA είναι βασισμένα στην σειριακή εκτέλεση του αλγορίθμου Προσομοιωμένης Ανόπτησης (Simulated Annealing). Ο χρόνος εκτέλεσης του συγκεκριμένου αλγορίθμου αυξάνει εκθετικά όσο αυξάνεται η λογική στο κύκλωμα ενώ με τον ρυθμό αύξησης της εξομοιούμενης λογικής, αν δεν βρεθεί κάποια εναλλακτική θα καταστεί ασύμφορος. Γι αυτό, η έρευνα για εύρεση κατάλληλης λύσης που θα εκμεταλλεύεται την παράλληλη επεξεργασία παραμένει κρίσιμή. Δυστυχώς οι περισσότερες προτάσεις που έχουν γίνει πάνω στην παράλληλη επεξεργασία, παρουσιάζουν μικρές τιμές επιτάχυνσης και η αποτελεσματικότητά τους εξαρτάται σε μεγάλο βαθμό από τμήματα τα οποία συνεχίζουν να εκτελούνται σειριακά. Σε αυτό το έγγραφο προτείνεται μια μέθοδος η οποία μπορεί να εκτελεστεί σε οποιοδήποτε πολυπύρηνο σύστημα αν και είναι αποδοτικότερη σε SIMD συστήματα ενώ παρέχονται παραδείγματα με χρήση CUDA C και της βιβλιοθήκης της NVidia για C++, Thrust. Στόχος της εργασίας είναι να εκμεταλλευτεί την δυνατότητα να εκτελείται ανά πάσα στιγμή ένας μεγάλος αριθμός νημάτων (threads) και των παράλληλων σχημάτων προγραμματισμού χωρίς να θυσιάζει μέρος της ποιότητας του τελικού κυκλώματος.