Bài giảng Kiến trúc máy tính - Chương 4: Bộ nhớ Cache - Nguyễn Hằng Phương

che là một dạng khác của bộ nhớ trong 
  Bộ nhớ ngoài bao gồm các thiết bị lưu trữ ngoại vi có thể truy cập 
 vào bộ xử lý thông qua bộ điều khiển I / O 
  Dung lượng 
  Bộ nhớ thường được biểu diễn dưới dạng byte 
  Đơn vị truyền 
  Đối với bộ nhớ trong, đơn vị truyền bằng số lượng đường dây điện 
 đi vào và ra khỏi module bộ nhớ 
Phương pháp truy cập các khối dữ liệu 6 
 Truy cập Truy cập Truy cập 
 Kết hợp 
 tuần tự trực tiếp ngẫu nhiên 
 Bộ nhớ được Mỗi vị trí trong 1 từ được lấy ra 
 Dùng cơ chế 
 tổ chức thành bộ nhớ có một dựa trên 1 phần 
 đọc-ghi chia 
 các đơn vị dữ cơ chế định địa nội dung chứ 
 sẻ 
 liệu - records chỉ riêng không dựa trên 
 địa chỉ của nó 
 Thời gian truy 
 Truy cập phải các block cập vào 1 vị trí mỗi vị trí có cơ 
 thực hiện theo hoặc record nhất định không chế định địa chỉ 
 một dãy tuần có địa chỉ duy đổi, không phụ riêng; thời gian 
 nhất dựa trên thuộc vào chuỗi truy cập không 
 tự các truy cập 
 vị trí thực tế đổi, không phụ 
 trước đó thuộc vị trí hoặc 
 các mẫu truy 
 1 vị trí bất kỳ có 
 Thời gian truy Thời gian truy cập trước 
 cập biến động thể được lựa 
 cập biến chọn ngẫu nhiên, 
 động đánh địa chỉ và 
 truy cập trực tiếp Bộ nhớ cache 
 có thể sử dụng 
 truy cập kết hợp 
 Bộ nhớ chính và 
 một số hệ thống 
 cache là truy 
 cập ngẫu nhiên 
Dung lượng và Hiệu năng: 7 
Hai đặc điểm quan trọng nhất của bộ nhớ 
 Ba tham số hiệu năng được sử dụng: 
 Thời gian truy cập 
 (độ trễ) Chu kỳ bộ nhớ 
 Tốc độ truyền tải 
 • Đối với bộ nhớ truy • Thời gian truy cập cộng 
 cập ngẫu nhiên, nó với thời gian cần trước • Tốc độ truyền dữ 
 là thời gian cần để khi truy cập thứ hai có liệu vào hoặc ra 
 thực hiện 1 thao tác thể bắt đầu khỏi bộ nhớ 
 đọc hoặc ghi • Liên quan đến hệ thống • Đối với bộ nhớ truy 
 • Đối với bộ nhớ truy bus, không liên quan cập ngẫu nhiên, 
 cập không ngẫu bộ xử lý tốc độ truyền tải 
 nhiên, nó là thời gian bằng 1/(chu kỳ) 
 cần để đặt cơ chế 
 đọc-ghi đến vị trí 
 mong muốn 
 8 
+ Bộ nhớ 
 - Các dạng phổ biến nhất: Bộ nhớ bán dẫn, Bộ nhớ bề mặt 
 từ, Bộ nhớ quang, Bộ nhớ quang từ 
 - Với bộ nhớ truy cập ngẫu nhiên, vấn đề quan trọng khi 
 thiết kế là tổ chức hay sự sắp xếp vật lý của các bit để tạo 
 thành các từ word 
 9 
+ Bộ nhớ 
 Một số đặc điểm vật lý quan trọng của lưu trữ dữ liệu: 
  Bộ nhớ khả biến (Volatile memory) 
  Thông tin bị phân rã tự nhiên hoặc bị mất khi nguồn điện tắt 
  Bộ nhớ bất biến (Non-volatile memory) 
  Thông tin một khi đã được ghi thì sẽ không bị hư hỏng cho 
 đến khi được cố tình thay đổi 
  Không cần cấp điện để giữ lại thông tin 
  Bộ nhớ bề mặt từ (Magnetic-surface memories) 
  Bất biến 
  Bộ nhớ bán dẫn (Semiconductor memory) 
  Khả biến hoặc bất biến 
  Bộ nhớ không xoá được (Nonerasable memory) 
  Không thể thay đổi, trừ khi phá hủy các khối lưu trữ 
  Bộ nhớ chỉ đọc (ROM) là bộ nhớ bán dẫn thuộc loại này 
