Startseite > Halbleiter > DSP-Algorithmen effizient implementieren – Teil 1 #####

DSP-Algorithmen effizient implementieren – Teil 1 #####

24. März 2009, 11:58 Uhr | Fabian Plepp

▶ Diesen Artikel anhören

Fortsetzung des Artikels von Teil 2

Phase 1: Die mathematische Modellierung des Problems

In Phase 3 erfolgt eine mathematische Anpassung des Algorithmus an die Hardware-Architektur. Dies ist besonders bei Festkomma-Prozessoren wie dem Blackfin notwendig. Weiterhin sollte eine Anpassung an die verfügbaren Prozessorbefehle erfolgen.

In Phase 4 wird zunächst die Software auf Systemebene geplant. Typische Fragestellungen in dieser Phase sind:

In welchem Speicher liegen welche Daten bzw. Funktionen?
Soll Cache verwendet werden?
Welche Mechanismen bezüglich der Optimierung sollen bereitgestellt werden (z.B. DMA-Transfers)?
Wie sollen der Core- und der Systemtakt eingestellt werden?
Sollen Interrupts oder soll Polling verwendet werden?
Bei Multicore-/Multiprozessoranwendungen: Wie sollen die Algorithmen bzw. der Algorithmus auf die einzelnen Prozessorkerne verteilt werden?

Die Hochsprachenimplementierung (Phase 5) sollte die Architektur des Prozessors berücksichtigen. Dabei wird das gesamte Programm zunächst in einer Hochsprache implementiert, um die Funktionalität zu gewährleisten.

Die letzte Stufe der Optimierung (Phase 6) ist die Ersetzung von zeitkritischen Hochsprachen-Funktionen durch handoptimierte Assembler-Funktionen.

Bevor näher auf die einzelnen Phasen der Optimierung eingegangen wird, werden im Folgenden ihre Zielkonflikte mit anderen Anforderungen an Embedded-Anwendungen vorgestellt. Der erste Zielkonflikt befindet sich auf der betriebwirtschaftlichen Ebene: Der Optimierungsprozess verlangt eine ausgiebige Planungs- und Implementierungsphase und erhöht somit die Entwicklungskosten. So sollte eine Optimierung nur dann durchgeführt werden, wenn hohe Stückzahlen die Opportunitätskosten (Kosten, die entstehen, wenn man eine alternative Möglichkeit nicht ausschöpft), nicht auf den nächst besseren Prozessor umzusteigen, rechtfertigen. Neben den betriebswirtschaftlichen Erwägungen stellen die Anforderungen des Software-Engineering-Paradigmas die zweite große Gruppe der Zielkonflikte: Durch die starke Orientierung an der Architektur ist die Portabilität des Programm-Codes stark eingeschränkt.

Das gleiche gilt zumeist für die Forderung nach Modularität, welche durch Parallelisierung der einzelnen Prozesse auf Assembler- und Systemebene nur noch schwer eingehalten werden kann. Des Weiteren leidet zumeist die Lesbarkeit des Codes unter dem Optimierungsprozess. Die restlichen Zielkonflikte sind technischer Natur: Meistens vergrößert sich der Code erheblich, so dass ein höherer Speicherbedarf besteht. Die Optimierung auf Systemebene kann mit einem höheren Energiebedarf einhergehen, welcher gerade in dem Bereich der portablen Systeme (Mobiltelefonie, Video-/ MP3-Spieler, PDAs) als besonders kritisch zu bewerten ist.

Die Phasen 1, 2 und 3 lassen sich nicht voneinander klar abgrenzen und haben jeweils starke Wechselwirkungen.

In dieser Phase wird die Außenwelt mathematisch modelliert, um Hinweise für eine mögliche Einschränkung der Eingabe- sowie Ausgabevektoren des Prozessors zu erhalten. Ein klassisches Beispiel ist die Modellierung eines Regelungssystems, bei dem durch die Einschränkung der Eingabevektoren die eigentlich nichtlineare Regelung linearisiert werden kann. Aber auch gerade Quantisierungsstufen und Abtastraten haben einen großen Einfluss auf die Leistung eines Systems und sollten hier möglichst kritisch bezüglich der Erfordernisse betrachtet werden. Welche Ansätze man dabei verfolgt, hängt von der jeweiligen Aufgabe ab. Zumeist werden hier mathematische Modellierungs-Tools wie Matlab/Simulink zu Hilfe genommen.

In dieser Phase wird der Algorithmus entwickelt oder ausgewählt und mathematisch optimiert. Dazu wird betrachtet, ob Symmetrien vorhanden oder Vereinfachungen möglich sind, die den Rechenaufwand reduzieren. Die numerische Mathematik stellt für viele Aufgaben schon Lösungen bereit, so dass für viele Teilaufgaben eines komplexen Algorithmus „nur“ noch eine Entscheidung bezüglich des besten Verfahrens getroffen werden muss. Hier überschneiden sich die Phasen 2 und 3, da die Rechenarchitektur zumeist einen sehr starken Einfluss auf das spätere Ergebnis hat und somit auf jeden Fall in die Überlegung mit einbezogen werden sollte. Ein einfaches Beispiel wäre die Anzahl der Divisionen in einem Algorithmus.