SoA-Vektoren auf SPU

8

Ich habe viel über die Vorteile der Organisation von Daten in "Structs of Arrays" (SoA) anstelle des typischen "Array of Structs" (AoS) gelesen, um einen besseren Durchsatz bei Verwendung von SIMD- Anweisungen zu erzielen . Obwohl das Warum für mich absolut sinnvoll ist, bin ich mir nicht sicher, wie viel ich tun soll, wenn ich mit Dingen wie Vektoren arbeite.

Vektoren selbst können als Struktur eines Datenarrays (fester Größe) verstanden werden, sodass Sie ein Array davon in eine Struktur von X-, Y- und Z-Arrays konvertieren können. Auf diese Weise können Sie 4 Vektoren gleichzeitig bearbeiten und nicht jeweils einen.

Aus dem speziellen Grund poste ich dies auf GameDev:

Ist dies sinnvoll für die Arbeit mit Vektoren auf der SPU? Ist es insbesondere sinnvoll, mehrere Arrays nur für einen einzelnen Vektor zu dMA? Oder wäre es besser, beim DMAing des Vektorarrays zu bleiben und es in die verschiedenen Komponenten abzuwickeln, mit denen gearbeitet werden soll?

Ich konnte den Vorteil des Ausschaltens des Abrollens erkennen (wenn Sie es 'AoS' gemacht haben), aber es scheint, als könnten Ihnen schnell die DMA-Kanäle ausgehen, wenn Sie diesen Weg einschlagen und mit mehreren Vektorsätzen gleichzeitig arbeiten würden.

(Hinweis: Noch keine Berufserfahrung mit Cell, aber ich habe eine Weile in OtherOS herumgespielt.)

Chris Waters
quelle

Antworten:

5

Ein Ansatz besteht darin, einen AoSoA-Ansatz (sprich: Array of Struct of Array) zu verwenden, der eine Mischung aus AoS und SoA ist. Die Idee ist, Daten im Wert von N Strukturen in einem zusammenhängenden Block in SoA-Form zu speichern, dann die nächsten N Strukturen im Wert von SoA.

Ihre AoS-Form für 16 Vektoren (mit 0,1,2 ... F bezeichnet), die bei einer Granularität von 4 Strukturen aufgerollt wurden, lautet:

000111222333444555666777888999AAABBBCCCDDDEEEFFF
XYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZXYZ

Für SoA ist dies:

0123456789ABCDEF
XXXXXXXXXXXXXXXXX

0123456789ABCDEF
JJJJJJJJJJJJJJJ

0123456789ABCDEF
ZZZZZZZZZZZZZZZZ

Für AoSoA wird dies:

01230123012345674567456789AB89AB89ABCDEFCDEFCDEF
XXXXYYYYZZZZXXXXYYYYZZZZXXXXYYYYZZZZXXXXYYYYZZZZ

Der AoSoA-Ansatz bietet die folgenden Vorteile von AoS:

  • Es ist nur eine einzige DMA-Übertragung erforderlich, um einen Teil der Strukturen in den lokalen SPU-Speicher zu übertragen.
  • Strukturen haben immer noch die Möglichkeit, dass alle Daten in eine Cacheline passen.
  • Das Block-Prefetching ist immer noch sehr einfach.

Der AoSoA-Ansatz bietet auch die folgenden Vorteile der SoA-Form:

  • Sie können Daten aus dem lokalen SPU-Speicher direkt in 128-Bit-Vektorregister laden, ohne Ihre Daten durcheinander bringen zu müssen.
  • Sie können immer noch 4 Strukturen gleichzeitig bearbeiten.
  • Sie können die SIMD'ness Ihres Vektorprozessors voll ausnutzen, wenn keine grundlegende Verzweigung vorhanden ist (dh keine nicht verwendeten Spuren in Ihrer Vektorarithmetik).

