GPU Accelerated Parameter Estimation by Global Optimization using Interval Analysis
Translated title
GPU Accelereret Parameterestimering ved brug af Global Optimering med Intervalanalyse
Authors
Rasmussen, Søren ; Eriksen, Mads Berre
Term
4. term
Education
Publication year
2013
Submitted on
2013-06-05
Pages
102
Abstract
Mange ingeniør- og forskningsopgaver kræver, at man estimerer parametre i ikke-lineære modeller. Denne afhandling undersøger, hvordan global optimering baseret på intervalanalyse (IA) kan bruges til dette, og hvordan metoden kan accelereres ved at udnytte parallel behandling på en grafikprocessor (GPU). IA-baseret global optimering er en matematisk stringent Branch & Bound-lignende metode, som kan finde en global løsning for glatte målfunktioner og samtidig håndtere afrundingsfejl ved at arbejde med sikre intervalgrænser. Problemet og metoden kan opdeles i mange uafhængige delopgaver, hvilket passer godt til GPU’ers parallelle arkitektur. Afhandlingen beskriver teknikker til effektivt at udnytte denne parallelisme og implementerer en GPU-accelereret global optimeringsalgoritme. Flere variationer af algoritmen bliver benchmarked og sammenlignet med tilsvarende sekventielle CPU-implementeringer. På de testede problemer og problemstørrelser opnås hastighedsforøgelser fra 1,43 til 60,4 gange. Analysen viser, at GPU’en ikke udnyttes fuldt ud, og at et ekstra niveau af parallelisme kan øge udnyttelsen og hastigheden yderligere. Konklusionen er, at for problemer med mange målinger har den præsenterede metode potentiale til betydelige hastighedsgevinster.
Many engineering and scientific tasks require estimating parameters in non-linear models. This thesis investigates how global optimization based on interval analysis (IA) can be used for this purpose and how it can be accelerated by exploiting parallel processing on a Graphics Processing Unit (GPU). IA-based global optimization is a mathematically rigorous Branch & Bound–type method that can find a global solution for smooth objective functions while handling numerical rounding errors by working with guaranteed interval bounds. The problems and methods decompose into many independent subproblems, which fit the parallel architecture of modern GPUs. The thesis presents techniques to exploit this parallelism efficiently and implements a GPU-accelerated global optimization algorithm. Several algorithmic variants are benchmarked and compared with corresponding sequential CPU implementations. On the tested problems and sizes, speedups from 1.43 to 60.4 times are achieved. The analysis shows that the GPU hardware is not fully utilized, and that adding another level of parallelism could improve utilization and speed further. The conclusion is that, for problems with large numbers of measurements, the presented method has the potential to deliver significant speedups.
[This abstract was generated with the help of AI]
Keywords