Bộ nhớ Cache : Cấu trúc Cache, Thuật toán thay thế (phương pháp thay thế dòng của tập trong Cache)

Trả lời:

1. Cấu trúc Cache

HinhAnh

- Cache ghi nhớ  1 tập hợp Ai các địa chỉ của BNC và các từ dữ liệu M(Ai) tương ứng của tập hợp Ai

- Dữ liệu trao đổi giữa cache và BNC được nhóm theo các khối dữ liệu

- Các dong cất giữ trong cache ko có địa chỉ riêng mà chúng được tham chiếu tại địa chỉ của chúng lưu vào trong BNC

- Địa chỉ các dòng trong cache được sắp xếp địa chỉ

- Nội dung của mảng là bản sao của tập các khối nhớ liên tiếp nhau kèm theo địa chỉ của BNC

2. Thuật toán thay thế (phương pháp thay thế dòng của tập trong Cache)

B1: CPU yêu cầu lệnh/d.liệu lưu trữ trong địa chỉ “a”

B2: Khi đó nội dung từ đ.chỉ “a” không có bên trong BN Cache, CPU phải mang nó về trực tiếp từ BN RAM.

B3: Bộ phận đ.khiển Cache  tải 1 hàng (thông thường 64 byte) bắt đầu từ đ.chỉ “a” và bên trong BN Cache. Điều đó nhiều hơn d.liệu CPU đã yêu cầu, do đó nếu chương trình tiếp tục chạy tuần tự (có nghĩa là yêu cầu đ.chỉ a + 1), lệnh/d.liệu tiếp theo CPU sẽ yêu cầu đã đc tải trong BN Cache.

B4: Mạch điện gọi là PreFetch tải nhiều v.trí d.liệu hơn sau dòng sau, có nghĩa là bắt đầu những nội dung tải từ địa chỉ a + 64 vào BN Cache.

Nếu chương trình thường chạy tuần tự thì CPU không bao h cần lấy d.liệu trực tiếp từ BN RAM về, nhũng lệnh và d.liệu CPU yêu cầu sẽ thường nằm trong BN Cache trc khi CPU hỏi tới chúng.

Nếu chương trình thường chạy tuần tự thì CPU không bao giờ cần lấy dữ liệu trực tiếp từ bộ nhớ RAM về (ngoại trừ việc tải lệnh đầu tiên), những lệnh và dữ liệu CPU yêu cầu sẽ thường nằm trong bộ nhớ Cache trước khi CPU hỏi tới chúng.

Tuy nhiên những chương trình lại không chạy như vậy, chúng sẽ thường nhảy từ vị trí bộ nhớ này tới vị trí bộ nhớ khác. Thách thức lớn nhất của Bộ phận điều khiển Cache chính là cố gắng phỏng đoán CPU sẽ nhảy tới địa chỉ nào, để tải nội dung của địa chỉ đó vào bên trong bộ nhớ Cache trước khi CPU yêu cầu nó để tránh trường hợp CPU phải đi tới bộ nhớ RAM của hệ thống, vì điều đó làm chậm hiệu suất làm việc của toàn bộ hệ thống. Nhiệm vụ này được gọi là Dự đoán rẽ nhánh và những CPU mới đều có đặc điểm này. Những CPU hiện đại có tỉ lệ “hit” ít nhất là 80%, có nghĩa là ít nhất 80% thời gian CPU không cần truy cập trực tiếp tới bộ nhớ RAM của hệ thống và thay thế vào truy cập tới bộ nhớ Cache .

3. Nguyên tắc hoạt động (theo vở chép)

     - Địa chỉ vật lý A từ bộ vxl được gửi đến cache khi bắt đầu chương trình truy cập bộ nhớ thì cache so sánh phần tử của A với tất cả các địa chỉ Ai, nếu có sự trùng thì cache được chọn từ dữ liệu tương ứng với địa chỉ A, tức là M(A). Và nó kết thúc chu trình truy cập bộ nhớ bằng cách truy nhập dữ liệu từ bộ vxl tới bản sao hoặc ngược lại đọc bản sao tới bộ vxl.Nếu ko có sự trùng hợp, cache khởi tạo 1 trình tự với 1 hoặc vài chu trình để nạp bộ địa chỉ tương ứng, địa chỉ A chứa M(A)

    - Cache chia thành 1 số tập  (set)

Vd: set 0->set k-1

   -Mỗi tập có một sô dòng (line)

Vd: line 0->set 0

   - Ko phải mảng chương trình nào cũng được cất toàn bộ vào cache mà chỉ một phần

   - Mảng thông tin của chương trình thuộc cache gọi là hit(trúng đích) và hệ số của hit gọi là hệ số trúng đích,ký hiệu là H,còn mảng  thông tin của chương trình ko thuộc cache goi la miss(trượt đích) và hệ số của miss gọi là hệ số trượt đích,ký hiệu là 1-H

  - Phương pháp thay thế dòng của tập trong cache gọi là thuật toán thay thế bao gồm 1 số phương pháp thay thế sau:

    + tùy ý

    + FIFO

    +ít sử dụng nhất

Từ đó ta có thể tính được thời gian truy xuất trung bình của dòng dữ liệu trong bộ nhớ

ta=Hta1+(1-H)ta2  hay  ta=ta1+(1-H)tb

ta1: thời gian truy xuất cache

ta2 : thời gian truy xuất BNC

tb=ta1-ta2 : thời gian vận chuyển từ BNC đến cache

Cho dòng X = 275 trong BN chính với số lượng các tập trong Cache là k  = 128. Xác định dòng X của BN chính đc xếp vào tập bao nhiêu của BN Cache.

à Dòng 275 sẽ đc xếp như sau : 275/128 = 2 + 19/128, nghĩa là dòng 275 của BN chính đc xếp vào tập 19 trong Cache.