[PYTHON] Matrixmultiplikation auf Raspberry Pi GPU (Teil 2)

Dieser Artikel sollte vor einer Woche im Raspberry Pi Adventskalender 2015 veröffentlicht werden. Dies ist eine Fortsetzung von Matrixmultiplikation mit GPU von Raspberry Pi (1). Es tut mir sehr leid, dass ich den Zeitplan bestanden habe.

Beim letzten Mal habe ich einen Teil erstellt, um die 16x64-Matrix in der folgenden Abbildung parallel zu SIMD zu berechnen. Daher werde ich andere Teile erstellen, um den Code für die Matrixmultiplikation zu vervollständigen.

i-loop und j-loop werden im Vergleich zu k-loop nur sehr wenige Male ausgeführt, daher ist dies einfach.

Über j-loop

for(j = 0; j < r; j+=64) {
   body
}

Wird in einen Baugruppenstil übersetzt

j = 0

j_loop_begin:

if(j >= r) goto j_loop_exit

body

j += 64
goto j_loop_begin

j_loop_exit:

Es gibt jedoch einen nutzlosen Sprung, wie er ist. Das Springen braucht Zeit, und wenn der Befehls-Cache-Eintrag entfernt wird, wird die Leistung anderer Teile beeinträchtigt. Sie können es so umschreiben, dass es nur einen Sprung in der Schleife gibt, wie unten gezeigt.

j = 0
if(j >= r) goto j_loop_exit

j_loop_begin:

body

j += 64
if(j < r) goto j_loop_begin
j_loop_exit:

Das allererste j> = r ist immer erfolglos und kann weggelassen werden.

j = 0

j_loop_begin:

body

j += 64
if(j < r) goto j_loop_begin

j_loop_exit:

Mit anderen Worten, es wird die Form einer Do-While-Typ-Schleife haben, wie unten gezeigt.

j = 0
do {
    body

    j += 64
} while (j < r);

Auch als die Form oben

j = r
do {
    body

    j -= 64
} while(j > 0);

Ich finde die Form besser. Der Punkt ist, dass letzteres die Anzahl der Zugriffe auf "r" reduziert. (Als Bonus wird die Anzahl der Operationen um eins reduziert. Ersteres war zweimal "j + 64" und "j - r", letzteres ist einmal "j - 64".)

j = 0
do {
    body

    j += 64
} while (j < r);  <-Lesen Sie hier jedes Mal r


j = r <-Nur einmal hier
do {
    body

    j -= 64
} while(j > 0);

Variablen mit niedriger Zugriffsfrequenz haben nur geringe Auswirkungen, selbst wenn sie an einem langsamen Ort platziert werden, sodass sie im Speicher oder mit der zuletzt eingeführten Methode gespeichert werden können. Dann können die gespeicherten Register und Akkumulatoren effektiv im Schleifenkörper verwendet werden, was indirekt zu einer Leistungsverbesserung führt. Schreiben Sie i-loop auf die gleiche Weise.

Software-Rohrauskleidung

Ich habe darüber nachgedacht, das zuletzt erwähnte Software-Pipeline-Lining durchzuführen, aber ich habe es nicht getan, weil ich die exklusive Kontrolle erschöpft habe, die später beschrieben wird.

Ich werde erklären, was ich versucht habe. Wenn Sie dieses Programm in Pseudocode schreiben, sieht es wie folgt aus. Wie ich letztes Mal erklärt habe, füge ich die 16x16-Matrix in 4 Schritten hinzu, aber es bleibt Zeit, an dem Punkt, an dem der 4. Block an den Host übertragen wird, keine Berechnung durchzuführen.

for (j) {

Adressberechnung und Cache-Initialisierung

    k-Der Teil, der aus der Schleife nach vorne ragt
    for (k) {
Berechnen Sie das Produkt der Vektoren von A und B.
    }
Während des Ladens des ersten Blocks k-Berechnen Sie den Betrag, der hinter der Schleife hervorsteht
Laden Sie den zweiten Block und berechnen Sie den ersten Block
Berechnen Sie den zweiten Block, während Sie den ersten Block speichern und den dritten Block laden
Berechnen Sie den 3. Block, während Sie den 2. Block speichern und den 4. Block laden
Berechnen Sie den 4. Block, während Sie den 3. Block speichern
Speichern Sie den 4. Block<-Ich habe nichts berechnet!

Bedingte Verzweigung(Gehen Sie zurück zum Anfang oder brechen Sie aus der Schleife aus)
}

Um diese Wartezeit (Latenz) zu füllen, wird der Vorgang des Einbringens von Anweisungen aus der nächsten Iteration als Software-Pipeline bezeichnet. In einigen Fällen können Sie es aus den nächsten und nachfolgenden Iterationen mitbringen. VideoCore IV führt (wahrscheinlich) keine fehlerhafte Ausführung von Anweisungen wie teuren GPUs durch, daher halte ich diese Art von Aufwand für wichtig.