Der AoSoA-Ansatz weist noch einige der Nachteile der SoA-Form auf:

  • Die Objektverwaltung muss mit sprudelnder Granularität erfolgen.
  • Direktzugriffsschreibvorgänge einer vollständigen Struktur müssen jetzt den verstreuten Speicher berühren.
  • (Dies kann sich als unproblematisch herausstellen, abhängig davon, wie Sie Ihre Strukturen organisieren / verwalten und wie lange sie dauern.)

Übrigens gelten diese AoSoA-Konzepte sehr gut für SSE / AVX / LRBni sowie für GPUs, die mit sehr breiten SIMD-Prozessoren verglichen werden können, z. 32/48/64 breit je nach Anbieter / Architektur.

jpaver
quelle
Ich sehe keinen Vorteil darin, dass sie nicht pro Komponente gepackt werden, es sei denn, Sie packen Nicht-Vektor-Daten, die Sie tatsächlich als Floats verwenden - obwohl ich sehe, dass Ihr AoS W ausschließt, was nicht sehr speicherzugriffsfreundlich erscheint, ich denke in diesem Fall gibt es einen Gewinn. Beachten Sie auch, dass SPUs keine Cache-Zeilen haben, außer für die Kommunikation mit dem Hauptspeicher.
Kaj
2
1. Wie bei allen Dingen kann Ihr Kilometerstand abhängig von Ihren genauen Daten / Algorithmen / Prozessoren variieren. In Fällen mit eingeschränkten Registern kann es hilfreich sein, die Notwendigkeit von 4 temporären Registern zu vermeiden, bevor Sie alle Ihre X-Felder in dasselbe Register mischen können. Aber wieder YMMV. 2. Meine Antwort war allgemeiner, da sich die Konzepte im Bereich der datenparallelen Programmierung gut übertragen lassen. Überlegungen zu Cache-Zeilen sind für GPU / SSE relevanter, aber ich hatte das Gefühl, ich sollte sie trotzdem erwähnen :)
jpaver
1
Fair genug, ich stehe erleuchtet da und werde lernen, subtiler zu kritisieren! Vielen Dank für Ihre Erkenntnis: o)
Kaj
3

SPUs sind tatsächlich ein interessanter Sonderfall, wenn es um die Vektorisierung von Code geht. Die Anweisungen sind in die Familien "Arithmetik" und "Laden / Speichern" unterteilt, und die beiden Familien werden in separaten Pipelines ausgeführt. Die SPU kann pro Zyklus einen von jedem Typ ausgeben.

Der mathematische Code ist offensichtlich stark an mathematische Anweisungen gebunden. Daher haben mathematische Schleifen auf SPU normalerweise viele, viele offene Zyklen in der Lade- / Speicherleitung. Da das Laden / Speichern von Rohren gemischt wird, verfügen Sie häufig über genügend kostenlose Lade- / Speicheranweisungen, um das xyzxyzxyzxyz-Formular ohne Overhead in das xxxxyyyyzzzz-Formular umzuwandeln.

Diese Technik wird zumindest bei Naughty Dog verwendet - Einzelheiten finden Sie in den Präsentationen der SPU-Baugruppen ( Teil 1 und Teil 2 ).

Leider ist der Compiler oft nicht intelligent genug, um dies automatisch zu tun. Wenn Sie sich für diesen Weg entscheiden, müssen Sie entweder die Assembly selbst schreiben oder Ihre Schleifen mithilfe von Intrinsics abrollen und den Assembler überprüfen, um sicherzustellen, dass er Ihren Wünschen entspricht. Wenn Sie also allgemeinen plattformübergreifenden Code schreiben möchten, der auf SPU gut funktioniert, sollten Sie sich für SoA oder AoSoA entscheiden (wie von jpaver vorgeschlagen).

Charlie
quelle
Ah, wir sind uns doch einig: o) Swizzle auf der SPU, wenn du es brauchst, Zeit genug, um es dort zu tun.
Kaj
1

