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

Abstract

Nested Data Parallelism ermöglicht den prägnanten und tre endenAusdruck 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 E ektivitä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 e ektiv im allgemeinen Verlgeich ist. Jede Implementierung hat Stärken und Schwächen. Es gibt allerdings, keine beste Implementierung.

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.