Các Phương Pháp Ánh Xạ Giữa Cache Và Bộ Nhớ Chính

bộ nhớ trong. Cách ghi này làm chậm tốc độ chung của hệ thống. Các ngoại vi có thể truy cập bộ nhớ trực tiếp

- Ghi lại: Để đảm bảo tốc độ xử lý của hệ thống, thông tin cần ghi chỉ được ghi vào khối trong cache. Để quản lý sự khác biệt nội dung giữa khối của cache và khối của bộ nhớ trong, một bit trạng thái (Dirty bit hay Update bit) được dùng để chỉ thị. Khi một thao tác ghi vào trong cache, bit trạng thái (Dirty bit hay Update bit) của khối cache sẽ được thiết lập. Khi một khối bị thay thế, khối này sẽ được ghi lại vào bộ nhớ trong chỉ khi bit trạng thái đã được thiết lập. Với cách ghi này, các ngoại vi liên hệ đến bộ nhớ trong thông qua cache.

Khi có một thất bại ghi vào cache thì phải lựa chọn một trong hai giải pháp sau:

- Ghi có nạp: khối cần ghi từ bộ nhớ trong được nạp vào trong cache như mô tả ở trên. Cách này thường được dùng trong cách ghi lại.

- Ghi không nạp: khối được thay đổi ở bộ nhớ trong không được đưa vào cache. Cách này được dùng trong cách ghi đồng thời.

Trong các tổ chức có nhiều hơn một bộ xử lý với các tổ chức cache và bộ nhớ chia sẻ, các vấn đề liên quan đến tính đồng nhất của dữ liệu cần được đảm bảo. Sự thay đổi dữ liệu trên một cache riêng lẻ sẽ làm cho dữ liệu trên các hệ thống cache và bộ nhớ liên quan không đồng nhất. Vấn đề trên có thể được giải quyết bằng một trong các hệ thống cache tổ chức như sau:

- Mỗi bộ điều khiển cache sẽ theo dòi các thao tác ghi vào bộ nhớ từ các bộ phận khác. Nếu thao tác ghi vào phần bộ nhớ chia sẻ được ánh xạ vào cache của nó quản lý, bộ điều khiển cache sẽ vô hiệu hoá sự thâm nhập này. Chiến lược này phụ thuộc vào cách ghi đồng thời trên tất cả các bộ điều khiển cache.

- Một vi mạch được dùng để điều khiển việc cập nhật, một thao tác ghi vào bộ nhớ từ một cache nào đó sẽ được cập nhật trên các cache khác.

- Một vùng nhớ chia sẻ cho một hay nhiều bộ xử lý thì không được ánh xạ lên cache. Như vậy, tất cả các thâm nhập vào vùng nhớ chia sẻ này đều bị thất bại cache.

Các mức Cache

Việc dùng cache trong có thể làm cho sự cách biệt giữa kích thước và thời gian thâm nhập giữa cache trong và bộ nhớ trong càng lớn.

Người ta đưa vào nhiều mức cache:

- Cache mức một (L1 cache): thường là cache trong (on-chip cache; nằm bên trong CPU)

- Cache mức hai (L2 cache) thường là cache ngoài (off-chip cache; cache này nằm bên ngoài CPU).

- Ngoài ra, trong một số hệ thống (PowerPC G4, IBM S/390 G4, Itanium của Intel) còn có tổ chức cache mức ba (L3 cache), đây là mức cache trung gian giữa cache

L2 và một thẻ bộ nhớ.

Bảng 4. 2. Kích thước cache của một số hệ thống


4 4 2 Các phương pháp ánh xạ giữa cache và bộ nhớ chính a Ánh xạ trực tiếp 1

4.4.2. Các phương pháp ánh xạ giữa cache và bộ nhớ chính

a) Ánh xạ trực tiếp (Direct mapping)

- Nguyên lý:

Trong kỹ thuật này, mỗi một Block của bộ nhớ chính chỉ được ánh xạ vào một line duy nhất.

Ánh xạ như sau:

i = j mod m

Trong đó:

i: Số hiệu line trong cache.

j: Số hiệu Block trong bộ nhớ chính. m: Số lượng line trong cache.

Cụ thể như sau:

Như vậy L 0 B 0 B m B 2m B nm L 1 B 1 B m 1 B 2m 1 B nm 1 L 2


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


Lúc này địa chỉ do CPU phát ra có 3 trường:

Trong đó Word Xác định từ nhớ trong Block như vậy kích thước của một 3

Trong đó:

+) Word: Xác định từ nhớ trong Block, như vậy kích thước của một Block là 2w

ngăn nhớ.

+) Line: Xác định line trong cache, như vậy có 2r line trong cache.

+) Tag: Xác định Block nào đang ở trong line Chúng ta có: Dung lượng cache là 2r. 2w = 2r+w.

Số lượng Block của bộ nhớ chính là: 2s do đó dung lượng bộ nhớ chính là: 2s * 2w = 2s+w.

- Bảng ánh xạ:

Ví dụ 4 5 Máy tính có 16MB bộ nhớ chính cache có dung lượng 64KB kích thước 4

Ví dụ 4.5:

Máy tính có 16MB bộ nhớ chính, cache có dung lượng 64KB, kích thước line là 4 byte. Xác định số bit cho mỗi trường của địa chỉ do CPU phát ra (ánh xạ trực tiếp).

Giải:

Chúng ta có:

Bộ nhớ chính = 16MB = 24.210.210 = 224.

Dung lượng cache = 64KB = 26.210 = 216. Kích thước line = 4 Byte = 22.

Do đó số lượng line trong cache là: 216/ 22 = 214. Và số bit cho phần Tag là: 24 - 2 - 14 = 8 (bit) Như vậy địa chỉ do CPU phát ra là:

- Bảng ánh xạ:


Số hiệu line

Số hiệu Block được ánh xạ

0

000000, 010000, . . ., FF0000

1

000001, 010001, . . ., FF0001

.

.

.

.

.

.

3FFF

00FFFC, 01FFFC, . . ., FFFFFC

Có thể bạn quan tâm!

Xem toàn bộ 233 trang tài liệu này.

- Sơ đồ thực hiện:

Hình 4 31 Ánh xạ trực tiếp Nhận xét Ưu điểm Kỹ thuật ánh xạ trực 5

Hình 4. 31. Ánh xạ trực tiếp

*) Nhận xét:

- Ưu điểm: Kỹ thuật ánh xạ trực tiếp thực hiện đơn giản và chi phí không cao.

- Nhược điểm: Một Block chỉ được ánh xạ vào một line nhất định.

Như vây, nếu một chương trình lặp đi lặp lại việc tham chiến đến các ngăn nhớ thuộc các block được ánh xạ vào cùng một line (cùng Tag, theo công thức: block j line j mod m), thì hai block sẽ liên tục thay thế nhau trong Cache và tỷ lệ trúng Cache (Cache hit) sẽ thấp.

b) Ánh xạ liên kết hoàn toàn (Fully Associative Mapping)

Kỹ thuật ánh xạ liên kết hoàn toàn khắc phục nhược điểm trên của Kỹ thuật ánh xạ trực tiếp: Mỗi block của bộ nhớ chính có thể được nạp vào bất kỳ line nào trong Cache.

Khi đó địa chỉ do CPU phát ra gồm hai trường:

Trong đó Word Xác dịnh từ nhớ trong block kích thước của block cũng là của 6

Trong đó:

+ Word: Xác dịnh từ nhớ trong block, kích thước của block (cũng là của line) là 2w.

+ Tag: Xác định block nào đang ở trong line.

Như vậy, chúng ta có: Số lượng block của Bộ chớ chính là 2s, vì vậy dung lượng bộ nhớ chính là: 2s+w.

Ví dụ 4.6:

Hãy xác định số bit cho mỗi trường của địa chỉ do bộ vi xử lý phát ra trong kỹ thuật ánh xạ liên kết hoàn toàn, biết rằng: Dung lượng bộ nhớ chính là 4GB, dung lượng Cache là 256KB, kích thước Line là 32 KB.

Giải:

Chúng ta có: Dung lượng Bộ nhớ chính là 4GB, bằng 232. Cache có dung lượng là 256 KB, bằng 218. Kích thước line là 32B, bằng 25.