+ 10 
 Phân cấp bộ nhớ 
  Thiết kế bộ nhớ của máy tính cần trả lời ba câu hỏi: 
  How much, how fast, how expensive 
  Cần có sự cân đối giữa dung lượng, thời gian truy cập và chi 
 phí 
  Thời gian truy cập nhanh hơn, chi phí lớn hơn cho mỗi bit 
  Dung lượng lớn hơn, chi phí nhỏ hơn cho mỗi bit 
  Dung lượng lớn hơn, thời gian truy cập chậm hơn 
  Giải pháp cho tình trạng khó xử khi thiết kế bộ nhớ: 
  Không dựa vào một thành phần hoặc công nghệ bộ nhớ 
  Sử dụng một hệ thống phân cấp bộ nhớ 
 11 
+ Bộ nhớ phân cấp 
 - Sơ đồ 
 a. Giảm chi phí cho mỗi bit 
 b. Tăng dung lượng 
 c. Tăng thời gian truy cập 
 dài hơn 
 d. Giảm tần suất truy cập 
 bộ nhớ của bộ vi xử lý 
 + 
2. NGUYÊN LÝ BỘ NHỚ CACHE 
 12 
 Bộ nhớ cache và bộ nhớ chính 13 
BXL kiểm tra 
xem từ có trong 
cache hay 
không: 
- Nếu có, cache 
gửi từ này đến 
BXL (nhanh) 
- Nếu không, 
cache đọc 1 
block trong bộ 
nhớ chính, rồi 
cache gửi word 
đến BXL 
Cấu trúc bộ nhớ chính/cache 14 
 15 
Thao tác đọc 
Cache 
+ 16 
 Tổ chức bộ nhớ cache điển hình 
 17 
3. Các yếu tố khi Thiết kế Cache 
 Table 4.2 Elements of Cache Design 
+ 18 
 Địa chỉ bộ nhớ cache 
 Bộ nhớ ảo 
  Cơ sở cho phép các chương trình định địa chỉ bộ nhớ theo 
 quan điểm logic, không liên quan đến số lượng bộ nhớ 
 chính vật lý có sẵn 
  Khi bộ nhớ ảo được sử dụng, trường địa chỉ trong lệnh 
 chứa địa chỉ ảo 
  Để đọc ra và ghi vào bộ nhớ chính, một khối phần cứng 
 quản lý bộ nhớ (memory management unit - MMU) sẽ 
 dịch từng địa chỉ ảo sang địa chỉ vật lý trong 
 bộ nhớ chính 
+ 
 Cache vật lý 
 và 
 cache logic 
 Ưu điểm? Nhược điểm? 
 20 
 Bảng 4.3 
 Kích 
 thước 
 cache 
 trong 
 một số 
 bộ xử lý 
a, Hai giá trị cách 
nhau bằng dấu / 
là cache lệnh và 
cache dữ liệu. 
b, Cả hai cache 
đều là cache lệnh; 
Không có cache 
dữ liệu. 
 21 
Hàm ánh xạ 
  Bởi vì số dòng (line) của cache ít hơn số khối (block) bộ nhớ 
 chính, cần có một thuật toán ánh xạ các khối bộ nhớ chính 
 vào các dòng bộ nhớ cache 
  Ba kỹ thuật có thể được sử dụng: 
 Trực tiếp Kết hợp Kết hợp Set 
 • Cho phép 1 khối bộ nhớ • Thể hiện ưu điểm 
 • Đơn giản nhất chính được tải vào bất của cả phương pháp 
 kỳ dòng cache nào trực tiếp và kết hợp, 
 • Ánh xạ mỗi khối của 
 • Logic điều khiển cache đồng thời giảm 
 bộ nhớ chính vào 
 diễn giải địa chỉ bộ nhớ nhược điểm 
 một line cache xác bằng trường Tag và 
 định trường Word 
 • Để xác định một khối có 
 ở trong cache không, 
 logic điều khiển cache 
 phải cùng lúc kiểm tra 
 Tag của tất cả các line 
 22 
Ánh xạ trực tiếp 
Hàm ánh xạ: i = j mod m 
trong đó i = số chỉ line cache 
 j = số chỉ block bộ nhớ chính 
 m = tổng số line trong cache 
