Implementation of FPGA Accelerator for a Simplex Algorithm:
Creators: name: Βαρσαμόπουλος, Σάββας Χρήστου
Publisher: name: Aristotle University of Thessaloniki
Year: 2014
Subjects: Επιλυτής
FPGA
Simplex
Solver

description: Ο γραμμικός προγραμματισμός (Linear Programming) είναι μια μαθηματική μέθοδος που αναπτύχτηκε για την επίλυση μεγάλου εύρους προβλημάτων όπου είναι αναγκαία η εύρεση της βέλτιστης λύσης μεταξύ πολλών πιθανών λύσεων. Αυτού του τύπου τα προβλήματα είναι άκρως απαιτητικά, λόγω των πολλών επαναλήψεων που χρειάζεται να τρέξει ο αλγόριθμος μέχρι να καταλήξουμε στην επιθυμητή τιμή. Μια ευρέως διαδεδομένη λύση για τέτοιου είδους προβλήματα αποτελεί ο αλγόριθμος Simplex. Ο Simplexαποτελεί έναν αλγόριθμο που λειτουργεί καλά ακόμη και κατόπιν ασυνήθιστων συνθηκών και διαθέτει πολλές δυνατότητες κλιμάκωσης. Παράγει το βέλτιστο αποτέλεσμα πραγματοποιώντας μια σειρά από μαθηματικές πράξεις (αφαιρέσεις, πολλαπλασιασμοί και διαιρέσεις) μεταξύ των σειρών του πίνακα που περιέχει τις πληροφορίες του προβλήματος και πιο συγκεκριμένα τις μεταβλητές και τις σταθερές του προβλήματος. Υπάρχουν αρκετές υλοποιήσεις του αλγορίθμου Simplexσε πλατφόρμες λογισμικού. Βέβαια, τα φυσικά προβλήματα που πηγάζουν από την καθημερινότητα έχουν συνήθως πολλές μεταβλητές και συνθήκες - περιορισμούς. Συνεπώς, η διαδικασία απόκτησης της βέλτιστης λύσης καθίσταται ιδιαιτέρως χρονοβόρα σε μια υλοποίηση σε πλατφόρμα λογισμικού. Για αυτό τον λόγο επιλέχθηκε σε αυτήν την εργασία η δημιουργία ενός επιλυτή αλγορίθμου Simplex σε υλικό (hardware)και πιο συγκεκριμένα σε FPGA. Γράψαμε κώδικα σε γλώσσα προγραμματισμού υλικού VHDL, ο οποίος αναπαριστά τη λειτουργία του αλγορίθμου Simplex και ελέγξαμε την ορθή λειτουργία του συστήματος στο περιβάλλον προσομοίωσης ModelSim. Οι μεταβλητές και οι περιορισμοί που δίνονται από το πρόβλημα αναπαραστάθηκαν σε ανισώσεις, όπου οι συντελεστές των μεταβλητών τέθηκαν ως προσημασμένα στοιχεία εύρους 32 ψηφίων. Η βέλτιστη λύση του προβλήματος προέκυψε ως προσημασμένος αριθμός σε αναπαράσταση σταθερής υποδιαστολής με εύρος 64 ψηφίων ακέραιου μέρους και 12 ψηφίων δεκαδικού μέρους. Η αξιολόγηση του προτεινόμενου συστήματος χρησιμοποιώντας ένα απλό πρόβλημα παρμένο από την καθημερινότητα, δείχνει μια αύξηση της μέγιστης συχνότητας λειτουργίας περίπου 3 τάξεις μεγέθους σε σχέση με μια αντίστοιχη επίλυση από έναν εμπορικό επιλυτή (LPsolve), ο οποίος λειτουργεί σε έναν υπολογιστή με επεξεργαστή στα 2,8GHz και μνήμη RAM 3GB. Η ακρίβεια του συστήματος στο χειρότερο δυνατό σενάριο από το πρόβλημα που επιλέχθηκε, έφτασε το ποσοστό λάθους του 2,24% .
description: Linear Programming (LP) is a mathematical method developed to solve a large variety of problems where we have to find the optimal solution among many possible solutions. This type of problem is computationally challenging, due to the many iterations that the algorithm must go through. A widely used solution for that kind of problems is the Simplex Algorithm. Simplex is a robust algorithm which also has great scalability properties. It produces the optimal solution by doing a set of mathematical operations between rows of a matrix that includes the information of the problem. There are many software implementations of the Simplex Algorithm. However, real life problems have many variables and constraints which result in a time consuming operation when used in a linear programming framework. Therefore, we chose in this work to make a hardware implementation of an FPGA accelerator for a Simplex Algorithm solver. We created a design in VHDL that works based on the Simplex Algorithm and tested the correct operation in the simulation environment of ModelSim. The variables and constraints are given in inequalities and the coefficients of the variables were represented in 32 bit signed elements. The optimal solution is presented in a signed fixed point number with 64 bits integer part and 12 bits fractional part. Evaluation of the proposed design using a simple real life problem demonstrates a speed up in the maximum frequency approximately 3 orders of magnitude over a software implementation (LPsolve) running on a 2,8GHz PC with 3GB of RAM. The accuracy of our design in the worst case scenario for the example that was tested, reached an error of 2,24% .