Natürlich kann die Latenz auch durch Multithreading ausgeblendet werden. Es ist ein Warp in der NVIDIA-GPU. VideoCore IV QPU kann 2 Threads gleichzeitig ausführen.

Single Thread Benchmark

Jetzt, da ich mit einer QPU laufen kann, habe ich einen Benchmark erstellt. Ich habe den Raspberry Pi Zero verwendet, den ich neulich gekauft habe. Die installierte CPU und GPU sind mit Raspberry Pi 1 identisch, und nur der CPU-Takt wird auf 1 GHz verbessert.

Der verwendete Quellcode ist unten.

https://github.com/nineties/py-videocore/blob/master/examples/sgemm_1thread.py

Unten sind die Ergebnisse. Hier ist der Typ von A 96x363 und der Typ von B ist 363x3072 gemäß dem pi-gemm.

Ich konnte es schnell genug machen, um mit nur einer QPU pi-gemm einzuholen. Da die theoretische Leistung einer QPU jedoch 2Gflops beträgt, ist es schade, dass die Leistung nur etwa 50% davon betrug. Als ich es gemessen habe, war der Uniforms Cache langsamer als erwartet und es waren ungefähr 2 Anweisungen für eine Ladung mit 1 QPU erforderlich. Dann wird die Länge des k-Schleifenkörpers ungefähr verdoppelt, was ungefähr 50% beträgt. Durch Erhöhen der Anzahl der QPUs werden Cache-Fehler erhöht und die Effizienz weiter verringert. Ich hatte es bis zu einem gewissen Grad erwartet, weil eine Last nur 4 Bytes beträgt und die Entfernung mit SoC kurz ist.

    L.k_loop

    fadd(ra1,  ra1,  r0).fmul(r0, r4, uniform)  #Diese Jungs sind ungefähr 7~Wie etwa 8 Uhren(2 Anweisungen)
    fadd(rb1,  rb1,  r0).fmul(r0, r4, uniform)

    ...

    fadd(rb31, rb31, r0, sig='load tmu0').mov(uniforms_address, r2)
    iadd(r2, r2, r3).mov(tmu0_s, r1)
    jzc(L.k_loop)
    iadd(r1, r1, 4).fmul(r0, r4, uniform)      # delay slot #Dieser Typ sieht aus wie 30 Uhren
    fadd(ra0,  ra0,  r0).fmul(r0, r4, uniform) # delay slot
    fadd(rb0,  rb0,  r0).fmul(r0, r4, uniform) # delay slot

Ich frage mich, wie ich das verbessern kann.

Die TMU verfügt über einen L1-Cache und scheint schneller zu sein als der Uniforms-Cache, verbraucht jedoch ALU für die Adressberechnung, sodass sie nicht zum Lesen verschiedener Vektoren nacheinander geeignet ist. Es scheint, dass es eine Möglichkeit gibt, zuerst zwei Vektoren mit TMU zu lesen und das direkte Produkt zu berechnen, während das Drehen und Senden für einen wiederholt wird. Dies verbraucht auch ALU mit Drehen, aber da die Anzahl der Treffer im Cache verringert wird, ist die Leistung beim Erhöhen der QPU möglicherweise besser.

Tatsächlich war es zwischen QPU und VPM nicht so langsam, und wenn es nur eine QPU gab, konnten beide Lese- / Schreibvorgänge ohne Stillstand ausgeführt werden. VPM wird jedoch von allen QPUs gemeinsam genutzt, sodass sich das Erhöhen der QPUs möglicherweise verlangsamt. Wenn Sie die Matrizen A und B mit VPM lesen, besteht auch das Problem, dass die Anzahl der DMAs erheblich zunimmt.

Ich denke, der erste Schritt besteht vorerst darin, die Leistung jedes Caches zu messen und die interne Struktur zu untersuchen. Das Obige ist eine zukünftige Aufgabe und wir werden weitermachen.

[Ergänzung] Ich dachte, dass der Uniforms-Cache aufgrund des Mechanismus nicht per Software vorab abgerufen werden kann, aber da der L2-Cache mit TMU geteilt wird, scheint es, dass Uniforms mithilfe von TMU im Voraus auf L2 gezogen werden können.

Zitiert aus dem VideoCore IV 3D-Architektur-Referenzhandbuch

Parallelisierung zwischen QPUs

VideoCore verfügt über 12 QPUs. Dieses Mal führt jede QPU einen Thread mit insgesamt 12 Threads aus. Daher ist, wie in der folgenden Abbildung gezeigt, die Matrix $ A $ horizontal in mehrere Teile und $ B $ vertikal in mehrere Teile unterteilt, und das Produkt aus diesen wird jeder QPU zugewiesen.

Synchrone Steuerung / exklusive Steuerung

Wie ein reguläres Multithread-Programm erfordert es die ausschließliche Kontrolle über den Zugriff auf gemeinsam genutzte Ressourcen. Aus diesem Grund verfügt VideoCore IV über einen Mutex und 16 4-Bit-Semaphos.

