Bộ nhớ cache ánh xạ trực tiếp hoạt động như thế nào?

Question

Tôi đang tham gia khóa học Kiến trúc hệ thống và tôi gặp khó khăn khi hiểu cách hoạt động của bộ nhớ cache được ánh xạ trực tiếp.

Tôi đã xem xét một vài nơi và họ giải thích nó theo một cách khác khiến tôi càng bối rối hơn.

Điều tôi không thể hiểu là Thẻ và chỉ mục là gì và chúng được chọn như thế nào?

Lời giải thích từ bài giảng của tôi là: "Địa chỉ chia là thành hai phần chỉ mục (ví dụ như 15 bit) được sử dụng để giải quyết (32k) RAMS trực tiếp Phần còn lại của địa chỉ, thẻ được lưu trữ và so sánh với thẻ đến."

Thẻ đó đến từ đâu? Nó không thể là địa chỉ đầy đủ của vị trí bộ nhớ trong RAM vì nó làm cho bộ nhớ cache ánh xạ trực tiếp vô dụng (khi so sánh với bộ nhớ cache kết hợp đầy đủ).

Cảm ơn bạn rất nhiều.

Answer 1

Cho phép sử dụng ví dụ. Một bộ nhớ cache 64 kilobyte, với 16 byte bộ nhớ cache dòng có 4096 dòng bộ nhớ cache khác nhau.

Bạn cần phải chia nhỏ địa chỉ thành ba phần khác nhau.

1. Các bit thấp nhất được sử dụng để cho bạn biết byte trong dòng bộ nhớ cache khi bạn lấy lại, phần này không được sử dụng trực tiếp trong tra cứu bộ nhớ cache. (bit 0-3 trong ví dụ này)
2. Các bit tiếp theo được sử dụng để INDEX bộ nhớ cache. Nếu bạn nghĩ về bộ nhớ cache là một cột lớn của các dòng bộ nhớ cache, các bit chỉ mục cho bạn biết hàng nào bạn cần xem xét cho dữ liệu của mình. (bit 4-15 trong ví dụ này)
3. Tất cả các bit khác là các bit TAG. Các bit này được lưu trữ trong kho lưu trữ dữ liệu bạn lưu trữ trong bộ nhớ cache và chúng tôi so sánh các bit tương ứng của yêu cầu bộ nhớ cache với những gì chúng tôi đã lưu trữ để tìm hiểu xem dữ liệu chúng tôi đang lưu vào bộ nhớ cache có phải là dữ liệu được yêu cầu hay không.

Số bit bạn sử dụng cho chỉ số này log_base_2 (number_of_cache_lines) [nó thực sự số lượng các bộ, nhưng trong một bộ nhớ cache ánh xạ trực tiếp, có cùng một số đường dây và bộ]

Answer 2

Một bộ nhớ cache được ánh xạ trực tiếp giống như một bảng có các hàng cũng được gọi là dòng bộ nhớ cache và ít nhất 2 cột một cho dữ liệu và một cột cho các thẻ.

Đây là cách hoạt động: Quyền truy cập đọc vào bộ nhớ đệm chiếm phần giữa của địa chỉ được gọi là chỉ mục và sử dụng nó làm số hàng. Dữ liệu và thẻ được tra cứu cùng một lúc. Tiếp theo, thẻ cần được so sánh với phần trên của địa chỉ để quyết định xem dòng có thuộc cùng một dải địa chỉ trong bộ nhớ và hợp lệ hay không. Đồng thời, phần dưới của địa chỉ có thể được sử dụng để chọn dữ liệu được yêu cầu từ dòng bộ nhớ cache (tôi giả sử một dòng bộ nhớ cache có thể chứa dữ liệu cho một số từ).

Tôi nhấn mạnh một chút về truy cập dữ liệu và truy cập thẻ + so sánh xảy ra cùng một lúc, vì đó là chìa khóa để giảm độ trễ (mục đích của bộ nhớ cache). Truy cập ram đường dẫn dữ liệu không cần phải là hai bước.

Lợi thế là đọc cơ bản là tra cứu bảng đơn giản và so sánh.

Nhưng nó được ánh xạ trực tiếp có nghĩa là cho mỗi địa chỉ đọc có chính xác một nơi trong bộ nhớ cache nơi dữ liệu này có thể được lưu trữ.Vì vậy, bất lợi là rất nhiều địa chỉ khác sẽ được ánh xạ tới cùng một địa điểm và có thể cạnh tranh cho dòng bộ nhớ cache này.

Answer 3

