Τρία θεμελιώδη ελαττώματα του SIMD ISA:s – Bits’n’Bites

26
Τρία θεμελιώδη ελαττώματα του SIMD ISA:s – Bits’n’Bites

Σύμφωνα με την ταξινόμηση του Flynn SIMD αναφέρεται σε μια αρχιτεκτονική υπολογιστή που μπορεί να επεξεργαστεί πολλαπλές ροές δεδομένων με μία μόνο εντολή (π.χ. „Μονή ροή εντολών, πολλαπλές ροές δεδομένων“). Υπάρχουν διαφορετικές ταξινομίες και μέσα σε αυτές πολλές διαφορετικές υποκατηγορίες και αρχιτεκτονικές που ταξινομούνται ως „SIMD“.

Σε αυτή την ανάρτηση όμως αναφέρομαι σε packed SIMD ISA:s, δηλαδή στον τύπο του SIMD αρχιτεκτονική συνόλου εντολών που είναι πιο συνηθισμένο στη σύγχρονη CPU:s καταναλωτικής ποιότητας. Πιο συγκεκριμένα αναφέρομαι μη προκαθορισμένο συσκευασμένο SIMD ISA: όπου οι λεπτομέρειες της συσκευασμένης επεξεργασίας SIMD εκτίθενται στο περιβάλλον λογισμικού.

Συσκευασμένο SIMD

Το κοινό χαρακτηριστικό των packed αρχιτεκτονικών SIMD είναι ότι πολλά στοιχεία δεδομένων συσκευάζονται σε έναν ενιαίο καταχωρητή σταθερού πλάτους. Ακολουθεί ένα παράδειγμα πιθανών διαμορφώσεων ενός συσκευασμένου καταχωρητή SIMD πλάτους 128 bit:

Καταχωρητής SIMD

Για παράδειγμα, ένας καταχωρητής 128-bit μπορεί να χωρέσει δεκαέξι ακέραιοι ψηφιολέξεις ή τέσσερις μεμονωμένες τιμές κινητής υποδιαστολής ακριβείας.

Αυτός ο τύπος αρχιτεκτονικής SIMD είναι εξαιρετικά δημοφιλής από τα μέσα της δεκαετίας του 1990 και μερικά γεμάτα SIMD ISA:

1 Τα AVX και νεότερα x86 SIMD ISA:s (ειδικά AVX-512) ενσωματώνουν χαρακτηριστικά από διανυσματική επεξεργασίακαθιστώντας τα συσκευασμένα υβρίδια επεξεργασίας SIMD / φορέα (επομένως ορισμένες από τις πτυχές που συζητούνται σε αυτό το άρθρο δεν ισχύουν πλήρως).

Η υπόσχεση όλων αυτών των ISA:s είναι η αυξημένη απόδοση επεξεργασίας δεδομένων, αφού κάθε εντολή εκτελεί πολλές λειτουργίες παράλληλα. Ωστόσο, υπάρχουν προβλήματα με αυτό το μοντέλο.

Ελάττωμα 1: Σταθερό πλάτος καταχωρητή

Εφόσον το μέγεθος του καταχωρητή είναι σταθερό, δεν υπάρχει τρόπος να κλιμακωθεί το ISA σε νέα επίπεδα παραλληλισμού υλικού χωρίς την προσθήκη νέων οδηγιών και καταχωρητών. Ενδεικτική περίπτωση: MMX (64 bit) έναντι SSE (128 bit) έναντι AVX (256 bit) έναντι AVX-512 (512 bit).

Η προσθήκη νέων μητρώων και οδηγιών έχει πολλές επιπτώσεις. Για παράδειγμα, το ABI πρέπει να ενημερωθεί και να προστεθεί υποστήριξη σε πυρήνες λειτουργικού συστήματος, μεταγλωττιστές και προγράμματα εντοπισμού σφαλμάτων.

