DSP-Algorithmen effizient implementieren – Teil 2

Der zweite Teil dieses Artikels führt die in Teil 1 begonnene Beschreibung der DSP-Optimierungstechniken auf Assemblerbasis fort und geht auf die Optimierung auf Hochsprachenebene ein. Dabei erläutert er abschließend auch die Möglichkeiten moderner Compiler und integrierter Entwicklungsumgebungen.

Der zweite Teil dieses Artikels führt die in Teil 1 begonnene Beschreibung der DSP-Optimierungstechniken auf Assemblerbasis fort und geht auf die Optimierung auf Hochsprachenebene ein. Dabei erläutert er abschließend auch die Möglichkeiten moderner Compiler und integrierter Entwicklungsumgebungen.

Viele algorithmische Ansätze in der Signalverarbeitung und Regelungstechnik ermöglichen eine Parallelisierung ihrer Berechnungen. Dazu zerlegt man den Algorithmus in Einzelschritte und stellt ein Diagramm auf, in dem sich der Algorithmus in Algorithmenzweige aufteilt, die parallelisiert und im späteren Verlauf wieder zusammengefügt werden können. Für die Implementierung der Parallelisierungsansätze einzelner Rechenoperationen enthalten moderne DSPs SIMD- (Single-Instruction-Multiple-Data) und MIMD-Befehle (Multiple-Instruction-Multiple-Data), welche die Parallelisierung von Berechnungen innerhalb eines Cores mit Hilfe mehrerer paralleler Recheneinheiten ermöglichen. Bei einem SIMD-Befehl werden pro Befehl gleichzeitig mehrere Daten geladen und in den Recheneinheiten in einem Takt verarbeitet. MIMD ist das parallele Abarbeiten mehrerer verschiedener unabhängiger Befehle für mehrere unabhängige Datenströme.

Ein Verfahren zur Auslastung der Einheiten des Prozessors ist das Software-Pipelining. Da alle modernen digitalen Signalprozessoren über eine Load-Store-Architektur verfügen, müssen die Daten erst in die Register geladen werden, um sie zu verarbeiten. Nach der Berechnung erfolgt das Zurückschreiben in den Speicher. Eine typische Software-Pipeline ist in Bild 9 dargestellt.

Listing 1. Bei einem FIR-Filter werden Daten in einen Puffer übernommen und dafür die ältesten Werte verworfen.

x(N-1) = Input();
Output = 0;
for(i=0;i<N;i++)
{
		Output += a(i)*x(i);
};

/* Verschieben des Puffers */
for(i=0;i<N-1;i++)
{
		x(i) = x(i+1);
};

 

Listing 2. Eine Iteration, die durch Abhängigkeiten zu Pipeline-Stalls führen kann.

for (int x = 0; x < 100; x++)
{
	a[x] = b[x]*x[x];
};

 

Listing 3. Bei der Schleifenabwicklung wird der ursprüngliche Schleifenkörper mehrmals in der Schleife verarbeitet, d.h., man führt mehrere Schleifenzyklen zu einer Schleife zusammen. Abhängigkeiten werden damit verhindert.

for (int x = 0; x < 100; x += 4 )
{
	a[x] = b[x]*x[x];
	a[x+1] = b[x+1]*x[x+1];
	a[x+2] = b[x+2]*x[x+2];
	a[x+3] = b[x+3]*x[x+3];
}
a[x] = a[x]+a[x+1]+a[x+2]+a[x+3];

Listing 4. Eine unoptimierte bedingte Zuweisung

if (variable)
	a=b;
else
	a=c;

 

Listing 5. Optimierter Zugriff auf ein C-Array

for (i=0;i<3; i++)
	{
	for (j=0;j<3; j++)
		{
		for (k=0;k<3; k++)
		{
		MyArray[i][j][k] = getValue();
		}
	}
};

 

Listing 6. Divisionen sollten bei einer DSP-Architektur möglichst vermieden werden.

/* unoptimierte Anweisung */
if ( X/Y > A/B )
	{ /* tue etwas */ };

 

Listing 7. Bei Divisionen durch Konstanten sollte die Division durch eine Multiplikation mit dem Kehrwert der Konstante ersetzt werden.

/* optimierte Anweisung */
if ( X*B > A*Y )
	{ /* tue etwas */ };

 

Die Stufe, in der noch nicht alle Slots (Fachterminus für die möglichen Funktionen, die der Prozessor in einem Zyklus ausführen kann) gefüllt sind, wird Prolog genannt (Bild 10). Wenn alle Slots belegt sind, spricht man vom Kernel, der sich bei Berechungen von größeren Arrays zumeist in der Schleife befindet. Die Phase, in der wieder Slots freigeben werden, nennt man Epilog.

Eine weitere Möglichkeit, zu parallelisieren, ist die Verwendung von Multi-Core-Prozessoren oder Prozessor-Clustern. Mittels „Divide- and Conquer“-Verfahren kann man den Algorithmus auf die einzelnen Cores aufteilen. Die Kommunikation zwischen den Cores erfolgt mittels Link-Ports, Rapid-I/Os und/oder Speicher-Mapping (es werden bestimmte Speicherbereiche zur Kommunikation genutzt, auf die alle Cores bzw. Prozessoren zugreifen können).

Einige MultiCore-Derivate wie der Blackfin-Prozessor BF561 bieten Hardware-Semaphore für den Zugriff auf den gemeinsam genutzten Speicher an.