Tôi đã tìm thấy một cuốn sách hay ở thư viện đã cung cấp cho tôi lời giải thích rõ ràng mà tôi cần và bây giờ tôi sẽ chia sẻ ở đây trong trường hợp một số sinh viên khác tình cờ gặp chủ đề này trong khi tìm kiếm về bộ nhớ cache.

Cuốn sách này là "Kiến trúc máy tính - Cách tiếp cận định lượng" 3rd edition bởi Hennesy và Patterson, trang 390.

Đầu tiên, hãy ghi nhớ rằng bộ nhớ chính được chia thành các khối cho bộ nhớ cache. Nếu chúng tôi có bộ nhớ cache 64 byte và RAM 1 GB, RAM sẽ được chia thành khối 128 KB (1 GB RAM/64B bộ nhớ cache = 128 KB Kích thước khối).

Từ cuốn sách:

đâu một khối có thể được đặt trong một bộ nhớ cache?

• Nếu mỗi khối chỉ có một nơi nó có thể xuất hiện trong bộ nhớ cache, bộ nhớ cache được cho là trực tiếp ánh xạ. Khối đích được tính bằng công thức này: <RAM Block Address> MOD <Number of Blocks in the Cache>

Vì vậy, giả sử chúng ta có 32 khối RAM và 8 khối bộ nhớ cache.

Nếu chúng ta muốn lưu trữ khối 12 từ RAM vào bộ nhớ cache, khối RAM 12 sẽ được lưu vào khối Cache 4. Tại sao? Bởi vì 12/8 = 1 phần còn lại 4. Phần còn lại là khối đích.

• Nếu một khối có thể được đặt bất cứ nơi nào trong bộ nhớ cache, bộ nhớ cache được cho là liên kết đầy đủ.

• Nếu khối có thể được đặt ở bất kỳ đâu trong một nhóm địa điểm bị hạn chế trong bộ nhớ cache, bộ nhớ cache là đặt liên kết.

Về cơ bản, tập hợp là một nhóm các khối trong bộ nhớ cache. Một khối được ánh xạ đầu tiên lên một tập hợp và sau đó khối có thể được đặt ở bất kỳ vị trí nào bên trong tập hợp.

Công thức là: <RAM Block Address> MOD <Number of Sets in the Cache>

Vì vậy, chúng ta hãy giả sử chúng ta có 32 khối bộ nhớ RAM và một bộ nhớ cache chia thành 4 bộ (mỗi bộ có hai khối, có nghĩa là 8 khối trong tổng số). Bằng cách này thiết lập 0 sẽ có khối 0 và 1, thiết lập 1 sẽ có khối 2 và 3, và như vậy ...

Nếu chúng ta muốn lưu trữ khối RAM 12 vào bộ nhớ cache, khối RAM sẽ được lưu trữ trong Các khối bộ nhớ cache 0 hoặc 1. Tại sao? Bởi vì 12/4 = 3 phần còn lại 0. Do đó, thiết lập 0 được chọn và khối có thể được đặt ở bất kỳ vị trí nào bên trong thiết lập 0 (có nghĩa là khối 0 và 1).

Bây giờ tôi sẽ quay lại vấn đề ban đầu của mình với địa chỉ.

Khối tìm thấy như thế nào nếu nó nằm trong bộ nhớ cache?

Mỗi khung khối trong bộ nhớ cache có địa chỉ. Chỉ cần để làm cho nó rõ ràng, một khối có cả địa chỉ và dữ liệu.

Địa chỉ khối được chia thành nhiều phần: Thẻ, Chỉ mục và Bù đắp.

Thẻ được sử dụng để tìm khối bên trong bộ nhớ cache, chỉ mục hiển thị tập hợp trong đó khối được đặt (làm cho nó khá dư thừa) và bù đắp được sử dụng để chọn dữ liệu.

Bằng cách "chọn dữ liệu", có nghĩa là trong khối bộ nhớ cache, rõ ràng sẽ có nhiều hơn một vị trí bộ nhớ, độ lệch được sử dụng để chọn giữa chúng.

Vì vậy, nếu bạn muốn có thể tưởng tượng một bảng, đây sẽ là các cột:

TAG | INDEX | OFFSET | DATA 1 | DATA 2 | ... | DATA N 

Tag sẽ được sử dụng để tìm ra khối, chỉ số sẽ hiển thị trong đó thiết lập các khối là, bù đắp sẽ chọn một của các trường bên phải của nó.

Tôi hy vọng rằng sự hiểu biết của tôi về điều này là chính xác, nếu nó không phải là xin vui lòng cho tôi biết.

Answer 4

OK. Đầu tiên hãy hiểu cách CPU tương tác với cache.

