इस लूप को पूरी तरह से अनलॉक करने के लिए जीसीसी से कैसे पूछें (यानी, इस लूप को छीलें)?

Question

क्या नीचे दिए गए फ़ंक्शन पूरी तरह से में लूप को अनलोल करने के लिए जीसीसी (संस्करण I का उपयोग 4.8.4) को निर्देशित करने का कोई तरीका है, यानी, इस लूप को छीलें? लूप के पुनरावृत्तियों की संख्या संकलन समय पर ज्ञात है: 58.

मुझे सबसे पहले बताएं कि मैंने क्या प्रयास किया है।

गैस ouput की जाँच करके:

gcc -fpic -O2 -S GEPDOT.c 

12 रजिस्टरों XMM0 - XMM11 किया जाता है। अगर मैं झंडा -funroll-छोरों जीसीसी के पास:

gcc -fpic -O2 -funroll-loops -S GEPDOT.c 

पाश केवल दो बार unrolled है। मैंने जीसीसी अनुकूलन विकल्पों की जांच की। जीसीसी का कहना है कि -Funroll-loops-frename-registers चालू हो जाएगा, इसलिए जब जीसीसी एक लूप को अनलॉक करता है, तो पंजीकरण आवंटन के लिए इसकी पूर्व पसंद रजिस्टरों का "बाएं ओवर" का उपयोग करना है। लेकिन XMM12 - XMM15 पर केवल 4 शेष हैं, इसलिए जीसीसी केवल सर्वोत्तम रूप से 2 बार अनलॉक कर सकता है। 16 एक्सएमएम रजिस्टरों के बदले 48 रहे थे, जीसीसी बिना किसी परेशानी के 4 गुना लूप को अनलॉक कर देगा।

फिर भी मैंने एक और प्रयोग किया। मैंने पहली बार लूप को दो बार मैन्युअल रूप से अनलॉक किया, एक समारोह GEPDOT_2 प्राप्त किया। तो फिर वहाँ है कोई फर्क नहीं बिल्कुल के बीच

gcc -fpic -O2 -S GEPDOT_2.c 

और

gcc -fpic -O2 -funroll-loops -S GEPDOT_2.c 

GEPDOT_2 के बाद से पहले से ही सभी रजिस्टरों का इस्तेमाल किया, कोई unrolling किया जाता है।

जीसीसी संभावित से बचने के लिए नामांकन रजिस्टर करता है झूठी निर्भरता पेश की गई। लेकिन मुझे यकीन है कि मेरे जीईपीडीओटी में ऐसी कोई संभावना नहीं होगी; यहां तक ​​कि यदि भी है, तो यह महत्वपूर्ण नहीं है। मैंने खुद को लूप को अनलॉक करने का प्रयास किया, और अनोलरिंग की तुलना में 4 गुना अनलोल करने से तेज 4 गुना तेज है। बेशक मैं मैन्युअल रूप से अधिक बार अनलॉक कर सकता हूं, लेकिन यह थकाऊ है। क्या जीसीसी मेरे लिए ऐसा कर सकता है? धन्यवाद।

// C file "GEPDOT.c" 
#include <emmintrin.h> 

