Τεχνικές βελτιστοποίησης σύνθετων αριθμητικών συστημάτων

Abstract

Modern embedded systems target domains of high-end applications, which require efficient implementations of computationally intensive Digital Signal Processing (DSP) functions. The performance of DSP systems is inherently affected by decisions on their design regarding the inner architecture of arithmetic units. Moreover, the implementation of hardware architectures targeted for accelerating the execution of applications from specialized fields, offers considerable heterogeneity, which has been proven to improve the performance and reduce the power consumption. However, the design decisions concerning the datapath of an acceleration unit largely affect both its performance and efficiency. The present thesis develops certain techniques for improving the performance of computational datapaths, which are based at either the conventional 2's complement arithmetic representation or alternative arithmetic forms, e.g., Carry - Save, Residue Number Systems.Targeting to optimize the design of Add - Multiply (AM) units, we fuse the adder and the MB encoding component of the subsequent multiplier in an one and only structural element of the datapath and introduce an improved technique of direct recoding of the sum of two numbers in its Modified Booth (MB) form. Thus, the adder of the conventional AM design is omitted and the recoding procedure becomes independent of the bit-length of the input numbers. Then, we adopt a high performance architecture for the synthesis of flexible hardware accelerators, which combines optimization techniques from both the architectural and arithmetic levels of design and incorporates uniform and flexible computational units. We introduce an improved computational unit, which uses Carry - Save (CS) arithmetic to carry out both additions / subtractions and multiplication operations without requiring time-consuming transformations from the CS representation to the respective 2's complement one.Furthermore, targeting to increase the performance of computationally intensive DSP applications, the Residue Number Systems (RNS) are considered to be a promising alternative for implementing efficient arithmetic systems. Targeting to increase the performance of the modulo 2^n+-1 AM operation, we focus on optimizing its design. Moreover, chained arithmetic operations dominate DSP applications and demand significant system resources for their execution. However, when keeping the intermediate results in a redundant representation, the execution of the chained arithmetic operations is accelerated and becomes more efficient due to the elimination of the intermediate additions. Thus, we use a special redundant modulo 2^n+1 representation to design units for the modulo 2^n+1 addition / multiplication with the one or both operands in this representation targeting to develop a systematic methodology based on the use of the aforementioned modulo 2^n+1 arithmetic units.Finally, considering that many DSP and multimedia applications carry out a large number of multiplications with coefficients that do not change during the execution of an application, we introduce a non-redundant radix-4 representation with signed digits and use it in order to explore a pre-encoded multiplier design. More specifically, before any multiplication operation is carried out, we encode the fixed coefficients using the proposed representation and store them in a ROM in a condensed form.

