Bài giảng Bộ xử lý đường ống - Chương 5: Bộ nhớ đệm (Caches)

Bộ nhớ đệm (Caches)Chương 5Nội dung• Phân cấp bộ nhớ – Làm thế nào để tạo ra một bộ nhớ lớn và nhanh? – Liên kết SRAM, DRAM, và đĩa cứng• Caching – Những bộ nhớ nhỏ lưu những dữ liệu quan trọng – Ví dụ• Bộ nhớ cache làm việc như thế nào? – Các thẻ: Tags – Các khối: Blocks (lines)• Thực thi – 3 loại cache: kết hợp toàn phần (Fully‐associative), kết hợp theo tập hợp (set‐associative), ánh xạ trực tiếp (direct‐mapped) • Hiệu năngĐặt vấn đề• Cần bộ nhớ lớn và nhanh– Bộ nhớ lệnh lớn ISA : 232 memory address (4GB)– Yêu cầu nhanh vì 33% các lệnh là loads/stores và 100% các lệnh cần phải tải về thanh ghi lệnh• Tồn tại bộ nhớ có thể có dung lượng lớn và truy nhập nhanh?Bộ nhớ lớn và nhanh• Các loại bộ nhớ đã có? – Hard disk: Huge (1000 GB) Super slow (1M cycles) – Flash: Big (100 GB) Very slow (1k cycles) – DRAM: Medium (10 GB) Slow (100 cycles) – SRAM: Small (10 MB) Fast (1‐10 cycles)• Cần bộ nhớ nhanh và lớn – Không thể sử dụng SRAM (too small) – Không thể sử dụng DRAM (too slow and small) – Không thể sử dụng Flash/Hard disk (way too slow)• Có thể kết nối giữa chúng: – Speed từ (small) SRAMs – Size từ (big) DRAM và Hard diskXây dựng một phân cấp sử dụng công nghệ khác để tận dụng các ưu điểm của các bộ nhớ có sẵn.Phân cấp bộ nhớ• Phân loại:– Dung lượng nhỏ và nhanh: SRAM– Chậm: DRAM– Đĩa cứng dung lượng lớn nhưng rất chậm• Viễn cảnh:– Rất lớn– Rất nhanh (on average)• Mục tiêu?– Lưu trữ thông tin quan trọng trong bộ nhớ nhanh.– Di chuyển những thông tin không quan trọng vào bộ nhớ chậmVí dụ: sửa video• Video dung lượng lớn (lớn hơn DRAM)• Lưu vào ổ cứng • Tải phần cần chỉnh sửa vào DRAM• CPU tải dữ liệu để xử lý vào cache.• Di chuyển dữ liệu mới vào DRAM và cache khi xử lý video • Chú ý:– Lưu những dữ liệu quan trọng vào bộ nhớ nhanh– Di chuyển những dữ liệu không quan trọng vào bộ nhớ chậmPhân cấp bộ nhớ ngày nay (Intel Nehalem)So sánh sự phát triển công nghệLàm thế nào để SRAMs có dung lượng lớn hơn, DRAM truy cập nhanh hơn?Các ý tưởng cơ bản về cache• Đặt những dữ liệu quan trọng trong bộ nhớ nhỏ và nhanh (cache).• Nếu truy cập (load/store) những dữ liệu quan trọng, cần thực hiện nhanh.• Nếu truy cập (load/store) những dữ liệu khác, dịch chuyển dữ liệu vào trong cache.• Nếu đặt chính xác dữ liệu cần dùng vào cache, khi đó hầu hết các truy cập sẽ tìm ra dữ liệu hữu ích trong cache và trở nên nhanh hơn. Hiệu năng của caches• Truy nhập dữ liệu trong DRAM hết 100 chu kỳ• Truy nhập dữ liệu trong Cache (SRAM) hết 1 chu kỳ • Tỷ lệ lệnh load/stores là 33%.Bỏ qua việc tải lệnh (Cần thêm bộ nhớ thứ hai sau đó)Tính toán hiệu năng cache • Sử dụng DRAM:– Truy nhập dữ liệu trong DRAM hết 100 chu kỳ– (33% tải/lưu dữ liệu)*100 chu kỳ = 33 chu kỳ truy cập bộ nhớ/ lệnh.• Sử dụng một SRAM cache hoàn hảo (dữ liệu trong cache 100% thời gian):– (33% tải/lưu dữ liệu)*1 chu kỳ = 0.33 chu kỳ truy cập bộ nhớ / lệnh.• Sử dụng SRAM cache thực tế hơn (dữ liệu ở trong 90% thời gian):– (33% tải/lưu dữ liệu)*(1 chu kỳ 90% thời gian + 100 chu kỳ 10% thời gian) =0.33*(1*0.9+100*0.1) =0.33*(1.9) = 0.67 chu kỳ truy cập bộ nhớ / lệnhVí dụ: bộ nhớ đệmExample: caching instructionsExample: caching instructionsExample: caching instructionsExample: caching instructionsExample: caching instructionsExample: caching instructionsExample: caching instructionsExample: caching instructionsCache làm việc như thế nào?Trả lời các câu hỏi sau: Sắp xếp khối trong cache như thế nào?Làm thế nào để biết sự hiện diện của một khối trong cache – tìm kiếm và nhận diện cache.Khối nào được thay thế trong trường hợp tìm kiếm dữ liệu trong cache thất bại.Ghi vào bộ nhớ - ghi dữ liệu vào bộ nhớ như thế nào -> chiến thuật ghi.Cache làm việc như thế nào?• Bộ nhớ kết hợp:– Lưu trữ một thẻ (tag) để chỉ ra định vị bộ nhớ trong cache.– Các thẻ (tag) là địa chỉ hoặc một phần địa chỉ của dữ liệu được định vị trong cache.– Phần còn lại của cache là lưu trữ dữ liệu• Làm thế nào để biết dữ liệu ở trạng thái sẵn sàng?– Cache bắt đầu tại thẻ có giá trị bằng 0– Làm thế nào biết có hay không lệnh ở vị trí địa chỉ 0?• Bit đánh dấu - Valid/Invalid bit – Thêm bit 1 khi dữ liệu là hợp lệ và bit 0 nếu không hợp lệ.– Nếu thẻ ánh xạ đến có bit đánh dấu bằng 0 (invalid (0)), bỏ qua dữ liệuCấu tạo cacheLưu trữ dữ liệu trong cache• Tải dữ liệu từ Bộ nhớ• Lưu thẻ (tag) (0x8)• Lưu dữ liệu (data) (add r2, r2, r1)• Đặt giá trị valid bit (1)A: 2Cache bị xóa khi chuyển đổi giữa các chương trình hoặc để máy tính ở chế độ chờ. Cần xóa cache bởi vì dữ liệu sẽ không còn hợp lệ.Q: Khi nào các bit đánh dấu bị xóa?1/ Không bao giờ2/ Khi xóa bộ nhớ cache3/ Sau khi tải vềTruy cập dữ liệu từ cache• Kiểm tra thẻ tag (0x8) trong cache• Kiểm tra nếu bit hợp lệ bằng 1• Đọc dữ liệu từ cache.Q: Sẽ làm gì nếu bit đánh dấu bằng 01/ Bỏ qua dữ liệu.2/ Đặt lại bằng 1.2/ Lấy dữ liệu từ DRAM.A: Lấy dữ liệu từ DRAM Nếu các bit hợp lệ không được đặt giá trị có nghĩa là dữ liệu trong cache không hợp lệ. Trong trường hợp này cần lấy dữ liệu từ DRAM đưa vào cache.Cache blocks (lines)Tăng hiệu năng bằng cách lưu trữ nhiều dữ liệu hơn ở mỗi tagHiệu năng sử dụng cache là gì?• Tìm kiếm một Cache n‐phần tử:– Cùng một vị trí → n chu kỳ – Cùng một thời điểm → n bộ so sánh– Tốn kém!• Sử dụng bộ nhớ:– Data: 32 bits (one word)– Tag: 30 bits (one address)– Valid: 1bit– 63 bits cho mỗi phần tử– Chỉ có 32 sử dụng để lưu dữ liệu– Rất không hiệu quả!Q: Bao nhiêu bit cần cho một địa chỉ thẻ (tag)?43032A: 30 Địa chỉ thẻ xác định địa chỉ dữ liệu trong cache, cần bits để nhận diện địa chỉ từ.(We would need 32 bits if the memory was not word­aligned.)Tốn quá nhiều không gian cho thẻ• Hai phí tổn của caches:– Tốn nhiều không gian cho thẻ (tags)– Tốn nhiều phần tử logic để tìm kiếm• Khắc phục vấn đề:– 1 word / tag: 1/2 wasted– 2 words / tag: 1/3 wasted– 4 words / tag: 1/5 wasted– 8 words / tag: 1/9 wasted– 16 words / tag: 1/17 wasted (được sử dụng trong bộ xử lý ngày nay)• Phương pháp khắc phục?– Các dữ liệu trong cache lớn hơn → ít thẻ hơn → hiệu năng lưu trữ tốt hơnTruy nhập dữ liệu từ cache• Tương tự như trước:– Kiểm tra nếu thẻ tag (0x8) ở trong cache– Kiểm tra nếu bit đánh dấu là 1– Đọc dữ liệu từ cache• Nhưng có nhiều từ hơn trong một khối cache:– Sử dụng địa chỉ các bit để chọn từ đúng với bộ dồn kênh MUX– Tag chỉ so sánh các bit là như nhau trong toàn bộ khốiĐánh địa chỉ cho các cache có kích thước khối khác nhau• Địa chỉ:– 2 bit cuối : xác định byte trong từ(không cần thiết bởi vì truy nhập bộ nhớ bằng các từ)– N bit tiếp theo: xác định từ trong khối(ví dụ, kích thước khối là 4 cần 2 bits để xác định từ)– 32‐N‐2 bit còn lại: tag (cần thiết để xác định địa chỉ bộ nhớ)Ví dụ: cache block sizeQ: Tại sao kích thước block 4 từ là tốt ?Ít tốn không gian hơnTải trước các dữ liệu cần dùng sau đóThẻ ít bit hơn.A: 2Bằng việc tải 3 từ tiếp theo cùng với từ cần dùng, tỷ lệ thành công cao hơn. Phương pháp này được gọi là không gian “cục bộ - địa phương”: Những dữ liệu gần với những dữ liệu vừa sử dụng là những dữ liệu hợp lệ nhất.Các khối cache lớn hơnliên kết theo dòng/khối• Ưu điểm:– Ít tốn không gian cho các thẻ (higher % data)– Quy định cục bộ:• N‐1 words tiếp theo có sẽ được sử dụng sau đó• Nhược điểm:– Nếu không sử dụng dữ liệu trong cache sẽ làm tốn không gian dữ liệu– Ví dụ:• for (int i=0; i<100; i+=2) { a[i]++; }• Tốn một nửa không gian– 64 bytes (8 words) là kích thước chuẩn– Intel luôn nạp 2 khối cache tại một thời điểm tương đương với 128 bytes hay 16 wordsCác loại cachesĐịa chỉ tương ứng một khối (9 mod 8) = 1Tìm kiếm dễ dàng, không linh hoạtĐịa chỉ tương ứng với một tập .(9 mod 4) = Set 1Tìm kiếm tốt hơn, linh hoạt hơnĐịa chỉ tương ứng với bất kỳ vị trí nào trong cache.Khó trong việc tìm kiếm, rất linh hoạtBộ đệm liên kết toàn khối full – associative • Tìm kiếm khối– Cần n bộ so sánh– Hoặc cần n chu kỳ• Mục tiêu?– Có thể đặt dữ liệu ở bất kỳ đâu trong cache: flexibility– N blocks → có thể lưu dữ n mảng dữ liệu, mỗi vị trí đặt khối có thể chứa một trong một trong tất cả các khối trong bộ nhớ.Q: Nhược điểm?Ít lãng phí không gianChỉ cần một bộ so sánhChỉ một block được tìm kiếmA: Chỉ một block được tìm kiếmTìm kiếm toàn bộ cache, với n bộ so sánh hoặc với một bộ sánh trong n chu kỳƯu nhược điểm của các loại cache • Fully‐associative– Ưu điểm: linh hoạt, dữ liệu có thể đặt ở bất kỳ vị trí nào (no conflicts)– Nhược: Khó khăn trong việc tìm kiếm (slow/expensive) • Set‐associative– Ưu: tương đối linh hoạt: dữ liệu có thể đặt ở bất kỳ vị trí nào trong tập– Nhược: Chỉ cần tìm kiếm một vài vị trí trong tập (reasonable speed/complexity)• Direct‐mapped– Ưu: Tìm kiếm linh hoạt, chỉ cần tìm kiếm một vị trí (fast/simple)– Nhược: xảy ra xung đột dữ liệu (conflicts)Thiết kế cacheBộ nhớ đệm ánh xạ trực tiếp tăng hiệu quả tìm kiếmVị trí khối trong bộ đệm ánh xạ trực tiếp• Mỗi địa chỉ ánh xạ tới một block• Đánh địa chỉ theo modulo (K = i mod n)K : vị trí khối đặt trong cachei : số thứ tự khối trong bộ nhớ trongn : số khối của cacheVí dụ:– 0 → (0 mod 8) = 0– 1 → (1 mod 8) = 1– 2 → (2 mod 8) = 2– 8 → (8 mod 8) = 0– 9 → (9 mod 8) = 1– 18 → (18 mod 8) = 2• Chú ý 3 bits cuối:– 0 → 000000 → 0– 1 → 000001 → 1– 2 → 000010 → 2– 8 → 001000 → 0– 9 → 001001 → 1– 18 → 010010 → 2(bỏ qua đánh địa chỉ byte)Tag bitsVí dụ bộ đệm ánh xạ trực tiếp• Ưu điểm: dễ dàng trong việc tìm kiếm– Sử dụng địa chỉ để tìm một vị trí (modulo addressing)– So sánh với tag• Nhược điểm: kém linh hoạt (1 chu kỳ tìm kiếm 1 khối )– Nếu 2 địa chỉ ánh xạ tới cùng một dòng khi đó chỉ có thể lưu trữ một khối dữ liệu– Xảy ra xung độtNếu 2 địa chỉ khối trong bộ nhớ trong có cùng địa chỉ modulo, cả 2 không được lưu trữ cùng nhau trong cache, kể cả khi cache còn trống. (Inflexible → Conflicts)01Bộ đệm: 2 khối nhớ, mỗi khối có 2 từBộ nhớ chính: 16 từQ2: Vị trí các từ trong bộ đệm?TagDataQ1: Có trong bộ đệm không?Valid0000xx0001xx0010xx0011xx0100xx0101xx0110xx0111xx1000xx1001xx1010xx1011xx1100xx1101xx1110xx1111xxCác từ: 2 bít thấp dùng để xác định các byte trong từ (32b words)(block address) modulo (# of blocks in the cache)IndexSET-HUST, 22/03/2011Chương 4. Bộ nhớ - Phân cấp bộ nhớ41Bộ đệm ánh xạ trực tiếp đơn giản00011011Bộ đệm: 4 khối nhớ kích thước 1 từBộ nhớ chính: 16 từQ2: Vị trí các từ trong bộ đệm?Dùng 2 bít thấp tiếp theo của địa chỉ –chỉ số – để xác định khối bộ đệm nào (i.e., chia lấy dư cho số khối trong bộ đệm)TagDataQ1: Có trong bộ đệm không?So sánh trường thẻ bộ đệm với 2 bit cao của địa chỉ bộ nhớ để xác định khối dữ liệu có trong bộ đệm không? Valid0000xx0001xx0010xx0011xx0100xx0101xx0110xx0111xx1000xx1001xx1010xx1011xx1100xx1101xx1110xx1111xxCác 1 từ: 2 bít thấp dùng để xác định các byte trong từ (32b words)(block address) modulo (# of blocks in the cache)IndexSET-HUST, 22/03/2011Chương 4. Bộ nhớ - Phân cấp bộ nhớ42Bộ đệm ánh xạ trực tiếp đơn giảnBộ đệm ánh xạ trực tiếp MIPSCác khối 1 từ, kích thước bộ đệm = 1K từ (hay 4KB)4320Tag10IndexData IndexTagValid012...10211022102331 30 . . . 13 12 11 . . . 2 1 0Byte offset20Data32HitBộ đệm ánh xạ trực tiếp khối nhiều từKhối 4 từ, Kích thước bộ đệm = 1K words448IndexDataIndexTagValid012...25325425531 30 . . . 13 12 11 . . . 4 3 2 1 0Byte offset2020TagHitData32Block offsetBộ nhớ đệm liên kết kiểu tập hợp: Set‐associative cacheslinh hoạt hơnCó thể thỏa hiệp?• Có thể kết hợp việc tìm kiếm dễ dàng trong bộ đệm ánh xạ trực tiếp (direct‐mapped) và sự linh hoạt trong bộ đệm kết hợp toàn khối (fully‐associative caches)? • Có: Bộ đệm kết hợp theo tập hợp (set‐associative)– Mỗi khối nằm trong một tập (1 set gồm nhiều khối - có cùng địa chỉ modulo)– Mỗi tập có nhiều khối (tìm kiếm kết hợp)• Dễ dàng hơn trong việc tìm kếm:– Xác định được khối dựa trên địa chỉ– Chỉ cần kiểm tra một số khối cache trong tập.• Linh hoạt:– Có thể đặt khối ở bất kỳ đâu trong tập– Giảm số lần trượt bộ đệm.Bộ đệm kiểu tập hợp (Set‐associative cache)• Mỗi địa chỉ ánh xạ tới một khối• Sử dụng địa chỉ modulo (K = i mod s)K : vị trí khối đặt trong cachei : số thứ tự khối trong bộ nhớ trongs : số lượng tập hợp trong cache– 0 → (0 mod 4) = anywhere in Set 0– 1 → (1 mod 4) = anywhere in Set 1– 2 → (2 mod 4) = anywhere in Set 2– 8 → (8 mod 4) = anywhere in Set 0– 9 → (9 mod 4) = anywhere in Set 1– 18 →(18 mod 4) = anywhere in Set 2• Xem xét 2 bits cuối:– 0 → 000000 → Set 0– 1 → 000001 → Set 1– 2 → 000010 → Set 2– 8 → 001000 → Set 0– 9 → 001001 → Set 1– 18 → 010010 → Set 2Tag bits(Ignoring byte addressing for now)Ví dụ: Set‐associative• Ưu điểm: Dễ dàng trong việc tìm kiếm – Sử dụng địa chỉ tìm kiếm các tập– So sánh tất cả các tag trong tập• Nhược điểm:– Ít linh hoạt hơn kiểu fully‐associative (can only go anywhere in the set)– Phức tạp hợp (kiểm tra nhiều tags hơn)Nếu hai địa chỉ có cùng một điạ chỉ modulo, có thể tìm chúng trong một tập. (More flexible→ Fewer conflicts)Bộ đệm kết hợp n đườngSET-HUST, 22/03/2011Chương 4. Bộ nhớ - Phân cấp bộ nhớ490Bộ đệm: 4 khối, 2 tậpBộ nhớ chính 16 khối 1 từQ2: Vị trí từ trong bộ đệm?Sử dụng bít thấp tiếp theo để xác định tập (i.e., chia lấy phần dư cho số tập trong bộ đệm)TagDataQ1: Có trong bộ đệm không?So sánh tất cả các thẻ trong tập với 3 bít địa chỉ caoV0000xx0001xx0010xx0011xx0100xx0101xx0110xx0111xx1000xx1001xx1010xx1011xx1100xx1101xx1110xx1111xxSet101Way01Khối 1 từ, 2 bit thấp cuối dùng để xác định byte trong từ (từ 32b)Bộ đệm kết hợp 4 tập28 = 256 đường / tập, 4 tập (mỗi đường chứa 1 khối = 256 đường)5031 30 . . . 13 12 11 . . . 2 1 0Byte offsetDataTagV012... 253 254 255DataTagV012... 253 254 255DataTagV012... 253 254 255 IndexDataTagV012... 253 254 2558Index22TagHitData324x1 selectWay 0Way 1Way 2Way 3Bố trí bộ đệm kết hợp toàn phần/ liên kết toàn phần Với kích thước bộ đệm cố định, tăng độ kết hợp theo hệ số 2 sẽ tăng số khối trong mỗi tập (tăng số đường) và giảm số tập – giảm kích thước trường index 1 bít và tăng kích thước trường tag 1 bit51Block offsetByte offsetIndexTagGiảm độ kết hợpKết hợp toàn phần(chỉ có một tập)Tag gồm tất cả các bít trừ bitoffset của khối và byteÁnh xạ trực tiếp(chỉ có một đường)Tag nhỏ hơn, chỉ có 1 khối so sánhTăng độ kết hợpChọn tậpSo sánh thẻChọn từ trong khốiLợi ích của bộ đệm kết hợp toàn phầnLựa trọn giữa bộ đệm kết hợp và bộ đệm trực tiếp phụ thuộc vào tổn thất trượt và giá thành triển khai52Data from Hennessy & Patterson, Computer Architecture, 2003Lợi ích lớn nhất là khi chuyển từ bộ đệm trực tiếp sang kết hợp 2 đường (tỉ lệ trượt giảm 20%+)Kích thước các trường trong bộ đệmSố bit trong bộ đệm gồm bit cho dữ liệu và bit cho các trường thẻĐịa chỉ byte 32 bitBộ đệm ánh xạ trực tiếp 2n khối, n bits cho trường indexKích thước khối là 2m từ (2m+2 bytes), m bits cho trường block offset xác định vị trí từ trong khối; 2 bits cho trường byte offset xác định vị trí byte trong từKích thước trường tag sẽ là?Tổng số bít trong bộ đệm ánh xạ trực tiếp sẽ là2n x (block size + tag field size + valid field size)Cần bao nhiêu bit cho bộ đệm ánh xạ trực tiếp kích thước 16KB dữ liệu, kích thước khối là 4 từ và dữ liệu được đánh địa chỉ bằng 32 bit?SET-HUST, 22/03/2011Chương 4. Bộ nhớ - Phân cấp bộ nhớ53Bộ nhớ đệm ngày nay• Intel Ivy Bridge (2012, 4‐core x86)– L1 Data: 32kB 8‐way set‐associative 64‐byte line– L1 Instruction: 32kB 8‐way set‐associative 64‐byte line– L2 I&D: 256kB 8‐way set‐associative 64‐byte line– L3 I&D: 8MB 16‐way set‐associative 64‐byte line• Qualcomm Krait (2012, 4‐core ARM)– L0 Data: 4kB Direct‐mapped 64‐byte line– L0 Instruction: 4kB Direct‐mapped 64‐byte line– L1Data: 16kB 4‐way set‐associative 64‐byte line– L1 Instruction: 16kB 4‐way set‐associative 64‐byte line– L2 I&D: 1MB 8‐way set‐associative 64‐byte line “Filter” cache. Designed to save energy for small pieces of codeHigher associativity for larger caches.Same block size across the whole hierarchyDung lượng bộ nhớ đệmđiều gì xảy ra nếu bộ nhớ đệm đầy?Dung lượng caches• Điều gì xảy ra khi cache đầy?• Chính xách thay thế– Cần chọn một số dữ liệu trong caches để loại bỏ (evict)– Chọn những dữ liệu không sử dụng từ lâu nhất• Dẫn đến:– Direct‐mapped: chỉ loại đi một khối (bởi vì một khối tương ứng với một vị trí)– Set/Fully‐associative:• Chọn ngẫu nhiên một khối để loại bỏ• Chọn khối nào không sử dụng lâu nhất (least recently used - LRU) để loại bỏ.Chính sách thay thế • Bốn chiến thuật chủ yếu chọn khối thay thế trong cache• Thay thế ngẫu nhiên– Để phân bố đồng đều việc thay thế, các khối cần thay thế trong cache được chọn ngẫu nhiên• Khối xưa nhất (Least Recently Used ): hiệu quả trong các vị trí tạm thời– Thay thế khối không được dùng từ lâu nhất• Vào trước ra trước (FIFO)– Khối được đưa vào cache đầu tiên, nếu bị thay thế sẽ là khối bị thay thế trước nhất.• Khối có tần suất sử dụng ít nhất (LFU – Least Frequently Used): Khối trong cache được tham chiếu ít nhấtThay thế ngẫu nhiên• Chọn ngẫu nhiên một khối để loại bỏ• Ví dụ: – Black loop và blue loop– Khi chuyển đổi giữa hai vòng lặp dữ liệu luôn được sử dụng lại• Problem: Dữ liệu loại bỏ là dữ liệu cần sử dụng lạiThay thế khối xưa nhấtLeast recently used (LRU) replacement• Loại bỏ khối không được sử dụng lâu nhất• Ví dụ :– Black loop và blue loop– Khi chuyển đổi giữa các vòng lặp, cần tất cả các lệnh trong vòng lặp mầu xanh ở lại trong cacheGhi vào bộ nhớ đệmChiến thuật ghi?Ghi vào bộ nhớ đệm• Khi đọc lệnh hoặc dữ liệu: đặt vào cache • Ghi như thế nào?• Write‐through (ghi đồng thời)– Thông tin được ghi đồng thời vào khối của cache và khối của bộ nhớ trong– Đơn giản, nhưng chậm (phải đợi ghi vào DRAM) • Write‐back (ghi lại)– Chỉ ghi dữ liệu vào cache– Nếu khối không có trong cache, cần nạp lại vào cache– Cần đánh dấu lại nếu dữ liệu trong cache được cập nhật– Khi một khối bị thay thế, khối này sẽ được ghi lại vào bộ nhớ trong.Write‐through• Luôn ghi vào DRAM • Nếu dữ liệu ở trong cache, khi đó ghi đồng thời vào cache.Q: Ghi chậm hơn vì sao?Phụ thuộc vào vị trí của dữ liệu trong cache.Châm do ghi vào DRAMChậm do ghi vào DRAM và cacheA: Chậm do ghi vào DRAM Ghi vào DRAM ở mọi thời điểm.Write‐through with allocate‐on‐write• Luôn ghi vào DRAM• Nếu dữ liệu trong cache, ghi đồng thời vào cache• Allocate‐on‐write– Nếu khối dữ liệu không có trong cache, tải khối về cacheQ: Tốt hơn tại sao?It isn’tFaster to read and write than just write Subsequent reads will hit in the cacheA: Subsequent reads will hit in the cacheThường hay truy cập dữ liệu và ghi lại, chỉ ghi một phần của khối như một từ hoặc một byte, do vậy tải vào cache sẽ nhanh hơn. Write‐back• Luôn ghi vào cache• Nếu khối dữ liệu không có trong cache, tải vào cache• Note: cache và DRAM là không như nhau!• Khi chúng ta loại bỏ một dòng cần phải biết khác với dữ liệu ghi từ DRAM như thế nào?Ghi vào bộ nhớ đệm• Write‐through đơn giản, nhưng chậm – Phải đợi ghi đồng thời với DRAM trong mọi lần ghi• Write‐back phức tạp hơn, nhưng nhanh– Phải đánh dấu dữ liệu ‘bẩn’ (dirty data) trong cache và ghi lại vào bộ nhớ trong nếu nó bị loại bỏ– Ghi nhanh hơn• Allocate‐on‐write tải dữ liệu vào cache khi ghi– no allocate : chỉ tải dữ liệu vào cache khi đọc.• Ghi vào cache ngày nay là kiểu write‐back– Intel’s new Xeon Phi có mức L2 write‐through cacheHiệu năng bộ nhớ đệmTỉ lệ trượt vs Kích thước khối vs Kích thước bộ đệmSET-HUST, 22/03/201167Chương 4. Bộ nhớ - Phân cấp bộ nhớTỉ lệ trượt tăng khi kích thước khối trở nên đáng kể so với kích thước bộ đệm vì với cũng kích thước bộ đệm số khối có thể lưu giữ giảm (tăng trượt do dung lượng)Tăng kích thước khối làm tổn thất trượt tăngXử lý trúng bộ đệm Đọc trúng (I$ và D$)Đó là điều ta cần!Ghi trúng (chỉ với D$)yêu cầu bộ đệm và bộ nhớ phải thống nhất (allocate)luôn ghi dữ liệu vào cả khối bộ đệm và vào bộ nhớ ở mức kế tiếp (ghi xuyên - write-through)ghi với tốc độ của bộ nhớ ở mức kế tiếp – chậm hơn! – sử dụng bộ đệm ghi (write buffer) và chỉ dừng khi bộ đệm ghi đầycho phép bộ đệm và bộ nhớ không thống nhấtchỉ ghi dữ liệu vào bộ đệm (ghi lại write-back khối bộ đệm vào bộ nhớ ở mức kế tiếp khi khối bộ đệm bị lấy lại)cần 1 bít bẩn (dirty) cho mỗi khối bộ đệm để chỉ ra là khối đó cần được ghi lại vào bộ nhớ khi nó bị lấy lại – có thể dùng bộ đệm ghi để tăng tốc việc ghi lại các khối bộ đệm bẩn68Xử lý trượt bộ đệm (Khối kích thước 1 từ)Đọc trượt (I$ và D$): mất thời gian read_miss_penaltydừng đường ống, nạp khối từ bộ nhớ ở mức kế tiếp, đưa vào bộ đệm và gửi từ được yêu cầu tới bộ xử lý, tiếp tục đường ốngGhi trượt (D$) mất thời gian write_miss_penalty và write_buffer_stallsCấp phát và ghi – Đầu tiên đọc khối từ bộ nhớ và ghi từ vào khốiorKhông cấp phát và ghi– bỏ qua việc ghi vào bộ đệm; ghi từ vào bộ đệm ghi (tức là sẽ ghi vào bộ nhớ ở mức kết tiếp), không cần dừng nếu bộ đệm ghi không đầySET-HUST, 22/03/2011Chương 4. Bộ nhớ - Phân cấp bộ nhớ69Đo hiệu năng bộ đệmGiả sử thời gian truy cập bộ nhớ khi trúng bộ đệm được bao gồm trong 1 chu kỳ thực hiện thông thường của CPU thì:70CPIstallSố chu kỳ MemStallC là tổn thất trượt là tổng của read-stalls và write-stallsRead-stall cycles = reads/program × read miss rate × read miss penaltyWrite-stall cycles = (writes/program × write miss rate × write miss penalty) + write buffer stallsVới bộ đệm ghi xuyên, ta có công thức đơn giảnMemory-stall cycles = accesses/program × miss rate × miss penaltyẢnh hưởng của hiệu năng bộ đệmTổn thất tương đối của bộ đệm sẽ tăng khi hiệu năng bộ xử lý tăng (tăng tốc độ đồng hồ và/hoặc giảm CPI)Tốc độ bộ nhớ không được cải thiện nhanh như tốc độ bộ xử lý. Tổn thất trượt dùng để tính CPIstall được đo theo số chu kỳ bộ xử lý cần thiết để xử lý trượtCPIideal càng thấp thì ảnh hưởng của dừng do trượt càng lớnBộ xử lý với CPIideal = 2, tổn thất trượt là 100, 36% là lệnh load/store, tỉ lệ trượt bộ nhớ I$ là 2% và bộ nhớ D$ là 4%Nếu CPIideal giảm xuống 1? 0.5? 0.25?Nếu tỉ lệ trượt bộ nhớ D$ tăng lên 1%? 2%?Nếu tốc độ đồng hồ CPU tăng gấp 2 (tổn hao trượt tăng gấp 2)?SET-HUST, 22/03/2011Chương 4. Bộ nhớ - Phân cấp bộ nhớ71Ảnh hưởng của hiệu năng bộ đệmTổn thất tương đối của bộ đệm sẽ tăng khi hiệu năng bộ xử lý tăng (tăng tốc độ đồng hồ và/hoặc giảm CPI)Tốc độ bộ nhớ không được cải thiện nhanh như tốc độ bộ xử lý. Tổn thất trượt dùng để tính CPIstall được đo theo số chu kỳ bộ xử lý cần thiết để xử lý trượtCPIideal càng thấp thì ảnh hưởng của dừng do trượt càng lớnBộ xử lý với CPIideal = 2, tổn thất trượt là 100, 36% là lệnh load/store, tỉ lệ trượt bộ nhớ I$ là 2% và bộ nhớ D$ là 4%MemStallC = 2% × 100 + 36% × 4% × 100 = 3.44 CPIstalls = 2 + 3.44 = 5.44 gấp 2 lần CPIideal !Nếu CPIideal giảm xuống 1? 0.5? 0.25?Nếu tỉ lệ trượt bộ nhớ D$ tăng lên 1%? 2%?Nếu tốc độ đồng hồ CPU tăng gấp 2 (tổn hao trượt tăng gấp 2)?SET-HUST, 22/03/2011Chương 4. Bộ nhớ - Phân cấp bộ nhớ72Nguyên nhân trượt bộ đệmKhông tránh được:Lần đầu truy cập khốiGiải pháp: tăng kích thước khối (làm tăng tổn thất trượt, khối rất lớn làm tăng tỉ lệ trượt)Dung lượng:Bộ đệm không thể chứa toàn bộ các khối truy cập bởi chương trìnhGiải pháp: tăng kích thước bộ đệm (có thể làm tăng thời gian truy cập)Xung đột:Nhiều vị trí bộ nhớ cùng được ánh xạ vào 1 vị trí bộ đệmGiải pháp 1: tăng kích thước bộ đệmGiải pháp 2: tăng độ kết hợp trong bộ đệm (có thể tăng thời gian truy cập)SET-HUST, 22/03/2011Chương 4. Bộ nhớ - Phân cấp bộ nhớ73Tỷ số trượt bộ đệmMiss ratio = % of cache misses = (# cache misses / # memory accesses)Tỷ lệ trượt (%) = (số lần trượt/số lần truy nhập) Q: Hiệu năng thay đổi thế nào khi tỷ số trượt bộ đệm giảm từ 10.5% đến 3.5%?SlowerStays the sameFasterA: FasterCác ứng dụng có thể chạy nhanh hơn, nhưng không thể biết là nhanh ơn bao nhiêu. Tỷ lệ Trúng cache lớn hơn rất nhiều so với trượt.Average Memory Access Time (AMAT -Thời gian truy cập bộ nhớ trung bình )• Số chu kỳ trung bình cho một truy cập bộ nhớ = (hit time) + (miss %)*(miss time + miss penalty)Hit time = 1 Hit (1cycle)Miss time = 1 Miss (1 cycle)Miss penalty = 3 Penalty % miss = 2/6 = 33% AMAT = (1) + (33%)*(1 + 3) = 2.3 cycles per accessMiss Penalty là thời gian sau khi tìm kiếm trong cache.Ví dụ: AMATMachine 1– 100 truy nhập DRAM– 1 chu kỳ truy nhập cache (hit or miss)• Tính AMAT cho lbm?– cache có dung lượng 256kB ?• 6% miss ratio• (1) + (6%)*(1+100) = 7.06 cycles per memory access– cache có dung lượng 8MB ?• 3% miss ratio• (1) + (3%)*(1+100) = 4.03 cycles per memory accessMachine 2– 100 cycles to DRAM– 2 cycle cache access time (hit or miss)• Tính AMAT cho bzip2?– 256kB cache?• 1.5% miss ratio• (2) + (1.5%)*(2+100) = 3.53Q: Tại sao bzip2’s AMAT với 256kB cache gần giống với lbm’s với 8MB?Slower cacheDifferent miss ratiosDifferent applicationsA: Slower cacheCache mất 2 cycles cho Machine 2 và chỉ một chu kỳ cho Machine 1. Diều này làm ảnh hưởng đến AMAT.Ứng dụng khác nhau sẽ thấy 8MB cache có 3% miss ratio đối với lbm trong khi bzip2 có 1.5% miss ratio với cache 256kBPerformance impacts of memory access time• Ảnh thưởng của cace đến hiệu năng như thế nào(CPI)?– 100 chu kỳ trừng phạt trượt bộ đệm– 3% tỷ lệ trượt – 1.33 lần truy nhập bộ nhớ trên một lệnh (1 for instruction 33% for data)– CPI = 1.0 khi thực thi thông thường (lý tưởng)• Hiệu năng thay đổi thế nào?– CPI = CPIExecution + Memory stall cycles per instruction = 1.0 + 1.33*0.03*100 = 4.99– Phân cấp bộ nhớ này làm bộ xử lý chạy chậm hơn 5 lần!• Caches là rất quan trọng! Caches là quan trọng nhất để tăng hiệu năng.How much does cache matter?Phân tách lệnh và dữ liệu bộ nhớ đệm• Cần nạp lệnh(IF) và dữ liệu (MEM) cùng một thời điểm• Cần 2 loại cache:– Instruction cache (just instructions)– Data cache (just data)• AMAT khi phân chia cache:– AMAT: (% lệnh truy cập)*(hit time + (tỷ lệ trượt bộ đệm lệnh)*(miss time + miss penalty)) + (% dữ liệu truy cập)*(hit time + (tỷ lệ trượt bộ đệm dữ liệu)*(miss time + miss penalty))• Ví dụ: – Thời gian truy nhập cache là 1 cycle (hit or miss) và thời gian truy nhập bộ nhớ 100 cycle– I‐cache: 1% miss ratio, D‐cache: 5% miss ratio– 33% là lệnh loads/stores → 25% truy cập dữ liệu / 75% truy cập lệnh– (75%)*(1 + (1%)*(1+100)) + (25%)*(1 + (5%)*(1+100)) = 1.5 + 1.5 = 3.0AMD/Intel cachesHeterogeneous processor cachesMemory hierarchy• We want big and fast– Build a hierarchy where we keep the most important data in fast memory– Other data goes in slow memory– If we move the data correctly we provide the illusion of fast and big• Registers 3 accesses/cycle 32­‐64• Cache 1­‐10 cycles 8kB­‐256kB• Cache 40 cycles 4­‐20MB• DRAM 200 cycles 4­‐16GB• Flash 1000+ cycles 64­‐512GB• Hard Disk 1M+ cycles 2 ­‐4TBSummary: how to make the memory hierarchy work• 3 different cache types– Fully‐associative: Have to search all blocks, but very flexible– Direct‐mapped: Only one place for each block, no flexibility– Set‐associative: Only have to search one set for each block, flexible• We can adjust the block (line) size to reduce the overhead of tags• We figure out where data goes in a cache by looking at the address– Last 2 bits are the byte in the word– Next N bits are the word in the cache block– Remaining bits are for the tag• We have different write policies– Write‐through: slow, simple– Write‐back: fast (keeps the data just in the cache), more complex• Performance effects are due to the average memory access time