Số lượng bộ nhớ cache bị giảm khi mã vectơ

Question

Tôi đã vector hóa sản phẩm chấm giữa 2 vectơ với SSE 4.2 và AVX 2, như bạn có thể xem bên dưới. Mã được biên dịch bằng GCC 4.8.4 với cờ tối ưu hóa -O2. Theo dự kiến, hiệu suất tốt hơn với cả hai (và AVX 2 nhanh hơn SSE 4.2), nhưng khi tôi lập mã với PAPI, tôi phát hiện ra rằng tổng số lần bị lỗi (chủ yếu là L1 và L2) tăng lên rất nhiều:

Nếu không có bản vẽ Gia:

PAPI_L1_TCM: 784,112,091 
PAPI_L2_TCM: 195,315,365 
PAPI_L3_TCM: 79,362 

Với SSE 4.2:

PAPI_L1_TCM: 1,024,234,171 
PAPI_L2_TCM: 311,541,918 
PAPI_L3_TCM: 68,842 

Với AVX 2:

PAPI_L1_TCM: 2,719,959,741 
PAPI_L2_TCM: 1,459,375,105 
PAPI_L3_TCM: 108,140 

Có thể có điều gì đó sai với mã của tôi hay là loại hành vi này bình thường không?

AVX 2 mã:

double vec_dotProduct(const vec& vecs, const unsigned int& start_a, const unsigned int& start_b, const int& n) { 
    double dot = 0; 
    register int i = 0; 
    const int loopBound = n-3; 

    __m256d vsum, vecPi, vecCi, vecQCi; 

    vsum = _mm256_set1_pd(0); 

    double * const pA = vecs.x+start_a ; 
    double * const pB = vecs.x+start_b ; 

    for(; i<loopBound ;i+=4){ 
     vecPi = _mm256_loadu_pd(&(pA)[i]); 
     vecCi = _mm256_loadu_pd(&(pB)[i]); 
     vecQCi = _mm256_mul_pd(vecPi,vecCi); 
     vsum = _mm256_add_pd(vsum,vecQCi); 
    } 

    vsum = _mm256_hadd_pd(vsum, vsum); 

    dot = ((double*)&vsum)[0] + ((double*)&vsum)[2]; 

    for(; i<n; i++) 
     dot += pA[i] * pB[i]; 

    return dot; 
} 

SSE 4.2 đang: Mã

double vec_dotProduct(const vec& vecs, const unsigned int& start_a, const unsigned int& start_b, const int& n) { 
    double dot = 0; 
    register int i = 0; 

    const int loopBound = n-1; 

    __m128d vsum, vecPi, vecCi, vecQCi; 

    vsum = _mm_set1_pd(0); 

    double * const pA = vecs.x+start_a ; 
    double * const pB = vecs.x+start_b ; 

    for(; i<loopBound ;i+=2){ 
     vecPi = _mm_load_pd(&(pA)[i]); 
     vecCi = _mm_load_pd(&(pB)[i]); 
     vecQCi = _mm_mul_pd(vecPi,vecCi); 
     vsum = _mm_add_pd(vsum,vecQCi); 
    } 

    vsum = _mm_hadd_pd(vsum, vsum); 

    _mm_storeh_pd(&dot, vsum); 

    for(; i<n; i++) 
     dot += pA[i] * pB[i]; 

    return dot; 
} 

Non-vectorized:

double dotProduct(const vec& vecs, const unsigned int& start_a, const unsigned int& start_b, const int& n) { 
    double dot = 0; 
    register int i = 0; 

    for (i = 0; i < n; ++i) 
    { 
     dot += vecs.x[start_a+i] * vecs.x[start_b+i]; 
    } 
    return dot; 
} 

Edit: hội của mã không vectorized:

0x000000000040f9e0 <+0>:  mov (%rcx),%r8d 
    0x000000000040f9e3 <+3>:  test %r8d,%r8d 
    0x000000000040f9e6 <+6>:  jle 0x40fa1d <dotProduct(vec const&, unsigned int const&, unsigned int const&, int const&)+61> 
    0x000000000040f9e8 <+8>:  mov (%rsi),%eax 
    0x000000000040f9ea <+10>: mov (%rdi),%rcx 
    0x000000000040f9ed <+13>: mov (%rdx),%edi 
    0x000000000040f9ef <+15>: vxorpd %xmm0,%xmm0,%xmm0 
    0x000000000040f9f3 <+19>: add %eax,%r8d 
    0x000000000040f9f6 <+22>: sub %eax,%edi 
    0x000000000040f9f8 <+24>: nopl 0x0(%rax,%rax,1) 
    0x000000000040fa00 <+32>: mov %eax,%esi 
    0x000000000040fa02 <+34>: lea (%rdi,%rax,1),%edx 
    0x000000000040fa05 <+37>: add $0x1,%eax 
    0x000000000040fa08 <+40>: vmovsd (%rcx,%rsi,8),%xmm1 
    0x000000000040fa0d <+45>: cmp %r8d,%eax 
    0x000000000040fa10 <+48>: vmulsd (%rcx,%rdx,8),%xmm1,%xmm1 
    0x000000000040fa15 <+53>: vaddsd %xmm1,%xmm0,%xmm0 
    0x000000000040fa19 <+57>: jne 0x40fa00 <dotProduct(vec const&, unsigned int const&, unsigned int const&, int const&)+32> 
    0x000000000040fa1b <+59>: repz retq 
    0x000000000040fa1d <+61>: vxorpd %xmm0,%xmm0,%xmm0 
    0x000000000040fa21 <+65>: retq 