Τα σύγχρονα ενσωματωμένα συστήματα στοχεύουν σε υψηλών προδιαγραφών πεδία εφαρμογών, οι οποίες απαιτούν αποδοτικές υλοποιήσεις για υπολογιστικά απαιτητικές συναρτήσεις Ψηφιακής Επεξεργασίας Σήματος (ΨΕΣ). Η απόδοση των συστημάτων ΨΕΣ επηρεάζεται εγγενώς από σχεδιαστικές αποφάσεις που αφορούν στην εσωτερική αρχιτεκτονική των αριθμητικών μονάδων που ενσωματώνουν. Συγχρόνως, η στοχευμένη ανάπτυξη αρχιτεκτονικών υλικού για την επιτάχυνση της εκτέλεσης εφαρμογών εξειδικευμένων πεδίων προσφέρει ένα βαθμό ετερογένειας, η οποία έχει αποδειχθεί ότι βελτιώνει την απόδοση και ελαττώνει την κατανάλωση ενέργειας. Ωστόσο, κατά τη σχεδίαση του μονοπατιού δεδομένων ενός επιταχυντή, οι αποφάσεις που λαμβάνονται επηρεάζουν σε μεγάλο βαθμό τόσο την απόδοση όσο και την αποτελεσματικότητά του. Στην παρούσα διατριβή αναπτύσσονται ορισμένες τεχνικές βελτίωσης της απόδοσης υπολογιστικών μονοπατιών δεδομένων για τη συμβατική αριθμητική αναπαράσταση συμπληρώματος ως προς 2 και για ορισμένες εναλλακτικές αριθμητικές αναπαραστάσεις, π.χ., Σωσίματος - Κρατουμένου, Αριθμητικά Συστήματα Υπολοίπων.Στοχεύοντας στη βελτιστοποίηση της σχεδίασης των μονάδων Άθροισης - Πολλαπλασιασμού (ΑΠ), παρουσιάζουμε μία βελτιωμένη τεχνική απευθείας μετασχηματισμού του αθροίσματος δύο αριθμών στη Modified Booth (MB) μορφή του συγχωνεύοντας τον αθροιστή και τη μονάδα ΜΒ κωδικοποίησης του πολλαπλασιαστή σε ένα και μοναδικό δομικό στοιχείο του μονοπατιού δεδομένων. Συνεπώς, ο αθροιστής της συμβατικής σχεδίασης ΑΠ εξαλείφεται και η διαδικασία μετασχηματισμού γίνεται ανεξάρτητη από το μήκος λέξης των εισόδων. Στη συνέχεια, υιοθετούμε μία αρχιτεκτονική υψηλής απόδοσης για τη σύνθεση ευέλικτων επιταχυντών υλικού, η οποία συνδυάζει τεχνικές βελτιστοποίησης τόσο από το υψηλότερο αρχιτεκτονικό όσο και από το χαμηλότερο αριθμητικό επίπεδο σχεδίασης περιλαμβάνοντας ομοιόμορφες και ευέλικτες υπολογιστικές μονάδες. Παρουσιάζουμε μία βελτιωμένη υπολογιστική μονάδα διεξάγοντας τους υπολογισμούς σε αριθμητική Σωσίματος - Κρατουμένου (ΣΚ) και διά μέσου των πράξεων πολλαπλασιασμού δίχως να απαιτούνται χρονοβόρες μετατροπές από την αναπαράσταση ΣΚ στην αντίστοιχη συμπληρώματος ως προς 2.Τα Αριθμητικά Συστήματα Υπολοίπων αποτελούν μία ελπιδοφόρα εναλλακτική τεχνική υλοποίησης αριθμητικών συστημάτων με στόχο την αύξηση της απόδοσης υπολογιστικά εντατικών εφαρμογών ΨΕΣ. Με στόχο την αύξηση της απόδοσης της λειτουργίας ΑΠ υπολοίπου 2^n+-1, εστιάζουμε στη βελτιστοποίηση της σχεδίασής της. Επιπλέον, επειδή οι αλυσιδωτές αριθμητικές λειτουργίες κυριαρχούν σε εφαρμογές ΨΕΣ και απαιτούν σημαντικούς πόρους του συστήματος για την εκτέλεσή τους, η διατήρηση των ενδιάμεσων αποτελεσμάτων σε μία πλεονάζουσα αναπαράσταση είναι μία ευρέως διαδεδομένη τεχνική για την επιτάχυνση και αποδοτικότερη εκτέλεση των αλυσιδωτών αριθμητικών λειτουργιών λόγω της εξάλειψης των ενδιάμεσων αθροίσεων. Χρησιμοποιώντας μία ειδική πλεονάζουσα αναπαράσταση υπολοίπου 2^n+1 σχεδιάζουμε μονάδες άθροισης / πολλαπλασιασμού υπολοίπου 2^n+1 με έναν ή δύο όρους στην αναπαράσταση αυτή στοχεύοντας στην ανάπτυξη μίας συστηματικής μεθοδολογίας για τη χρησιμοποίηση των προαναφερόμενων αριθμητικών μονάδων υπολοίπου 2^n+1.Τέλος, λαμβάνοντας υπόψη ότι εφαρμογές ΨΕΣ και πολυμέσων διεξάγουν μεγάλο αριθμό πολλαπλασιασμών με συντελεστές που δε μεταβάλλονται όσο εκτελείται μία εφαρμογή, διερευνούμε μία μη-πλεονάζουσα αναπαράσταση με προσημασμένα ψηφία και βάση το 4 και χρησιμοποιούμε την προτεινόμενη αναπαράσταση προκειμένου να διερευνήσουμε ένα σχέδιο προ-κωδικοποιημένου πολλαπλασιαστή προ-κωδικοποιώντας τους σταθερούς συντελεστές και αποθηκεύοντάς τους σε μία μνήμη τύπου ROM σε μία συμπυκνωμένη μορφή.