GPU Accelerated Parameter Estimation by Global Optimization using Interval Analysis

Rasmussen, Søren ; Eriksen, Mads Berre

4. term

Signal Processing and Computing, Master

2013

2013-06-06

102 pages

Dette kandidatspeciale omhandler emnet non-linear parameterestimering ved brug af metoder til global optimering baseret på intervalanalyse (IA), accellereret vha. parallel implementation på en grafikprocessor (GPU). Global optimering med IA er en matematisk garanteret metode af Branch & Bound typen, i stand til på pålidelig vis at løse globale optimeringsproblemer med kontinuært differentiabele objektivfunktioner, selv når afrundingsfejl finder sted. Strukturen af disse problemer og metoder er parallel i sin natur, og passer godt til moderne GPU-arkitektur. Metoder til effektivt at udnytte denne parallelisme præsenteres og baseret på disse implementeres en parallel GPU-accelereret algoritme til global optimering. En samling af algoritmiske variationer af den parallelle GPU-accelererede algoritme benchmarkes og sammenlignes med tilsvarende sekventielle CPU-baserede implementationer. Resultaterne viser hastighedsforøgelser imellem 1,43 og 60,4 gange for de anvendte testproblemer og problemstørrelser. En analyse viser at de GPU-accelerede implementationer ikke anvender GPU-hardwaren til fulde. Det vurderes der ved at introducere et yderligere lag af parallelisme kan opnås højere anvendelsesgrad og hastighedsforøgelse. Det konkluderes at den presenterede metode giver potentiale for signifikante hastighedsforøgelser for problemer med højt antal målinger.

This master thesis treats the topic of non-linear parameter estimation using global optimization methods based on interval analysis (IA), accelerated by parallel implementation on a Graphics Processing Unit (GPU). Global optimization using IA is a mathematically rigorous Branch & Bound-type method, capable of reliably solving global optimization problems with continuously differentiable objective functions, even in the presence of rounding errors. The structure of the problems and methods considered is parallel by nature and fit the parallel architecture of modern GPUs well. Methods for efficiently exploiting this parallelism are presented, based on which a parallel GPU accelerated global optimization algorithm is implemented. A set of algorithmic variations of the parallel GPU accelerated algorithm are benchmarked and compared to corresponding sequential CPU based implementations. Results show speedups ranging from 1.43 to 60.4 times for the test problems and problem sizes used. Analysis shows that the GPU accelerated implementations do not utilize the GPU hardware fully. It is assessed that further utilization and speedup can be obtained by introducing an additional level parallelism. It is concluded that for problems with large numbers of measurements, use of the method presented has the potential of yielding significant speedups.

Global Optimering ; Interval ; GPU ; Interval analyse ; parameter estimering

Download
Download
View record in AAU Student Projects