Bài tập kỹ thuật lập trình chương 4

Chia sẻ: Yan Liang | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

396
lượt xem 110
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo Bài tập kỹ thuật lập trình chương 4, với những câu hỏi trắc nghiệm dễ hiểu, dành cho các bạn đang theo học công nghệ thông tin chuyên kỹ thuật lập trình.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài tập kỹ thuật lập trình chương 4

BÀI TẬP CHƯƠNG 4 1. Giaû söû coù boä nhôù Cache phoái hôïp hoaøn toaøn nhö hình veõ, Cho bieát: a. Kích thöôùc boä nhôù trong? b. Kích thöôùc Cache? c. Ñeå laáy byte döõ lieäu coù giaù trò 32 (hình veõ), CPU caàn ñoïc ñòa chæ naøo? d. Ñieàu gì xaûy ra khi CPU ñoïc caùc ñòa chæ sau: +) 0000111011 +) 0100100100 +) 0E4h e. Chæ ra ñòa chæ cuûa 3 oâ nhôù khaùc nhau ñang hieän dieän trong Cache 2. Giaû söû moät maùy tính coù boä nhôù trong laø 512 byte, Cache 256 byte. a. Haõy xaây döïng baûng moâ taû toå chöùc Cache töông öùng tröïc tieáp cho maùy naøy, neáu moãi khoái trong cache laø 32 byte. b. Cho bieát caùc khoái: 2, 9, vaø 15 cuûa boä nhôù trong ñöôïc ñaët vaøo vò trí naøo cuûa Cache. c. Cho ví duï moät tröôøng hợp thaønh coâng Cache. 3. Laëp laïi caâu 2 cho tröôøng hôïp Cache 2-way phoái hôïp taäp hôïp (töùc laø moãi taäp hôïp coù 2 khoái). 4. Xeùt moät CPU chaïy ôû 500MHz, taäp leänh coù daïng nhö bảng. Trung bình moãi leänh coù tæ leä thaâm nhaäp boä nhôù laø 1.3 Coù 2 khaû naêng toå chöùc boä nhôù Cache cho maùy naøy: Caùch 1: Duøng Cache töông öùng tröïc tieáp vôùi: - miss penalty = 50 chu kyø - miss rate = 1,4% Caùch 2: Duøng Cache phoái hôïp taäp hôïp vôùi: - miss penalty = 65 chu kyø - miss rate = 1% - Thôøi gian choïn taäp hôïp laøm cho CPI trung bình taêng 1,1 laàn Anh (chò) haõy choïn caùch toát hôn. Giaûi thích vì sao. 5. Câu 4 (Giáo trình) Cho một bộ nhớ cache tương ứng trực tiếp có 8 khối, mỗi khối có 16 byte. Bộ nhớ trong có 64 khối. Giả sử lúc khởi động máy, 8 khối đầu tiên của bộ nhớ trong được đưa lên cache. a. Viết bảng nhãn của các khối đang hiện diện trong Cache b. CPU đọc các ô nhớ sau đây: 04AH, 27CH, 3F5H. Nếu thất bại Cache thì cập nhật bãng nhãn. c. CPU dùng cách ghi lại. Khi thất bại cache, CPU dùng cách ghi có nạp. Mô tả công việc của bộ quản lý cache khi CPU ghi dữ liệu mới vào các ô nhớ: 0C3H, 05AH, 1D5H.
BÀI GIẢI CHƯƠNG 4 2. BNT = 512 byte; Cache 256 byte Index V D Tag (1 bit) a. Cache tương ứng trực tiếp:Tag – Index – Offset 000 0 0 - Khối có 32 byte => Offset = 5 bit 001 0 0 - Số khối cache = 256/32 = 8 => Index = 3 bit 010 0 0 - BNT 512 byte => Địa chỉ ô nhớ = 9 bit 011 0 0 ==> Tag = 9 bit – (5 + 3) = 1 100 0 0 101 0 0 b. Đưa các khối vào Cache 110 0 0 - Khối i=2: ==> k = 2 mod 8 = 2 111 0 0 i=2 ==> 0010 = Tag của i=2: 0 và Đặt V = 1 tại khối Index = 010 Index V D Tag (1bit) - Khối i=9: ==> k = 9 mod 8 = 1 000 0 0 i=9 ==> 1001 = Tag của i=9: 1 và Đặt V = 1 tại khối Index = 001 1 0 1 001 010 1 0 0 - Khối i=15: ==> k = 15 mod 8 = 7 011 0 0 i=15 ==> 1111 = Tag của i=15: 1 và Đặt V = 1 tại khối Index = 100 0 0 111 101 0 0 110 0 0 c. Cache hit: 111111111, 111111110, 111111101 111 1 0 1 3. Lặp lại câu 2 cho trường hợp Cache 2-way phối hợp tập hợp (tức là mỗi tập hợp có 2 khối). Index V D Tag (2bit) a. Cache 2-way: Tag – Index – Offset 00 0 0 - Khối có 32 byte => Offset = 5 bit 0 0 - Số khối cache = 256/32 = 8 01 0 0 => Số tập hợp = 8/2 = 4 => Index = 2 bit 0 0 - BNT 512 byte => Địa chỉ ô nhớ = 9 bit 10 0 0 ==> Tag = 9 bit – (5 + 2) = 2 bit 0 0 b. Đưa các khối vào Cache: 11 0 0 - Khối i=2: => k = 2 mod 4 = 2. i=2 => 0010 => Tag của i=2 là 00 0 0 và Đặt V = 1 tại khối Index = 10 Index V D Tag (2bit) - Khối i=9: => k = 9 mod 4 = 1. i=9 => 1001 => Tag của i=9 là 10 00 0 0 và Đặt V = 1 tại khối Index = 01 0 0 - Khối i=15: => k = 15 mod 4 = 3; i=15 => 1111 => Tag của i=15 01 1 0 10 là 11 và Đặt V = 1 tại khối Index = 11 0 0 10 0 0 1 0 00 11 1 0 11 4. 0 0 Tính thời gian thi hành (CPUTime) của từng cách tổ chức Cache ⎛ MemAccess ⎞ CPUtime = IC × ⎜ CPI + × MissRate × MissPenalty ⎟ × CycleTime ⎝ Execution Inst ⎠ CÁCH 1: CPI1 = (2x0.45) + (2x0.35) + (3x0.2) = 2.2 => CPUTime1 = IC x (2.2 + 1.3 x 1.4 x 50) x 1/500*106 = IC x 93.2 x 1/500*106 CÁCH 2: CPI2 = 1.1 x CPI1 = 1.1 x 2.2 = 2.42 => CPUTime2 = IC x (2.42 + 1.3 x 1 x 65) x 1/500*106 = IC x 86.92 x 1/500*106 n = CPUTime1 / CPUTime2 = 93.2 / 86.92 = 1.07 lần
CPUTime1 > CPUTime2 Vậy, tốc độ thi hành của chương trình trên Cache cách 2 nhanh hơn trên Cache cách 1 Lựa chọn Cache cách 2 để sử dụng. 5. Cho một bộ nhớ cache tương ứng trực tiếp có 8 khối, mỗi khối có 16 byte. Bộ nhớ trong có 64 khối. Giả sử lúc khởi động máy, 8 khối đầu tiên của bộ nhớ trong (i=0 ... 7) được đưa lên cache. a. Viết bảng nhãn của các khối đang hiện diện trong Cache - Khối có 16 byte => Offset = 4 bit - Cache có 8 khối => Index = 3 bit - BNT: 64 x 16 = 1024 byte => Địa chỉ ô nhớ = 10 bit ==> Tag = 10 – (4 + 3) = 3 bit - Đưa 8 khối đầu tiên vào Cache: * Khối i =0 => k = 0 mod 8 = 0 i=0 => 000000 => Tag của i=0: 000 và Đặt V = 1 tại khối Index = 000 * Khối i =1 => k = 1 mod 8 = 1 i=1 => 000001 => Tag của i=0: 000 và Đặt V = 1 tại khối Index = 001 * Khối i =2 => k = 2 mod 8 = 2 i=2 => 000010 => Tag của i=0: 000 và Đặt V = 1 tại khối Index = 010 * Khối i =3 => k = 3 mod 8 = 3 i=3 => 000011 => Tag của i=3: 000 và Đặt V = 1 tại khối Index = 011 * Khối i =4 => k = 4 mod 8 = 4 i=4 => 000100 => Tag của i=4: 000 và Đặt V = 1 tại khối Index V D Tag (3 bit) Index = 100 000 1 0 000 * Khối i =5 => k = 5 mod 8 = 5 001 1 0 000 i=5 => 000101 => Tag của i=5: 000 và Đặt V = 1 tại khối 010 1 0 000 Index = 101 011 1 0 000 * Khối i =6 => k = 6 mod 8 = 6 100 1 0 000 i=6 => 000110 => Tag của i=6: 000 và Đặt V = 1 tại khối 101 1 0 000 Index = 110 110 1 0 000 * Khối i =7 => k = 7 mod 8 = 7 111 1 0 000 i=7 => 000111 => Tag của i=7: 000 và Đặt V = 1 tại khối Index = 111 b. CPU đọc các ô nhớ sau đây: 04AH, 27CH, 3F5H. Nếu thất bại Cache thì cập nhật bãng nhãn. * 04Ah = 0001001010 => Cache hit * 27Ch = 1001111100 => Cache miss => Trừng phạt cache Ô nhớ 27Ch đang nằm trong khối i=39 trong BNT Index V D Tag (3 bit) => k = 39 mod 8 = 7 => Lấy khối i=39 đưa vào Cache tại 000 1 0 000 khối k=7. Cập nhật bảng nhản: 001 1 0 000 010 1 0 000 011 1 0 000 100 1 0 000 101 1 0 000 110 1 0 000 111 1 0 100
* 3F5h = 1111110101 => Cache miss => Trừng phạt cache Ô nhớ 3F5h đang nằm trong khối i=63 trong BNT Index V D Tag (3 bit) => k = 63 mod 8 = 7 => Lấy khối i=63 đưa vào Cache tại 000 1 0 000 khối k=7. Cập nhật bảng nhản: 001 1 0 000 010 1 0 000 011 1 0 000 100 1 0 000 101 1 0 000 c. CPU dùng cách ghi lại. Khi thất bại cache, CPU dùng 110 1 0 000 cách ghi có nạp. Mô tả công việc của bộ quản lý cache khi 111 1 0 111 CPU ghi dữ liệu mới vào các ô nhớ: 0C3H, 05AH, 1D5H. * 0C3h = 0011000011 => Cache miss => CPU dùng cách ghi có nạp: CPU ghi trực tiếp giá trị vào bộ nhớ Index V D Tag (3 bit) trong. Sau đó nạp khối chứa ô nhớ 0C3h vào Cache: 000 1 0 000 001 1 0 000 => i=12 => k=12 mod 8 = 4. Cập nhật bảng nhản: 010 1 0 000 011 1 0 000 100 1 0 001 101 1 0 000 110 1 0 000 111 1 0 111 * 05Ah = 0001011010 => Cache hit => CPU dùng cách Index V D Tag (3 bit) ghi lại: CPU ghi dữ liệu mới cho ô nhớ 05Ah vào Cache 000 1 0 000 => Đặt D = 1. Cập nhật bảng nhản 001 1 0 000 010 1 0 000 011 1 0 000 100 1 0 001 101 1 1 000 110 1 0 000 111 1 0 111 * 1D5h = 0111010101 => Cache miss => CPU dùng cách ghi có nạp: CPU ghi trực tiếp dữ liệu của ô nhớ 1D5h vào Index V D Tag (3 bit) bộ nhớ trong. Sau đó nạp khối chứa ô nhớ 1D5h vào 000 1 0 000 Cache: i=29 => k=29 mod 8 = 5 => Lấy khối i=29 đưa 001 1 0 000 vào cache tại k=5. Vì khối k=5 trong cache có D=1 (dữ 010 1 0 000 liệu có thay đổi) nên phải copy khối k=5 vào BNT tại i=5 011 1 0 000 trước khi đưa khối i=29 vào cache. 100 1 0 001 101 1 0 011 Cập nhật bảng nhản: 110 1 0 000 111 1 0 111