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ớ

oa Khoa học & Kỹ thuật Máy tính 33
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 34
 Tác dụng của Cache quan hệ
  Tăng “quan hệ” giảm miss rate
  But with diminishing returns
  Mô phỏng 1 hệ thống 64KB cache dữ 
 liệu, 16-word/khối với SPEC2000
  1-way: 10.3%
  2-way: 8.6%
  4-way: 8.3%
  8-way: 8.1%
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 35
 Tổ chức hiện thực 
 “ Set Associative Cache”
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 36
 Chính sách thay thế
  Ánh xạ trực tiếp: không có lựa chọn ≠
  Ánh xạ quan hệ tệp n-chiều
  Chọn phần tử (v=0), nếu có 
  Nếu không, chọn giữa các phần tử trong tệp
  Chọn “ít dùng nhất” (LRU)
  Chọn phần tử nào ít dùng nhất
  Đơn giản với 2-way, phức tạp hơn với 4-way, 
 phức tạp cho những tệp > 4
  Chọn ngẫu nhiên
  Cho kết quả giống LRU đối với tệp quan hệ 
 lớn.
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 37
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 38
 Ví dụ: Cache đa cấp
  Giả sử
  CPU có CPI = 1, clock rate = 4GHz
  Miss rate/instruction = 2%
  Thời gian truy suất bộ nhớ chính = 100ns
  Nếu chỉ có cache sơ cấp (cấp 1)
  Miss penalty = 100ns/0.25ns = 400 cycles
  Effective CPI = 1 + 0.02 × 400 = 9
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 39
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 40
 Nhận xét về cache đa cấp
  Cache sơ cấp (Primary cache)
  Tập trung vào giảm thời gian hit
  Cache cấp 2 (L-2 cache)
  Tập trung vào giảm tỷ lệ mis, tránh truy xuất 
 bộ nhớ chính
  Hit time không tác dụng nhiều ở cấp này
  Kết quả
  L-1 cache thường nhỏ ơn Cache cấp 2
  L-1 block size nhỏ hơn L-2 block size
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 41
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 42
 Chuyển đổi địa chỉ
  Trang có dung lượng cố định (e.g., 4K)
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 43
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 44
 Bảng phân trang (Page Tables)
  Lưu trữ thông tin sắp xếp trang
  Bảng ánh xạ trang 2 chiều, đánh chỉ số theo 
 trang ảo
  Thanh ghi ánh xạ trong CPU sẽ chỉ đến bảng 
 ánh xạ trong bộ nhớ vật lý
  Nếu trang tồn tại trong bộ nhớ
  PTE chứa chỉ số trang vật lý tương ứng
  Cùng với bit trạng thái (đã tham chiếu, dirty,)
  Nếu trang không tồn tại trong bộ nhớ
  PTE tham chiếu đến vùng swap trên đĩa
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 45
 Chuyển đổi với bảng phân trang
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 46
 Ánh xạ trang (pages) lên đĩa
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 47
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 48
 Chuyển đổi nhanh với TLB
  TLB = Translation-lookaside buffer
  Việc chuyển đổi địa chỉ: truy xuất xảy ra 2 lần 
 truy cập bộ nhớ
  Truy cập để lấy được địa chỉ vật lý tương ứng PTE
  Sau đó mới truy cập để lấy thông tin bộ nhớ
  Tuy nhiên truy cập bảng trang: tính cục bộ
  Sử dụng bộ nhớ cache nhanh PTE trong CPU
  Translation Look-aside Buffer (TLB)
  Thường thì: 16–512 PTEs, 0.5–1 chu kỳ với hit, 10–
 100 chu kỳ với miss, 0.01%–1% miss rate
