Parallelisierung der Generierung von redundanzreduzierten FIR-Filterstrukturen

Student:Matthias Hampel
Title:Parallelisierung der Generierung von redundanzreduzierten FIR-Filterstrukturen
Type:diploma thesis
Advisors:Klemm, M.; Kókai, G.; Zvada, S.
State:submitted on October 4, 2006
Prerequisits:
Topic:

Voraussetzungen

FIR-Filter (Finite Impulse Response Filter) werden in der digitalen Signalverarbeitung eingesetzt und bilden zusammen mit den IIR-Filtern (Infinite Impulse Response Filter) die digitalen Filtersysteme. FIR-Filter gehören in die Klasse der diskreten nicht-rekursiven Systeme und werden wie jedes lineare diskrete System durch ihre Übertragungsfunktion vollständig charakterisiert.

Das Ziel ist in dem redFIR-System, aus gegebenen Koeffizienten eine FIR-Struktur in VHDL zu generieren, deren IC-Ressourcenbedarf sehr gering ist. Die Optimierung in diesem System basiert dann an den Filterkoeffizienten eingesetzt, um den Frequenzgang eines Eingangssignalspektrums mittels der Übertragungsfunktion zu manipulieren. Dazu wurde eine neue erweiterte Optimierungsstrategie entwickelt, die größere Filter-Strukturen verwalten kann und gleichzeitig bessere Eigenschaften in ihrer Komplexität (Laufzeit, Speicherbedarf etc.) bei besseren Optimierungsergebnissen besitzt. Dabei wurden genetische Algorithmen eingesetzt.

Ausgabenstellung

Im Rahmen der Diplomarbeit soll die existierende Implementierung des Verfahren als Aussgangspunkt für eine Parallelisierung herangezogen werden.

Für eine Parallelisierung müssen zunächst die bisher existierenden parallelen Verfahren analysiert werden, inwieweit sie sich für eine Nutzung im redFIR-System eignen. Es ist zu überlegen, welche Ansätze sich für die Parallelisierung für ein paralleles System mit gemeinsamen Speicher (SMP-System) als auch für ein System mit verteiltem Speicher (Rechnerbündel) eignen. Die Analysen sollen sich dabei auf eine fundierte Literaturrecherche stützen und die Eignung anhand dieser belegen.

Das jeweils geeignetste Verfahren für SMP-Systeme und für Rechnerbündel soll im Anschluß im redFIR-System implementiert werden. Für die Parallelisierung für ein SMP-System ist der vorliegende C++-Quellcode des Systems dahingehend zu erweitern, dass unter Ausnutzung einer Bibliothek für Aktivitätstränge (bspw. POSIX threads) ein Maximum an Leistung erreicht werden kann. Ähnliches ist auch für die Cluster-Parallelisierung zu implementieren. Hierbei soll MPI als Kommunikationsbibliothek Anwendung finden; das Programm soll ebenfalls so optimiert werden, dass eine maximale Leistungsfähigkeit zu erwarten ist.

Zum Beurteilung der Leistungsfähigkeit sind zum Abschluss der Arbeit aussagekräftige Leistungsmessungen durchzuführen. Die Ergebnisse dieser Messungen sollen im Rahmen der Ausarbeitung analysiert und bewertet werden.

Meilensteine

  • Einarbeitung in den existierenden Code
  • SMP-Parallelisierung mittels OpenMP
  • SMP-Parallelisierung mittels Threads
  • MPI-Parallelisierung
  • Messungen und Beurteilung der Ergebnisse
  • Optimierungen
  • Ausarbeitung

Literatur

  • Vanyi, R. Zvada, Sz., Frühauf H. H., Kokai, G.: Generating Resource-Optimal FIR Structures with Derivation Tree Based Genetic Programming submitted in the journal Annals of Operations Research Special Issue on STOCHASTIC SEARCH ALGORITHMS
  • Stephan Otto: Entwicklung und Vergleich genetischer Algorithmen zur Generierung redundanzreduzierter FIR-Filter für digitale Schaltkreise, Diplomarbeit 2002
  • Peter S. Pacheco: Parallel programming with MPI, Morgan Kaufmann, San Francisco, CA, USA, 2003
  • Bradford Nichols, Dick Buttlar and Jacqueline Proulx Farrell: Pthreads programming, O'Reilly, Bonn, 1996
watermark seal