Hardware and software development for the efficient mapping of mathematical problems on field programmable gate array systems

Abstract

In the industrial market, designers have a significant incentive to get their products to market quickly: to maximize revenue and time-in-market. Every week that a product is not being sold represents lost revenue, increases the product’s market risk and lowers the chance of success. Field Programmable Gate Arrays (FPGAs) offer a low-risk, quick time-to-market solution that industrial designers can easily modify when they need to make changes, fix bugs or create product derivatives at some point in the future. However, power consumption is one of the main disadvantages of FPGAs. The post-fabrication flexibility provided by these devices is implemented using a large number of pre-fabricated routing tracks and programmable switches that consume a significant amount of power. This problem becomes even more critical when FPGAs are used for applications related to cryptography, since this high power consumption makes potential security applications more vulnerable to power analysis attacks. Facing this challenge the designers are sometimes forced to make radical changes to the design. These changes could include the partitioning of the algorithm into different hardware and software blocks, re-allocation of the FPGA logic or even re-designing the whole system from scratch. Since these options have a huge impact on time and money, early phase power estimations on FPGA devices are becoming more and more important. In this dissertation we investigate the power consumption problem and we evaluate the power estimation software that is being provided by the major FPGA vendors. We evaluate the difference between software and hardware cryptography blocks related to their power consumption and processing speed. Another part of this thesis also investigates the power consumption reduction that we can achieve by either using clock gating or Real-Time reconfiguration. We continue by exploring deeper the cryptography and the security algorithms by proposing and implementing faster large number factorization algorithms. We partition the algorithms in both software and hardware in such a way that we can achieve the best possible performance. Finally, we use the Real-Time reconfiguration capability of the state of the art FPGA devices in order to achieve even higher speed-ups.

Στην αγορά της βιομηχανίας, οι σχεδιαστές έχουν σοβαρά κίνητρα για να βγά- λουν τα προϊόντα τους γρήγορα στην αγορά. Αυτά είναι η αύξηση των κερδών και η διάρκεια του χρόνου διάθεσης του προϊόντος μέσα στην αγορά. Κάθε βδο- μάδα που ένα προϊόν δεν πωλείται, αυτό αντιπροσωπεύει χαμένα κέρδη και αυξάνει το ρίσκο αποτυχίας του προϊόντος στην αγορά. Τα επαναποργραμμα- τιζόμενα ολοκληρωμένα κυκλώματα (FPGAs) προσφέρουν μία λύση χαμηλού ρίσκου με γρήγορη είσοδο στην αγορά, όπου οι σχεδιαστές μπορούν εύκολα να μεταβάλλουν το προϊόν όταν χρειάζεται να κάνουν αλλαγές, να διορθώνουν λάθη ή ακόμη και να δημιουργήσουν παράγωγα προϊόντων κάποια στιγμή στο μέλλον. Παρόλ’αυτά, η αυξημένη κατανάλωση ενέργειας είναι ένα απο τα κύρια μειονεκτήματα των ολοκληρωμένων FPGAs. Η ευελιξία που προσφέρουν οφεί- λεται σε έναν μεγάλο αριθμό διαδρόμων δρομολόγησης και λογικών πυλών που καταναλώνουν πολύ μεγάλο ποσό ενέργειας. Αυτό το πρόβλημα γίνεται ακόμη πιο κρίσιμο όταν οι FPGAs χρησιμοποιούνται σε εφαρμογές κρυπτογραφίας, μιας και η μεγάλη κατανάλωση ενέργειας κάνει τις εφαρμογές αυτές πιο ευά- λωτες σε επιθέσεις ανάλυσης της ενέργειας (Power Analysis Attacks). Για να αντιμετωπίσουν αυτή την πρόκληση οι σχεδιαστές έιναι αναγκα- σμένοι, μερικές φορές, να κάνουν ριζοσπαστικές αλλαγές στον σχεδιασμό του προϊοντος. Αυτές οι αλλαγές μπορούν να περιλαμβάνουν τον διαχωρισμό του αλγορίθμου σε υποκομμάτια υλικού και λογισμικού (Hardware / Software Partitioning), ανακατανομή της λογικής ή ακόμη και επανασχεδίαση όλου του συ- στήματος. Μιας και αυτές οι αλλαγές έχουν μεγάλο κόστος τόσο σε χρήματα όσο και σε χρόνο, η εκτίμηση της κατανάλωσης της ενέργειας στις FPGAs στα αρχικά στάδια του σχεδιασμού γίνεται όλο και πιο σημαντική. Σε αυτή την διατριβή ερευνούμε το πρόβλημα της κατανάλωσης ενέργειας στις FPGAs και αξιολογούμε το λογισμικό της εκτίμησης της ενέργειας που παρέχεται απο τους μεγαλύτερους κατασκευαστές αυτών των ολοκληρωμένων. Αξιολογούμε την διαφορά ανάμεσα σε υλικό και λογισμικό για πολλούς κρυ- πτογραφικούς αλγορίθμους σε σχέση με την κατανάλωση ενέργειας και την ταχύτητα εκτέλεσης τους. Ένα άλλο κομμάτι αυτής της διατριβής διερευνά τη μείωση της κατανάλωσης ενέργειας που μπορούμε να επιτύχουμε είτε με την χρήση της τεχνικής του Clock-Gating είτε της τεχνικής του επαναπρογραμμα- τισμού σε πραγματικό χρόνο. Συνεχίζουμε με την βαθύτερη διερεύνηση της κρυπτογραφίας και των αλ- γορίθμων ασφαλείας με την πρόταση και την υλοποίηση γρηγορότερων αλγο- ρίθμων για την παραγοντοποίηση μεγάλων αριθμών. Διαχωρίζουμε τους αλγο- ρίθμους σε λογισμικό και υλικό με τέτοιο τρόπο ώστε να έχουμε το βέλτιστο δυνατό αποτέλεσμα. Τέλος, χρησιμοποιούμε την δυνατότητα επαναπρογραμ- ματισμού σε πραγματικό χρόνο των ολοκληρωμένων κυκλωμάτων FPGA ώστε να επιτύχουμε ακόμη πιο μεγάλες επιταχύνσεις.