Có ba lớp bộ nhớ (rộng rãi nói) - cache (thường làm bằng SRAM chip), main memory (thường làm bằng DRAM chip), và storage (thường từ, như đĩa cứng). Bất cứ khi nào CPU cần bất kỳ dữ liệu nào từ một số vị trí cụ thể, đầu tiên nó sẽ tìm kiếm bộ nhớ cache để xem nó có ở đó hay không. Bộ nhớ cache nằm gần CPU nhất về phân cấp bộ nhớ, do đó thời gian truy cập của nó là ít nhất (và chi phí cao nhất), vì vậy nếu CPU dữ liệu đang tìm kiếm có thể tìm thấy ở đó, nó tạo thành 'hit' và dữ liệu được lấy từ đó để sử dụng bởi CPU. Nếu nó không có ở đó, thì dữ liệu phải được chuyển từ bộ nhớ chính sang bộ nhớ cache trước khi nó có thể được truy cập bởi CPU (CPU thường chỉ tương tác với bộ nhớ đệm), mà phải chịu một hình phạt thời gian.

Vì vậy, để tìm hiểu xem dữ liệu có trong bộ đệm hay không, các thuật toán khác nhau được áp dụng. Một là phương pháp bộ nhớ cache được ánh xạ trực tiếp này. Để đơn giản, hãy giả sử một hệ thống bộ nhớ có sẵn 10 vị trí bộ nhớ cache (được đánh số từ 0 đến 9) và 40 vị trí bộ nhớ chính có sẵn (được đánh số từ 0 đến 39). Bức ảnh này tiền nó lên:

Có 40 vị trí bộ nhớ chính có sẵn, nhưng chỉ tối đa 10 có thể được cung cấp trong bộ nhớ cache. Vì vậy, bây giờ, bởi một số phương tiện, các yêu cầu đến từ CPU cần phải được chuyển hướng đến một vị trí bộ nhớ cache. Điều đó có hai vấn đề:

1. Cách chuyển hướng? Cụ thể, làm thế nào để làm điều đó theo một cách có thể đoán trước sẽ không thay đổi theo thời gian?

2. Nếu vị trí bộ đệm đã được lấp đầy với một số dữ liệu, yêu cầu đến từ CPU phải xác định địa chỉ mà từ đó nó yêu cầu dữ liệu giống với địa chỉ có dữ liệu được lưu trữ ở vị trí đó.

Trong ví dụ đơn giản của chúng tôi, chúng tôi có thể chuyển hướng bằng một logic đơn giản. Do chúng tôi phải lập bản đồ 40 vị trí bộ nhớ chính được đánh số serially từ 0 đến 39 đến 10 vị trí bộ nhớ cache được đánh số từ 0 đến 9, vị trí bộ nhớ cache cho vị trí bộ nhớ n có thể là n%10. Vì vậy, 21 tương ứng với 1, 37 tương ứng với 7, v.v. Điều đó trở thành chỉ số .

Nhưng 37, 17, 7 tất cả tương ứng với 7. Vì vậy, để phân biệt giữa chúng, hãy đến thẻ . Vì vậy, giống như chỉ mục là n%10, thẻ là int(n/10). Vì vậy, bây giờ 37, 17, 7 sẽ có cùng chỉ mục 7, nhưng các thẻ khác nhau như 3, 1, 0, v.v ... Đó là, ánh xạ có thể được xác định hoàn toàn bởi hai thẻ dữ liệu và chỉ mục.

Vì vậy, bây giờ nếu một yêu cầu đến cho vị trí địa chỉ 29, sẽ chuyển thành thẻ 2 và chỉ mục của 9. Chỉ mục tương ứng với số vị trí bộ nhớ cache, vì vậy vị trí bộ nhớ cache không. 9 sẽ được truy vấn để xem nó có chứa bất kỳ dữ liệu nào không và nếu có, nếu thẻ được liên kết là 2. Nếu có, đó là một lần truy cập CPU và dữ liệu sẽ được tìm nạp từ vị trí đó ngay lập tức. Nếu nó trống, hoặc thẻ không phải là 2, nó có nghĩa là nó chứa dữ liệu tương ứng với một số địa chỉ bộ nhớ khác chứ không phải 29 (mặc dù nó sẽ có cùng chỉ mục, có nghĩa là nó chứa dữ liệu từ địa chỉ như 9, 19, 39, v.v.) Vì vậy, nó là một lỗi CPU, và dữ liệu từ vị trí số. 29 trong bộ nhớ chính sẽ phải được tải vào bộ nhớ cache tại vị trí 29 (và thẻ thay đổi thành 2, và xóa bất kỳ dữ liệu nào đã có trước đó), sau đó nó được lấy bởi CPU.