Tại sao bộ nhớ cache đọc bỏ lỡ nhanh hơn ghi lỗi?

Question

Tôi cần tính toán mảng (writeArray) sử dụng mảng khác (readArray) nhưng vấn đề là ánh xạ chỉ mục không giống nhau giữa các mảng (Giá trị tại chỉ số x của writeArray phải được tính với giá trị tại chỉ mục y của readArray). không phải là rất thân thiện với bộ nhớ cache.

Tuy nhiên tôi có thể chọn xem vòng lặp duyệt readArray tuần tự hay writeArray tuần tự.

Vì vậy, đây là một mã đơn giản:

int *readArray = new int[ARRAY_SIZE];  // Array to read 
int *writeArray = new int[ARRAY_SIZE];  // Array to write 
int *refArray = new int[ARRAY_SIZE];  // Index mapping between read and write, could be also array of pointers instead indexes 

// Code not showed here : Initialization of readArray with values, writeArray with zeroes and refArray with random indexes for mapping between readArray and writeArray (values of indexes between 0 and ARRAY_SIZE - 1) 

// Version 1: Random read (browse writeArray/refArray sequentially) 
for (int n = 0; n < ARRAY_SIZE; ++n) { 
    writeArray[n] = readArray[refArray[n]]; 
} 

// Version 2: Random write (browse readArray/refArray sequentially) 
for (int n = 0; n < ARRAY_SIZE; ++n) { 
    writeArray[refArray[n]] = readArray[n]; 
} 

Tôi đã suy nghĩ bộ nhớ cache mà đọc bỏ lỡ là chậm hơn viết bỏ lỡ (vì CPU cần phải chờ đợi trước khi đọc trọn vẹn nếu chỉ lệnh kế tiếp phụ thuộc dữ liệu đọc nhưng đối với viết nó không cần phải đợi để xử lý lệnh tiếp theo) nhưng với lược tả có vẻ như phiên bản 1 nhanh hơn phiên bản 2 (phiên bản 2 chậm hơn khoảng 50% so với phiên bản 1).

Tôi cũng đã cố gắng này:

// Version 3: Same as version 2 but without polluting cache 
for (int n = 0; n < ARRAY_SIZE; ++n) { 
    _mm_stream_si32(&writeArray[refArray[n]], readArray[n]); 
} 

Bởi vì tôi không cần phải đọc giá trị của writeArray vì vậy không có lý do gì để làm ô nhiễm bộ nhớ cache với giá trị bằng văn bản nhưng phiên bản này là chậm hơn nhiều hơn các phiên bản khác (6700% chậm hơn phiên bản 1).

Tại sao viết thư bỏ lỡ chậm hơn đọc bỏ lỡ? Tại sao bỏ qua bộ nhớ cache để viết chậm hơn sử dụng nó ngay cả khi chúng ta không đọc những dữ liệu sau này?

Answer 1

Hãy bắt đầu với phiên bản cuối cùng - những gì bạn đã làm là sử dụng các cửa hàng trực tuyến cho mẫu truy cập không tuần tự (không phải luồng). Bạn đang truy cập ngẫu nhiên các số nguyên, có nghĩa là bạn đang viết một phần (int) thành các dòng bộ nhớ cache đầy đủ. Khi viết bình thường, điều này không quan trọng, vì lõi sẽ kéo dòng vào bộ nhớ cache và chỉ cần sửa đổi đoạn cần thiết (sau này sẽ được viết lại khi bạn cần lưu trữ cho một thứ khác), nhưng vì bạn yêu cầu nó tránh bộ nhớ đệm, bạn thực sự phải làm điều này một phần hợp nhất trong bộ nhớ mà là rất tốn kém và ngăn chặn. Cửa hàng phát trực tuyến chỉ hữu ích khi bạn được đảm bảo sửa đổi toàn bộ dòng (ví dụ: bằng cách đi qua dãy liên tục).

Đối với phiên bản thứ 2 - giả định của bạn là chính xác, nếu có sự phụ thuộc dữ liệu thông qua tải, bạn sẽ phải đợi chúng, nhưng không có chuỗi phụ thuộc thực sự ở đây. Bạn chỉ có một tập hợp các tải với mức phụ thuộc 2 cấp, nhưng không có sự phụ thuộc lẫn nhau giữa chúng để gây ra bất kỳ sự tuần tự hóa nào trong các lần lặp (tức là lặp lại n == 2 và n == 3 có thể bắt đầu ngay cả trước khi n == 1 nhận được tải đầu tiên). Hiệu quả, giả sử CPU của bạn có thể duy trì N truy cập nổi bật (tùy thuộc vào kích thước và mức bộ nhớ cache liên quan), bạn sẽ khởi chạy tham chiếu N đầu tiên đến refArray song song (giả sử tính toán chỉ mục nhanh), tiếp theo là tham chiếu đầu tiên của N readArray, sau đó là lô tiếp theo và cứ tiếp tục như vậy.

Bây giờ, vì không có sự phụ thuộc dữ liệu, nó trở thành một câu hỏi về băng thông. Trong trường hợp đó, nói chung, tải dễ dàng hơn cho bộ vi xử lý do tính chất không theo thứ tự của chúng - bạn có thể khởi chạy chúng song song và không theo thứ tự, khi bạn biết địa chỉ (chỉ phụ thuộc vào tính toán chỉ số nhanh) . Cửa hàng, mặt khác, cần phải được quan sát theo thứ tự chương trình (để duy trì tính nhất quán của bộ nhớ), gần như tuần tự hóa chúng (có một số thủ thuật CPU có thể, tùy thuộc vào kiến ​​trúc vi mô chính xác của bạn, nhưng nó sẽ không thay đổi lớn hình ảnh).

Chỉnh sửa: Một ràng buộc khác được thêm vào trong phiên bản 2 (mà tôi cho là còn quan trọng hơn), là sự định hướng bộ nhớ.Bộ xử lý phải tính toán các tải và lưu trữ các địa chỉ, để biết nếu có bất kỳ va chạm nào (chúng ta biết không có, nhưng bộ vi xử lý không ...). Nếu tải phụ thuộc vào một cửa hàng, nó phải bị chặn, trong trường hợp dữ liệu mới phải được chuyển tiếp. Bây giờ, vì tải được khởi chạy trong máy OOO sớm, nên điều quan trọng là phải biết địa chỉ cho tất cả các cửa hàng càng sớm càng tốt để tránh va chạm (hoặc tệ hơn - những suy đoán thất bại và gây ra xả hàng loạt)