Vectorization of the adaptive Monte Carlo algorithm FOAM for contemporary SIMD computer architectures

Większość współczesnych CPU daje możliwość wykonywania instrukcji dla obliczeńwektorowych na wielokrotnych (zwektoryzowanych) zbiorach danych. Tego typuarchitektura komputerowa nazywana jest SIMD (ang. Single Instruction, MultipleData). Na przykład obecne CPU firmy Intel oferują operacje wektorowe na 8 lub 16danych pojedynczej precyzji. Nowe wersje kompilatorów, np. GCC, dają możliwośćwykorzystania takiej wektorowości w programach użytkowych. Celem pracy jestwektoryzacja adaptacyjnego algorytmu Monte Carlo o nazwie FOAM – służącego donumerycznego całkowania funkcji wielu zmiennych i generowania wielowymiarowychpunktów losowych – dla oferowanych aktualnie architektur SIMD oraz zbadanie jegowydajności. W niniejszej pracy przedstawiono krótką historię komputerów wektorowych,metody, możliwości oraz ograniczenia wektoryzacji, przykłady zastosowań w przypadkualgorytmów Monte Carlo oraz opis algorytmu Monte Carlo FOAM. Dokonano równieżoptymalizacji i wektoryzacji wspomnianego algorytmu oraz zbadano wydajność powprowadzonych zmianach, a także wyjaśniono, dlaczego algorytm ten nie jest dobrzewektoryzowalny przy pewnych ustawieniach.Most contemporary CPUs offer a possibility of executing instructions for vectorcomputation working on multiple (vectorized) data sets. This kind of architecture iscalled SIMD (Single Instruction, Multiple Data). For instance, current Intel CPUs offervector instructions taking data of 8 or 16 chunks. New versions of compilers, e.g. GCC,allow to utilize this possibility in user applications. The aim of this thesis isvectorization of the adaptive Monte Carlo algorithm FOAM (which serves as a tool innumerical integration of multivariate functions and multidimensional random numbergeneration) for the contemporary SIMD architectures as well as investigation of itsefficiency. In this work, first, a short history of vector computers is presented. Thenmethods, abilities and limitations of vectorization are discussed. A few examples ofvectorized Monte Carlo applications are given and the FOAM algorithm is described.Some optimization and vectorization of FOAM are made, and then these changes areinvestigated in terms of efficiency. It is also explained why this algorithm cannot beproperly vectorized in the case of some settings