uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
A study on SSE optimisation regarding initialisation and evaluation of the Fast Multipole Method
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Scientific Computing.
2016 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

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
Keyword [en]
SSE, SIMD, Fast Multipole Method, AVX, N-body problem
National Category
Computer Science
URN: urn:nbn:se:uu:diva-298122OAI: oai:DiVA.org:uu-298122DiVA: diva2:944705
Educational program
Master Programme in Engineering Physics
Available from: 2016-06-30 Created: 2016-06-29 Last updated: 2016-06-30Bibliographically approved

Open Access in DiVA

fulltext(623 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 623 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Division of Scientific Computing
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 13 hits
ReferencesLink to record
Permanent link

Direct link