void GEPDOT (double *A, double *B, double *C) { 
    __m128d A1_vec = _mm_load_pd(A); A += 2; 
    __m128d B_vec = _mm_load1_pd(B); B++; 
    __m128d C1_vec = A1_vec * B_vec; 
    __m128d A2_vec = _mm_load_pd(A); A += 2; 
    __m128d C2_vec = A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); B++; 
    __m128d C3_vec = A1_vec * B_vec; 
    __m128d C4_vec = A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); B++; 
    __m128d C5_vec = A1_vec * B_vec; 
    __m128d C6_vec = A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); B++; 
    __m128d C7_vec = A1_vec * B_vec; 
    A1_vec = _mm_load_pd(A); A += 2; 
    __m128d C8_vec = A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); B++; 
    int k = 58; 
    /* can compiler unroll the loop completely (i.e., peel this loop)? */ 
    while (k--) { 
    C1_vec += A1_vec * B_vec; 
    A2_vec = _mm_load_pd(A); A += 2; 
    C2_vec += A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); B++; 
    C3_vec += A1_vec * B_vec; 
    C4_vec += A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); B++; 
    C5_vec += A1_vec * B_vec; 
    C6_vec += A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); B++; 
    C7_vec += A1_vec * B_vec; 
    A1_vec = _mm_load_pd(A); A += 2; 
    C8_vec += A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); B++; 
    } 
    C1_vec += A1_vec * B_vec; 
    A2_vec = _mm_load_pd(A); 
    C2_vec += A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); B++; 
    C3_vec += A1_vec * B_vec; 
    C4_vec += A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); B++; 
    C5_vec += A1_vec * B_vec; 
    C6_vec += A2_vec * B_vec; 
    B_vec = _mm_load1_pd(B); 
    C7_vec += A1_vec * B_vec; 
    C8_vec += A2_vec * B_vec; 
    /* [write-back] */ 
    A1_vec = _mm_load_pd(C); C1_vec = A1_vec - C1_vec; 
    A2_vec = _mm_load_pd(C + 2); C2_vec = A2_vec - C2_vec; 
    A1_vec = _mm_load_pd(C + 4); C3_vec = A1_vec - C3_vec; 
    A2_vec = _mm_load_pd(C + 6); C4_vec = A2_vec - C4_vec; 
    A1_vec = _mm_load_pd(C + 8); C5_vec = A1_vec - C5_vec; 
    A2_vec = _mm_load_pd(C + 10); C6_vec = A2_vec - C6_vec; 
    A1_vec = _mm_load_pd(C + 12); C7_vec = A1_vec - C7_vec; 
    A2_vec = _mm_load_pd(C + 14); C8_vec = A2_vec - C8_vec; 
    _mm_store_pd(C,C1_vec); _mm_store_pd(C + 2,C2_vec); 
    _mm_store_pd(C + 4,C3_vec); _mm_store_pd(C + 6,C4_vec); 
    _mm_store_pd(C + 8,C5_vec); _mm_store_pd(C + 10,C6_vec); 
    _mm_store_pd(C + 12,C7_vec); _mm_store_pd(C + 14,C8_vec); 
    } 

---

अद्यतन 1

@ user3386109 द्वारा टिप्पणी के लिए धन्यवाद, मैं इस सवाल का एक छोटा सा विस्तार करना चाहते हैं। @ user3386109 बहुत अच्छा प्रश्न उठाता है। असल में मुझे इष्टतम पंजीकरण आवंटन के लिए कंपाइलर की क्षमता पर कुछ संदेह है, जब शेड्यूल करने के लिए कई समानांतर निर्देश हैं।

मैं व्यक्तिगत रूप से लगता है कि एक विश्वसनीय तरीका पहले कोड पाश शरीर एएसएम इनलाइन विधानसभा में (जो एचपीसी के लिए महत्वपूर्ण है), तो यह नकल के रूप में कई बार के रूप में मैं चाहता हूँ के लिए है। मेरे पास इस साल की शुरुआत में एक अलोकप्रिय पोस्ट था: inline assembly। कोड थोड़ा अलग था क्योंकि लूप पुनरावृत्तियों की संख्या, जे, एक फ़ंक्शन तर्क है इसलिए संकलन समय पर अज्ञात है। उस स्थिति में मैं लूप को पूरी तरह से अनलॉक नहीं कर सकता, इसलिए मैंने केवल दो बार असेंबली कोड डुप्लिकेट किया, और लूप को एक लेबल में बदल दिया और कूद दिया।यह पता चला कि मेरी लिखित असेंबली का परिणामी प्रदर्शन कंपाइलर जेनरेट असेंबली से लगभग 5% अधिक है, जो यह सुझाव दे सकता है कि संकलक हमारे अपेक्षित, इष्टतम तरीके से रजिस्टरों को आवंटित करने में विफल रहता है।

मैं असेंबली कोडिंग में एक बच्चा था (और अभी भी) था, ताकि x86 असेंबली पर थोड़ा सा सीखने के लिए मेरे लिए एक अच्छा केस अध्ययन किया जा सके। लेकिन लंबे समय तक मैं असेंबली के लिए बड़े अनुपात के साथ जीईपीडीओटी कोड करने की इच्छा नहीं करता हूं।