BK  Misses có thể giải quyết bằng phần cứng hoặc mềm
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 49
 Chuyển đổi nhanh với TLB (tt.)
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 50
 Xử lý TLB Misses
  Nếu trang yêu cầu có trong bộ nhớ chính
  Nạp PTE từ bộ nhớ chính & thử lại
  Có thể thực hiện bằng phần cứng
  Trở nên phức tạp với các cấu trúc bảng ánh xạ trang phức 
 tạp
  Hoặc bằng phần mềm
  Xử dụng cơ chế ngoại lệ đặc biệt, xử lý chuyên dụng
  Nếu trang yêu cầu không có trong bộ nhớ 
 chính
  OS sẽ nạp trang yêu cầu từ đĩa và cập nhật bảng 
 ánh xạ trang
  Sau đó khởi động lại lệnh bị lỗi trang
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 51
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 52
 Khi có lỗi trang
  Sử dụng địa chỉ bị lỗi để tìm phần tử PTE 
 trang tương ứng
  Xác định vị trí trên đĩa 
  Chọn trang trong bảng ánh xạ để thay thế
  Nếu bị sửa đổi nhiều: cập nhật lên đĩa
  Đọc trang yêu cầu từ đĩa & Cập nhật bảng 
 ánh xạ trang
  Khởi động quá trình chậy lại
  Khởi động lại lệnh gây lỗi trang
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 53
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 54
 Thực hiện bảo vệ bộ nhớ
  Các chương trình chạy đồng thời chia sẻ chung 
 không gian địa chỉ ảo
  Nhưng cần được bảo vệ, tránh truy cập lẫn nhau
  Cần sự tham gia của hệ điều hành
  Phần cứng hỗ trợ hệ điều hành
  Chế độ đặc quyền (Privileged supervisor mode)
  Lệnh đặc quyền
  Bảng ánh xạ trang và các thông tin trạng thái khác 
 chỉ được truy cập bằng chế độ đặc quyền
  Ngoại lệ “gọi hệ thống” (System call exception) (ví 
 dụ: syscall in MIPS)
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 55
 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 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 56
 Sắp đặt khối
  Xác định bởi hàm ánh xạ quan hệ
  Ánh xạ trực tiếp (1-way associative)
  Chỉ có 1 phương án duy nhất 1:1
  Ánh xạ tệp n (n-way associative)
  Có n cách ánh xạ (1:n)
  Ánh xạ toàn phần (Fully associative)
  Bất cứ trang nào
  Mối quan hệ càng cao: càng giảm lỗi 
 trang
  Gia tăng phức tạp, giá thành & thời gian 
 truy xuất
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 57
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 58
 Thay thế khối (Replacement)
  Lựa chọn trang thay thế khi có lỗi trang
  Trang ít sử dụng nhất (LRU)
  Tương đối phức tạp & phí tổn phần cứng khi 
 mối quan hệ ánh xạ cao
  Ngẫu nhiên
  Gần với LRU, dễ thực hiện hơn
  Bộ nhớ ảo
  LRU xấp xỉ với hỗ trợ bằng phần cứng
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 59
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 60
 Nguồn gốc của “Misses”
  Misses bắt buộc (lúc khởi động)
  Lần đầu tiên truy cập khối
  Miss do dung lượng (Capacity)
  Do hạn chế dung lượng cache
  Một khối vừa thay ra lại bị truy cập ngay sau đó
  Miss do đụng độ (aka collision misses)
  Trong trường hợp cache quan hệ không toàn phần
  Tranh chấp các khối trong cùng 1 tệp
  Sẽ không xảy ra đối với cache quan hệ toàn phần 
 vớii dung lượng tổng như nhau
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 61
 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 khối Giảm compulsory Tăng miss penalty. 
 misses For very large block 
 size, may increase 
 miss rate due to 
 pollution.
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 62
 Hỗ trợ tập lệnh
  Chế độ người dùng & hệ thống
  Các lệnh đặc dụng (privileged instructions) 
 chỉ có ở chế độ hệ thống
  Bẫy hệ thống khi có sự chuyển từ chế độ 
 người dùng sang hệ thống
  Các tài nguyên vật lý chỉ truy cập được với 
 những lệnh đặc dụng
  Kể cả bảng ánh xạ trang, đ/khiển ngắt quãng, 
 Thanh ghi I/O
BK
TP.HCM
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 63
 Đ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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 64
 Các tín hiệu giao tiếp
 Read/Write Read/Write
 Valid Valid
 Address 32 Address 32
 CPU Write Data 32 Cache Write Data 128 Memory
 Read Data 32 Read Data 128
 Ready Ready
 Multiple cycles 
 per access
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 65
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 66
 Tổ chức TLB cache cấp 2
 Intel Nehalem AMD Opteron X4
 Virtual addr 48 bits 48 bits
 Physical addr 44 bits 48 bits
 Page size 4KB, 2/4MB 4KB, 2/4MB
 L1 TLB L1 I-TLB: 128 entries for small L1 I-TLB: 48 entries
 (per core) pages, 7 per thread (2 ) for L1 D-TLB: 48 entries
 large pages Both fully associative, LRU 
 L1 D-TLB: 64 entries for small replacement
 pages, 32 for large pages
 Both 4-way, LRU replacement
 L2 TLB Single L2 TLB: 512 entries L2 I-TLB: 512 entries
 (per core) 4-way, LRU replacement L2 D-TLB: 512 entries
 Both 4-way, round-robin LRU
 TLB misses Handled in hardware Handled in hardware
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 67
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 68
 Hạn chế phí tổn Mis (Penalty)
  Trả về “từ” được yêu cầu trước tiên
  Sau đó nạp tiếp phần còn lại của khối
  Xử lý Non-blocking miss
  Hit under miss: allow hits to proceed
  Mis under miss: allow multiple outstanding 
 misses
  Nạp trước bằng phần cứng: Lệnh & Dữ liệu
  Opteron X4: bank interleaved L1 D-cache
  Two concurrent accesses per cycle
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 69
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 70