Wie bei allen Optimierungen Profil! Die Lesbarkeit steht an erster Stelle und sollte nur geopfert werden, wenn die Profilerstellung einen bestimmten Engpass feststellt und Sie alle Optionen für die Optimierung des High-Level-Algorithmus ausgeschöpft haben (der schnellste Weg, die Arbeit zu erledigen, besteht darin, die Arbeit nicht erledigen zu müssen!). Sie sollten immer ein neues Profil erstellen Befolgen Sie eine Optimierung auf niedriger Ebene, um zu bestätigen, dass Sie die Dinge wirklich schneller als umgekehrt gemacht haben, insbesondere bei Pipelines, die so eigenartig sind wie die der Zelle.

Welche Techniken Sie dann verwenden, hängt von den Einzelheiten des Engpasses ab. Wenn Sie mit Vektortypen arbeiten, repräsentiert eine Vektorkomponente, die Sie in einem Ergebnis ignorieren, im Allgemeinen verschwendete Arbeit. Das Wechseln von SoA / AoS ist nur dann sinnvoll, wenn Sie durch das Befüllen solcher nicht verwendeter Komponenten (z. B. ein Punktprodukt auf der PS3-PSU gegenüber vier Punktprodukten parallel in derselben Zeitspanne) nützlichere Arbeiten ausführen können. Um Ihre Frage zu beantworten, klingt es für mich nach einer Pessimisierung, wenn Sie Zeit damit verbringen, Komponenten zu mischen, um nur eine Operation an einem einzelnen Vektor auszuführen!

Die Kehrseite von SPUs ist, dass der Großteil der Kosten für kleine DMA-Übertragungen im Setup liegt. Bei weniger als 128 Bytes dauert die Übertragung dieselbe Anzahl von Zyklen, bei weniger als einem Kilobyte nur wenige Zyklen mehr. Machen Sie sich also keine Sorgen, dass Sie mehr Daten DMAen, als Sie unbedingt benötigen. Das Reduzieren der Anzahl der ausgelösten sequentiellen DMA-Übertragungen und das Ausführen von Arbeiten während der DMA-Übertragungen - und damit das Entfalten von Schleifenprologen und Epilogen zur Bildung von Software-Pipelines - ist der Schlüssel zu einer guten SPU-Leistung, und es ist am einfachsten, Eckfälle durch Abrufen zusätzlicher Daten zu behandeln / Verwerfen teilweise berechneter Ergebnisse als Springen durch Reifen, um zu versuchen, die genaue Datenmenge zu ermitteln, die zum Lesen und Verarbeiten erforderlich ist.

Mondschatten
quelle
Wenn Sie sie am Ende gemäß dem AOSAO-Ansatz auspacken, ziehen Sie tatsächlich mindestens mehrere Vektoren gleichzeitig ein. Außerdem möchten Sie einen Stapel ziehen, und während Sie diese verarbeiten, ziehen Sie den nächsten Stapel ein. Während Sie den ersten Stapel versenden, verarbeiten Sie den zweiten und ziehen den dritten ein. Auf diese Weise verbergen Sie so viel Latenz wie möglich.
Kaj
0

Nein, das wäre im Allgemeinen nicht sehr sinnvoll, da die meisten Vektor-Opcodes mit einem Vektor als Ganzes und nicht mit separaten Komponenten arbeiten. Sie können also bereits einen Vektor in einer Anweisung multiplizieren, während Sie beim Aufteilen der einzelnen Komponenten 4 Anweisungen dafür ausgeben würden. Da Sie also im Allgemeinen viele Operationen an einem Teil einer Struktur ausführen, ist es besser, sie in ein Array zu packen, aber Sie tun kaum etwas nur an einer Komponente eines Vektors oder an jeder Komponente, die so stark beschädigt ist out würde nicht funktionieren.
Wenn Sie eine Situation finden, in der Sie nur mit den (sagen wir) x-Komponenten von Vektoren etwas tun müssen, könnte dies natürlich funktionieren, aber die Strafe, alles zurückzuschwenken, wenn Sie den tatsächlichen Vektor benötigen, wäre nicht billig, also könnten Sie es Ich frage mich, ob Sie zunächst keine Vektoren verwenden sollten, sondern nur eine Reihe von Floats, die es Vektor-Opcodes ermöglichen, ihre spezifischen Berechnungen durchzuführen.