Ich werde die Synchronisationssteuerung mit diesen schreiben, aber dieses Mal habe ich es unterlassen, den Teil, der synchronisiert werden muss, mit einem ganzen Mutex einzuschließen. Natürlich sollte es einen Einfluss auf die Leistung haben ...

Hauptsächlich die von QPU gemeinsam genutzten Ressourcen

• VPM --DMA-Controller (VCD zum Laden, VDW zum Speichern) --Reserviert für diese Einstellungen und den Start

Usw., aber

Es können jeweils nur zwei VPM-Leseeinstellungen eingerichtet werden, die ignoriert werden, wenn die Warteschlange voll ist. (Referenzhandbuch P56)

Und

Das Laden in DMA kann erst ausgegeben werden, wenn der vorherige abgeschlossen ist. Gleiches gilt für das Geschäft. (Wie P56)

Es gibt einige Einschränkungen wie. Keiner von ihnen mag die Freundlichkeit wie "Stall bis zum Ende des vorherigen", und die Anfrage wird ignoriert oder Raspi selbst stoppt. Es scheint auch einige Einschränkungen zu geben, die im Referenzhandbuch nicht erwähnt werden (insbesondere in Bezug auf das zusätzliche Schritt-Setup-Register). Es war eine ziemliche Buße, denn der Fehler meines eigenen Assemblers überschnitt sich damit.

Semafo wird verwendet, um Situationen zu behandeln, in denen die Anzahl der Ressourcen begrenzt ist, wie z. B. "nur bis zu zwei". Behalten Sie einen aller Threads als Master-Thread bei, und zuerst wird das Semapho um 2 erhöht. Threads, die VPM lesen möchten, senken dieses Semapho um eins und erhöhen es um eins, wenn sie damit fertig sind. Threads, die versuchen, sie unter 0 zu senken, befinden sich im Wartezustand, sodass Sie bis zu zwei gleichzeitig verwenden können. Das Sperren kann auch mit einem Semapho erfolgen.

Ich habe das Semapho in diesem Teil nicht verwendet, weil ich es diesmal mit Mutex umgeben habe, aber ich verwende es an der Stelle, um das Ende des Threads zu synchronisieren. Der Master-Thread muss warten, bis alle Threads ihre Berechnungen abgeschlossen haben, bevor er einen Interrupt an den Host ausgibt. Wenn 12 Threads vorhanden sind, wird wie folgt synchronisiert.

1. Jeder Thread erhöht das Semapho um 1, wenn die Berechnung, für die er verantwortlich ist, abgeschlossen ist.
2. Nachdem der Master-Thread das Semapho 12 Mal abgesenkt hat, gibt er einen Interrupt an den Host aus und wird beendet.

Es ist sehr einfach. Unten ist der Code für diesen Teil.

    sema_up(COMPLETED)  # Notify completion to the thread 0

    ...

    mov(null, uniform, set_flags=True)  # thread index

    jzc(L.skip_fin)
    nop(); nop(); nop()

    # Only thread 0 enters here.
    for i in range(n_threads):
        sema_down(COMPLETED)    # Wait completion of all threads.

    interrupt()

    L.skip_fin

    exit(interrupt=False)

Eigentlich dachte ich daran, die Verarbeitung von vier Blöcken zu einer Pipeline zu machen, wie in der folgenden Abbildung gezeigt. Ich kann es versuchen, wenn ich Zeit habe.

Benchmark

Der Code ist unten.

https://github.com/nineties/py-videocore/blob/master/examples/sgemm.py

Die Matrixgröße beträgt 96x363 für A und 363x3072 für B wie zuvor. Mit 12 Threads wurde A in zwei und B in sechs geteilt, was am schnellsten war. Ich stelle mir vor, dass hier der Cache für A (TMU) und der Cache für B (Uniformen) gut ausbalanciert sind. Ich werde bald detaillierte Nachforschungen anstellen.

Zusammenfassung

• Ich habe die Matrixmultiplikation mit einfacher Genauigkeit auf der GPU von Raspberry Pi versucht. Wir konnten ungefähr 33% der theoretischen Leistung produzieren, ungefähr 8 Gflops. Ich denke, es gibt noch Raum für Anstrengungen, also werde ich mein Bestes geben. ――Es ist ungefähr 120-mal schneller als numpy + BLAS und ungefähr 8-mal schneller als pi-gemm.

Nur das Berechnen (mit doppelter Genauigkeit) mit numpy + BLAS auf meinem Laptop (Core i7-5600U 2,6 GHz) entspricht ungefähr der gleichen Geschwindigkeit. Mit anderen Worten, selbst wenn Sie sich bemühen, die GPU von Raspberry Pi zu verwenden, ist die Berechnung mit einem normalen Computer leider schneller. Pi-Zero kostet 600 Yen, daher kann es rentabel sein, wenn es sich um ein Preis-Leistungs-Verhältnis handelt.