Ένας βέλτιστος κανόνας Golomb είναι ένα σύνολο απο διακριτούς θετικούς ακεραίους (σημεία), τέτοιους ώστε όλες οι διαφορές, που μετρώνται από κάθε διαφορετικό ζευγάρι, να είναι μοναδικές, και να καταλαμβάνουν το μικρότερο χώρο σε σχέση με οποιοδήποτε άλλο κανόνα που έχει τον ίδιο αριθμό σημείων. Οι βέλτιστοι κανόνες Golomb χρησιμοποιούνται σε ένα ευρύ φάσμα εφαρμογών πολλών επιστημονικών τομέων, αλλά η εύρεση τους είναι ακριβή υπολογιστικά και εξαιρετικά χρονοβόρα, παρά την συνεχιζόμενη ανάπτυξη της τεχνολογίας. Ωστόσο, είναι ένα πρόβλημα που μπορεί να παραλληλοποιηθει. Συνεπώς υπάρχει μεγάλο κίνητρο για να σχεδιάσουμε μία προσαρμοσμένη λύση βασισμένη στην τεχνολογία των FPGA. Η σχεδίασή μας υλοποιείται στο Convey HC-2ex, μια ετερογενή υπολογιστική πλατφόρμα πολλών FPGA, που μας επιτρέπει να χρησιμοποιήσουμε αποτελεσματικά πολλά επίπεδα παραλληλοποίησης, με σκοπό να βελτιώσουμε προηγούμενες αρχιτεκτονικές που εστίαζαν στην λύση αυτού του προβλήματος. Ακολουθώντας την αξιολόγηση των αποτελεσμάτων του HC-2ex, μεταφέραμε την σχεδίαση μας σε δύο σύγχρονες FPGA αξιοποιώντας την εξέλιξη των σχεδιαστικών εργαλείων βασισμένων σε γλώσσες περιγραφής υλικού. Παρά την μεγάλη κλίμακα της πλατφόρμας HC-2ex, αντιμετωπίσαμε περιορισμούς όσον αφορά τον χώρο, εξαιτίας της χαμηλής απόδοσης των παλιότερων σχεδιαστικών εργαλείων. Αντιθέτως, τα αποτελέσματα από τις δύο FPGA είναι αρκετά υποσχόμενα, καθώς πετυχαίνουμε σχεδόν τέλεια αξιοποίηση των διαθέσιμων πόρων, διατηρώντας υψηλό ρολόι, και καταλήγοντας σε ένα πιθανό speedup 3x σε σχέση με το HC-2ex, που πέφτει στο 2x στην περίπτωση μεγαλύτερων βέλτιστων κανόνων Golomb.
(EL)
An optimal Golomb ruler is a set of distinct positive integers (marks) such that the differences, computed over all different pairs, are distinct, and they occupy less space than any other ruler with the same number of marks. Optimal Golomb rulers are utilized in a great variety of applications over many scientific fields, with their derivation being computationally expensive and extremmelly time-consuming, despite the continuous growth of technology. However, finding and proving a Golomb ruler to be optimal is a problem that can be parallelized. Therefore there is a great incentive to design a custom solution based on FPGA technology. Our design utilizes Convey HC-2ex, a heterogeneous multi-fpga computing platform, that allows us to effectively use many levels of parallelism, in order to improve previous architectures focused on solving this problem. Following the evaluation of the HC-2ex results, we relocated our design to two contemporary FPGAs, capitalizing on the evolution of HDL designing tools. Despite the greater scale of the HC-2ex platform, we confronted spatial limitations, due to the low performance of the older designing tool. On the other hand, the results from the two FPGAs are significantly more promising, as we achieve close to perfect utilization of their available resources, with a high clock, resulting to a potential speedup of 3X over the HC-2ex, down to 2X in the case of larger OGRs.
(EN)