1. एएसएम इनलाइन विधानसभा पोर्टेबल नहीं होने के लिए critisized कर दिया गया है: वहाँ मुख्य रूप से तीन कारण हैं। हालांकि मुझे समझ में नहीं आता क्यों। शायद क्योंकि विभिन्न मशीनों के अलग-अलग रजिस्ट्रार हैं?
2. कंपाइलर भी बेहतर हो रहा है। इसलिए मैं अभी भी अच्छा आउटपुट उत्पन्न करने में कंपाइलर की सहायता करने के लिए एल्गोरिदमिक ऑप्टिमाइज़ेशन और बेहतर सी कोडिंग आदत पसंद करूंगा;
3. अंतिम कारण अधिक महत्वपूर्ण है। पुनरावृत्तियों की संख्या हमेशा 58 नहीं हो सकती है। मैं एक उच्च प्रदर्शन मैट्रिक्स कारकराइजेशन सबराउटिन विकसित कर रहा हूं। कैश अवरोधक कारक एनबी के लिए, पुनरावृत्तियों की संख्या (एनबी -2) होगी। मैं एनबी को फ़ंक्शन तर्क के रूप में नहीं डालूंगा, जैसा कि मैंने पहले की पोस्ट में किया था। यह एक मशीन विशिष्ट पैरामीटर एक मैक्रो के रूप में परिभाषित किया जाएगा। इसलिए पुनरावृत्तियों की संख्या संकलित समय पर ज्ञात है, लेकिन मशीन से मशीन में भिन्न हो सकती है। मान लीजिए कि मैन्युअल लूप में एनबी के लिए अनलॉकिंग में मुझे कितना कठिन काम करना है। तो अगर एक लूप छीलने के लिए संकलक को निर्देश देने का कोई तरीका है, तो यह बहुत अच्छा है।

यदि आप उच्च प्रदर्शन, अभी तक पोर्टेबल लाइब्रेरी बनाने में कुछ अनुभव साझा कर सकते हैं तो मुझे बहुत सराहना की जाएगी।

Answer 1

अनुकूलक मानकों बदलाव करने का प्रयास करें:

gcc -O3 -funroll-loops --param max-completely-peeled-insns=1000 --param max-completely-peel-times=100 

इस चाल करना चाहिए।

Answer 2

यह कोई जवाब नहीं है, लेकिन जीसीसी के साथ मैट्रिक्स गुणाओं को सदिश बनाने की कोशिश करने वाले अन्य लोगों के लिए रुचि हो सकती है।

नीचे, मुझे लगता है ग पंक्ति-प्रमुख क्रम में एक 4 × 4 मैट्रिक्स है, एक, ख एक 4-पंक्ति, n -column स्तंभ-प्रमुख आदेश (स्थानांतरित) में मैट्रिक्स है एक 4-स्तंभ, n -row पंक्ति-प्रमुख क्रम में मैट्रिक्स, और ऑपरेशन की गणना करने के लिए एक × ख + ग, जहां × अर्थ है आव्यूह गुणन ग = जाता है।

अनुभवहीन समारोह यह पूरा करने के

void slow_4(double  *c, 
      const double *a, 
      const double *b, 
      size_t  n) 
{ 
    size_t row, col, i; 

    for (row = 0; row < 4; row++) 
     for (col = 0; col < 4; col++) 
      for (i = 0; i < n; i++) 
       c[4*row+col] += a[4*i+row] * b[4*i+col]; 
} 

जीसीसी, जीसीसी भी

#if defined(__AVX__) || defined(__AVX2__) 

typedef double vec4d __attribute__((vector_size (4 * sizeof (double)))); 

void fast_4(vec4d  *c, 
      const vec4d *a, 
      const vec4d *b, 
      size_t  n) 
{ 
    const vec4d *const b_end = b + n; 

    vec4d s0 = c[0]; 
    vec4d s1 = c[1]; 
    vec4d s2 = c[2]; 
    vec4d s3 = c[3]; 

    while (b < b_end) { 
     const vec4d bc = *(b++); 
     const vec4d ac = *(a++); 
     const vec4d a0 = { ac[0], ac[0], ac[0], ac[0] }; 
     const vec4d a1 = { ac[1], ac[1], ac[1], ac[1] }; 
     const vec4d a2 = { ac[2], ac[2], ac[2], ac[2] }; 
     const vec4d a3 = { ac[3], ac[3], ac[3], ac[3] }; 
     s0 += a0 * bc; 
     s1 += a1 * bc; 
     s2 += a2 * bc; 
     s3 += a3 * bc; 
    } 

    c[0] = s0; 
    c[1] = s1; 
    c[2] = s2; 
    c[3] = s3; 
} 

