Parallelisierung mit SIMD

In dieser Übung soll eine Einführung in die Nutzung von Vektoroperationen erfolgen. Vektoroperationen erfüllen das Single-Instruction Multiple-Data Stream Paradigma. Bei SIMD werden die gleiche (i.A. arithmetische, Boolesche, logische oder relationale) Operation auf verschiedene Daten gleichzeitig angewendet. Die Daten müssen homogen sein, daher die Anwendung auf Vektoren.

Die Lua Virtual Machine (lvm) bot bisher Parallelität auf Kontrollpfadebene. Schon bei der Parallelisierung wurde deutlich dass zusätzliche Kommunikation und Nachrichten die mögliche Beschleunigung teils deutlich reduzieren kann. D.h. man parallele Programm sinnvoll gestalten um einen Vorteil durch (physische) Parallelisierung zu bekommen. Bei der Datenpfadparalleliät wird diese Randbedingung nochmals verschärft. Es muss genauestens der zusätzliche Aufwand - wie z.B. das Kopieren von Daten von einem Puffer in einen anderen - bedacht und analysiert werden.

Die modernen (Dekstop und Server) Mikroprozessoren stellen Vektoroperationen zur Verfügung, die in (C) Programmen direkt über den Compiler genutzt werden können.

Je ach verfügbarer Prozessorerweiterung gibt es unterschiedlich breite Vektordatenformate, i.A. 128 und 256 Bit, mittlerweile auch 512 Bits. Die Datenwortbreite ist immer gleich. Es werden verschiedene Datentypen der Vektorelemente unterstützt, i.A. 16 und 32 Bit Integer, 32 und 64 Bit Fliesskomma (float und double Datentypen).

• Hat man z.B W=128 Bit, und der Datentyp ist 16 Bits Integer, dann können pro Vektoroperation 8 parallele Operationen wie z.B. Addition durchgeführt werden.
• Hat man z.B W=128 Bit, und der Datentyp ist 32 Bits Float, dann können pro Vektoroperation 4 parallele Operationen wie z.B. Addition durchgeführt werden.

Die Vektoroperationen arbeiten auf (speicherbasierten) Registern fester Breite. Beispiele in C sind:

#include <immintrin.h>
__v4sf x4; // 4 x Single Precisio Float
__v8sf x8; // 8 x Single Precision Float
c=__mm_add_ps(a,b)

Lua verarbeitet i.A. Daten mit doppelter Float Präzision (double), Arrays sind heterogen und können nicht direkt für Vektoroperationen genutzt werden. Es gibt aber das Array Module welches typisierte und gepackte Arrays unterstützt. Diese wird hier verwendet.

Ein typischer Lua Aufruf einer C Funktion:

#include "lua.h"
#include "lauxlib.h"

int foo(ua_State *L ) {
  int arg1 = luaL_checkint( L, 1 ),
      arg2 = luaL_checkint( L, 2 );
  lua_pushnumber( L, 1234 );
  return 1;
}

Die Ein- und Ausgabewerte werden über den Stack übergeben. Der Rückgabewert einer Lua-C Funktion gibt die Anzahl der Elemente auf dem Stack als Rückgabe an.

Man muss dann ein binäres Modul (Shared Object Library) name.so erzeugen und kann diese dann mittels require name laden. Unten ist ein Beispiel gezeigt.

Frage 1. Wann würden sich wohl Vektoroperationen für ein Lua Programm lohnen? Welche Eigenschaften müsste ein Algorithmus haben der mit Vektoroperationen beschleunigt werden soll?

Nachfolgend ist ein Beispielmodul in C gezeigt welches einfache Vektoroperationen in Lua zur Verfügung stellt. Es gibt Operationen die auf einzelnen Vektoren operieren und welche die auf Arrays in multiplen Vielfachen der Vektoren operieren (also eine Batchverarbeitung).

Aufgabe 2. Untersuche die parallelen Einzeloperationen (z.B. v4add) im Vergleich zur reinen Lua Berechnung und der sequenziellen C Implementierung (z.B. v4addS). Ist eine Beschleunigung erzielbar, wo liegt die "Reibung"?

128 Bit Vektoroperationen

Aufgabe 3. Jetzt untersuche die Array-basierte v4prodsum Funktion, wähle die Größe der Arrays (float) groß genug um einen Effekt zu sehen. Welche typische Beschleunigung (unter Berücksichtigung des Lua-C Overhwads) kann erzielt werden?

256 Bit Vektoroperationen

• Das Array Module wird i.A. eine 4 Byte Ausrichtung vornehmen. Bisher waren alle Datenadressen auf 16 byte ausgerichtet.
• Solange wir dem Array Modul nicht die Ausrichtung vorgeben können (wird noch ergänzt) müssen wir uns behelfen.
• Dazu werden wir das Array etwas größer machen und dann die Ausrichtung (Bytes) mittels der simd.align Funktion erfragen, die uns einen Offset (in 4 Byte Schritten gibt) definiert. Die Produktsummenberechnung erwartet jetzt diesen Offset und die tatsächliche Länge des Arrays (ohne Offset und Anhang).