Ένα άλλο πρόβλημα είναι ότι κάθε νέα γενιά SIMD απαιτεί νέους κωδικούς και κωδικοποιήσεις εντολών. Σε σύνολα εντολών σταθερού πλάτους (π.χ. ARM) αυτό μπορεί να απαγορεύσει τυχόν νέες επεκτάσεις, καθώς ενδέχεται να μην έχουν απομείνει αρκετές υποδοχές κωδικοποίησης για την προσθήκη των νέων εντολών. Στα σύνολα εντολών μεταβλητού πλάτους (π.χ. x86) το αποτέλεσμα είναι συνήθως ότι οι εντολές γίνονται όλο και μεγαλύτερες (βλαττώνοντας ουσιαστικά την πυκνότητα του κώδικα). Παραδόξως, κάθε νέα γενιά SIMD ουσιαστικά καθιστά περιττές τις προηγούμενες γενιές (εκτός από την υποστήριξη δυαδικής συμβατότητας προς τα πίσω), έτσι ένας μεγάλος αριθμός εντολών σπαταλιέται χωρίς να προσθέτει μεγάλη αξία.

Τέλος, κάθε λογισμικό που θέλει να χρησιμοποιήσει το νέο σύνολο εντολών πρέπει να ξαναγραφεί (ή τουλάχιστον να μεταγλωττιστεί ξανά). Το χειρότερο είναι ότι οι προγραμματιστές λογισμικού πρέπει συχνά να στοχεύουν πολλές γενιές SIMD και να προσθέτουν μηχανισμούς στα προγράμματά τους που επιλέγουν δυναμικά τις βέλτιστες διαδρομές κώδικα ανάλογα με το ποια γενιά SIMD υποστηρίζεται.

Ελάττωμα 2: Σωληνώσεις

Το πακεταρισμένο παράδειγμα SIMD είναι ότι υπάρχει μια αντιστοίχιση 1:1 μεταξύ του πλάτους του καταχωρητή και του πλάτους της μονάδας εκτέλεσης (αυτό συνήθως απαιτείται για την επίτευξη λογικής απόδοσης για εντολές που συνδυάζουν εισόδους από πολλές λωρίδες). Ταυτόχρονα, πολλές λειτουργίες SIMD διοχετεύονται και απαιτούν αρκετούς κύκλους ρολογιού για να ολοκληρωθούν (π.χ. αριθμητικές οδηγίες κινητής υποδιαστολής και φόρτωση μνήμης). Η παρενέργεια αυτού είναι ότι το αποτέλεσμα μιας εντολής SIMD δεν είναι έτοιμο για χρήση έως ότου αρκετές οδηγίες αργότερα στη ροή εντολών.

Κατά συνέπεια, πρέπει να υπάρχουν βρόχοι ξετυλιγμένο προκειμένου να αποφευχθούν οι πάγκοι και να παραμείνει απασχολημένος ο αγωγός. Αυτό μπορεί να γίνει σε προηγμένες υλοποιήσεις υλικού με μετονομασία μητρώου και κερδοσκοπική εκτέλεση εκτός σειράς, αλλά για απλούστερες (συνήθως πιο αποδοτικές σε ενέργεια) υλοποιήσεις υλικού πρέπει να ξεδιπλωθούν βρόχοι στο λογισμικό. Πολλοί προγραμματιστές λογισμικού και μεταγλωττιστές που στοχεύουν να υποστηρίξουν τόσο σε σειρά όσο και εκτός σειράς επεξεργαστές απλώς ξετυλίγουν όλους τους βρόχους SIMD στο λογισμικό.

Ωστόσο, το ξετύλιγμα βρόχου βλάπτει την πυκνότητα του κώδικα (δηλαδή κάνει το πρόγραμμα δυαδικό μεγαλύτερο), το οποίο με τη σειρά του βλάπτει την απόδοση της κρυφής μνήμης εντολών (λιγότερα τμήματα προγράμματος χωρούν στην κρυφή μνήμη εντολών, γεγονός που μειώνει την αναλογία επιτυχίας της κρυφής μνήμης).

Το ξετύλιγμα βρόχου αυξάνεται επίσης καταγράψτε την πίεση (δηλαδή πρέπει να χρησιμοποιηθούν περισσότεροι καταχωρητές για να διατηρηθεί η κατάσταση πολλαπλών επαναλήψεων βρόχων σε καταχωρητές), επομένως η αρχιτεκτονική πρέπει να παρέχει αρκετούς καταχωρητές SIMD για να αποφευχθεί εγγραφείτε διαρροή.

