Implementacja metody roju cząstek w OpenCL

Abstract

Presented thesis describes Particle Swarm Optimization algorithm, a type of a heuristic algorithm used for many optimization problems. The objective of this paper was to implement PSO utilizing computing power of graphics processing units (GPU) emphasizing research of the impact of selected configuration parameters. Cross-platform availability was the main reason why OpenCL was chosen as the framework in which the algorithm was implemented. Main bottlenecks of GPU parallel implementation were high global memory access time and high execution time of random number generator functions. The former was eliminated by removal of the critical section from the algorithm, while the latter by implementing own RNG algorithm, that executed directly on the kernel. W pracy przedstawiono metodę roju cząstek (PSO), algorytmu typu heurystycznego wykorzystywanego do wielu problemów optymalizacyjnych. Celem pracy była implementacja algorytmu PSO wykorzystująca moc obliczeniową kart graficznych (GPU) z uwzględnieniem badania wpływu różnych wartości parametrów konfiguracyjnych. Do implementacji użyto frameworku OpenCL ze względu na jego wieloplatformowość. Główne problemy implementacyjne: wolne czasy dostępu do pamięci globalnej oraz narzut spowodowany generacją liczb losowych rozwiązano przez usunięcie sekcji krytycznej algorytmu oraz wykorzystanie własnej implementacji generatora liczb losowych używanej na karcie graficznej.