![\"\"](\"https:\/\/i0.wp.com\/imalogic.com\/blog\/wp-content\/uploads\/2017\/05\/362679_3042860063.jpg?ssl=1\")
<\/a><\/p>\nThe perfect piece of code candidate for optimization was selected: a little function used to calculate the distance squared between two points.<\/p>\n
Like a good chocolate mousse, SSE2 was used to optimize and perform distance squared operation using \u201cbig register\u201d<\/p>\n
SSE2<\/b> (Streaming SIMD Extensions 2<\/b>), is one of the Intel SIMD<\/a> (Single Instruction, Multiple Data) processor supplementary instruction<\/a> sets first introduced by Intel<\/a> with the initial version of the Pentium 4<\/a> in 2001. It extends the earlier SSE<\/a> instruction set, and is intended to fully replace MMX<\/a>. Intel extended SSE2 to create SSE3<\/a> in 2004. SSE2 added 144 new instructions to SSE, which has 70 instructions. Competing chip-maker AMD<\/a> added support for SSE2 with the introduction of their Opteron<\/a> and Athlon 64<\/a> ranges of AMD64<\/a> 64-bit CPUs in 2003. Most of the SSE2 instructions implement the integer vector operations also found in MMX. They use the XMM registers instead of the MMX registers, which are wider and allow for significant performance improvements in specialized applications.<\/p>\n \u00a0<\/p>\n After several days of try\/error, finally i reach to gain some time ( around \u00a022% )\u00a0\u2013 So, yes assembler optimisation can be usefull but should be used for well selected part of code (innerloop). But assembler optimization still need expensive time to do.<\/p>\n \u00a0<\/p>\n A next try should be to use GPU capabilities to reduce time calculation. But need also to adapt the code to pass massive input\/output data using specific texture buffer.<\/p>\n Original C++ vs optimized SSE version<\/strong><\/p>\n RUNNING K-MEANS WITH UNIFORM SEEDING, looking for 25 clusters Original : Potential at 140 iterations: 1.50983e+008 at Time: 2.21731<\/strong><\/p>\n SSE optimized<\/strong> : Potential at 140 iterations: 1.50983e+008 at Time: 1.74357 + 21,3%<\/span><\/strong><\/p>\n RUNNING K-MEANS++, looking for 25 clusters Original :\u00a0Potential at 30 iterations: 1.64884e+007 at Time: 0.471352<\/strong><\/p>\n SSE optimized<\/strong> : Potential at 30 iterations: 1.64884e+007 at Time: 0.368786 + 21,7%<\/span><\/strong><\/p>\n RUNNING K-MEANS++ WITH RETRIES DURING SEEDING, looking for 25 clusters Original :\u00a0Potential at 45 iterations: 1.62709e+007 at Time: 0.705721<\/strong><\/p>\n SSE optimized<\/strong> : Potential at 45 iterations: 1.62709e+007 at Time: 0.552436 \u00a0+ 21,8%<\/span><\/strong><\/p>\n<\/body>","protected":false},"excerpt":{"rendered":" K-MEANS \/ Distance Squared optimisation using SSE instruction A long time ago, a friend ask me to try some KMEANS<\/p>\n","protected":false},"author":1,"featured_media":404,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[7],"tags":[],"class_list":["post-402","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-coding"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/imalogic.com\/blog\/wp-content\/uploads\/2017\/05\/616705-3-65HWPEI2.png?fit=354%2C262&ssl=1","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8J21V-6u","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/posts\/402","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/comments?post=402"}],"version-history":[{"count":1,"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/posts\/402\/revisions"}],"predecessor-version":[{"id":408,"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/posts\/402\/revisions\/408"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/media\/404"}],"wp:attachment":[{"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/media?parent=402"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/categories?post=402"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/imalogic.com\/blog\/wp-json\/wp\/v2\/tags?post=402"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}<\/a><\/p>\n\/**\r\n * Returns the distance squared between two points.\r\n **\/\r\nScalar distSq(const Point &lhs, const Point &rhs) {\r\n ASSERT(lhs.getNumDimensions() == rhs.getNumDimensions());\r\n Scalar result = 0;\r\n for (int i = 0; i < lhs.getNumDimensions(); i++)\r\n result += (lhs[i] - rhs[i]) * (lhs[i] - rhs[i]);\r\n return result;\r\n}\t<\/span><\/code><\/pre>\ndouble distSq(double* a,double* b)\r\n{\r\n unsigned int i=0;\r\n unsigned int size = data->nCol; \r\n double fres = 0.0;\r\n\r\n__declspec(align(16)) double ftmp[2] = { 0.0, 0.0 };\r\n __m128d mres, mres1,mres2;\r\n __m128d m1,m2; \r\n\r\n\r\n mres = _mm_xor_pd(mres,mres); \r\n\r\n\r\n for (unsigned int i = 0; i < size \/ 16 ; i+=1) \u00a0{\r\n\u00a0 \u00a0mres1 = _mm_sub_pd(_mm_loadu_pd(&a[16*i]),_mm_loadu_pd(&b[16*i])); \r\n\u00a0 \u00a0m1 = _mm_mul_pd(mres1,mres1); \r\n\u00a0 \u00a0mres2 = _mm_sub_pd(_mm_loadu_pd(&a[16*i+2]),_mm_loadu_pd(&b[16*i+2])); \r\n\u00a0 \u00a0mres = _mm_add_pd(mres,m1);\/\/ \r\n\u00a0 \u00a0m2 = _mm_mul_pd(mres2,mres2); \r\n\u00a0 \u00a0mres1 = _mm_sub_pd(_mm_loadu_pd(&a[16*i+4]),_mm_loadu_pd(&b[16*i+4])); \r\n\u00a0 \u00a0mres = _mm_add_pd(mres,m2);\/\/ \r\n\u00a0 \u00a0m1 = _mm_mul_pd(mres1,mres1); \r\n\u00a0 \u00a0mres2 = _mm_sub_pd(_mm_loadu_pd(&a[16*i+6]),_mm_loadu_pd(&b[16*i+6])); \r\n\u00a0 \u00a0mres = _mm_add_pd(mres,m1);\/\/ \r\n\u00a0 \u00a0m2 = _mm_mul_pd(mres2,mres2); \r\n\u00a0 \u00a0mres1 = _mm_sub_pd(_mm_loadu_pd(&a[16*i+8]),_mm_loadu_pd(&b[16*i+8])); \r\n\u00a0 \u00a0mres = _mm_add_pd(mres,m2);\/\/ \r\n\u00a0 \u00a0m1 = _mm_mul_pd(mres1,mres1); \r\n\u00a0 \u00a0mres2 = _mm_sub_pd(_mm_loadu_pd(&a[16*i+10]),_mm_loadu_pd(&b[16*i+10])); \r\n\u00a0 \u00a0mres = _mm_add_pd(mres,m1);\/\/ \r\n\u00a0 \u00a0m2 = _mm_mul_pd(mres2,mres2); \r\n\u00a0 \u00a0mres1 = _mm_sub_pd(_mm_loadu_pd(&a[16*i+12]),_mm_loadu_pd(&b[16*i+12])); \r\n\u00a0 \u00a0mres = _mm_add_pd(mres,m2);\/\/ \r\n\u00a0 \u00a0m1 = _mm_mul_pd(mres1,mres1); \r\n\u00a0 \u00a0mres2 = _mm_sub_pd(_mm_loadu_pd(&a[16*i+14]),_mm_loadu_pd(&b[16*i+14])); \r\n\u00a0 \u00a0mres = _mm_add_pd(mres,m1);\/\/ \r\n\u00a0 \u00a0m2 = _mm_mul_pd(mres2,mres2); \r\n\u00a0 \u00a0mres = _mm_add_pd(mres,m2);\/\/ \r\n }\r\n _mm_store_pd(ftmp, mres); \r\nfres = ftmp[0] + ftmp[1]; \r\n\r\n if ((size % 16) != 0) {\r\n\u00a0 \u00a0for (unsigned int i = size - (size % 16); i < size; i++) fres += (a[i]-b[i]) * (a[i]-b[i]);\r\n }\r\n return fres;\r\n}<\/pre>\nTest Result<\/h1>\n
\n=============================================================<\/p>\n
\n==========================================<\/p>\n
\n======================================================================<\/p>\n