Kaj
quelle
2
Sie vermissen den Punkt von SoA für die Vektormathematik. Sie haben selten nur ein Objekt, an dem Sie arbeiten - in der Praxis iterieren Sie ein Array und machen dasselbe mit vielen Objekten. Erwägen Sie 4-Punkt-Produkte. Wenn Sie Vektoren als AoS in xyz0-Form speichern, erfordert das Aufnehmen des Punkts zweier Vektoren das Multiplizieren von Shuffle-Add-Shuffle-Add - 5 Anweisungen. Für 4-Punkt-Produkte sind 20 Anweisungen erforderlich. Wenn Sie dagegen 8 Vektoren SoA-Mode gespeichert haben (xxxx, yyyy, zzzz, xxxx, yyyy, zzzz), können Sie 4-Punkt-Produkte mit nur 3 Anweisungen (mul, madd, madd) erstellen - das ist mehr als sechsmal schneller.
Charlie
Gutes Argument. Zwei Beobachtungen. Ich würde das W immer präsent halten, damit ich keine 20 Anweisungen benötige. Zweitens kann der größte Teil des verbleibenden Overheads in der Latenz anderer Anweisungen verborgen sein - Ihre enge Schleife würde unter schweren Pipeline-Stillständen leiden, nicht wahr? Das 6-fache ist eine theoretische Optimierung. Also, obwohl ja, Sie möchten Ihre Vorgänge stapeln - kaum jemals müssen Sie nur eine schnelle Charge von Punktprodukten ausführen, ohne dass Sie etwas anderes mit diesen Daten tun müssen. Die Kosten für das Deswizzling / Scatter auf der PPU-Seite wären für mich ein zu großes Opfer.
Kaj
Stöhnen, ich stehe korrigiert da - auf SPU würde ich 20 brauchen, wenn es naiv gemacht würde (aber ich würde an Ort und Stelle mischen). Es ist eines der Dinge, bei denen ich viele Swizzles gemacht habe, um es optimal zu machen. 360 hat einen schönen Punkt (aber es fehlt die großartige Bit-Manipulation).
Kaj
Ja, jetzt wo ich darüber nachdenke, wenn Sie versuchen, "4-Punkt-Produkte" zu machen, können Sie eher besser als 20 Anweisungen machen, weil Sie einige der späteren Ergänzungen kombinieren können. Wenn Sie Ihre Vektoren jedoch in den Registern xxxx, yyyy, zzzz haben - unabhängig davon, ob Sie sie als SoA gespeichert oder gespeichert haben -, werden diese Shuffles vollständig entfernt. Wie auch immer, Sie haben Recht, dass SoA den Code für verzweigte Logik langsamer macht - aber ich würde argumentieren, dass die Lösung in vielen Fällen darin besteht, Ihre Daten zu bündeln und die verzweigte Logik in schöne flache Schleifen umzugestalten.
Charlie
Einverstanden. Ich bin mir ziemlich sicher, dass es Fälle gibt, in denen ich meinen alten SPU-Code (kann nicht, vorherige Firma) zur Optimierung in das xxxxyyyyzzzz-Format verschoben habe, ohne ihn speziell zu bemerken. Ich habe es jedoch nie von der PPU in diesem Format angeboten. Wohlgemerkt, OP, was in Betracht gezogen wird, x, y, z getrennt zu dmaen. Das würde bei mir definitiv nicht funktionieren. Ich würde auch (wie ich) lieber lokal swizzeln, da nicht alles im xxxxyyyyzzzz-Format besser funktioniert. Ich denke, ich muss deine Schlachten auswählen. Die Optimierung für SPU ist ein Knaller und Sie fühlen sich schrecklich schlau, wenn Sie diese enge Lösung gefunden haben: o)
Kaj