ΑΛΓΟΡΙΘΜΟΣ ΠΡΟΓΡΑΜΜΑΤΟΣ ΚΑΙ ΕΛΕΓΧΟΣ ΥΠΕΡΧΕΙΛΙΣΗΣ.
Το πρόγραμμα διαβάζει από ένα array 8 αριθμούς καθένας από τους οποίους έχει μέγεθος 1 byte και τους συσσωρεύει σε ένα καταχωρητή του DLX. Όταν συμβεί υπερχείλιση στον καταχωρητή το πρόγραμμα τερματίζει. Ο καταχωρητής στον οποίο συσσωρεύονται οι αριθμοί είναι ο καταχωρητής R1. Τα δεδομένα κάθε πίνακα ακεραίων αριθμών φορτώνονται σε καταχωρητές και επεξεργάζονται όλα μαζί. Αυτό που προστίθεται στον καταχωρητή R1 είναι το άθροισμα κάθε οκτάδας αριθμών και στη συνέχεια γίνεται ο έλεγχος για υπερχείλιση.
Αφού κάθε αριθμός έχει μέγεθος 1 byte μπορούμε σε έναν καταχωρητή 32-bit να φορτώσουμε 4 bytes. Φορτώνουμε έτσι τους 4 πρώτους αριθμούς στον καταχωρητή R5 και τους 4 επόμενους στον καταχωρητή R6. Προσθέτοντας αυτούς τους δύο καταχωρητές επιτυγχάνουμε πρόσθεση των οκτώ αριθμών του πίνακα ανά δύο. Δηλαδή με μια εντολή πρόσθεσης εκτελούμε ουσιαστικά 4 προσθέσεις bytes. Γνωρίζουμε ότι ο μέγιστος μη προσημασμένος αριθμός που μπορεί να αποθηκευθεί σε ένα byte (8 bit) είναι ο 255 και ο κάθε αριθμός του πίνακα μπορεί να είναι από 0 ως 63. Έτσι ακόμα και αν προστεθούν δύο αριθμοί με τη μέγιστη τιμή (63), το άθροισμά τους (=126) θα χωράει να αποθηκευτεί σε ένα byte και δεν επηρεάζεται το επόμενο byte του καταχωρητή. Ένας καταχωρητής 32–bit επομένως εξακολουθεί να χωράει τα 4 αποτελέσματα των προσθέσεων αφού το καθένα θα έχει μέγεθος 1 byte. Το αποτέλεσμα αποθηκεύεται στον καταχωρητή R6. Στο παρακάτω σχήμα φαίνεται το αποτέλεσμα των ενεργειών αυτών όταν όλοι οι αριθμοί είναι 63.
R5
00111111 00111111 00111111 00111111
+
R6
00111111 00111111 00111111 00111111
addu r6,r6,r5
R6
01111110 01111110 01111110 01111110
Στη συνέχεια εκτελούμε μια λογική πράξη AND μεταξύ του καταχωρητή R6 που περιέχει το αποτέλεσμα και του αριθμού (0000FFFF)16 για να μεταφέρουμε τα δύο δεξιά bytes του καταχωρητή R6 σε άλλο καταχωρητή, τον R5, και κατόπιν εκτελούμε δεξιά λογική ολίσθηση κατά 16bits στον καταχωρητή R6 για να φέρουμε τα δύο άλλα bytes στις δεξιές θέσεις. Με την διαδικασία αυτή έχουμε χωρίσει τα 4 αποτελέσματα της προηγούμενης πρόσθεσης σε δύο ζευγάρια τα οποία αποθηκεύσαμε σε δύο καταχωρητές όπως φαίνεται στο παρακάτω σχήμα.
R6
01111110 01111110 01111110 01111110
srli r6,r6,16
andi r5,r6,0xffff
R6
00000000 00000000 01111110 01111110
R5
00000000 00000000 01111110 01111110
Μπορούμε τώρα να επαναλάβουμε την πρόσθεση των καταχωρητών R6 και R5 με την οποία επιτυγχάνουμε την πρόσθεση των 4 bytes ανά 2. Το αποτέλεσμα επομένως θα είναι μεγέθους δύο bytes. Και σ’ αυτή την περίπτωση το μέγιστο αποτέλεσμα που μπορεί να προκύψει είναι 252, άρα δεν υπάρχει περίπτωση υπερχείλισης του byte.
Στη συνέχεια ακολουθούμε την ίδια διαδικασία με πριν, αλλά με διαφορετικές παραμέτρους, για να πάρουμε κάθε byte σε ξεχωριστό καταχωρητή. Έχουμε έτσι λογική πράξη AND του R6 με τον αριθμό (000000FF)16 και δεξιά ολίσθηση κατά 8 bit. Προσθέτοντας τα δύο αυτά αποτελέσματα έχουμε το άθροισμα όλων των αριθμών του πίνακα. Το άθροισμα αυτό το προσθέτουμε στον καταχωρητή R1.
Για τον έλεγχο της υπερχείλισης ακολουθούμε την εξής διαδικασία: Παίρνουμε τον αντίστροφο του αριθμού που έχει αποθηκευτεί στον R1. Το μέγεθος αυτό εκφράζει την διαφορά του αθροίσματος που συσσωρεύεται στον R1 από τον μέγιστο μη προσημασμένο αριθμό που μπορεί να αποθηκευτεί σε έναν καταχωρητή 32-bit, δηλαδή τον (FFFFFFFF)16. Επομένως υπερχείλιση θα συμβεί αν η διαφορά αυτή είναι μικρότερη από τον αριθμό που πρόκειται να προσθέσουμε.
Σύμφωνα με τα παραπάνω ο κώδικας του προγράμματος θα είναι ο εξής:
.data
array: .byte 63, 63, 63, 63, 63, 63, 63, 63
init: .word 0x0
mask: .word 0xffffffff
.text
.global main
main: ;Initialization of register r1 (register to overflow)
lw r1,init
;Load 0xffffffff to r2 to use xor as inverter
lw r2,mask
loop: ;Load numbers into two 32-bit registers
lw r5,array
lw r6,array+4
;Invert result of previous loop to check overflow
xor r7,r1,r2
;Add the two 32-bit registers.
addu r6,r6,r5
;Logic AND to obtain the 2 lower bytes of the result
andi r5,r6,0xffff
;Logic shift by 16 bits to obtain the 2 upper bytes of the result
srli r6,r6,16
;Add the two 32-bit registers.
addu r6,r6,r5
;Logic AND to obtain the lower byte of the result
andi r5,r6,0x00ff
;Logic shift by 8 bits to obtain the other byte of the result
srli r6,r6,8
;Final result of the array numbers.
addu r6,r6,r5
;Checking overflow
sltu r7,r7,r6
;Add result to register r1
addu r1,r1,r6
;Branch unless overflow has occurred
beqz r7,loop
finish: trap 0
Με κατάλληλη αντιμετάθεση των εντολών στον παραπάνω κώδικα έχουν αποφευχθεί οι RAW κίνδυνοι και έτσι δεν υπάρχουν καθυστερήσεις. Σε κάθε κύκλο επομένως τερματίζει μια εντολή. Σε κάθε βρόγχο υπάρχει μόνο η καθυστέρηση από την εντολή διακλάδωσης όταν αυτή ακολουθείται, όπου φορτώνεται αρχικά η εντολή trap 0 αλλά στη συνέχεια ματαιώνεται.
ΕΚΤΕΛΕΣΗ ΚΑΙ ΑΠΟΤΕΛΕΣΜΑΤΑ
Ο μικρότερος αριθμός πακέτων που απαιτείται ώστε να συμβεί υπερχείλιση είναι πακέτα των 8.
Πρέπει δηλαδή όλοι οι αριθμοί να είναι ίσοι με 63. Το παραπάνω πρόγραμμα επεξεργάζεται ένα πακέτο ακεραίων που βρίσκονται στη μνήμη σε 14 κύκλους ρολογιού. Για το πρώτο όμως πακέτο που θα φορτωθεί θα χρειαστεί 16 κύκλους λόγω των 2 εντολών φόρτωσης που εκτελούν τις αρχικοποιήσεις, ενώ για το τελευταίο πακέτο, στο οποίο θα συμβεί υπερχείλιση, θα χρειαστεί 18 κύκλους. Άρα συνολικά θα έχουμε 852759×14+16+18=119304658 κύκλους και ο συνολικός χρόνος εκτέλεσης του προγράμματος για αυτά τα πακέτα θα είναι sec.
Στα παρακάτω σχήματα απεικονίζονται τα αποτελέσματα της προσομοίωσης για την επεξεργασία του πρώτου, δεύτερου και τελευταίου πακέτου αριθμών.
Εικόνα 1. Επεξεργασία πρώτου πακέτου
Η πρόσθεση στον καταχωρητή R1 δεν έχει ακόμα ολοκληρωθεί γι’ αυτό ο καταχωρητής φαίνεται να περιέχει ακόμα την προηγούμενη τιμή.
Εικόνα 2. Επεξεργασία δεύτερου πακέτου
Μετά την επεξεργασία του δεύτερου πακέτου ο DLX έχει εκτελέσει 30 κύκλους. Άρα για το δεύτερο πακέτο χρειάστηκαν 14 κύκλοι.
Εικόνα 3. Επεξεργασία τελευταίου πακέτου (υπερχείλιση)
Για να υπολογίσουμε τους κύκλους που χρειάζονται για την επεξεργασία του τελευταίου πακέτου, αρχικοποιούμε τον R1 στην τιμή (FFFFFF00)16 που είναι η τιμή που θα είχε ο καταχωρητής μετά την επεξεργασία των προηγούμενων πακέτων, αφού 8521760×8×63=4294967040=(FFFFFF00)16. Έτσι στη μέτρηση δεν υπολογίζουμε τις 2 εντολές φόρτωσης που εκτελούνται μόνο κατά την εκκίνηση του προγράμματος και επομένως έχουμε 18 κύκλους.
Σε κάθε βρόγχο εισέρχονται στο IF στάδιο της σωλήνωσης 14 εντολές. Η τελευταία από αυτές όμως ματαιώνεται λόγω της ακολουθούμενης διακλάδωσης. Αν υποθέσουμε ότι αυτή η εντολή δεν καταναλώνει καθόλου ενέργεια, τότε ένας βρόγχος θα καταναλώνει ενέργεια ίση με 13×10-9 joule. Στον τελευταίο βρόγχο εκτελούνται 14 εντολές αφού η διακλάδωση δεν ακολουθείται, ενώ στον πρώτο βρόγχο εκτελούνται 2 εντολές περισσότερες. Επομένως συνολικά η κατανάλωση ενέργειας για την επεξεργασία του συγκεκριμένου αριθμού πακέτων των οκτώ θα είναι 8521759×(13×10-9)+14×10-9+15×10-9=11×10-2 joule.