Tổ chức cache ánh xạ trực tiếp 23 
+ 24 
 Ví dụ 
  Cache 64 Kbyte 
  1 word = 1 byte 
  Block dữ liệu 4 byte (word) 
  Cache gồm 16K = 214 line, mỗi line 4 byte 
  Địa chỉ bộ nhớ 24 bit 
  224 = 16M 
  Bộ nhớ chính 16Mbyte, chia thành 4M block 
 25 
Ví dụ 
 ánh 
 xạ 
 trực 
 tiếp 
+ 26 
 Tổng kết ánh xạ trực tiếp 
  Độ dài địa chỉ nhớ = (s + w) bits 
  Số lượng đơn vị địa chỉ= 2s+w words or bytes 
  Kích thước khối= kích thước line = 2w words or bytes 
  Số khối trong bộ nhớ chính = 2s+ w/2w = 2s 
  Số line trong bộ nhớ cache = m = 2r 
  Kích thước của tag = (s – r) bits 
 27 
 Ánh xạ kết hợp 
Cho phép 1 khối bộ nhớ chính được tải vào bất kỳ dòng cache nào 
 28 
Tổ chức Cache kết hợp 
 29 
Ví dụ 
ánh 
 xạ 
kết 
hợp 
+ 30 
 Tổng kết ánh xạ kết hợp 
  Độ dài địa chỉ = (s + w) bit 
  Số lượng đơn vị địa chỉ = 2s+w word hoặc byte 
  Kích thước block = Kích thước line = 2w word hoặc byte 
  Số lượng block trong bộ nhớ chính = 2s+ w/2w = 2s 
  Số lượng line trong cache = không xác định 
  Kích thước tag = s bit 
 31 
 Ánh xạ kết hợp tập hợp 
 Thể hiện ưu điểm của cả phương pháp trực tiếp và kết hợp 
 đồng thời giảm nhược điểm 
 Cache bao gồm một số set (v) 
 Mỗi set chứa một số line (k) 
 1 khối được ánh xạ vào 1 line bất kỳ trong 1 set nhất định 
 Mối quan hệ: 
  m = v* k 
  i = j modulo v 
 Ví dụ: 1 set có 2 line 
  Ánh xạ kết hợp 2 chiều 
  Một khối có thể nằm trong 1 trong 2 line của 1 set 
+ 
 Ánh xạ 
 Kết hợp 
 tập hợp 
 k chiều 
 33 
Tổ chức cache kết hợp tập hợp k chiều 
34 
+ 35 
 Tổng kết ánh xạ kết hợp tập hợp 
  Độ dài địa chỉ = (s + w) bits 
  Số lượng đơn vị địa chỉ = 2s+w words or bytes 
  Kích thước khối= kích thước line = 2w words or bytes 
  Số khối trong bộ nhớ chính = 2s+w/2w=2s 
  Số line trong set = k 
  Số set = v = 2d 
  Số line trong cache = m=kv = k * 2d 
  Kích thước của cache = k * 2d+w words or bytes 
  Kích thước của tag = (s – d) bits 
 36 
+ Sự kết hợp thay đổi theo kích thước cache 
+ 37 
 Thuật toán Thay thế 
  Khi bộ nhớ cache đã đầy, nếu một khối mới được đưa 
 vào cache, một trong những khối hiện có phải được 
 thay thế 
  Đối với ánh xạ trực tiếp: chỉ có một line có thể cho một 
 khối bất kỳ và không có sự lựa chọn nào khác 
  Đối với các kỹ thuật kết hợp và kết hợp tập hợp, cần có 
 một thuật toán thay thế 
  Để đạt được tốc độ cao, thuật toán phải được thực hiện 
 trong phần cứng 
+ 38 
 Các thuật toán thay thế phổ biến 
  Least recently used (LRU) 
  Hiệu quả nhất 
  Thay thế khối nằm trong cache lâu nhất mà không có tham chiếu đến 
 nó 
  Do triển khai đơn giản, LRU là thuật toán thay thế phổ biến nhất 
  First-in-first-out (FIFO) 
  Thay thế khối đã nằm trong cache lâu nhất 
  Dễ dàng thực hiện như một kỹ thuật vòng đệm hoặc round-robin 
  Least frequently used (LFU) 
  Thay thế khối có ít tham chiếu đến nó nhất 
  Có thể thực hiện bằng cách kết hợp một bộ đếm với mỗi line 
 Chính sách ghi 39 
 Khi một khối trong cache 
 được thay thế, có 2 trường Có hai vấn đề phải đối mặt: 
 hợp cần xem xét: 
