Details
| Autor: | Frank Schäfer |
| Titel: | Das hermitesche Eigenwertproblem - Implementierungsaspekte für Festkomma-SIMD-DSPs |
| Typ: | Dissertation |
| Fachgebiet: | Informationstechnik |
| Reihe: | Mobile Nachrichtenübertragung, Nr.: 38 |
| Auflage: | 1 |
| Sprache: | Deutsch |
| Erscheinungsdatum: | Oktober 2008 |
| Lieferstatus: | Lieferbar |
| Umfang: | 152 Seiten |
| Bindung: | Soft |
| Preis: | 49,00 EUR |
| ISBN: | 9783938860182 |
| Umschlag: | (vorn) |
| Inhaltsverzeichnis: | (pdf) |
Abstrakt in Englisch
New digital communications standards and multimedia applications demand for con- tinuously rising requirements of hardware architectures regarding speed of operation and power efficiency. Digital signal processors (DSPs) offer the advantage of the flexible adjustment to new applications due to their programmability over application specific integrated circuits (ASICs). At the Vodafone Chair Mobile Communications Systems the CATS method (Concept for Application Tailored Signalprocessors) was established to cope with these demands. The building set construction system ensures a scalable perfor- mance by a variable number of parallel data paths (SIMD) for CATS based DSPs. The data paths again can be adapted by special instructions to new applications. Data trans- fers between the data paths of the DSP are carried out along the ICU (Interconnection Unit) with limited number of transfer options.
The hermitian eigenvalue problem with its rich mathematical structure is considered as “one of the most aesthetically pleasing problems in numerical linear algebra”. This and the rising number of SIMD architectures are cause and justification to examine these topics in connection.
The one-sided Jacobi algorithm is among the regarded eigenvalue algorithms the most suitable for the implementation on a linear parallel CATS DSP architecture on the basis of the criteria performance, numeric stability and convergence speed. The memory allo- cation and the parallel order scheme influence the communication effort of the ICU and must be chosen in such a way that data flow does not delay the numeric computations.
A speed-up in comparison to a serial implementation of the one-sided Jacobi algorithm up to the factor P = n/2 is achievable while preserving a complete utilization of each of the P data paths (n × n . . . size of the hermitian matrix). When adding additional parallelism, e.g. P = n, a further acceleration is possible while the extent of utilization is decreasing at the same time. The numerical procedure for the computation of the rotation parameters contributes substantially to the necessary clock cycle number of the algorithm and the attainable numeric precision. A direct computation of the rotation parameters with the Newton algorithm is suitable particularly well. The employment of a fixed-point arithmetic with rounding increases the precision by nearly an order of magnitude with negligible additional expenses.
Data paths with floating point arithmetic reduce the effort for dynamic intermediate scalings of entire matrices and continue to increase the precision. The employment of the newly introduced Jacobi tracking leads to reduced expenditure in systems with a small rate of change.
Abstrakt in Deutsch
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öß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.