This thesis introduces a SIMD approach to the convex hull algorithm Jarvis March, also known as the Gift Wrapping algorithm. A vectorized version of the algorithm is presented, and the study compares its performance against scalar versions to assess its effectiveness. Experimental results show a speedup factor of approximately 3.5 in the vectorized portion of the algorithm using AVX-512 instructions, contributing to an overall speedup factor of 1.18 compared to its scalar execution. However, contrary to expectations, the experimental results demonstrated that the vectorized implementation exhibited slower performance compared to the commonly implemented scalar version, achieving only half the speed. A roofline model analysis was employed to identify potential bottlenecks, pinpointing memory bandwidth as the primary constraint in the vectorized implementation. Consequently, the vectorized version of the Jarvis March algorithm presented is not recommended unless sufficient memory bandwidth or further improvements to the algorithm can be attained.

Denna avhandling introducerar en SIMD-ansats till den konvexa höljalgoritmen Jarvis March. En vektoriserad version av algoritmen presenteras, och studien jämför algoritmens prestanda mot skalära versioner för att bedöma dess effektivitet. Resultaten visar en hastighetsökning med en faktor 3,5 i den vektoriserbara delen av algoritmen vid anvädning av AVX-512-instruktioner, vilket bidrog till en total hastighetsökning med en faktor 1,18 jämfört med den skalära exekveringen. Emellertid, i strid med förväntningarna, visar de experimentella resultaten att den vektoriserade implementationen uppvisade långsammare prestanda jämfört med den vanligtvis implementerade skalära versionen och uppnådde endast hälften av hastigheten. Roofline-modellen användes för att identifiera potentiella flaskhalsar och pekar ut minnesbandbredden som den primära begränsningen i den vektoriserade implementationen. Följaktligen rekommenderas inte vektorisering av Jarvis March-algoritmen om inte tillräcklig minnesbandbredd eller vidare förbättringar av algoritmen kan erhållas.