Nếu khối cũ trong cache chưa thay Nhiều thiết bị có thể truy cập vào bộ 
 đổi, có thể ghi đè khối mới lên mà nhớ chính 
 không cần ghi khối cũ ra trước 
 Nếu ít nhất 1 thao tác ghi đã được Một vấn đề phức tạp hơn xảy ra khi 
thực hiện trên 1 word trong line của nhiều bộ xử lý được gắn vào cùng 
 cache thì bộ nhớ chính phải được một bus và mỗi bộ xử lý lại có 
 cập nhật bằng cách ghi line của cache cục bộ riêng - nếu một word 
cache ra khối của bộ nhớ trước khi bị thay đổi trong một cache, nó có 
 đưa khối mới vào thể làm mất hiệu lực một word 
 trong các cache khác 
+ 40 
 Write Through 
 và Write Back 
  Write through 
  Kỹ thuật đơn giản nhất 
  Tất cả các thao tác ghi được thực hiện cho bộ nhớ chính cũng 
 như cache 
  Nhược điểm: tạo ra lưu lượng bộ nhớ đáng kể và có thể tạo ra 
 nút cổ chai 
  Write back 
  Giảm ghi bộ nhớ 
  Chỉ cập nhật trong bộ nhớ cache 
  Nhiều phần bộ nhớ chính không hợp lệ. Do đó truy cập bằng các 
 mô-đun I / O chỉ có thể được cho phép thông qua cache 
  Nhược điểm: mạch phức tạp và khả năng có nút cổ chai 
+ 41 
 Ghi vào cache 
  Đầu tiên, giả sử rằng địa chỉ mà ta muốn ghi vào đã được nạp 
 vào cache. Giả sử cache dùng ánh xạ trực tiếp. 
  Nếu ghi 1 giá trị mới vào địa chỉ đó để lưu trữ dữ liệu mới trong cache 
+ 42 
 Write through 
  Ghi để cập nhật cả bộ nhớ cache và bộ nhớ chính 
 + Đơn giản 
 -- Mất ý nghĩa của cache 
+ Write-back 43 
  Ghi dữ liệu vào cache trước, không cập nhật main memory luôn 
  Các lệnh đọc sau đó được phục vụ bởi cache 
  Lưu dữ liệu mới về main memory chỉ khi block trong cache bị thay thế 
Kích thước Line 44 
 Khi 1 khối dữ liệu được lấy ra và đặt trong cache, sẽ thu được không 
 chỉ word mong muốn mà còn 1 số word liền kề 
 Khi kích thước khối tăng, ban đầu tỷ lệ truy cập sẽ tăng do nguyên tắc 
 cục bộ 
 Khi kích thước khối tăng thêm, nhìều dữ liệu hữu ích hơn được đưa 
 vào cache 
 Tỷ lệ truy cập bắt đầu giảm khi khối lớn hơn và xác suất sử dụng 
 thông tin mới truy xuất sẽ thấp hơn xác suất tái sử dụng thông tin đã 
 thay thế 
 2 tác động: 
 1, Khối lớn hơn làm giảm số lượng khối trong 1 cache 
 2, Khi 1 khối lớn hơn, mỗi word thêm vào lại càng khác word yêu cầu 
+ 45 
 Cache nhiều cấp 
  Khi mật độ logic tăng lên, cache có thể nằm trên cùng chip với bộ xử lý 
  Cache trên chip làm giảm hoạt động bus ngoài của bộ xử lý; tăng tốc 
 thời gian xử lý và tăng hiệu năng toàn hệ thống 
  Khi chỉ thị yêu cầu hoặc dữ liệu được tìm thấy trong cache trên chip, 
 truy cập bus được loại bỏ 
  Truy cập bộ nhớ cache trên chip sẽ nhanh hơn đáng kể so với các chu 
 trình bus trạng thái zero-wait 
  Trong giai đoạn này, bus tự do hỗ trợ các lượt truyền khác 
  Cache 2 cấp: Cache bên trong là cấp1 (L1), Cache bên ngoài là cấp 2 
 (L2) 
  Tiết kiệm tiềm năng do sử dụng cache L2 phụ thuộc vào tỷ lệ truy cập 
 vào cả cache L1 và L2 
  Việc sử dụng cache nhiều cấp làm cho các vấn đề thiết kế liên quan đến 
 cache phức tạp hơn, gồm kích thước, thuật toán thay thế, chính sách ghi 
