Bộ nhớ cache CPU: khoảng cách giữa hai địa chỉ có nhỏ hơn 8 byte để có lợi thế bộ đệm không?

Question

Có vẻ như một câu hỏi lạ ..

Nói kích thước của dòng bộ nhớ cache là 64 byte. Hơn nữa, giả sử rằng L1, L2, L3 có cùng kích thước đường bộ nhớ cache (this bài viết cho biết đó là trường hợp của Intel Core i7).

Có hai đối tượng A, B trên bộ nhớ có địa chỉ (vật lý) cách nhau N cách nhau byte. Để đơn giản, chúng ta hãy giả A là trên ranh giới bộ nhớ cache, có nghĩa là, địa chỉ của nó là bội số của 64.

1) Nếu N < 64, khi A được nạp bởi CPU, B sẽ được đọc vào bộ nhớ cache, quá. Vì vậy, nếu cần B và dòng bộ nhớ cache chưa được gỡ bỏ, CPU sẽ tìm nạp B trong một thời gian rất ngắn. Mọi người đều hạnh phúc.

2) Nếu N >> 64 (ví dụ: nhiều lớn hơn 64), khi A được lấy bởi CPU, B không được đọc vào dòng bộ nhớ cache cùng với A. Vì vậy, chúng tôi nói "CPU không thích các con trỏ theo dõi" và đó là một trong những lý do để tránh cấu trúc dữ liệu dựa trên nút được phân bổ heap, chẳng hạn như std::list.

Câu hỏi của tôi là, nếu N> 64 nhưng vẫn còn nhỏ, nói N = 70, nói cách khác, A và B không phù hợp trong một dòng bộ nhớ cache nhưng không quá xa nhau, khi A được tải bởi CPU, việc lấy B có cùng số lượng chu kỳ đồng hồ vì nó sẽ mất khi N lớn hơn 64?

rephrase - khi A được nạp, chúng ta hãy t đại diện cho trôi qua thời điểm lấy B, là t (N = 70) nhỏ hơn nhiều hơn, hoặc gần như tương đương với, t (N = 9999999)?

Tôi hỏi câu hỏi này vì tôi nghi ngờ t (N = 70) là nhỏ hơn nhiều so t (N = 9.999.999), kể từ CPU Cache là thứ bậc.

Thậm chí còn tốt hơn nếu có nghiên cứu định lượng.

Answer 1

Có ít nhất ba yếu tố có thể tìm nạp B sau khi bỏ lỡ nhanh hơn. Đầu tiên, một bộ xử lý có thể tìm nạp khối tiếp theo (không phụ thuộc vào bất kỳ công cụ tìm nạp trước dựa trên stride nào, phụ thuộc vào hai lần bị lỡ gần nhau trong thời gian và địa điểm để xác định bước đi; giá trị sải chân [nó là một] và có thể được bắt đầu sau lần bỏ lỡ đầu tiên). Vì việc tìm nạp trước đó tiêu thụ băng thông bộ nhớ và lưu trữ trên chip, nó thường có cơ chế điều chỉnh (có thể đơn giản như có bộ đệm prefetch có kích cỡ khiêm tốn và chỉ thực hiện tìm nạp trước khi đầu vào cao khi giao diện bộ nhớ đủ nhàn rỗi).Thứ hai, bởi vì DRAM được tổ chức thành hàng và thay đổi hàng (trong một ngân hàng) tăng độ trễ, nếu B nằm trong cùng một hàng DRAM như A, truy cập vào B có thể tránh độ trễ của một hàng nạp tiền (để đóng hàng mở trước đó) và kích hoạt (để mở hàng mới). (Điều này cũng có thể cải thiện việc sử dụng băng thông bộ nhớ.)

