Bài giảng Kiến trúc máy tính - Chương 5: Tổ chức và Cấu trúc bộ nhớ

Nội dung text: Bài giảng Kiến trúc máy tính - Chương 5: Tổ chức và Cấu trúc bộ nhớ

1. Các loại Bộ nhớ (Công nghệ)  RAM tĩnh (SRAM)  0.5ns – 2.5ns, $2000 – $5000 per GB  RAM động (DRAM)  50ns – 70ns, $20 – $75 per GB  Đĩa từ (Magnetic disk)  5ms – 20ms, $0.20 – $2 per GB  Bộ nhớ lý tưởng  Thời gian truy xuất theo SRAM  Dung lượng & Giá thành/GB theo đĩa BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 2
2. Tận dụng lợi thế về cục bộ  Tổ chức phân tầng bộ nhớ  Lưu trữ mọi thứ trên đĩa  Chỉ nạp vào bộ nhớ Chính (DRAM) 1 phần đang sử dụng từ đĩa  Chỉ nạp vào bộ nhớ đệm CACHE (SRAM) 1 phần đang truy cập ở bộ nhớ chính  Bộ nhớ đệm (Cache) là bộ nhớ mà CPU truy cập trực tiếp BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 4
3. Bộ nhớ đệm (Cache)  Bộ nhớ Cache  Trong cấu trúc lớp của tổ chức hệ thống bộ nhớ, Cache là lớp trực tiếp với CPU  Giả sử truy cập X1, , Xn–1, Xn  Làm sao biết được dữ liệu cần truy cập có trong Cache?  Ở đâu? BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 6
4. Nhãn (Tags) & Bit hợp lệ  Làm sao có thể biết được một khối nào đó tồn tại trong cache?  Chứa cả địa chỉ khối và dữ liệu  Thực tế, chỉ cần những bit cao  Gọi là nhãn (tag)  Nếu dữ liệu không hiện diện thì  Valid bit: 1 = hiện diện, 0 = không hiện diện  Khởi động ban đầu là không hiện diện (0) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 8
5. Ví dụ (tt.) Word addr Binary addr Hit/miss Cache block 22 10 110 Miss 110 Index V Tag Data 000 N 001 N 010 N 011 N 100 N 101 N 110 Y 10 Mem[10110] 111 N BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 10
6. Ví dụ (tt.) Word addr Binary addr Hit/miss Cache block 22 10 110 Hit 110 26 11 010 Hit 010 Index V Tag Data 000 N 001 N 010 Y 11 Mem[11010] 011 N 100 N 101 N 110 Y 10 Mem[10110] 111 N BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 12
7. Ví dụ (tt.) Word addr Binary addr Hit/miss Cache block 18 10 010 Miss 010 Index V Tag Data 000 Y 10 Mem[10000] 001 N 010 Y 10 Mem[10010] 011 Y 00 Mem[00011] 100 N 101 N 110 Y 10 Mem[10110] 111 N BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 14
8. Ví dụ: Khối có kích thước lớn  64 blocks, 16 bytes/block  Địa chỉ 1200 sẽ ánh xạ vào khối nào?  Địa chỉ Block = 1200/16 = 75  Chỉ số Block = 75 modulo 64 = 11 31 10 9 4 3 0 Tag Index Offset 22 bits 6 bits 4 bits BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 16
9. Xử lý Cache Misses  CPU sẽ xử lý bình thường theo lộ trình, nếu thông tin có trong cache (cache hit)  Nếu thông tin không có trong cache (mis)  Lộ trình bị “khựng lại” (Stall the CPU pipeline)  Nạp 1 khối từ lớp dưới  Nếu đó là lệnh (Instruction cache miss)  Khởi động lại bước nạp lệnh (instruction fetch)  Nếu là truy cập dữ liệu (Data cache miss)  Hoàn tất việc truy cập BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 18
10. “Write-Through”  Khi ghi dữ liệu lên bộ nhớ, nếu tồn tại trong cache cập nhật khối dữ liệu trong cache  Tuy nhiên có thể xuất hiện bất đồng nhất dữ liệu trong cache và bộ nhớ  Write through: đồng thời cập nhật luôn bộ nhớ  Thời gian ghi sẽ dài hơn  Ví dụ: nếu CPI = 1, 10% số lệnh là lệnh store (ghi bộ nhớ) và (100 chu kỳ/lệnh ghi bộ nhớ)  CPI (thực tế) = 1 + 0.1×100 = 11  Giải pháp: Ghi ra vùng đệm (buffer)  Dưới dạng hàng đợi ghi ra bô nhớ  CPU tiếp tục ngay (khựng lại khi buffer đầy đợi) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 20
11. Write Allocation  Điều gì xảy ra khi có “write miss”?  Trong trường hợp “write-through”  Xác định khối on mis: Nạp từ bộ nhớ, cập nhật  Không cần xác định: Không nạp, tìm cách cập nhật thẳng lên bộ nhớ  Trong trường hợp “write-back”  Thường là nạp khối từ bộ nhớ BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 22
12. Ví dụ: Intrinsity FastMATH (tt.) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật máy tính 24
13. Tăng băng thông Bộ nhớ  4-word wide memory  Miss penalty = 1 + 15 + 1 = 17 bus cycles  Bandwidth = 16 bytes / 17 cycles = 0.94 B/cycle  4-bank interleaved memory  Miss penalty = 1 + 15 + 4×1 = 20 bus cycles  BK Bandwidth = 16 bytes / 20 cycles = 0.8 B/cycle TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 26
14. Ví dụ: Hiệu suất Cache  Giả sử  I-cache miss rate = 2% (truy xuất lệnh)  D-cache miss rate = 4% (truy xuất Dữ liệu)  Miss penalty = 100 cycles (Phí tổn theo t/gian)  Base CPI (ideal cache) = 2  Lệnh Load & stores chiếm 36% của c/trình  Số chu kỳ “trượt” /lệnh sẽ là  I-cache: 0.02 × 100 = 2  D-cache: 0.36 × 0.04 × 100 = 1.44  CPI (thực tế) = 2 + 2 + 1.44 = 5.44  CPU với bộ nhớ lý tưởng: 2.72 lần (5.44/2) nhanh hơn BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 28
15. Kết luận  Khi hiệu suất CPU tăng  Miss penalty becomes more significant  Giảm CPI  Phần lớn thời gian sẽ tiêu tốn do đợi truy xuất bộ nhớ  Tăng tần số xung Clock  Khựng do truy cập bộ nhớ tăng chu kỳ CPU  Không thể bỏ qua hành vi cache khi đánh giá hiệu suất hệ thống BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 30
16. Bộ nhớ Caches quan hệ  Associative cache: Đa ánh xạ (≠ ánh xạ trực tiếp  Cho phép 1 khối bộ nhớ ánh xạ vào bất cứ phần tử nào của cache  Yêu phải dò tìm tất cả trong cache để truy cập 1 khối nào đó  Bộ so sánh cho mỗi phần tử cache (giá thành sẽ cao)  Tập quan hệ n-chiều (n-ways)  Mỗi tập chứa n phần tử  Chỉ số khối xác định tập (set)  (Block number) modulo (#Sets in cache)  Dò tìm các phần tử trong tập để truy cập khối BK  n bộ so sánh (giá thành sẽ thấp hơn) TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 32
17. Các tập quan hệ (n-ways)  cache có 8 phần tử BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 34
18. Ví dụ: (tt.)  2-way set associative Block Cache Hit/miss Cache content after access address index Set 0 Set 1 0 0 miss Mem[0] 8 0 miss Mem[0] Mem[8] 0 0 hit Mem[0] Mem[8] 6 0 miss Mem[0] Mem[6] 8 0 miss Mem[8] Mem[6]  Fully associative Block Hit/miss Cache content after access address 0 miss Mem[0] 8 miss Mem[0] Mem[8] 0 hit Mem[0] Mem[8] 6 miss Mem[0] Mem[8] Mem[6] 8 hit Mem[0] Mem[8] Mem[6] BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 36
19. Tổ chức hiện thực “ Set Associative Cache” BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 38
20. Cache đa cấp (multilevel)  Cache sơ cấp (cấp 1) gắn trực tiếp với CPU  Dung lượng nhỏ nhưng nhanh  Cache cấp 2: giải quyết khi thông tin không có ở cấp 1  Dung lượng lớn hơn, chậm hơn, nhưng vẫn nhanh hơn bộ nhớ chính  Bộ nhớ chính giải quyết khi thông tin không có ở cấp 2  Một số hệ thống: cấp 3 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 40
21. Ví dụ: Cache đa cấp (tt.)  Giả sử thêm cache cấp 2  Thời gian truy xuất = 5ns  Miss rate toàn cục (to main memory) = 0.5%  Primary miss trong trường hợp L-2 hit  Penalty = 5ns/0.25ns = 20 cycles  Primary miss trong trường hợp L-2 miss  Extra penalty = 0.5% của 400 cycles  CPI = 1 + 0.02 × 20 + 0.005 × 400 = 3.4 BK  Tỷ số hiệu năng = 9/3.4 = 2.6 TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 42
22. Bộ nhớ ảo (Virtual Memory)  Bộ nhớ chính được sử dụng như “cache” của bộ nhớ đại trà (Đĩa từ)  Quản lý với sự kết hợp phần cứng CPU và hệ điều hành (OS)  Bộ nhớ chính được sử dụng chung cho nhiều chương trình đồng thời  Mỗi chương trình chiếm 1 không gian bộ nhớ riêng & chỉ những phần được dùng thường xuyên  Không gian của mỗi chương trình được bảo vệ, trách sự xâm lấn giữa chúng  CPU và OS chuyển đổi từ địa chỉ ảo sang địa chỉ vật lý  Khối “bộ nhớ ảo” được gọi là trang BK  Khi 1 khối ảo không tồn tại trong bộ nhớ lỗi trang TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 44
23. Lỗi trang (Page fault)  Khi xuất hiện lỗi trang, trang yêu cầu được nạp từ đĩa vào bộ nhớ  Thời gian: hàng triệu chu kỳ clock  OS sẽ xử lý  Tiêu chí: tối thiểu số lỗi trang  Sắp xếp theo quan hệ toàn phần  Sử dụng các giải thuật thông minh BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 46
24. Chuyển đổi với bảng phân trang BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 48
25. Thay thế & cập nhật  Để giảm lỗi trang, việc thay thế thường chọn trang ít sử dụng nhất (LRU)  Bit tham chiếu trong bảng phân trang PTE gán lên 1 mỗi khi trang được tham chiếu  Hệ điều hành sẽ định kỳ xóa về 0  Trang có bit tham chiếu bằng 0: chưa được dùng  Cập nhật trở lại đĩa: thời gian lên tới hàng triệu chu kỳ (phụ thuộc vào loại đĩa)  Cập nhật nguyên khối, không cập nhật từng từ  “Write through” không thực tế  Sử dụng “write-back”  “Dirty bit” trong bảng PTE = 1, khi trang thay đổi nội dung BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 50
26. Chuyển đổi nhanh với TLB (tt.) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 52
27. Bộ xử lý (handler) TLB Miss  TLB miss xuất hiện 2 trường hợp  Trang hiện hữu, nhưng PTE không có trong TLB  Trang không tồn tại trong bộ nhớ chính  TLB mis cần nhận biết trước khi thanh ghi đích được cập nhật  Xuất hiện ngoại lệ  Bộ xử lý sẽ sao chép PTE từ bộ nhớ vào TLB  Sau đó lệnh được khởi đọng lại BK  Nếu trang không có, lỗi trang xảy ra TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 54
28. Giao tiếp TLB & Cache  If cache tag uses physical address  Need to translate before cache lookup  Alternative: use virtual address tag  Complications due to aliasing  Different virtual addresses for shared physical address BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 56
29. Cấu trúc phân tầng bộ nhớ  Nguyên tắc chung được áp dụng cho tất cả các tầng (lớp) trong cầu trúc phân tầng bộ nhớ  Sử dụng thuật ngữ “cache”  Các hoạt động tại mỗi tầng  Sắp đặt khối (Block placement)  Tìm kiếm khối (Finding a block)  Thay thế khối trong tường hợp miss  Chính sách cập nhật (Write policy) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 58
30. Tìm kiếm khối Cách ánh xạ Phương pháp định vị So sánh nhãn (associativity) (Location method) (Tag comparisons) Trực tiếp Chỉ số (index) 1 Tệp quan hệ n (n-way) Tệp chỉ số (Set index), n sau đó tìm từng thành phần trong tệp Quan hệ toàn phần Tìm toàn bộ (Search all Ánh xạ tương ứng (Fully Associative) entries) Full lookup table 0  Caches phần cứng  Giảm thiểu so sánh giảm giá thành  Bộ nhớ ảo  Full table lookup makes full associativity feasible  Benefit in reduced miss rate BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 60
31. Phương thức cập nhật đĩa  “Write-through”  Cập nhật cả tầng trên & dưới  Đơn giản việc thay thế, nhưng yêu cầu có write buffer  “Write-back”  Chỉ cập nhật tầng trên  Cập nhật tầng thấp khi có nhu cầu thay thê  Cần lưu trữ nhiều trạng thái  Bộ nhớ ảo  Chỉ “write-back” là khả thi với thời gian ghi BK đĩa TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 62
32. Tối ưu thiết kế cache Thay đổi thiết kế Ảnh hưởng miss rate Hiệu ứng ngược Tăng dung lượng Giảm capacity misses Có thể tăng thời gian cache truy xuất Tăng quan hệ Giảm conflict misses Có thể tăng thời gian truy xuất Tăng dung lượng Giảm compulsory Tăng miss penalty. khối misses For very large block size, may increase miss rate due to pollution. BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 64
33. Điều khiển Cache  Ví dụ đặc tính cache  Ánh xạ trực tiếp, write-back, write allocate  Kích thước khối: 4 từ (words) = (16 bytes)  Kích thước cache: 16 KB (1024 blocks)  Địa chỉ 32-bit byte  Valid bit & dirty bit cho mỗi khối  Blocking cache  CPU waits until access is complete 31 10 9 4 3 0 Tag Index Offset 18 bits 10 bits 4 bits BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 66
34. Cache nhiều cấp on chip Intel Nehalem 4-core processor Per core: 32KB L1 I-cache, 32KB L1 D-cache, 512KB L2 cache BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 68
35. Tổ chức Cache 3 cấp Intel Nehalem AMD Opteron X4 L1 caches L1 I-cache: 32KB, 64-byte L1 I-cache: 32KB, 64-byte (per core) blocks, 4-way, approx LRU blocks, 2-way, LRU replacement, hit time n/a replacement, hit time 3 cycles L1 D-cache: 32KB, 64-byte L1 D-cache: 32KB, 64-byte blocks, 8-way, approx LRU blocks, 2-way, LRU replacement, write- replacement, write- back/allocate, hit time n/a back/allocate, hit time 9 cycles L2 unified 256KB, 64-byte blocks, 8-way, 512KB, 64-byte blocks, 16-way, cache approx LRU replacement, write- approx LRU replacement, write- (per core) back/allocate, hit time n/a back/allocate, hit time n/a L3 unified 8MB, 64-byte blocks, 16-way, 2MB, 64-byte blocks, 32-way, cache replacement n/a, write- replace block shared by fewest (shared) back/allocate, hit time n/a cores, write-back/allocate, hit time 32 cycles n/a: data not available BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 70
36. Kết luận  Bộ nhớ có tốc độ truy xuất nhanh Nhỏ ; Bộ nhớ có chứa dung lượng lớn Chậm  Mục tiêu mong muốn: nhanh và lớn   Cơ chế Caching giải quyết vấn đề   Nguyên tắc cục bộ  Chương trình sử dụng 1 phần nhỏ không gian bộ nhớ  Tổ chức bộ nhớ theo kiến trúc tầng  L1 cache  L2 cache   DRAM (bộ nhớ)  disk  Thiết kế hệ thống bộ nhớ rất quan trọng đối với đa xử lý BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 72