Tỉ lệ truy cập (L1 & L2) cho 8 Kbyte và 16 Kbyte L1 46 
+ 47 
 Cache thống nhất / cache phân chia 
  Phân chia cache trở nên phổ biến: 
  1 dành cho chỉ thị / 1 cho dữ liệu 
  Tồn tại ngang hàng, thường là 2 cache L1 
  Ưu điểm của cache thống nhất: 
  Tốc độ truy cập cao hơn 
  Cân bằng tải chỉ thị và dữ liệu được nạp tự động 
  Chỉ cần thiết kế và thực hiện một bộ nhớ cache 
  Xu hướng: cache phân chia ở L1 và cache thống nhất ở các cấp cao 
 hơn 
  Ưu điểm của cache phân chia: 
  Loại bỏ sự cạnh tranh cache giữa khối tìm nạp / giải mã lệnh và khối 
 thực hiện 
  Quan trọng trong pipelining 
Vấn đề Giải pháp Bộ xử lý 
 48 
Bộ nhớ ngoài chậm hơn bus hệ Thêm cache ngoài dùng công 386 
thống nghệ bộ nhớ nhanh hơn 
Tăng tốc độ xử lý dẫn đến bus ngoài Di chuyển cache ngoài lên 486 
trở thành nút cổ chai đối với truy cập chip, hoạt động ở cùng tốc độ 
cache. với bộ vi xử lý 
cache nội bộ khá nhỏ, do không gian Thêm cache L2 bên ngoài 486 
hạn chế trên chip. bằng công nghệ nhanh hơn 
 bộ nhớ chính 4. 
Có cạnh tranh khi cả khối truy xuất Tạo cache dữ liệu và lệnh Pentium 
lệnh và khối thực thi đồng thời yêu riêng Cache 
cầu truy cập vào cache. Khi đó, khối 
truy xuất bị đình trệ trong khi truy Pentium 
cập dữ liệu của khối thực thi diễn ra 
Tăng tốc độ xử lý dẫn đến bus ngoài Tạo back-side bus chạy ở tốc Pentium Pro 4 
trở thành nút cổ chai cho truy cập độ cao hơn bus ngoài chính 
cache L2 (phía trước). BSB dành riêng 
 cho cache L2. 
 Di chuyển L2 cache lên chip Pentium II 
 xử lý 
Một số ứng dụng xử lý cơ sở dữ liệu Thêm cache L3 bên ngoài Pentium III 
khổng lồ và phải truy cập nhanh Bảng 4.4 
tới lượng lớn dữ liệu. Cache trên Intel 
chip là quá nhỏ. Cache 
 Di chuyển L3 cache lên chip Pentium 4 
 xử lý Evolution 
Sơ đồ khối Pentium 4 49 
 50 
Các chế độ hoạt động Cache Pentium 4 
 Note: CD = 0; NW = 1 là kết hợp không hợp lệ. 
+ Tổng kết 51 
 Bộ nhớ Cache 
 Chương 4 
  Các yếu tố trong thiết kế 
  Đặc điểm của hệ thống bộ 
 cache 
 nhớ 
  Vị trí  Địa chỉ bộ nhớ cache 
  Dung lượng  Kích thước bộ nhớ cache 
  Đơn vị truyền  Hàm ánh xạ 
  Bộ nhớ phân cấp  Thuật toán thay thế 
  How much?  Chính sách ghi 
  How fast?  Kích thước line 
  How expensive?  Số lượng cache 
  Nguyên lý bộ nhớ Cache  Tổ chức cache Pentium 4 
+ 52 
 Câu hỏi chương 4 
 1. Phân biệt truy cập tuần tự, truy cập trực tiếp, và truy cập ngẫu nhiên? 
 2. Mối quan hệ giữa thời gian truy cập, giá bộ nhớ, và dung lượng là gì? 
 3. Tính cục bộ của tham hiếu ảnh hưởng thế nào đến việc sử dụng nhiều cấp độ 
 bộ nhớ? 
 4. Sự khác nhau giữa ánh xạ trực tiếp, ánh xạ kết hợp, và ánh xạ kết hợp tập 
 hợp là gì? 
 5. Đối với cache ánh xạ trực tiếp, một địa chỉ bộ nhớ chính gồm bao nhiêu 
 trường? Là những trường gì? 
 6 Đối với cache kết hợp, một địa chỉ bộ nhớ chính gồm bao nhiêu trường? Là 
 những trường gì? 
 7. Đối với cache kết hợp tập hợp, một địa chỉ bộ nhớ chính gồm bao nhiêu 
 trường? Là những trường gì? 
 8. Phân biệt write through và write back? 
 9. Ưu và nhược điểm của cache phân chia?