Nested Data Parallelism for Image Processing Algorithms : Optimisations in Functional Programming Languages

URL
Dokumentart: Bachelor Thesis
Institut: Department Informatik
Sprache: Deutsch
Erstellungsjahr: 2015
Publikationsdatum:
SWD-Schlagwörter: HASKELL
DDC-Sachgruppe: Informatik

Kurzfassung auf Deutsch:

Nested Data Parallelism ermöglicht den prägnanten und treendenAusdruck irregulär-paralleler Programme und erreicht trotzdessen eine Performance vergleichbar zu Flat Data Parallelism. Dies wird durch eine Programmtransformation (’Vectorization’) erreicht. Verschachtelte Funktionen und Datenstrukturenwerden dabei auf ache Funktionen und Datenstrukturen reduziert. Diese Arbeit verlgeicht und bewertet die Eektivität von Nested Data Parallelism und manueller Parallelisierung. Es werden vier Implementierungen des Histogramausgleichs erstellt - eine Sequentielle, eine Manuell-parallelisierte, Eine die Nested-Data-Parallelism verwendet und die davon Vektorisierte. Diese werden bezüglich Arbeitsaufwand, Ähnlichkeit zum Algorithmus, Komplexitätklassen und mehr bewertet. Dies gechieht in Haskell als Example für funktionale Programmiersprachen. Die Arbeit zieht den Schluss, dass Nested Data Parallelism eektiv im allgemeinen Verlgeich ist. Jede Implementierung hat Stärken und Schwächen. Es gibt allerdings, keine beste Implementierung.

Kurzfassung auf Englisch:

Nested Data Parallelism enables the concise expression of irregularly parallel programs while still being nearly as performing as at data parallel programs. This is achived by a program transformation (’Vectorizaiton’) . It attens complex nesting of data structures and functions. This thesis is a comparison and evaluation of Nested Data Parallelism and manual parallelism of irregular image processing algorithms such as Histogram Balancing in functional programming languages by the example of Haskell. Four implementations for Histogram Balancing are created and evaluated on constant factors, running time complexity, human workload and more. They are: sequential, manually-parallelized, nested data parallel and nally a vectorized thereof. The thesis comes to the conclusion, that Nested Data Parallelism compares well to the other approaches. Though, every implementation has its advantages and drawbacks - none is the best.

Hinweis zum Urheberrecht

Für Dokumente, die in elektronischer Form über Datenenetze angeboten werden, gilt uneingeschränkt das Urheberrechtsgesetz (UrhG). Insbesondere gilt:

Einzelne Vervielfältigungen, z.B. Kopien und Ausdrucke, dürfen nur zum privaten und sonstigen eigenen Gebrauch angefertigt werden (Paragraph 53 Urheberrecht). Die Herstellung und Verbreitung von weiteren Reproduktionen ist nur mit ausdrücklicher Genehmigung des Urhebers gestattet.

Der Benutzer ist für die Einhaltung der Rechtsvorschriften selbst verantwortlich und kann bei Mißbrauch haftbar gemacht werden.