#endif 

साथ बेहतर कर सकते हैं

#if defined(__SSE2__) || defined(__SSE3__) 

typedef double vec2d __attribute__((vector_size (2 * sizeof (double)))); 

void fast_4(vec2d  *c, 
      const vec2d *a, 
      const vec2d *b, 
      size_t  n) 
{ 
    const vec2d *const b_end = b + 2L * n; 

    vec2d s00 = c[0]; 
    vec2d s02 = c[1]; 
    vec2d s10 = c[2]; 
    vec2d s12 = c[3]; 
    vec2d s20 = c[4]; 
    vec2d s22 = c[5]; 
    vec2d s30 = c[6]; 
    vec2d s32 = c[7]; 

    while (b < b_end) { 
     const vec2d b0 = b[0]; 
     const vec2d b2 = b[1]; 
     const vec2d a0 = { a[0][0], a[0][0] }; 
     const vec2d a1 = { a[0][1], a[0][1] }; 
     const vec2d a2 = { a[1][0], a[1][0] }; 
     const vec2d a3 = { a[1][1], a[1][1] }; 
     s00 += a0 * b0; 
     s10 += a1 * b0; 
     s20 += a2 * b0; 
     s30 += a3 * b0; 
     s02 += a0 * b2; 
     s12 += a1 * b2; 
     s22 += a2 * b2; 
     s32 += a3 * b2; 
     b += 2; 
     a += 2; 
    } 

    c[0] = s00; 
    c[1] = s02; 
    c[2] = s10; 
    c[3] = s12; 
    c[4] = s20; 
    c[5] = s22; 
    c[6] = s30; 
    c[7] = s32; 
} 

#endif 

का उपयोग कर AVX लिए SSE2/SSE3 के लिए बहुत अच्छी कोड उत्पन्न करता है

जीसीसी -4.8 का उपयोग कर जेनरेटेड असेंबली का एसएसई 3 संस्करण।4 (-O2 -march=x86-64 -mtune=generic -msse3)

fast_4: 
     salq $5, %rcx 
     movapd (%rdi), %xmm13 
     addq %rdx, %rcx 
     cmpq %rcx, %rdx 
     movapd 16(%rdi), %xmm12 
     movapd 32(%rdi), %xmm11 
     movapd 48(%rdi), %xmm10 
     movapd 64(%rdi), %xmm9 
     movapd 80(%rdi), %xmm8 
     movapd 96(%rdi), %xmm7 
     movapd 112(%rdi), %xmm6 
     jnb  .L2 
.L3: 
     movddup (%rsi), %xmm5 
     addq $32, %rdx 
     movapd -32(%rdx), %xmm1 
     addq $32, %rsi 
     movddup -24(%rsi), %xmm4 
     movapd %xmm5, %xmm14 
     movddup -16(%rsi), %xmm3 
     movddup -8(%rsi), %xmm2 
     mulpd %xmm1, %xmm14 
     movapd -16(%rdx), %xmm0 
     cmpq %rdx, %rcx 
     mulpd %xmm0, %xmm5 
     addpd %xmm14, %xmm13 
     movapd %xmm4, %xmm14 
     mulpd %xmm0, %xmm4 
     addpd %xmm5, %xmm12 
     mulpd %xmm1, %xmm14 
     addpd %xmm4, %xmm10 
     addpd %xmm14, %xmm11 
     movapd %xmm3, %xmm14 
     mulpd %xmm0, %xmm3 
     mulpd %xmm1, %xmm14 
     mulpd %xmm2, %xmm0 
     addpd %xmm3, %xmm8 
     mulpd %xmm2, %xmm1 
     addpd %xmm14, %xmm9 
     addpd %xmm0, %xmm6 
     addpd %xmm1, %xmm7 
     ja  .L3 
.L2: 
     movapd %xmm13, (%rdi) 
     movapd %xmm12, 16(%rdi) 
     movapd %xmm11, 32(%rdi) 
     movapd %xmm10, 48(%rdi) 
     movapd %xmm9, 64(%rdi) 
     movapd %xmm8, 80(%rdi) 
     movapd %xmm7, 96(%rdi) 
     movapd %xmm6, 112(%rdi) 
     ret 