Edit2: Dưới đây bạn có thể tìm thấy sự so sánh của cache L1 giữa vectorized và mã không vectorized cho N lớn hơn (N trên nhãn x và L1 cache trên nhãn y). Về cơ bản, đối với các N lớn hơn thì vẫn còn nhiều lỗi trong phiên bản vectơ hơn là trong phiên bản không được vectơ hóa.

Answer 1

Rostislav là đúng rằng trình biên dịch là tự động vectorizing, và từ các tài liệu GCC trên -O2:.

"-O2 Optimize thậm chí nhiều hơn GCC thực hiện gần như tất cả các tối ưu hóa được hỗ trợ mà không liên quan đến một sự cân bằng tốc độ không gian. " (từ đây: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html)

GCC với cờ -O2 đang cố gắng tạo mã hiệu quả nhất mà không cần kích thước hoặc tốc độ mã.

Vì vậy, về chu kỳ CPU, mã vectơ tự động -O2 sẽ yêu cầu watt ít nhất để chạy, nhưng sẽ không phải là mã nhanh nhất hoặc nhỏ nhất. Đây là trường hợp tốt nhất cho mã chạy trên các thiết bị di động và trên các hệ thống đa người dùng, và chúng có xu hướng là sử dụng ưu tiên của C++. Nếu bạn muốn tốc độ tối đa tuyệt đối bất kể bao nhiêu watt sử dụng, hãy thử -O3 hoặc -Ofast nếu phiên bản GCC của bạn hỗ trợ chúng hoặc đi với các giải pháp nhanh hơn được tối ưu hóa bằng tay của bạn.

Nguyên nhân của việc này có thể là sự kết hợp của hai yếu tố.

Mã đầu tiên, nhanh hơn tạo nhiều yêu cầu hơn cho bộ nhớ/bộ nhớ cache trong cùng một khoảng thời gian, điều này nhấn mạnh thuật toán dự đoán tìm nạp trước. Bộ nhớ cache L1 không phải là rất lớn, thường là 1MB - 3MB và được chia sẻ giữa tất cả các quy trình đang chạy trên CPU Core đó, vì vậy, CPU Core không thể tìm nạp trước cho đến khi khối được tìm nạp trước đó không còn được sử dụng nữa.Nếu mã đang chạy nhanh hơn, sẽ có ít thời gian hơn để tìm nạp trước giữa các khối và trong mã hiệu quả các đường ống, nhiều lần nhớ cache hơn sẽ được thực hiện trước khi CPU Core dừng hoàn toàn cho đến khi các lần tải chờ xử lý hoàn tất. Các hệ điều hành thứ hai, hiện đại thường phân chia các quy trình đơn luồng giữa nhiều lõi bằng cách điều chỉnh ái lực luồng, để tận dụng bộ đệm bổ sung trên nhiều lõi, mặc dù nó không thể chạy bất kỳ mã nào song song - ví dụ điền vào cache của core 0 với dữ liệu của bạn và sau đó chạy nó trong khi điền cache của lõi 1, sau đó chạy trên core 1 trong khi nạp lại cache của core 0, round-robin cho đến khi hoàn thành. Giả thuyết song song này cải thiện tốc độ tổng thể của các quy trình đơn luồng và giảm đáng kể các lỗi bộ nhớ cache, nhưng chỉ có thể được thực hiện trong các trường hợp rất cụ thể ... các trường hợp cụ thể mà trình biên dịch tốt sẽ tạo ra mã bất cứ khi nào có thể.

Answer 2

Như bạn có thể thấy trong một số nhận xét, các lần xóa bộ nhớ cache đến từ việc tăng hiệu suất.

Ví dụ với CPU gần đây, bạn sẽ có thể thực thi 2 AVX2 thêm hoặc mul tại mỗi chu kỳ sao cho 512 bit tại mỗi chu kỳ. Thời gian bạn sẽ cần để tải dữ liệu sẽ cao hơn vì nó sẽ yêu cầu một số dòng bộ nhớ cache.

Ngoài ra, tùy thuộc vào cách hệ thống của bạn được cấu hình, siêu luồng, affinities vv, lịch trình của bạn có thể làm những thứ khác cùng một lúc gây ô nhiễm bộ nhớ cache của bạn với các chủ đề/quy trình khác.

Điều cuối cùng. Các CPU hiện nay khá hiệu quả để nhận ra các mẫu đơn giản như một mẫu bạn có với các vòng rất nhỏ và sau đó sẽ sử dụng tự động tìm nạp trước sau vài lần lặp. Nó sẽ không đủ để khắc phục vấn đề kích thước bộ nhớ cache.

Hãy thử với các kích thước khác nhau cho N, bạn sẽ thấy kết quả thú vị. Đồng thời, căn chỉnh dữ liệu của bạn lúc đầu và đảm bảo rằng nếu bạn sử dụng 2 biến, không có cùng một đường bộ nhớ cache.