Thứ ba, nếu B nằm trong cùng trang dịch địa chỉ là A, TLB có thể tránh được. (Trong nhiều thiết kế trang bảng phân cấp đi bộ cũng nhanh hơn ở các vùng lân cận vì cấu trúc phân trang có thể được lưu trữ. Ví dụ, trong x86-64, nếu B nằm trong cùng vùng 2MiB như A, TLB miss có thể chỉ phải thực hiện một truy cập bộ nhớ vì thư mục trang vẫn có thể được lưu trữ, hơn nữa, nếu bản dịch cho B nằm trong cùng một dòng bộ nhớ cache 64 byte như bản dịch cho A và TLB bị bỏ lỡ đối với A có phần gần đây, thì dòng bộ nhớ cache vẫn có thể xuất hiện.)

Trong một số trường hợp, người ta cũng có thể khai thác công cụ tìm nạp trước stride-base bằng cách sắp xếp các đối tượng có khả năng bỏ lỡ cùng nhau trong một sải chân cố định, trật tự. Điều này có vẻ là một tối ưu hóa bối cảnh khá khó khăn và hạn chế.

Một cách rõ ràng là sải chân có thể tăng độ trễ bằng cách giới thiệu các lỗi xung đột. Hầu hết các cache sử dụng modulo đơn giản là sức mạnh của hai chỉ mục với sự kết hợp giới hạn, do đó sức mạnh của hai bước (hoặc ánh xạ khác cho cùng một bộ nhớ đệm) có thể đặt một lượng dữ liệu không cân xứng trong một số lượng giới hạn các bộ. Khi sự kết hợp bị vượt quá, các lỗi xung đột sẽ xảy ra. (Sự liên kết bị xáo trộn và không lập chỉ mục modulo hai đã được đề xuất để giảm vấn đề này, nhưng các kỹ thuật này chưa được áp dụng rộng rãi.)

(Bằng cách này, lý do con trỏ theo đuổi đặc biệt chậm không chỉ là địa phương không gian thấp nhưng không thể bắt đầu truy cập vào B cho đến khi quyền truy cập vào A đã hoàn thành vì có sự phụ thuộc dữ liệu, tức là độ trễ của tìm nạp B không thể chồng chéo với độ trễ tìm nạp A.)

Answer 2

Nếu B ở địa chỉ thấp hơn A, nó sẽ không nằm trong cùng một dòng bộ nhớ cache ngay cả khi chúng liền kề nhau. Vì vậy, trường hợp N < 64 của bạn bị đặt tên sai: đó thực sự là trường hợp "cùng một dòng bộ nhớ cache".

---

Kể từ khi bạn đề cập đến Intel i7: Sandybridge-gia đình có một prefetcher "không gian" trong L2, trong đó (nếu không có rất nhiều bỏ lỡ vượt trội đã được) prefetches dòng bộ nhớ cache khác trong một cặp để hoàn thành một cặp dòng 128B được sắp xếp tự nhiên.

Từ thủ công tối ưu hóa của Intel, trong mục 2.3 Sandy Bridge:

2.3.5.4 Data Prefetching

• ... Một số prefetchers lấy vào L1.

• không gian Prefetcher: prefetcher này phấn đấu để hoàn thành tất cả các dòng bộ nhớ cache vời để bộ nhớ cache L2 với dòng cặp mà hoàn thành nó vào một 128-byte đoạn thẳng hàng.

• ... nhiều prefetchers khác cố gắng prefetch vào L2

IDK bao lâu nó thực hiện điều này; nếu nó không đưa ra yêu cầu cho đến khi dòng bộ nhớ cache đầu tiên đến, nó sẽ không giúp ích nhiều cho một trường hợp theo dõi con trỏ.Tải phụ thuộc chỉ có thể thực thi một vài chu kỳ sau khi dòng bộ nhớ cache đến trong L1D, nếu nó thực sự chỉ là con trỏ mà không có một loạt độ trễ tính toán. Nhưng nếu nó phát hành prefetch ngay sau khi miss đầu tiên (chứa địa chỉ cho tải thứ 2), tải thứ hai có thể tìm thấy dữ liệu của nó đã có trong cache L1D, đã đến một chu kỳ hoặc hai sau khi tải nhu cầu đầu tiên.

Dù sao, điều này làm cho ranh giới 128B phù hợp để tìm nạp trước trong CPU Intel.

---

Xem câu trả lời tuyệt vời của Paul cho các yếu tố khác.