उत्पन्न विधानसभा (-O2 -march=x86-64 -mtune=generic -mavx) की avx संस्करण अनिवार्य रूप से

fast_4: 
     salq  $5, %rcx 
     vmovapd (%rdi), %ymm5 
     addq  %rdx, %rcx 
     vmovapd 32(%rdi), %ymm4 
     cmpq  %rcx, %rdx 
     vmovapd 64(%rdi), %ymm3 
     vmovapd 96(%rdi), %ymm2 
     jnb  .L2 
.L3: 
     addq  $32, %rsi 
     vmovapd -32(%rsi), %ymm1 
     addq  $32, %rdx 
     vmovapd -32(%rdx), %ymm0 
     cmpq  %rdx, %rcx 
     vpermilpd $0, %ymm1, %ymm6 
     vperm2f128 $0, %ymm6, %ymm6, %ymm6 
     vmulpd  %ymm0, %ymm6, %ymm6 
     vaddpd  %ymm6, %ymm5, %ymm5 
     vpermilpd $15, %ymm1, %ymm6 
     vperm2f128 $0, %ymm6, %ymm6, %ymm6 
     vmulpd  %ymm0, %ymm6, %ymm6 
     vaddpd  %ymm6, %ymm4, %ymm4 
     vpermilpd $0, %ymm1, %ymm6 
     vpermilpd $15, %ymm1, %ymm1 
     vperm2f128 $17, %ymm6, %ymm6, %ymm6 
     vperm2f128 $17, %ymm1, %ymm1, %ymm1 
     vmulpd  %ymm0, %ymm6, %ymm6 
     vmulpd  %ymm0, %ymm1, %ymm0 
     vaddpd  %ymm6, %ymm3, %ymm3 
     vaddpd  %ymm0, %ymm2, %ymm2 
     ja   .L3 
.L2: 
     vmovapd %ymm5, (%rdi) 
     vmovapd %ymm4, 32(%rdi) 
     vmovapd %ymm3, 64(%rdi) 
     vmovapd %ymm2, 96(%rdi) 
     vzeroupper 
     ret 

है रजिस्टर निर्धारण, इष्टतम नहीं है मुझे लगता है कि, लेकिन यह या तो नृशंस नहीं लगती है अनिवार्य रूप से है। मैं इस बिंदु पर इसे अनुकूलित करने की कोशिश किए बिना उपर्युक्त से व्यक्तिगत रूप से खुश हूं।

कोर i5-4200U प्रोसेसर (AVX2- सक्षम) पर, उपर्युक्त कार्यों के तेज़ संस्करण एसएसई 3 के लिए 1843 सीपीयू चक्र (माध्य) में और 448 चक्रों के लिए 1248 चक्रों में दो 4 × 256 मैट्रिक्स के उत्पाद की गणना करते हैं। यह प्रति मैट्रिक्स प्रविष्टि 1.8 और 1.22 चक्र नीचे आता है। तुलनात्मक रूप से धीमे संस्करण की तुलना में प्रति मैट्रिक्स प्रविष्टि के बारे में 11 चक्र होते हैं।

(चक्र की गिनती मंझला मान होते हैं, यानी आधा परीक्षण तेजी से कर रहे थे। मैं केवल कुछ किसी न किसी बेंच मार्किंग ~ 100k दोहराता साथ भाग गया या ऐसा है, तो एक अलग नज़रिए से इन नंबरों से लेते हैं।)

इस पर सीपीयू, कैश इफेक्ट्स इस प्रकार हैं कि 4 × 512 मैट्रिक्स आकार पर AVX2 अभी भी 1.2 चक्र प्रति प्रविष्टि पर है, लेकिन 4 × 1024 पर, यह 4 × 4096 से 1.5 पर 4 × 8192 से 1.8 पर, और 4 पर गिर जाता है प्रति प्रविष्टि × 65536 से 2.2 चक्र। एसएसई 3 संस्करण 4 × 3072 तक प्रति प्रविष्टि 1.8 चक्र पर रहता है, जिस बिंदु पर यह धीमा हो जाता है; 4 × 65536 पर यह प्रति प्रवेश के बारे में 2.2 चक्र भी है। मुझे विश्वास है कि यह (लैपटॉप!) सीपीयू इस बिंदु पर सीमित कैश बैंडविड्थ है।