Xác định số bit:


5

27

- Sơ đồ thực hiện:

Tag Word

Hình 4 32 Ánh xạ liên kết hoàn toàn Nhận xét Ưu điểm Tỷ lệ cache hit 7

Hình 4. 32. Ánh xạ liên kết hoàn toàn

*) Nhận xét:

- Ưu điểm: Tỷ lệ cache hit cao hơn kỹ thuật ánh xạ trực tiếp.

- Nhược điểm:

+) Mạch điều khiển phức tạp, do phải so sánh đồng thời một số hiệu block với các tag của tất cả các line trong Cache.

+) Làm tăng thời gian truy nhập Cache.

c) Ánh xạ liên kết tập hợp (Set Associative Mapping)

Ta thấy đối với Kỹ thuật ánh xạ liên kết đầy đủ, thời gian tìm kiếm không nhỏ do phải so sánh với tất cả các Tag của tất cả các Line trong Cache. Vì vậy, người ta khắc phục như sau:

- Nhóm một số Line liên tiếp thành một tập hợp (Set).

- Một block của bộ nhớ chính chỉ được nạp vào một Set nhất định, nhưng có thể nạp vào một Line bất kỳ của Set đó.

- Bộ nhớ Cache được chia thành v Set mỗi Set có k Line, do đó số lượng Line trong Cache là: m = v * k.

Chúng ta có ánh xạ: i = j mod v

Trong đó: +) i: Số hiệu Set trong Cache.

+) j: Số hiệu Block trong bộ nhớ chính.

+) v: Số lượng Set.

Cụ thể như sau:

Block 0 được ánh xạ vào Set 0 Block 1 được ánh xạ vào Set 1

. . .

Block v được ánh xạ vào Set v

Địa chỉ do CPU phát ra gồm có 3 trường:

Ví dụ 4 7 Bộ nhớ chính của một máy tính có dung lượng là 4GB Bộ nhớ Cache 8

Ví dụ 4.7:

Bộ nhớ chính của một máy tính có dung lượng là 4GB, Bộ nhớ Cache có dung lượng là 256 KB, kích thước Line là 32 Byte và mỗi Set có 8 Line. Hãy tìm dạng địa chỉ truy nhập Cache do CPU phát ra trong trường hợp dùng kỹ thuật ánh xạ liên kết tập hợp.

Giải:

Ta có: BNC = 4GB = 232 Cache = 256KB = 218

Line = 32B = 25

1Set = 23 Line

Vì vậy: Số lượng line = 218/ 25 = 213, Vì vậy, số lượng Set = 213/ 23 = 210 Tag = 32 - 5 - 10 = 17

Do đó địa chỉ do CPU phát ra là:


17

10

5

Tag Set Word


- Sơ đồ thực hiện:

Hình 4 33 Ánh xạ liên kết tập hợp Nhận xét Có v set mỗi set có k line 9

Hình 4. 33. Ánh xạ liên kết tập hợp

*) Nhận xét: Có v set, mỗi set có k line, Cache có m line Nếu:

+) v=m, k=1: là kỹ thuật ánh xa là ánh xạ trực tiếp.

+) v=1, k=m: là kỹ thuật ánh xa là ánh xạ liên kết đầy đủ.

+) v=m/2, k=2: ánh xạ liên kết tập hợp 2 đường.

+) v=m/4, k=4: ánh xạ liên kết tập hơp 4 đường.

4.4.3. Giải thuật thay thế

Khi truy nhập thông tin, nếu Cache miss thì cần phải thay Block tương ứng đưa vào Cache, nghĩa là thay Block cũ trong Cache. Vấn đề đặt ra là thay Block cũ nào ?

a. Ánh xạ trực tiếp: Không được phép lựa chọn, vì: Block j Chỉ và chỉ được ánh xạ vào Line (j mod m).

b. Ánh xạ liên kết (tập hợp hoặc đầy đủ): Có các thuật toán thay thế Block cũ như sau:

- Thuật toán ngẫu nhiên (Random): Thay một cách ngẫu nhiên một Block cũ nào đó trong Cache.

Đặc điểm:

+) Dễ thực hiện bằng phần cứng.

Ngày đăng: 29/06/2022