Das hermitesche Eigenwertproblem - Implementierungsaspekte für Festkomma-SIMD-DSPs

Neuartige digitale Kommunikationsstandards und Multimediaanwendungen weisen kontinuierlich steigende Anforderungen an Hardwarearchitekturen bezüglich Verarbeitungsgeschwindigkeit und Leistungseffizienz auf. Digitale Signalprozessoren (DSPs) bieten gegen über applikationsspezifischen integrierten Schaltkreisen (ASICs) wegen ihrer flexiblen Programmierbarkeit den Vorteil der Anpassungsfähigkeit an neue Applikationen.

Am Vodafone Stiftunglehrstuhl Mobile Nachrichtensysteme wurde die CATS-Methode (Concept for Application Tailored Signalprocessors) entwickelt, um diesen Anforderungen gerecht zu werden. Das Baukastenprinzip gewährleistet eine skalierbare Leistungsfähigkeit durch den Einsatz einer beliebigen Anzahl paralleler Datenpfade (SIMD) für CATS-basierte DSPs. Die Datenpfade wiederum lassen sich durch Spezialinstruktionen auf neue Algorithmen zuschneiden. Datentransferoperationen zwischen den einzelnen Datenpfaden werden mit Hilfe der ICU (Interconnection Unit) mit einer begrenzten Anzahl von Transfermöglichkeiten ausgeführt.

Das hermitesche Eigenwertproblem mit seinen vielfältigen mathematischen Strukturen wird als “eines der ästhetisch ansprechendsten Aufgaben der numerischen linearen Algebra” angesehen. Diese Tatsache und die stetig steigende Anzahl an verfügbaren SIMDArchitekturen rechtfertigen diese beiden Themen im Zusammenhang zu betrachten.
Der einseitige Jacobi-Algorithmus ist von den betrachteten Eigenwertalgorithmen der geeignetste für die Implementierung auf einer linearen parallelen CATS-DSP-Architektur unter den Gesichtspunkten numerische Stabilität und Konvergenzgeschwindigkeit. Die Anordnung der Matrixelemente im Speicher und das parallele Ordnungsschema haben beträchtlichen Einfluß auf den Kommunikationsaufwand in der ICU und müssen so gew ählt werden, dass der Datenfluß nicht zu Verzögerungen der numerischen Operationen in den Datenpfaden führt.

Eine Beschleunigung im Vergleich zu einer linearen Implementierung des einseitigen Jacobi-Algorithmus bis zum Faktor P = n/2 ist unter Beibehaltung einer vollständigen Auslastung der P Datenpfade erzielbar (n×n. Gr¨oße der hermiteschen Matrix). Durch Hinzufügen weiterer Datenpfade, z.B. P = n, ist eine weitere Beschleunigung bei gleichermaßen abnehmender Auslastung erzielbar. Das gewählte numerische Verfahren zur Berechnung der Rotationsparameter trägt entscheidend zur Anzahl erforderlicher Taktzyklen und zur erzielbaren numerischen Präzision bei. Als besonders günstig hat sich die direkte Berechnung der Parameter nach dem Newton-Verfahren erwiesen. Die Verwendung von Rundungsarithmetik erhöht die Genauigkeit um etwa eine Größenordnung bei vernachlässigbarem Mehraufwand. Datenpfade mit Fließkommaarithmetik reduzieren den Aufwand für die dynamische Skalierung von Matrizen und erhöhen die Rechengenauigkeit weiter. Die Anwendung des neu eingeführten Jacobi-Trackings minimiert die Algorithmenkomplexität in Systemen mit geringer Änderungsrate abermals.