Kiến trúc và tổ chức máy tính - Chương 4: Bộ nhớ máy tính

bangtqh@utc2.edu.vn KIẾN TRÚC VÀ TỔ CHỨC MÁY TÍNH (Computer Organization and Architecture) Chương 4 Bộ nhớ máy tính bangtqh@utc2.edu.vn Nội dung 1. Tổng quan về hệ thống nhớ – Đặc trưng của hệ thống nhớ – Phân cấp hệ thống nhớ 2. Bộ nhớ bán dẫn – Phân loại – Tổ chức chip nhớ – Thiết kế module nhớ bán dẫn 3. Bộ nhớ chính 4. Bộ nhớ đệm nhanh – Nguyên tắc chung của cache – Các phương pháp ánh xạ 5. Bộ nhớ ngoài 2Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn 4.1. Tổng quan về hệ thống nhớ
Các đặc trưng của hệ thống nhớ – Vị trí (location) • Bên trong Bộ xử lý: Các thanh ghi • Bộ nhớ trong: Bộ nhớ chính; Bộ nhớ cache • Bộ nhớ ngoài: Đĩa từ, băng từ, Đĩa quang – Dung lượng (capacity) • Độ dài ngăn nhớ (tính bằng bit: 16 bit, 32 bit, 64bit) • Số lượng ngăn nhớ – Đơn vị truyền (unit of transfer) • Truyền theo từ nhớ (word) • Truyền theo khối nhớ (block) 3Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn 4.1. Tổng quan về hệ thống nhớ (tt)
Các đặc trưng (tiếp) – Phương pháp truy nhập (access method) • Truy nhập tuần tự (băng từ) • Truy nhập trực tiếp (đĩa từ, đĩa quang) • Truy nhập ngẫu nhiên (bộ nhớ trong) • Truy nhập liên kết (bộ nhớ cache) – Kiểu vật lý của bộ nhớ (physical type) • Bộ nhớ bán dẫn • Bộ nhớ từ: băng từ và đĩa từ • Bộ nhớ quang: đĩa quang – Các đặc trưng vật lý (physical characteristics) • Bộ nhớ khả biến / không khả biến • Bộ nhớ xóa được / không xóa được 4Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn
Các đặc trưng (tiếp) – Hiệu năng • Thời gian truy nhập • Chu kỳ nhớ • Tốc độ truyền 4.1. Tổng quan về hệ thống nhớ (tt) 5Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Phân cấp hệ thống nhớ
Từ trái sang phải:  Dung lượng tăng dần  Tốc độ trao đổi dữ liệu giảm dần  Giá thành /1 bit giảm dần  Tần xuất truy cập bởi CPU giảm dần  Mức trái chứa 1 phần dữ liệu của mức phải 6 Tập thanh thi Cache L1 Cache L2 Bộ nhớ chính Bộ xử lý Bộ nhớ ngoài Bộ nhớ mạng Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn 4.2. Bộ nhớ bán dẫn
Phân loại bộ nhớ bán dẫn 7 Kiểu bộ nhớ Tiêu chuẩn Khả năng xóa Cơ chế ghi Khả biến Read Only Memory (ROM) Bộ nhớ chỉ đọc Không xóa được Mặt nạ Không Programmable ROM (PROM) Bằng điện Erasable PROM (EPROM) Hầu như chỉ đọc Bằng tia cực tím Electrically Erasable PROM (EEPROM) Bằng điện từng byte Flash memory Bộ nhớ Đọc-Ghi Bằng điện từng khối Random Access Memory (RAM) Bằng điện từng byte Có Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn ROM (Read Only Memory)
Bộ nhớ không khả biến
Lưu trữ các thông tin: – Thư viện các chương trình con – Các chương trình điều kiển hệ thống – Các bảng chức năng – Vi chương trình 8Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Các kiểu ROM
ROM mặt nạ (ROM cố định): – Thông tin được ghi ngay khi sản xuất – Rất đắt
PROM (Programmble ROM): – Khi sản xuất chưa ghi dữ liệu – Cần thiết bị chuyên dùng để ghi bằng chương trình, chỉ ghi được một lần
EPROM (Erasable PROM): – Khi sản xuất chưa ghi dữ liệu – Cần thiết bị chuyên dụng để ghi bằng chương trình, ghi được nhiều lần – Trước khi ghi lại, phải xóa bằng tia cực tím 9Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Các kiểu ROM (tt)
EEPROM (Electrically Erasable PROM): – Có thể ghi theo từng byte – Xóa bằng điện – Ghi lâu hơn đọc
Flash memory (bộ nhớ cực nhanh) – Ghi theo khối – Xóa bằng điện 10Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn RAM (Random Access Memory)
Bộ nhớ đọc / ghi
Khả biến
Lưu trữ thông tin tạm thời
Có hai loại RAM: – SRAM (Static RAM) – DRAM (Dynamic RAM) 11Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Các kiểu RAM (tt)
SRAM (Ram tĩnh) – Các bit được lưu trữ bằng các Flip-Flop – Không cần mạch làm tươi – Cấu trúc phức tạp hơn DRAM – Dung lượng nhỏ – Tốc độ nhanh hơn DRAM – Đắt hơn DRAM – Dùng làm bộ nhớ cache 12Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Các kiểu RAM
DRAM (Ram động) – Các bit được lưu trữ trên tụ điện → cần phải có mạch làm tươi – Cấu trúc đơn giản – Dung lượng lớn – Tốc độ chậm hơn SRAM – Rẻ hơn SRAM – Dùng làm bộ nhớ chính
DRAM có nhiều loại – SDR DRAM (Single Data Rate DRAM) – DDR DRAM (Double Data Rate DRAM) 13Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Các kiểu DRAM
SD DRAM (Single Data Rate DRAM) – Truy xuất đồng bộ với xung đồng hồ
DDR DRAM (Double Data Rate SDRAM) – DDR2 – DDR3
RDRAM (Rambus DRAM) 14Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Tổ chức chip nhớ Chän §iÒu khiÓn D÷ liÖu vµo Chän §iÒu khiÓn D÷ liÖu ra ¤ nhí ¤ nhí a) Ghi b) §äc 15
Ô nhớ là phần tử nhớ được 1 bit thông tin
Các tín hiệu: • Tín hiệu chọn được gửi đến để chọn ô nhớ • Tín hiệu điều khiển chỉ thị việc ghi hay đọc • Tín hiệu thứ ba là đường dữ liệu Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Tổ chức chip nhớ (tt)
Sơ đồ cơ bản của chip nhớ 16 Chip nhớ 2n x m bit D0 D1 Dm - 1 A0 A1 An - 1 CS RD WR . . . . . . . . Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Các tín hiệu của chip nhớ
Các đường địa chỉ: A0 ÷ An - 1 → có 2n ngăn nhớ.
Các đường dữ liệu: D0 ÷ Dm - 1 → độ dài ngăn nhớ là m bit.
Dung lượng chip nhớ = 2n x m bit
Các đường điều khiển: – Tín hiệu chọn chip: CS (Chip Select) – Tín hiệu điều khiển đọc: RD / OE – Tín hiệu điều khiển ghi: WR / WE
Các tín hiệu tích cực ở mức 0 17Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Tổ chức của DRAM
Dùng n đường địa chỉ dồn kênh → cho phép truyền 2n bit địa chỉ
Tín hiệu chọn địa chỉ hàng RAS (Row Address Select)
Tín hiệu chọn địa chỉ cột CAS (Column Address Select)
Dung lượng của DRAM: 22n x m bit
Ví dụ – DRAM có 14 chân địa chỉ dồn kênh, 8 chân dữ liệu  dung lượng = 228 x 8 bit = 28 x 220 x 8 = 256 MB x 8 bit 18Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn VD: chip 16MB DRAM (4M x 4 bit) 19Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Các chip nhớ (nhìn bên ngoài) 20Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Thiết kế modul nhớ bán dẫn
Dung lượng chip nhớ là 2n x m bit
Cần thiết kế để tăng dung lượng: – Tăng độ dài từ nhớ (tăng m) – Tăng số lượng ngăn nhớ (tăng n) – Kết hợp cả hai loại (tăng m và n) 21Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Thiết kế tăng độ dài từ nhớ Ví dụ 1
Cho chip nhớ SRAM 4K x 4 bit
Hãy thiết kế module nhớ 4K x 8 bit Giải
Chip nhớ 4K x 4 bit = 4 x 210 x 4 bit = 212 x 4 bit
Chip nhớ có – 12 đường địa chỉ – 4 đường dữ liệu
Module nhớ cần thiết kế có – 12 đường địa chỉ – 8 đường dữ liệu 22Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Ví dụ 1 (tiếp) Khi CS = 0  cả 2 chip cùng làm việc WE, OE chung nhau  Cả 2 chip cùng ghi, cùng đọc 23Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Thiết kế tăng độ dài từ nhớ (tt) Ví dụ 2
Cho chip nhớ SRAM 8K x 8 bit
Hãy thiết kế module nhớ 8K x 32 bit Giải: ???
Chip nhớ 8K x 8 bit = 810 x 8 bit = 213 x 8 bit
Chip nhớ sẽ có – 13 đường địa chỉ – 8 đường dữ liệu
Module nhớ cần thiết kế có – 13 đường địa chỉ – 32 đường dữ liệu 24Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Tăng độ dài từ nhớ tổng quát
Cho chip 2n x m bit
Thiết kế module nhớ 2n x (k.m) bit
Giải: – Dùng k chip nhớ 2n x m – Các đường CS, WE, OE đấu chung tất cả các chip – Đường dữ liệu mỗi chip sẽ chiếp 1 đoạn trong chip kết quả 25Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Thiết kế tăng số lượng ngăn nhớ Ví dụ 3:
Cho chip nhớ SRAM 4K x 8 bit
Hãy thiết kế module nhớ 8K x 8 bit Giải
Chip nhớ 4K x 8 bit = 4 x 210 x 8 bit = 212 x 8 bit
Chip nhớ có – 12 đường địa chỉ – 8 đường dữ liệu
Module nhớ cần thiết kế có dung lượng = 213 x 8 bit – 13 đường địa chỉ – 8 đường dữ liệu 26Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Ví dụ 3 (tt) 27Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Tăng số lượng ngăn nhớ tổng quát
Cho chip nhớ 2n x m bit
Hãy thiết kế module nhớ 2k+n x m bit Giải: Ghép nối 2k chip và dùng bộ giải mã k:2k (k2k) 28Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Bộ giải mã 24 và 3 8 29 A Y0 B Y1 C Y2 Y3 Y4 Y5 Y6 Y7 CS Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Bài tập thiết kế module nhớ 1. Tăng số lượng từ nhớ gấp 4 lần – Cho chip nhớ SRAM 4K x 8 bit – Thiết kế module nhớ 16K x 8 bit 2. Tăng số lượng từ nhớ gấp 8 lần – Cho chip nhớ SRAM 4K x 8 bit – Thiết kế module nhớ 32K x 8 bit 30Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Thiết kế module nhớ tăng hỗn hợp
Tăng cả về số lượng ngăng nhớ và độ dài từ nhớ Ví dụ: – Cho chip nhớ SRAM: 8K x 4 bit – Hãy thiết kế modul nhớ 16K x 8 bit Giải: – Dung lượng chip nhớ: 213 x 4 bit – Chip nhớ có: 13 đường địa chỉ (A0 ÷ A12), 4 đường dữ liệu (D0 ÷ D3) – Modul nhớ cần có: 14 đường địa chỉ (A0 ÷ A13), 8 đường dữ liệu (D0 ÷ D7) 31Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Ví dụ (tt) 32 A0÷A12 D0÷D3 CS WE OE A0÷A12 D0÷D3 CS WE OE A0÷A12 D3÷D0 CS WE OE A0÷A12 D3÷D0 CS WE OE A Y0 G Y1 A12÷A0 WE OE A13 CS D7÷D0 D7÷D0 Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Lời giải tổng quát
Bài toán tăng số lượng và độ dài tổng quát: – Cho chip nhớ 2n x m bit – Cần ghép nối modul nhớ: 2p+n x (q.m) bit ⇒ Cần ghép nối q.2p chip thành 2p bộ, mỗi bộ q chip và phải dùng bộ giải mã p: 2p (p → 2p) 33Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Bài tập
Cho chip nhớ SRAM 4K x 4 bit
Hãy thiết kế module nhớ 8K x 8 bit Làm ra giấy và nộp lại vào cuối buổi 34Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn 4.3. Bộ nhớ chính
Các đặc trưng cơ bản – Chứa các chương trình đang thực hiện và các dữ liệu đang được sử dụng – Tồn tại trên mọi hệ thống máy tính – Được đánh địa chỉ trực tiếp bởi CPU: có nhiều ngăn nhớ, mỗi ngăn nhớ được gán một địa chỉ xác định – Việc quản lý logic BNC tùy thuộc vào từng HĐH – Về nguyên tắc, người lập trình có thể can thiệp trực tiếp vào toàn bộ BNC của máy tính 35Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn 4.3. Bộ nhớ chính (tt)
Tổ chức bộ nhớ đan xen – Độ rộng của bus dữ liệu để trao đổi với bộ nhớ thường là bội số của 2 (m = 8, 16, 32, 64, ... bit) – Các ngăn nhớ tổ chức theo byte  tổ chức vật lý khác nhau. Ví dụ: m= 8 bit  1 băng nhớ tuyến tính 36 Bus hệ thống Bank nhớĐịa chỉ 0 1 2 3 n . . . . . D7 ÷ D0 Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn 37 m = 16 bit  2 băng nhớ đan xen Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn m = 32 bit, 4 băng đan xen 38Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn m=64 bit, 8 băng nhớ đan xen 39Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn 4.4. Bộ nhớ đệm nhanh (cache)
Nguyên tắc chung
Các kỹ thuật ánh xạ địa chỉ
Các thuật toán thay thế
Hoạt động của cache
Bài tập 40Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Nguyên tắc chung 41
Cache có tốc độ nhanh hơn bộ nhớ chính
Cache được đặt giữa CPU và bộ nhớ chính nhằm tăng tốc độ truy nhập bộ nhớ của CPU
Cache có thể được đặt trên chip CPU Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Ví dụ về thao tác của cache
CPU yêu cầu nội dung của ngăn nhớ
CPU kiểm tra trên cache với dữ liệu này cần truy xuất – Nếu có: CPU nhận dữ liệu từ cache – Nếu không có: Đọc Block nhớ chứa dữ liệu từ bộ nhớ chính vào cache  tiếp theo truyền dữ liệu từ cache vào CPU 42Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Các khái niệm
Cache hit, cache miss: – Cache hit (trúng cache): khi CPU truy nhập một từ nhớ mà từ nhớ đó đang có trong cache. – Cache miss (trượt cache): khi CPU truy nhập một từ nhớ mà từ nhớ đó không có trong cache.
Nguyên lý định vị tham số bộ nhớ: – Định vị về thời gian: Một mục thông tin vừa được truy nhập thì có xác suất lớn là ngay sau đó nó được truy nhập lại. – Đinh vị về không gian: Một mục thông tin vừa được truy nhập thì có xác suất lớn là ngay sau đó các mục lân cận sẽ được truy nhập. 43Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Cấu trúc chung của cache
Trao đổi thông tin giữa Cache và BNC: – BNC được chia thành các Block nhớ – Cache được chia thành các Line nhớ – Kích thước Line bằng kích thước Block ⇒ Số lượng Line << Số lượng Block của BNC
Mỗi Line trong cache được gắn thêm một Tag để xác định Block nào (của BNC) đang ở trong Line 44Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Cấu trúc chung của cache (tt)
Một số block của bộ nhớ chính được nạp vào các Line của cache
Nội dung Tag sẽ cho biết block nào của BNC đang được chứa ở line đó
Khi CPU truy cập (đọc/ghi) một từ nhớ có 2 khả năng xảy ra: – Từ nhớ có trong cache (cache hit) – Từ nhớ không có trong cache (cache miss)
Vì số Line của cache ít hơn số block của BNC nên cần có một giải thuật ánh xạ dữ liệu từ BNC vào cache 45Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Cấu trúc chung của cache (tt) BXL Tag D÷ liÖu Bé nhí cache Bé nhí chÝnh L0 L1 Lm-2 Lm-1 B0 B1 B2 Bp-2 Bp-1 . . . . . . . . . . . . . . 46Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Các kỹ thuật ánh xạ địa chỉ BNCCache
Ánh xạ trực tiếp (direct mapping)
Ánh xạ liên kết toàn phần (fully associative mapping)
Ánh xạ liên kết tập hợp (set associative mapping) 47Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Ánh xạ trực tiếp (direct mapping)
Mỗi Block của BNC chỉ được ánh xạ vào một Line duy nhất: i = j mod m – i: số hiệu Line của Block khi ánh xạ vào trong cache – j: số hiệu Block trong BNC – m: số lượng Line trong cache
Cụ thể: – B0 → L0 Bm → L0 . . . – B1 → L1 Bm+1 → L1 . . . – . . . . . . – Bm-1 → Lm-1 B2m-1 → Lm-1 . . . 48Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Ánh xạ trực tiếp (tt)
Như vậy: L0 : B0, Bm, B2m, ..., Bnm L1 : B1, Bm+1, B2m+1, ..., Bnm+1 . . . . . . . Lm-1: Bm-1, B2m-1, B3m-1, ..., B(n+1)m-1
Khi đó: Địa chỉ CPU phát ra gồm 3 thông tin – Số hiệu ô nhớ trong Block (nằm trong Line của cahe) – Số hiệu Line trong cache – Số hiệu của Block nào đang nằm trong cache 49 Tag Line Word n3 bit n1 bitn2 bit Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Ánh xạ trực tiếp (tt)  Word: xác định byte nhớ trong Line (block) BNC ⇒ Kích thước 1 line = 2n1  Line: Xác định số hiệu Line trong cache ⇒ Có 2n2 Line trong cache  Tag: số bít còn lại là n3 = N – n2 – n1 ⇒ BNC chứa 2n3 ô nhớ 50 Tag Line Word n3 bit n1 bitn2 bit Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Ví dụ 1
Cho máy tính có dung lượng nhớ – RAM = 128 MB, cache = 256 KB, line = 32 byte, – Độ dài ngăn nhớ = 1 byte. Tìm số bit của các trường địa chỉ ánh xạ trực tiếp vào cache Giải: Ta có: – BNC = 128 MB = 27 * 220 byte = 227 byte  N = 27 – Cache = 256 KB = 28 * 210 byte = 218 byte – Line = 32 byte = 25 byte  số bit trường word là n3 = 5 – Số Line trong cache: 218/25 = 213  số bit trường line n2 = 13 – Số bit của trường Tag là n3 = N – (n2 – n1) = 9 51 5139 Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Ví dụ 2
Cho máy tính có : – RAM = 256 MB, cache = 64 KB, line = 16 byte, – Độ dài ngăn nhớ = 4 byte. Tìm dạng địa chỉ do BXL phát ra?
Giải: Ta có: – RAM=256MB = 228 byte = 228/22 = 226 ng/nhớ  N=26 – Cache = 64 KB = 216 byte = 216/22 = 214 ng/nhớ – Line = 16 byte =24/22 = 22 ng/nhớ  n1 = 2 – Số Line trong cache: 214/22 = 212  n2 = 12 – Số bit của phần Tag: N - 12 - 2 = 12, n3= 12 52 21212 Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Sơ đồ thực hiện Chương 4 - Bộ nhớ máy tính 53 WordLine bangtqh@utc2.edu.vn Nhận xét
Ưu điểm: – Dễ thực hiện, vì một Block được ánh xạ cố định vào một Line ⇒ không cần thuật toán chọn Line. – Thiết kế mạch đơn giản.
Nhược điểm: – Tỉ lệ cache hit thấp. Chương 4 - Bộ nhớ máy tính 54 bangtqh@utc2.edu.vn Ánh xạ liên kết toàn phần
Mỗi Block trong bộ nhớ chính (BNC) được ánh xạ vào một Line bất kỳ trong Cache
Khi đó, địa chỉ do BXL phát ra có dạng:
Để kiểm tra xem 1 block có trong cache hay không, phải đồng thời kiểm tra tất cả các tag của các line trong cache  phức tạp hơn – Word: xác định ngăn nhớ trong Block  Block có 2w ngăn nhớ – Tag: xác định Block đang ở trong Line  Số lượng Block: 2s  Dung lượng BNC: 2s + w ngăn nhớ Chương 4 - Bộ nhớ máy tính 55 Tag Word s bit w bit bangtqh@utc2.edu.vn Sơ đồ thực hiện 56Chương 4 - Bộ nhớ máy tính bangtqh@utc2.edu.vn Nhận xét
Ưu điểm: – Tỉ lệ cache hit cao hơn ánh xạ trực tiếp vì một Block được phép vào một Line bất kỳ.
Nhược điểm: – Thiết kế mạch tương đối phức tạp, thể hiện ở mạch so sánh. Chương 4 - Bộ nhớ máy tính 57 bangtqh@utc2.edu.vn Ánh xạ liên kết tập hợp
Cache được chia thành nhiều Set, mỗi Set gồm nhiều Line liên tiếp
Một Block của BNC chỉ được ánh xạ vào một Set duy nhất trong cache, nhưng được ánh xạ vào Line bất kỳ trong set đó: i = j mod v – i: số hiệu Set trong cache – j: số hiệu Block trong BNC – v: số lượng Set trong cache Chương 4 - Bộ nhớ máy tính 58 bangtqh@utc2.edu.vn Ánh xạ liên kết tập hợp (tt)
Khi đó, địa chỉ do BXL phát ra gồm: – Word: xác định số hiệu ngăn nhớ trong Block  Block (Line) có 2w ngăn nhớ – Set: xác định số hiệu Set trong cache  Cache có 2d Set – Tag: xác định Block nào đang ở trong Line  BNC chứa 2s + w ngăn nhớ Chương 4 - Bộ nhớ máy tính 59 Tag Set Word s - d bit w bitd bit bangtqh@utc2.edu.vn Ví dụ 1
Cho máy tính có dung lượng: – BNC = 512 MB, cache = 128 KB, line = 32 byte, – Set = 8 Line, độ dài ngăn nhớ = 1 byte. Tìm dạng địa chỉ do BXL phát ra?
Giải: Ta có: – BNC = 512 MB = 229 byte; Cache = 128 KB = 217 byte – Line = 25 byte ⇒ w = 5 – Dung lượng Set: 23 * 25 = 28 byte  số Set trong Cache: 217/28 = 29  d = 9 – Số bit của phần Tag: 29 - 9 - 5 = 15  s - d = 15 Chương 4 - Bộ nhớ máy tính 60 5915 bangtqh@utc2.edu.vn Ví dụ 2
Cho máy tính có dung lượng: – BNC = 256 MB, cache = 128 KB, line = 64 byte, – Set = 4 Line, độ dài ngăn nhớ = 4 byte. T×m d¹ng ®Þa chØ do BXL ph¸t ra?
Giải: ta có – BNC = 228 byte = 228/22 = 226 ng/nhớ – Cache = 217 byte = 217/22 = 215 ng/nhớ – Line = 26/22 = 24 ng/nhớ ⇒ w = 4 – Dung lượng Set: 22 * 24= 26 số lượng Set: 215/26 = 29  d = 9 – Số bit của phần Tag: 26 - 9 - 4 = 13, s - d = 13 Chương 4 - Bộ nhớ máy tính 61 4913 bangtqh@utc2.edu.vn Sơ đồ thực hiện Chương 4 - Bộ nhớ máy tính 62 bangtqh@utc2.edu.vn Nhận xét
Ưu điểm: – Tỉ lệ cache hit cao vì một Block được phép vào một Line bất kỳ trong Set, và dễ so sánh. – Đây là kỹ thuật ánh xạ tốt nhất trong 3 kỹ thuật.
Nhược điểm : – Thiết kế mạch phức tạp. Chương 4 - Bộ nhớ máy tính 63 bangtqh@utc2.edu.vn Các thuật toán thay thế Block trong cache
Khi CPU truy cập 1 thông tin không có trong cache  nạp block trên BNC chứa thông tin đó vào cache (thay thế block cũ đang ở trong cache)
Kỹ thuật ánh xạ trực tiếp  chỉ 1 cách nạp block vào line cố định trong cache  không cần thuật giải để nạp
Hai kỹ thuật ánh xạ liên kết (tập hợp, toàn phần):  cần có giải thuật lựa chọn thay thế Chương 4 - Bộ nhớ máy tính 64 bangtqh@utc2.edu.vn Các thuật toán thay thế Block trong cache
4 Thuật toán thay thế – Random: thay ngẫu nhiên một Block cũ nào đó Dễ thực hiện, nhanh nhất, tỉ lệ cache hit thấp. – FIFO (First In - First Out) • Ánh xạ liên kết toàn phần: thay Block đã tồn tại lâu nhất trong toàn cache • Ánh xạ liên kết tập hợp: thay Block đã tồn tại lâu nhất trong set  Phương pháp này có tỉ lệ cache hit không cao – LFU (Least Frequently Used): thay Block có số lần dùng ít nhất  tỉ lệ cache hit tương đối cao – LRU (Least Recently Used): thay Block có khoảng thời gian dài nhất không được dùng  tỉ lệ cache hit cao Chương 4 - Bộ nhớ máy tính 65 bangtqh@utc2.edu.vn Phương pháp truy cập cache
Đọc: – Nếu cache hit: đọc ngăn nhớ từ cache – Nếu cache miss: thay Block ⇒ cache hit
Ghi: – Nếu cache hit: có 2 phương pháp: • Write through: ghi dữ liệu vào cả cache và cả BNC ⇒ không cần thiết, tốc độ chậm, mạch đơn giản. • Write back: chỉ ghi vào cache, khi nào Block (trong cache) được ghi bị thay đi  ghi vào BNC ⇒ tốc độ nhanh, mạch phức tạp. – Nếu cache miss: thay Block ⇒