A study on SSE optimisation regarding initialisation and evaluation of the Fast Multipole Method
Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
The following study examines whether the initialisation (multipole expansions at the finest level) and evaluation of the numerical method Fast Multipole Method (FMM) can benefit from implementing SSE instructions. The implementation of SSE-instructions have been studied and compared to the serial case. Moreover, studied parts of the algorithm include arithmetics on complex numbers, and the usage of applying SSE instructions to complex numbers of double precision.
In conclusion, the initialisation has not experienced any improvement in terms of throughput by appliying SSE instructions. However, the evaluation reached almost the double speed-up when SSE instructions were applied. The difference in results are most likely due to the structure of the both algorithms. The initialisation is simple, but the evaluation which involves more operations can benefit from SSE instructions.
Furthermore, a scheme is proposed for how SSE instructions can be applied to data sets which are not divisable by the unroll factor and to data sets of varying size.
Place, publisher, year, edition, pages
2016. , 16 p.
TVE, TVE 16 011 maj
SSE, SIMD, Fast Multipole Method, AVX, N-body problem
IdentifiersURN: urn:nbn:se:uu:diva-298122OAI: oai:DiVA.org:uu-298122DiVA: diva2:944705
Master Programme in Engineering Physics
Engblom, Stefan, Docent
Sjödin, Martin, ProfessorStrømme, Maria, Professor