dòng Cache, chia sẻ sai và liên kết

Question

tôi đã viết chương trình sau C ngắn ++ để tạo lại hiệu ứng chia sẻ giả như mô tả của Herb Sutter:

Say, chúng tôi muốn thực hiện tổng số tiền là hoạt động nguyên khối lượng công việc và chúng tôi muốn họ được chia đều cho một số (PARALLEL) của các chủ đề. Với mục đích của phép thử này, mỗi luồng sẽ tăng biến riêng của nó từ một mảng các số nguyên, vì vậy quá trình này có thể là lý tưởng song song.

void thread_func(int* ptr) 
{ 
    for (unsigned i = 0; i < WORKLOAD/PARALLEL; ++i) 
    { 
     (*ptr)++; 
    } 
} 

int main() 
{ 
    int arr[PARALLEL * PADDING]; 
    thread threads[PARALLEL]; 

    for (unsigned i = 0; i < PARALLEL; ++i) 
    { 
     threads[i] = thread(thread_func, &(arr[i * PADDING])); 
    } 
    for (auto& th : threads) 
    { 
     th.join(); 
    } 
    return 0; 
} 

Tôi nghĩ ý tưởng này rất dễ nắm bắt. Nếu bạn đặt

#define PADDING 16 

mỗi luồng sẽ hoạt động trên một dòng bộ nhớ cache riêng biệt (giả định chiều dài của dòng bộ nhớ cache là 64 byte). Vì vậy, kết quả sẽ là tăng tốc độ tuyến tính cho đến khi PARALLEL> # lõi. Mặt khác, nếu PADDING được đặt thành bất kỳ giá trị nào dưới 16, bạn sẽ gặp phải sự tranh chấp gay gắt, vì ít nhất hai luồng có thể hoạt động trên cùng một dòng bộ nhớ cache, tuy nhiên được bảo vệ bằng một phần cứng gắn sẵn. Chúng tôi hy vọng tốc độ tăng tốc của chúng tôi không chỉ là tuyến dưới trong trường hợp này, mà thậm chí là luôn luôn < 1, bởi vì đoàn tàu khóa vô hình.

Bây giờ, nỗ lực đầu tiên của tôi gần như thỏa mãn những kỳ vọng này, nhưng giá trị tối thiểu của PADDING cần thiết để tránh chia sẻ sai là khoảng 8 và không 16. Tôi đã khá bối rối trong khoảng nửa giờ cho đến khi tôi đi đến kết luận rõ ràng, không có sự đảm bảo nào cho mảng của tôi được căn chỉnh chính xác đến đầu của một dòng bộ nhớ đệm bên trong bộ nhớ chính. Căn chỉnh thực tế có thể khác nhau tùy thuộc vào nhiều điều kiện, bao gồm kích thước của mảng.

Trong ví dụ này, tất nhiên chúng ta không cần phải sắp xếp mảng theo cách đặc biệt, vì chúng ta chỉ có thể để PADDING ở mức 16 và mọi thứ hoạt động tốt. Nhưng người ta có thể tưởng tượng các trường hợp, nơi nó tạo sự khác biệt, cho dù một cấu trúc nhất định có được liên kết với một đường bộ nhớ cache hay không. Do đó, tôi đã thêm một số dòng mã để có được một số thông tin về sự liên kết thực sự của mảng của tôi.

int main() 
{ 
    int arr[PARALLEL * 16]; 
    thread threads[PARALLEL]; 
    int offset = 0; 

    while (reinterpret_cast<int>(&arr[offset]) % 64) ++offset; 
    for (unsigned i = 0; i < PARALLEL; ++i) 
    { 
     threads[i] = thread(thread_func, &(arr[i * 16 + offset])); 
    } 
    for (auto& th : threads) 
    { 
     th.join(); 
    } 
    return 0; 
} 

Mặc dù giải pháp này làm việc tốt cho tôi trong trường hợp này, tôi không chắc đó có phải là cách tiếp cận tốt hay không. Vì vậy, đây là câu hỏi của tôi:

Có cách nào phổ biến để có đối tượng trong bộ nhớ phù hợp với dòng bộ nhớ cache khác với những gì tôi đã làm trong ví dụ trên?

(sử dụng g ++ MinGW Win32 x86 v.4.8.1 posix lùn rev3)

Answer 1

Bạn sẽ có thể yêu cầu sự liên kết cần thiết từ trình biên dịch:

alignas(64) int arr[PARALELL * PADDING]; // align the array to a 64 byte line 

Answer 2

gcc hỗ trợ từ khóa liên kết: http://gcc.gnu.org/onlinedocs/gcc/Variable-Attributes.html

Bạn có thể muốn một cái gì đó như thế này:

int arr[PARALLEL * 16] __attribute__ ((aligned (8)));

Điều này căn chỉnh arr thành ranh giới tám byte.

Visual Studio cũng có một tính năng tương tự: http://msdn.microsoft.com/en-us/library/83ythb65.aspx