Ελάττωμα 3: Χειρισμός ουράς

Όταν ο αριθμός των στοιχείων πίνακα που πρόκειται να υποβληθούν σε επεξεργασία σε έναν βρόχο δεν είναι πολλαπλάσιος του αριθμού των στοιχείων στον καταχωρητή SIMD, ο ειδικός χειρισμός της ουράς βρόχου πρέπει να υλοποιηθεί στο λογισμικό. Για παράδειγμα, εάν ένας πίνακας περιέχει 99 στοιχεία 32 bit και η αρχιτεκτονική SIMD έχει πλάτος 128 bit (δηλ. ένας καταχωρητής SIMD περιέχει τέσσερα στοιχεία 32 bit), 4*24=96 στοιχεία μπορούν να υποβληθούν σε επεξεργασία στον κύριο βρόχο SIMD και 99 -96=3 στοιχεία πρέπει να υποβληθούν σε επεξεργασία μετά τον κύριο βρόχο.

Αυτό απαιτεί επιπλέον κωδικό μετά τον βρόχο για το χειρισμό της ουράς. Ορισμένες αρχιτεκτονικές υποστηρίζουν μάσκα φόρτωσης/αποθήκευσης που καθιστά δυνατή τη χρήση εντολών SIMD για την επεξεργασία της ουράς, ενώ ένα πιο συνηθισμένο σενάριο είναι ότι πρέπει να χρησιμοποιήσετε βαθμωτές (μη SIMD) οδηγίες για την υλοποίηση της ουράς (στην τελευταία περίπτωση μπορεί να υπάρχει προβλήματα εάν οι βαθμωτές εντολές και οι εντολές SIMD έχουν διαφορετικές δυνατότητες και/ή σημασιολογία, αλλά αυτό δεν είναι πρόβλημα με το συσκευασμένο SIMD καθεαυτό, απλώς με το πώς έχουν σχεδιαστεί ορισμένα ISA:.

Συνήθως χρειάζεστε επίσης επιπλέον λογική ελέγχου πριν από το βρόχο. Για παράδειγμα, εάν το μήκος του πίνακα είναι μικρότερο από το πλάτος του καταχωρητή SIMD, ο κύριος βρόχος SIMD θα πρέπει να παραλειφθεί.

Η προστιθέμενη λογική ελέγχου και ο κώδικας χειρισμού ουράς βλάπτουν την πυκνότητα του κώδικα (και πάλι μειώνουν την αποτελεσματικότητα της κρυφής μνήμης εντολών) και προσθέτουν επιπλέον επιβάρυνση (και είναι γενικά άβολο στον κώδικα).

Εναλλακτικές

Μια εναλλακτική λύση στο συσκευασμένο SIMD που αντιμετωπίζει όλα τα ελαττώματα που αναφέρονται παραπάνω είναι α Διανυσματικός επεξεργαστής. Ίσως ο πιο αξιοσημείωτος διανυσματικός επεξεργαστής είναι ο Cray-1 (κυκλοφόρησε το 1975) και έχει χρησιμεύσει ως έμπνευση για μια νέα γενιά αρχιτεκτονικών συνόλων εντολών, συμπεριλαμβανομένου του RISC-V RVV.

Αρκετά άλλα (ίσως λιγότερο γνωστά) έργα επιδιώκουν ένα παρόμοιο διανυσματικό μοντέλο, συμπεριλαμβανομένου του Agner Fog ForwardComτου Robert Finch Thor2021 και το δικό μου MRISC32. Μια ενδιαφέρουσα παραλλαγή είναι Free-SOC (με βάση το OpenPOWER) και του Simple-V επέκταση που αντιστοιχίζει διανύσματα στα βαθμωτά αρχεία καταχωρητών (τα οποία επεκτείνονται ώστε να περιλαμβάνουν περίπου 128 καταχωρητές το καθένα).

ΜΠΡΑΤΣΟ ΟΛΑ είναι ένα κατηγόρημα-κεντρικό, διανυσματικό αγνωστικό ISA που αντιμετωπίζει πολλά από τα παραδοσιακά ζητήματα SIMD.

Μια εντελώς διαφορετική προσέγγιση ακολουθεί ο Mitch Alsup’s Το 66000 μου και η μέθοδος Virtual Vector (VVM), η οποία μετατρέπει τους βαθμωτούς βρόχους σε διανυσματοποιημένους βρόχους στο υλικό με τη βοήθεια ειδικών οδηγιών διακόσμησης βρόχου. Με αυτόν τον τρόπο δεν χρειάζεται καν να έχει διανυσματικό αρχείο μητρώου.

Μια άλλη ενδιαφέρουσα αρχιτεκτονική είναι η Μύλοςπου έχει επίσης υποστήριξη για φορείς χωρίς συσκευασμένο SIMD.

Παραδείγματα

Επεξεργασία: Αυτή η ενότητα προστέθηκε στις 19-08-2021 για να παρέχει ορισμένα παραδείγματα κώδικα που δείχνουν τη διαφορά μεταξύ του πακέτου SIMD και άλλων εναλλακτικών.

Μια απλή ρουτίνα από ΜΠΛΑΣ είναι saxpy, που υπολογίζει z = a*x + y, όπου ένα είναι μια σταθερά, Χ και y είναι πίνακες και το „s“ στο „saxpy“ σημαίνει απλή κινητή υποδιαστολή ακριβείας.

Παρακάτω υπάρχουν αποσπάσματα κώδικα assembler που εφαρμόζουν το saxpy για διαφορετικά ISA:s.

Συσκευασμένο SIMD (x86_64 / SSE)

saxpy:
    test    rdi, rdi
    je      .done
    cmp     rdi, 8
    jae     .at_least_8
    xor     r8d, r8d
    jmp     .tail_2_loop
.at_least_8:
    mov     r8, rdi
    and     r8, -8
    movaps  xmm1, xmm0
    shufps  xmm1, xmm0, 0
    lea     rax, [r8 - 8]
    mov     r9, rax
    shr     r9, 3
    add     r9, 1
    test    rax, rax
    je      .dont_unroll
    mov     r10, r9
    and     r10, -2
    neg     r10
    xor     eax, eax
.main_loop:
    movups  xmm2, xmmword ptr [rsi + 4*rax]
    movups  xmm3, xmmword ptr [rsi + 4*rax + 16]
    mulps   xmm2, xmm1
    mulps   xmm3, xmm1
    movups  xmm4, xmmword ptr [rdx + 4*rax]
    addps   xmm4, xmm2
    movups  xmm2, xmmword ptr [rdx + 4*rax + 16]
    addps   xmm2, xmm3
    movups  xmmword ptr [rcx + 4*rax], xmm4
    movups  xmmword ptr [rcx + 4*rax + 16], xmm2
    movups  xmm2, xmmword ptr [rsi + 4*rax + 32]
    movups  xmm3, xmmword ptr [rsi + 4*rax + 48]
    mulps   xmm2, xmm1
    mulps   xmm3, xmm1
    movups  xmm4, xmmword ptr [rdx + 4*rax + 32]
    addps   xmm4, xmm2
    movups  xmm2, xmmword ptr [rdx + 4*rax + 48]
    addps   xmm2, xmm3
    movups  xmmword ptr [rcx + 4*rax + 32], xmm4
    movups  xmmword ptr [rcx + 4*rax + 48], xmm2
    add     rax, 16
    add     r10, 2
    jne     .main_loop
    test    r9b, 1
    je      .tail_2
.tail_1:
    movups  xmm2, xmmword ptr [rsi + 4*rax]
    movups  xmm3, xmmword ptr [rsi + 4*rax + 16]
    mulps   xmm2, xmm1
    mulps   xmm3, xmm1
    movups  xmm1, xmmword ptr [rdx + 4*rax]
    addps   xmm1, xmm2
    movups  xmm2, xmmword ptr [rdx + 4*rax + 16]
    addps   xmm2, xmm3
    movups  xmmword ptr [rcx + 4*rax], xmm1
    movups  xmmword ptr [rcx + 4*rax + 16], xmm2
.tail_2:
    cmp     r8, rdi
    je      .done
.tail_2_loop:
    movss   xmm1, dword ptr [rsi + 4*r8]
    mulss   xmm1, xmm0
    addss   xmm1, dword ptr [rdx + 4*r8]
    movss   dword ptr [rcx + 4*r8], xmm1
    add     r8, 1
    cmp     rdi, r8
    jne     .tail_2_loop
.done:
    ret
.dont_unroll:
    xor     eax, eax
    test    r9b, 1
    jne     .tail_1
    jmp     .tail_2

Παρατηρήστε πώς ο συσκευασμένος κώδικας SIMD περιέχει μια 4x ξετυλιγμένη έκδοση του κύριου βρόχου SIMD και έναν βρόχο κλιμακωτή ουρά.

Διάνυσμα (MRISC32)

saxpy:
    bz    r1, 2f          ; Nothing to do?
    getsr vl, #0x10       ; Query the maximum vector length
1:
    minu  vl, vl, r1      ; Define the operation vector length
    sub   r1, r1, vl      ; Decrement loop counter
    ldw   v1, [r3, #4]    ; Load x (element stride = 4 bytes)
    ldw   v2, [r4, #4]    ; Load y
    fmul  v1, v1, r2      ; x * a
    fadd  v1, v1, v2      ; + y
    stw   v1, [r5, #4]    ; Store z
    ldea  r3, [r3, vl*4]  ; Increment address (x)
    ldea  r4, [r4, vl*4]  ; Increment address (y)
    ldea  r5, [r5, vl*4]  ; Increment address (z)
    bnz   r1, 1b
2:
    ret

Σε αντίθεση με τη γεμάτη έκδοση SIMD, η διανυσματική έκδοση είναι πολύ πιο συμπαγής, καθώς χειρίζεται το ξετύλιγμα και την ουρά στο υλικό.

Virtual Vector Method (My 66000)

saxpy:
    beq0    r1,1f         ; Nothing to do?
    mov     r8,#0         ; Loop counter = 0
    vec     r9,{}         ; Start vector loop
    lduw    r6,[r3+r8<<2] ; Load x
    lduw    r7,[r4+r8<<2] ; Load y
    fmacf   r6,r6,r2,r7   ; x * a + y
    stw     r6,[r5+r8<<2] ; Store z
    loop    ne,r8,r1,#1   ; Increment counter and loop
1:
    ret

Η μέθοδος εικονικού διανύσματος (VVM) είναι μια νέα τεχνική που εφευρέθηκε από τον Mitch Alsup και επιτρέπει τη διανυσματοποίηση χωρίς διανυσματικό αρχείο μητρώου. Όπως μπορείτε να δείτε σε αυτό το παράδειγμα μόνο βαθμωτές εντολές και αναφορές σε ονόματα καταχωρητών βαθμωτών (“r*„) είναι μεταχειρισμένα. Οι βασικοί παίκτες εδώ είναι οι οδηγίες VEC και LOOP που μετατρέπουν τον βαθμωτό βρόχο σε διανυσματικό βρόχο.

Ουσιαστικά η εντολή VEC σηματοδοτεί την κορυφή του διανυσματικού βρόχου (το r9 αποθηκεύει τη διεύθυνση της έναρξης του βρόχου, η οποία χρησιμοποιείται σιωπηρά από την εντολή LOOP αργότερα). Όλες οι οδηγίες μεταξύ VEC και LOOP αποκωδικοποιούνται και αναλύονται μία φορά και στη συνέχεια εκτελούνται σύμφωνα με τις δυνατότητες του υλικού. Σε αυτήν την περίπτωση, τα περισσότερα αναγνωριστικά καταχωρητών (r1, r3, r4, r5, r6, r7, r8) χρησιμοποιούνται ως εικονικοί διανυσματικοί καταχωρητές, ενώ ο r2 χρησιμοποιείται ως βαθμωτός καταχωρητής. Η εντολή LOOP αυξάνει τον μετρητή κατά 1, τον συγκρίνει με το r1 και επαναλαμβάνει τον βρόχο εφόσον πληρούται η συνθήκη, όχι ίση („ne“).

Περαιτέρω ανάγνωση

Δείτε επίσης: Το SIMD θεωρείται επιβλαβές (D. Patterson, A. Waterman, 2017)

Schreibe einen Kommentar