Computer Systems: A Programmer's Perspective Chương 6 · The Memory Hierarchy

Chương 6 · Phân cấp bộ nhớ Chapter 6 · The Memory Hierarchy

Bộ nhớ không phẳng: một kim tự tháp lưu trữ mà mã khéo léo biết trèo lên đỉnh Bộ nhớ xếp thành nhiều tầng — và mã tốt biết cách dùng tầng nhanh Memory is not flat: a pyramid of storage that clever code learns to climb

Cho tới chương này, sách vẫn dùng một mô hình đơn giản: bộ nhớ là một mảng byte tuyến tính mà CPU truy cập trong thời gian không đổi. Bryant và O'Hallaron chỉ ra mô hình đó không phản ánh cách máy thật vận hành: thực tế, hệ thống bộ nhớ là một phân cấp (hierarchy) các thiết bị lưu trữ với dung lượng, giá thành và thời gian truy cập rất khác nhau.1 Nếu dữ liệu nằm trong thanh ghi CPU, nó được truy cập trong 0 chu kỳ; trong bộ nhớ đệm (cache), 4 đến 75 chu kỳ; trong bộ nhớ chính, hàng trăm chu kỳ; còn trên đĩa, hàng chục triệu chu kỳ.1

Trước giờ ta cứ nghĩ bộ nhớ là một dãy ô, ô nào cũng lấy nhanh như nhau. Thật ra không phải vậy. Máy có nhiều loại chỗ chứa, xếp thành tầng: trên cùng bé xíu nhưng cực nhanh, dưới cùng rất lớn nhưng chậm. Lấy một con số từ thanh ghi gần như tức thì; lấy từ đĩa thì chậm hơn hàng chục triệu lần. Nhớ nhé: bộ nhớ là một kim tự tháp, không phải một mặt bàn phẳng.

Until this chapter, the book used a simple model: memory is a linear array of bytes the CPU accesses in constant time. Bryant and O'Hallaron show that model does not reflect how real machines work: in practice, a memory system is a hierarchy of storage devices with widely different capacities, costs, and access times.1 If your data are in a CPU register, they are accessed in 0 cycles; in a cache, 4 to 75 cycles; in main memory, hundreds of cycles; and on disk, tens of millions of cycles.1

Điều làm cho phân cấp này hoạt động được không phải phần cứng mà là một tính chất của phần mềm: chương trình viết tốt có xu hướng truy cập chỗ lưu trữ ở một tầng nhiều hơn hẳn tầng ngay dưới. Nhờ vậy, tầng dưới được phép chậm hơn — và do đó lớn hơn, rẻ hơn tính trên mỗi bit. Hiệu ứng tổng thể: một kho nhớ khổng lồ có giá gần bằng thiết bị rẻ ở đáy nhưng phục vụ dữ liệu với tốc độ gần bằng thiết bị nhanh ở đỉnh.1 Trên hệ Core i7 của tác giả, các nhân nhân ma trận cùng số phép toán nhưng khác mức cục bộ có thời gian chạy chênh nhau tới gần 40 lần.1

Luận đề của chương: hệ thống bộ nhớ không phải mảng byte phẳng chi phí như nhau, mà là một phân cấp các công nghệ lưu trữ nhanh–chậm chênh nhau nhiều bậc độ lớn; vì chương trình tốt có tính cục bộ (locality), mỗi tầng có thể làm bộ nhớ đệm (cache) cho tầng dưới, cho ta tốc độ gần đỉnh với chi phí gần đáy — và lập trình viên hiểu điều này có thể viết mã đặt dữ liệu ở tầng cao để chạy nhanh hơn hẳn.1

Ý chính: bộ nhớ xếp tầng nhanh–chậm. Vì chương trình hay dùng đi dùng lại một nhóm dữ liệu gần nhau, máy giữ bản sao của chúng ở tầng nhanh. Viết mã biết tận dụng điều đó thì chạy nhanh hơn rất nhiều. Nhớ nhé: để dữ liệu hay dùng ở tầng nhanh thì chương trình bay.

The chapter's thesis: a memory system is not a flat array of equal-cost bytes but a hierarchy of storage technologies whose speeds differ by orders of magnitude; because good programs have locality, each level can serve as a cache for the one below, giving near-top speed at near-bottom cost — and a programmer who understands this can write code that keeps data high in the hierarchy and runs far faster.1

Cụm khái niệm 01 Concept cluster 01

Công nghệ lưu trữ: vì sao có loại nhanh mà đắt, loại chậm mà rẻ Các loại chỗ chứa dữ liệu, và vì sao chúng khác nhau Storage technologies: why some are fast and costly, others slow and cheap

Phần lớn thành công của máy tính đến từ tiến bộ về lưu trữ. Những máy đầu tiên chỉ có vài kilobyte bộ nhớ truy cập ngẫu nhiên; IBM PC-XT năm 1982 mới có đĩa 10 megabyte. Đến năm 2015, máy tiêu biểu có dung lượng đĩa gấp 300.000 lần, và cứ vài năm lại tăng gấp đôi.1 Chương mở đầu bằng cách so sánh các công nghệ nền tảng — SRAM, DRAM, đĩa quay và đĩa thể rắn (SSD) — vì mỗi loại có một đánh đổi giá/tốc độ riêng.

Máy tính mạnh lên phần lớn nhờ chỗ chứa dữ liệu ngày càng tốt. Có loại nhớ cực nhanh nhưng đắt và nhỏ; có loại rất lớn, rẻ nhưng chậm. Không loại nào vừa nhanh, vừa rẻ, vừa lớn cả. Nhớ nhé: nhanh thì đắt và nhỏ, rẻ thì chậm và lớn — luôn phải chọn.

Much of computing's success comes from storage progress. Early machines had a few kilobytes of RAM; the 1982 IBM PC-XT had a 10-megabyte disk. By 2015 a typical machine had 300,000 times the disk capacity, doubling every couple of years.1 The chapter opens by contrasting the fundamental technologies — SRAM, DRAM, rotating disks, and solid state disks (SSDs) — because each carries its own price/speed trade-off.

Định nghĩa. SRAM (RAM tĩnh) lưu mỗi bit trong một ô nhớ hai trạng thái bền bằng mạch sáu transistor; nó giữ giá trị chừng nào còn điện. DRAM (RAM động) lưu mỗi bit bằng điện tích trên một tụ nhỏ (khoảng 30 femtofarad), chỉ cần một tụ và một transistor nên dày đặc hơn nhiều, nhưng phải được làm tươi (refresh) định kỳ.1

Nói đơn giản. SRAM như một công tắc giữ nguyên trạng thái, nhanh nhưng tốn chỗ. DRAM như một cái xô nước rỉ, phải đổ đầy lại liên tục, nhưng nhỏ gọn nên chứa được nhiều. Nhớ nhé: SRAM nhanh mà cồng kềnh, DRAM nhỏ gọn mà phải nạp lại hoài.

Definition. SRAM (static RAM) stores each bit in a bistable six-transistor cell and holds its value as long as it is powered. DRAM (dynamic RAM) stores each bit as charge on a tiny capacitor (about 30 femtofarads) with just one capacitor and one transistor, so it is far denser, but it must be refreshed periodically.1

SRAM: 6 transistor/bit · ~1× · giá ~1000×
DRAM: 1 transistor/bit · ~10× · giá 1×
Đĩa: Taccess = Tseek + Trotation + Ttransfer
  ≈ 9 + 4 + 0,02 = 13,02 ms

SRAM: nhanh, đắt, nhỏ
DRAM: vừa phải
Đĩa: rất lớn, rất chậm (~13 ms)

SRAM: 6 transistors/bit · ~1× · ~1000× cost
DRAM: 1 transistor/bit · ~10× · 1× cost
Disk: Taccess = Tseek + Trotation + Ttransfer
  ≈ 9 + 4 + 0.02 = 13.02 ms

  1. SRAM vs DRAM

    SRAM và DRAM — đánh đổi giữa tốc độ, mật độ và giá SRAM và DRAM — nhanh-đắt hay nhỏ-gọn SRAM vs DRAM — trading speed, density and cost

    Bảng đặc trưng của sách tóm gọn đánh đổi: một ô SRAM dùng 6 transistor cho mỗi bit, truy cập lấy làm mốc 1×, bền chừng nào còn điện, không nhạy nhiễu — nhưng đắt khoảng 1.000× tính trên mỗi bit. Một ô DRAM chỉ dùng 1 transistor, nên rẻ bằng 1× nhưng truy cập chậm khoảng 10×, không bền và nhạy với nhiễu, ánh sáng.1 Vì thế SRAM dùng làm cache, DRAM làm bộ nhớ chính.

    SRAM dùng nhiều linh kiện cho một bit nên đắt và chiếm chỗ, bù lại chạy nhanh và giữ giá trị chắc. DRAM chỉ cần một tụ tí hon nên rẻ và chứa được nhiều, nhưng chậm hơn và hay quên nếu không nạp lại. Nhớ nhé: SRAM làm ngăn nhanh sát CPU, DRAM làm kho lớn phía dưới.

    The book's table captures the trade-off: an SRAM cell uses 6 transistors per bit, a baseline 1× access time, stays persistent while powered, and is insensitive to noise — but costs roughly 1,000× per bit. A DRAM cell uses just 1 transistor, so it costs 1× but is about 10× slower, not persistent, and sensitive to disturbances and light.1 Hence SRAM for caches, DRAM for main memory.

    Bạn gặp nó ở đâuWhere you meet it Mỗi khi bạn thấy máy có vài megabyte cache nhưng hàng gigabyte RAM: cache ít vì SRAM đắt, RAM nhiều vì DRAM rẻ.1 Máy có rất nhiều RAM nhưng chỉ vài megabyte cache — vì loại nhanh thì đắt. Whenever a machine has a few megabytes of cache but gigabytes of RAM: little cache because SRAM is costly, lots of RAM because DRAM is cheap.1

    Vì sao DRAM phải làm tươi

    Dòng rò làm ô DRAM mất điện tích trong khoảng 10–100 mili-giây, nên hệ thống phải đọc ra rồi ghi lại từng bit định kỳ. Một số hệ còn mã hoá sửa lỗi: một từ 64 bit được mã bằng 72 bit để phát hiện và sửa một bit sai.1

    Bộ nhớ không mất (nonvolatile)

    SRAM và DRAM đều mất dữ liệu khi tắt điện. Các bộ nhớ không mất — gọi chung là ROM dù một số ghi lại được — gồm PROM, EPROM, EEPROM và flash; flash là nền tảng cho SSD mà ta gặp ngay sau đây.1

  2. rotating disks

    Đĩa quay — rất lớn, rất rẻ, nhưng thời gian truy cập bị cơ học chi phối Đĩa quay — chứa nhiều, giá rẻ, nhưng chậm vì phải quay và dịch đầu đọc Rotating disks — huge, cheap, but access time is dominated by mechanics

    Đĩa chứa hàng trăm tới hàng nghìn gigabyte, nhưng đọc một thông tin mất cỡ mili-giây — chậm hơn DRAM khoảng một trăm nghìn lần và SRAM khoảng một triệu lần.1 Thời gian truy cập một sector gồm ba phần: thời gian tìm (seek), độ trễ quay (rotational latency) và thời gian truyền (transfer). Với một đĩa 7.200 vòng/phút, Tseek 9 ms, 400 sector/rãnh, tổng thời gian ước tính là 9 + 4 + 0,02 = 13,02 ms — bị thời gian tìm và độ trễ quay chi phối gần hết.1

    Đĩa quay giống một cái đĩa than: có một cánh tay mang đầu đọc phải dịch tới đúng rãnh, rồi chờ chỗ cần đọc quay tới dưới đầu. Vì có bộ phận chuyển động nên nó chậm hơn bộ nhớ điện tử rất nhiều. Nhớ nhé: đĩa chậm vì phải chờ cơ học quay và dịch, không phải vì thiếu dung lượng.

    Disks hold hundreds to thousands of gigabytes, but reading takes on the order of milliseconds — about a hundred thousand times longer than DRAM and a million times longer than SRAM.1 A sector's access time has three parts: seek time, rotational latency, and transfer time. For a 7,200 RPM disk with Tseek 9 ms and 400 sectors per track, the estimate is 9 + 4 + 0.02 = 13.02 ms — almost entirely seek and rotation.1

    Bạn gặp nó ở đâuWhere you meet it Byte đầu của một sector tốn nhiều thời gian, các byte sau gần như miễn phí — vì thế đọc tuần tự luôn nhanh hơn đọc rải rác.1 Đọc liền một mạch nhanh hơn nhiều so với nhảy lung tung khắp đĩa. The first byte of a sector is expensive, the rest are essentially free — which is why sequential reads beat scattered ones.1

    Đĩa so với bộ nhớ, bằng con số

    Sách ước tính: đọc một từ 64 bit mất ~4 ns từ SRAM và ~60 ns từ DRAM; đọc một khối cỡ sector 512 byte mất ~256 ns từ SRAM và ~4.000 ns từ DRAM. Thời gian truy cập đĩa ~10 ms lớn hơn SRAM khoảng 40.000 lần và DRAM khoảng 2.500 lần.1

    Khối logic và DMA

    Đĩa giấu hình học phức tạp sau một dãy khối logic (logical block) cùng kích thước. Khi đọc, bộ điều khiển đĩa chuyển dữ liệu thẳng vào bộ nhớ chính qua truy cập bộ nhớ trực tiếp (DMA) rồi báo CPU bằng một ngắt, để CPU làm việc khác trong lúc chờ.1

  3. SSDs & the widening gap

    SSD và khoảng cách ngày càng rộng với CPU Ổ SSD và vì sao CPU ngày càng “đợi” bộ nhớ SSDs and the widening gap with the CPU

    SSD là đĩa dựa trên flash, không có bộ phận chuyển động nên truy cập ngẫu nhiên nhanh hơn, ít tốn điện và bền hơn đĩa quay. Theo thông số chiếc Intel SSD 730 mà sách dẫn, đọc tuần tự đạt 550 MB/s và ghi 470 MB/s; ngẫu nhiên đạt 89.000 IOPS khi đọc và 74.000 IOPS khi ghi.12 Đọc nhanh hơn ghi, và mỗi khối flash chỉ chịu được khoảng 100.000 lần ghi trước khi hỏng.1

    SSD là ổ nhớ không có đĩa quay, chỉ toàn chip, nên lấy dữ liệu bất kỳ đâu cũng nhanh. Nó đọc nhanh hơn ghi, và dùng lâu quá cũng mòn. Dù vậy nó vẫn chậm hơn RAM nhiều. Nhớ nhé: SSD nhanh hơn đĩa quay nhưng vẫn là tầng dưới của RAM.

    An SSD is a flash-based disk with no moving parts, so it has faster random access, uses less power, and is more rugged than a rotating disk. Per the Intel SSD 730 spec the book cites, sequential reads reach 550 MB/s and writes 470 MB/s; random access reaches 89,000 read IOPS and 74,000 write IOPS.12 Reads are faster than writes, and each flash block survives only about 100,000 writes before wearing out.1

    Bạn gặp nó ở đâuWhere you meet it Xu hướng lưu trữ cho thấy vì sao phải có cache: từ 1985–2015, giá mỗi megabyte DRAM giảm 44.000 lần nhưng thời gian truy cập chỉ nhanh lên 10 lần, còn chu kỳ CPU nhanh lên 500 lần — khoảng cách CPU–bộ nhớ ngày càng rộng.1 CPU nhanh lên rất nhiều, còn bộ nhớ thì chỉ nhanh lên chút ít — nên CPU hay phải chờ. Storage trends show why caches are needed: from 1985–2015, DRAM cost per megabyte fell 44,000× but access time improved only 10×, while CPU cycle time improved 500× — the processor–memory gap keeps widening.1

    Vì sao ghi ngẫu nhiên chậm

    Flash chỉ ghi được một trang sau khi đã xoá cả khối chứa nó, mà xoá một khối tốn cỡ 1 ms. Muốn sửa một trang đang có dữ liệu, các trang hữu ích khác trong khối phải được chép sang khối mới trước. Tầng dịch flash (flash translation layer) và logic cân bằng hao mòn (wear-leveling) cố giảm chi phí này.1

    Khoảng cách là độ trễ rồi thành thông lượng

    Trước khoảng 2003, khoảng cách CPU–bộ nhớ chủ yếu là vấn đề độ trễ (latency). Sau khi vi xử lý nhiều nhân xuất hiện, nó ngày càng là vấn đề thông lượng (throughput), khi nhiều nhân cùng phát yêu cầu tới DRAM và đĩa song song.1

Cụm khái niệm 02 Concept cluster 02

Tính cục bộ, và vì sao mỗi tầng có thể làm cache cho tầng dưới Dữ liệu gần nhau, dùng lại nhiều — nền tảng của phân cấp Locality, and why each level can cache the one below

Chương trình viết tốt có xu hướng tham chiếu những dữ liệu nằm gần dữ liệu vừa dùng, hoặc chính dữ liệu vừa dùng. Xu hướng này — nguyên lý cục bộ (principle of locality) — là một ý tưởng bền bỉ, chi phối thiết kế cả phần cứng lẫn phần mềm.14 Nói chung, chương trình có tính cục bộ tốt chạy nhanh hơn chương trình có tính cục bộ kém.

Chương trình tốt thường “quanh quẩn” một chỗ: vừa đọc ô này thì sắp đọc ô bên cạnh, hoặc đọc lại chính ô vừa rồi. Nhờ thế máy đoán trước được và để sẵn dữ liệu ở tầng nhanh. Nhớ nhé: chương trình quanh quẩn một vùng thì máy phục vụ nhanh.

Well-written programs tend to reference data near recently referenced data, or the recently referenced data itself. This tendency — the principle of locality — is an enduring idea that shapes the design of both hardware and software.14 In general, programs with good locality run faster than those with poor locality.

Định nghĩa. Cục bộ thời gian (temporal locality): một ô nhớ được tham chiếu một lần thì có khả năng được tham chiếu lại nhiều lần trong tương lai gần. Cục bộ không gian (spatial locality): nếu một ô được tham chiếu, các ô gần nó có khả năng được tham chiếu sắp tới.1

Nói đơn giản. Cục bộ thời gian là “dùng rồi sẽ dùng lại”. Cục bộ không gian là “dùng ô này thì sắp dùng ô kế bên”. Nhớ nhé: dùng lại = cục bộ thời gian; dùng chỗ kế bên = cục bộ không gian.

Definition. Temporal locality: a location referenced once is likely to be referenced again soon. Spatial locality: if a location is referenced, nearby locations are likely to be referenced soon.1

Chi phí truy cập (chu kỳ):
L0 thanh ghi 0 · L1 ~4 · L2 ~10
L3 ~50 · bộ nhớ chính ~200
đĩa hàng chục triệu

càng lên cao càng nhanh:
thanh ghi → cache → RAM → đĩa

Access cost (cycles):
L0 registers 0 · L1 ~4 · L2 ~10
L3 ~50 · main memory ~200
disk tens of millions

  1. stride-1 patterns

    Bước nhảy 1 — nguồn cục bộ không gian quan trọng nhất Đi tuần tự từng ô — cách duyệt tốt nhất cho cache Stride-1 patterns — the key source of spatial locality

    Hàm quét một vectơ lần lượt từng phần tử có mẫu tham chiếu bước nhảy 1 (stride-1) và cục bộ không gian tốt; quét cách k phần tử là bước nhảy k, bước càng lớn cục bộ càng kém.1 Vì mảng trong C xếp theo thứ tự hàng (row-major), duyệt theo hàng cho bước nhảy 1, còn duyệt theo cột cho bước nhảy N — và sách cho biết phiên bản duyệt theo hàng chạy nhanh hơn phiên bản theo cột tới 25 lần trên máy để bàn của tác giả.1

    Nếu bạn đọc mảng theo đúng thứ tự nó nằm trong bộ nhớ (từng ô liền nhau), máy phục vụ rất nhanh. Nếu bạn nhảy cóc, mỗi lần lại phải lấy khối mới, chậm hẳn. Cùng một phép tính, đổi thứ tự hai vòng lặp có thể làm chương trình nhanh lên hàng chục lần. Nhớ nhé: duyệt mảng theo đúng thứ tự nó nằm trong bộ nhớ.

    A function scanning a vector element by element has a stride-1 reference pattern and good spatial locality; visiting every kth element is stride-k, and larger strides mean poorer locality.1 Because C arrays are laid out in row-major order, scanning by rows gives stride-1 while scanning by columns gives stride-N — and the book reports the row-wise version runs 25 times faster than the column-wise one on the authors' desktop.1

    Bạn gặp nó ở đâuWhere you meet it Khi hoán đổi hai vòng lặp i và j trong phép cộng ma trận làm tốc độ đổi hẳn, dù kết quả giống nhau.1 Khi chỉ đổi thứ tự hai vòng lặp mà chương trình nhanh hoặc chậm hẳn. When swapping the i and j loops in a matrix sum changes the speed dramatically, though the result is identical.1

    Cục bộ của lệnh

    Mã lệnh cũng có tính cục bộ: thân một vòng lặp được nạp tuần tự (cục bộ không gian) và chạy nhiều lần (cục bộ thời gian). Thân vòng lặp càng nhỏ và số vòng càng nhiều thì cục bộ càng tốt.1

    Đọc code bằng mắt

    Trước khi đo đạc, chỉ cần liếc mã nguồn và ước lượng cục bộ đã là một kỹ năng quý: biến dùng lặp lại (cục bộ thời gian tốt), và bước nhảy nhỏ (cục bộ không gian tốt) là hai dấu hiệu dễ nhận.1

  2. the hierarchy

    Phân cấp L0–L6 — mỗi tầng là cache cho tầng ngay dưới Các tầng L0–L6 — tầng trên giữ bản sao của tầng dưới The L0–L6 hierarchy — each level caches the one below

    Hai tính chất — công nghệ lưu trữ chênh lệch tốc độ và phần mềm có cục bộ — bổ trợ nhau tuyệt đẹp, gợi ra cách tổ chức gọi là phân cấp bộ nhớ (memory hierarchy): thanh ghi CPU ở L0; các cache SRAM L1–L3; bộ nhớ chính DRAM ở L4; đĩa cục bộ ở L5; lưu trữ từ xa ở L6.1 Ý trung tâm: với mỗi tầng k, thiết bị nhanh–nhỏ ở tầng k làm cache cho thiết bị chậm–lớn ở tầng k+1.1

    Các chỗ chứa dữ liệu xếp thành bậc thang: trên cùng nhỏ-nhanh, dưới cùng lớn-chậm. Mỗi bậc giữ sẵn bản sao của những thứ hay dùng từ bậc dưới. Khi cần, máy nhìn bậc trên trước; thường là có sẵn. Nhớ nhé: mỗi tầng là bộ nhớ đệm cho tầng ngay dưới nó.

    The two properties — storage technologies that differ in speed and software with locality — complement each other beautifully, suggesting the memory hierarchy: CPU registers at L0; SRAM caches L1–L3; DRAM main memory at L4; local disks at L5; remote storage at L6.1 The central idea: for each level k, the fast, small device at level k is a cache for the slow, large device at level k+1.1

    Bạn gặp nó ở đâuWhere you meet it Caching có mặt khắp nơi: trình duyệt lưu trang vừa xem trên đĩa, hệ điều hành dùng RAM làm cache cho đĩa — cùng một nguyên lý ở mọi tầng.1 Trình duyệt giữ lại trang vừa xem để mở lại cho nhanh — đó cũng là caching. Caching is everywhere: a browser keeps recently viewed pages on disk, the OS uses RAM as a cache for disk — the same principle at every level.1

    Khối và đơn vị chuyển

    Tầng k+1 được chia thành các khối (block) cùng kích thước; tầng k giữ bản sao một tập con các khối đó. Dữ liệu luôn được chép qua lại theo từng khối. Tầng càng xa CPU, thời gian truy cập càng lâu nên khối thường càng lớn để khấu hao chi phí.1

    Ai quản lý cache

    Trình biên dịch quản lý tệp thanh ghi; các cache L1–L3 do phần cứng quản lý hoàn toàn; bộ nhớ ảo do hệ điều hành cùng phần cứng dịch địa chỉ; cache đĩa do firmware; cache web do trình duyệt — mỗi tầng một cơ chế.1

  3. hits & misses

    Trúng và trượt — ba loại trượt mà lập trình viên nên biết Trúng (có sẵn) và trượt (phải đi lấy) Hits & misses — the three kinds of miss to know

    Khi cần một đối tượng d, nếu nó đã nằm ở tầng k thì ta có trúng (hit) và đọc nhanh; nếu không, ta có trượt (miss): tầng k phải lấy khối chứa d từ tầng k+1, có thể phải loại bỏ (evict) một khối cũ theo chính sách thay thế (ví dụ LRU).1 Sách phân biệt ba loại trượt: trượt bắt buộc (cold/compulsory) khi cache còn trống; trượt xung đột (conflict) khi nhiều khối ánh xạ vào cùng chỗ; và trượt dung lượng (capacity) khi tập làm việc lớn hơn cache.1

    “Trúng” là thứ cần đã có sẵn ở tầng nhanh — lấy liền. “Trượt” là chưa có, phải xuống tầng dưới lấy, và có khi phải bỏ bớt thứ cũ để lấy chỗ. Có ba kiểu trượt: do mới bắt đầu, do chen chỗ, và do chứa không nổi. Nhớ nhé: trúng thì nhanh, trượt thì phải đi lấy — mục tiêu là giảm trượt.

    When a program needs object d, if it is already at level k we have a hit and read it fast; otherwise a miss: level k fetches the block containing d from level k+1, possibly evicting an old block per a replacement policy (e.g. LRU).1 The book distinguishes three kinds of miss: cold (compulsory) misses on an empty cache; conflict misses when several blocks map to the same slot; and capacity misses when the working set exceeds the cache.1

    Bạn gặp nó ở đâuWhere you meet it Khi một chương trình đột nhiên chậm lúc kích thước dữ liệu vượt một ngưỡng nào đó — thường là lúc tập làm việc không còn lọt trong một tầng cache.1 Khi dữ liệu to lên một chút mà chương trình chậm hẳn — cache không chứa nổi nữa. When a program suddenly slows once the data grows past some size — usually when the working set no longer fits in a cache level.1

Cụm khái niệm 03 Concept cluster 03

Bộ nhớ đệm: bộ ba tham số (S, E, B), và cách viết mã thân thiện với cache Cache được tổ chức ra sao, và viết mã thế nào cho khéo Cache memories: the (S, E, B) parameters, and writing cache-friendly code

Một cache được tổ chức thành một mảng gồm S = 2s tập hợp (set); mỗi tập có E dòng (line); mỗi dòng chứa một khối dữ liệu B = 2b byte, một bit hợp lệ (valid), và t bit thẻ (tag).1 Tổ chức này được đặc trưng bởi bộ (S, E, B, m), với kích thước C = S × E × B. Một địa chỉ được chia thành ba phần: bit thẻ, bit chỉ số tập hợp, và bit độ lệch trong khối — đúng như một bảng băm với hàm băm cực đơn giản.1

Hãy hình dung cache như một tủ nhiều ngăn kéo (các “tập hợp”), mỗi ngăn giữ một hoặc vài hộp (các “dòng”), mỗi hộp chứa một khối dữ liệu liền nhau. Khi cần một ô nhớ, máy dùng vài bit của địa chỉ để biết mở ngăn nào, rồi so “nhãn” để biết hộp nào. Nhớ nhé: cache là cái tủ có ngăn và hộp, địa chỉ cho biết mở ngăn nào.

A cache is organized as an array of S = 2s sets; each set has E lines; each line holds a data block of B = 2b bytes, a valid bit, and t tag bits.1 This is characterized by the tuple (S, E, B, m), with size C = S × E × B. An address splits into three fields: tag bits, set index bits, and block offset bits — exactly like a hash table with an extremely simple hash function.1

Định nghĩa. Cache phân loại theo E — số dòng mỗi tập. E = 1 là ánh xạ trực tiếp (direct-mapped): mỗi tập một dòng. 1 < E < C/B là liên kết tập hợp E chiều (E-way set-associative). E = C/B (một tập duy nhất) là liên kết đầy đủ (fully associative).1

Nói đơn giản. Mỗi ngăn kéo chỉ một hộp là loại “trực tiếp”, dễ làm nhưng dễ chen chỗ. Mỗi ngăn vài hộp là loại “liên kết tập hợp”, ít chen chỗ hơn. Nhớ nhé: nhiều hộp mỗi ngăn thì ít đụng độ hơn.

Definition. Caches are classed by E — lines per set. E = 1 is direct-mapped: one line per set. 1 < E < C/B is E-way set-associative. E = C/B (a single set) is fully associative.1

C = S × E × B
s = log₂S · b = log₂B
t = m − (s + b)
tỉ lệ trượt = #trượt / #tham chiếu

kích thước = số ngăn × số hộp × cỡ khối
tỉ lệ trượt càng thấp càng nhanh

C = S × E × B
s = log₂S · b = log₂B
t = m − (s + b)
miss rate = #misses / #references

  1. direct-mapped

    Ánh xạ trực tiếp — ba bước: chọn tập, so thẻ, lấy từ Ánh xạ trực tiếp — đơn giản nhất, nhưng dễ chen chỗ Direct-mapped — three steps: set select, line match, word select

    Với cache ánh xạ trực tiếp, mỗi lần truy cập gồm ba bước: (1) dùng s bit chỉ số để chọn tập; (2) so t bit thẻ của dòng duy nhất trong tập và kiểm tra bit hợp lệ; (3) nếu khớp, dùng b bit độ lệch để lấy từ cần trong khối.1 Vì mỗi tập chỉ một dòng, việc so khớp cực nhanh — nhưng cũng chính vì thế mà dễ sinh xung đột.

    Máy làm ba việc rất nhanh: mở đúng ngăn, so nhãn cái hộp duy nhất trong ngăn, rồi lấy đúng byte trong hộp. Vì mỗi ngăn chỉ chứa một hộp nên làm cực nhanh, nhưng hai thứ cần cùng lúc mà “rơi” vào một ngăn thì phải tranh chỗ. Nhớ nhé: một hộp mỗi ngăn thì nhanh nhưng dễ tranh chỗ.

    In a direct-mapped cache each access has three steps: (1) use the s index bits to select a set; (2) compare the t tag bits of the set's single line and check the valid bit; (3) if they match, use the b offset bits to extract the requested word from the block.1 With one line per set the match is very fast — but that is exactly what makes conflicts easy.

    Bạn gặp nó ở đâuWhere you meet it Cache dùng bit giữa làm chỉ số tập (không phải bit cao) để các khối liền nhau rơi vào các tập khác nhau, giúp giữ cả một vùng mảng trong cache cùng lúc.1 Máy chọn ngăn bằng các bit ở giữa địa chỉ, để các ô liền nhau không dồn hết vào một ngăn. Caches use the middle address bits as the set index (not the high bits) so adjacent blocks fall into different sets, keeping a whole array region cached at once.1

    Dòng, tập, khối

    Sách nhấn mạnh phân biệt: khối là gói dữ liệu di chuyển giữa các tầng; dòng là nơi chứa một khối cùng bit hợp lệ và thẻ; tập là nhóm một hay nhiều dòng. Ở cache trực tiếp thì dòng và tập trùng nhau, nhưng ở cache liên kết thì không.1

    Vấn đề với ghi

    Với ghi, có ghi xuyên (write-through) (ghi ngay xuống tầng dưới) hoặc ghi trả sau (write-back) (chỉ ghi khi dòng bị loại bỏ, cần một bit “bẩn”). Sách khuyên lập trình viên cứ hình dung mô hình write-back, write-allocate.1

  2. conflict misses

    Xung đột và giằng co — và vì sao liên kết tập hợp cứu nguy Khi hai mảng “đánh nhau” giành một chỗ trong cache Conflict misses & thrashing — why associativity helps

    Trượt xung đột hay xảy ra khi chương trình truy cập các mảng có kích thước là luỹ thừa của 2. Trong ví dụ tích vô hướng của sách, nếu x và y ánh xạ vào cùng một tập, mỗi lần lặp lại nạp rồi loại bỏ đúng khối vừa dùng — hiện tượng giằng co (thrashing) — có thể làm chậm đi 2–3 lần dù cache đủ sức chứa.1 Cache liên kết tập hợp (set-associative) cho mỗi tập nhiều dòng nên giảm hẳn xung đột; Core i7 dùng L1, L2 tám chiều và L3 mười sáu chiều.13

    Nếu hai mảng tình cờ cùng “rơi” vào một ngăn, chúng thay phiên hất nhau ra khỏi ngăn đó, nên dù cache còn trống chỗ khác, máy vẫn cứ trượt liên tục — chậm đi vài lần. Cách sửa dễ: cho mỗi ngăn chứa nhiều hộp. Nhớ nhé: nhiều hộp mỗi ngăn thì hai mảng thôi tranh chỗ.

    Conflict misses often strike when a program accesses arrays whose sizes are powers of 2. In the book's dot-product example, if x and y map to the same set, each iteration loads then evicts the very block just used — thrashing — which can slow things by a factor of 2–3 even though the cache is big enough.1 A set-associative cache gives each set several lines and sharply cuts conflicts; the Core i7 uses 8-way L1 and L2 and 16-way L3.13

    Bạn gặp nó ở đâuWhere you meet it Mẹo đơn giản của sách: thêm vài phần tử đệm ở cuối một mảng (ví dụ khai báo float x[12] thay vì x[8]) để x và y rơi vào tập khác nhau, xoá bỏ giằng co.1 Đôi khi chỉ cần nới mảng rộng ra một chút là hết cảnh hai mảng tranh chỗ. The book's simple trick: pad an array with a few extra elements (e.g. declare float x[12] instead of x[8]) so x and y land in different sets, ending the thrashing.1

    Core i7 bằng con số

    Sách cho bảng đặc trưng cache Core i7: L1 i-cache và d-cache mỗi loại 32 KB, 8 chiều, khối 64 byte, 64 tập, truy cập ~4 chu kỳ; L2 hợp nhất 256 KB, 8 chiều, ~10 chu kỳ; L3 hợp nhất 8 MB dùng chung, 16 chiều, ~40–75 chu kỳ.13

    Một lưu ý về con số L3

    Sách dùng hai cách trình bày độ trễ L3: bảng khái quát (Hình 6.23) ghi gọn ~50 chu kỳ, còn bảng Core i7 thực (Hình 6.39) ghi 40–75 chu kỳ. Bài này theo khung của sách: dùng ~50 ở mức tổng quát và 40–75 cho máy Core i7 cụ thể.1

  3. the memory mountain

    Ngọn núi bộ nhớ — chạy trên đỉnh, đừng chạy dưới thung lũng Ngọn núi bộ nhớ — bức tranh tốc độ theo cục bộ The memory mountain — run on the peaks, not in the valleys

    Nếu đo thông lượng đọc (read throughput) khi thay đổi kích thước tập làm việc (cục bộ thời gian) và bước nhảy (cục bộ không gian), ta được một mặt hai chiều gọi là ngọn núi bộ nhớ (memory mountain). Trên hệ Core i7 Haswell, đỉnh cao nhất của sườn L1 đọc hơn 14 GB/s, còn điểm thấp nhất của sườn bộ nhớ chính chỉ 900 MB/s — chênh hơn một bậc độ lớn.13 Thậm chí khi tập làm việc quá lớn, bước nhảy 1 vẫn giữ thông lượng phẳng ~12 GB/s nhờ cơ chế nạp trước (prefetching) phần cứng.1

    Người ta vẽ được một “ngọn núi”: dữ liệu càng gọn và duyệt càng tuần tự thì càng lên đỉnh (nhanh); dữ liệu càng to và nhảy càng xa thì càng xuống thung lũng (chậm). Đỉnh và đáy chênh nhau hơn mười lần. Viết mã khéo là cố chạy trên đỉnh. Nhớ nhé: gọn và tuần tự thì ở đỉnh núi, to và nhảy xa thì rơi xuống đáy.

    If you measure read throughput while varying working-set size (temporal locality) and stride (spatial locality), you get a two-dimensional surface called the memory mountain. On a Core i7 Haswell system, the highest peak of the L1 ridge reads over 14 GB/s, while the lowest point of the main-memory ridge is only 900 MB/s — over an order of magnitude apart.13 Even when the working set is too large, stride-1 keeps throughput flat at about 12 GB/s thanks to hardware prefetching.1

    Bạn gặp nó ở đâuWhere you meet it Trong phép nhân ma trận: sắp lại thứ tự vòng lặp đưa nó về lớp “BC” chỉ 0,5 lần trượt mỗi vòng, thay vì lớp “AC” tới 2,0 lần trượt — cùng số phép toán, khác hẳn tốc độ.1 Cùng một phép nhân ma trận, đổi thứ tự vòng lặp cho ít trượt hơn hẳn nên nhanh hơn nhiều. In matrix multiply: reordering the loops moves it to the "BC" class at just 0.5 misses per iteration instead of the "AC" class at 2.0 — same operations, very different speed.1

    Hai quy tắc viết mã thân thiện

    Sách rút ra: (1) làm cho trường hợp phổ biến chạy nhanh — tập trung vào vòng lặp trong của các hàm lõi; (2) giảm số lần trượt trong mỗi vòng lặp trong. Hai dấu hiệu tốt: dùng lại biến cục bộ (cache vào thanh ghi) và mẫu bước nhảy 1.1

    Cùng phép tính, khác cục bộ

    Với cache khối 64 byte và mảng lớn hơn cache, sumarrayrows (theo hàng) đạt tỉ lệ trượt 1/4, còn sumarraycols (theo cột) gần như trượt mọi lần — chênh lệch đủ để bản theo hàng nhanh hơn 25 lần.1

Ba ngộ nhận thường gặp Three common misconceptions

“Bộ nhớ là mảng phẳng, ô nào cũng nhanh như nhau” “Memory is a flat array; every cell is equally fast”

Ngộ nhận: CPU truy cập mọi ô nhớ trong thời gian không đổi.

Thực tế: đó chỉ là mô hình đơn giản; thật ra chi phí truy cập chênh nhau từ 0 chu kỳ (thanh ghi) tới hàng chục triệu chu kỳ (đĩa).1

Myth: the CPU accesses every cell in constant time.

Reality: that is only a simple model; real access cost ranges from 0 cycles (registers) to tens of millions (disk).1

“Cache là việc của phần cứng, lập trình viên khỏi lo” “Caching is the hardware's job, not the programmer's”

Ngộ nhận: cache chạy tự động nên cách viết mã không ảnh hưởng.

Thực tế: cùng một thuật toán, mã có cục bộ tốt có thể nhanh hơn hàng chục lần (ví dụ duyệt theo hàng nhanh hơn theo cột 25 lần).1

Myth: caches run automatically, so how you write code does not matter.

Reality: for the same algorithm, code with good locality can be an order of magnitude faster (row-wise beats column-wise by 25×).1

“Cache lớn hơn thì luôn tốt hơn” “A bigger cache is always better”

Ngộ nhận: cứ làm cache thật lớn là mọi chương trình nhanh lên.

Thực tế: cache lớn tăng tỉ lệ trúng nhưng khó làm nhanh, nên tăng thời gian trúng — đó là lý do L1 nhỏ hơn L2, L2 nhỏ hơn L3; mỗi tham số là một đánh đổi.1

Myth: just make the cache huge and every program speeds up.

Reality: a bigger cache raises the hit rate but is harder to make fast, so it raises hit time — which is why L1 is smaller than L2, L2 than L3; each parameter is a trade-off.1

Tự kiểm Self-check

Năm câu hỏi để biết bạn đã nắm phân cấp bộ nhớ Năm câu hỏi kiểm tra nhanh Five questions to check you grasped the hierarchy

Trả lời được những câu này nghĩa là bạn đã hiểu vì sao bộ nhớ xếp tầng, và làm sao viết mã để dữ liệu nằm ở tầng nhanh.

Nếu trả lời được, nghĩa là bạn đã hiểu chương này.

Answering these means you understand why memory is tiered, and how to write code that keeps data in the fast levels.

  1. Vì sao SRAM dùng làm cache còn DRAM dùng làm bộ nhớ chính? Nêu đánh đổi giữa chúng theo bảng đặc trưng của sách.

    Gợi ý sâu hơn: con số “6 transistor/bit” và “~1000× giá” nói lên điều gì về vì sao cache phải nhỏ?

  2. Phân biệt cục bộ thời gian và cục bộ không gian. Cho một ví dụ mã có cục bộ không gian tốt và một ví dụ kém.

    Gợi ý sâu hơn: vì sao duyệt mảng C theo cột lại cho mẫu bước nhảy N?

  3. “Mỗi tầng là cache cho tầng dưới” nghĩa là gì? Kể các mức L0–L6 theo thứ tự.

    Gợi ý sâu hơn: vì sao tầng càng xa CPU thì khối chuyển thường càng lớn?

  4. Một cache (S, E, B, m) có kích thước bao nhiêu? Ba trường của địa chỉ là gì và mỗi trường dùng để làm gì?

    Gợi ý sâu hơn: vì sao cache dùng bit giữa làm chỉ số tập thay vì bit cao?

  5. Trượt xung đột là gì, vì sao hay gặp với mảng kích thước luỹ thừa 2, và liên kết tập hợp giúp thế nào?

    Gợi ý sâu hơn: trên ngọn núi bộ nhớ, đỉnh L1 và đáy bộ nhớ chính chênh nhau khoảng bao nhiêu?

  1. Vì sao có loại nhớ nhanh mà đắt, loại chậm mà rẻ? Kể hai loại.

  2. “Dùng lại” và “dùng chỗ kế bên” là hai kiểu cục bộ nào?

  3. Vì sao để dữ liệu hay dùng ở tầng nhanh thì chương trình chạy nhanh hơn?

  4. Cache giống cái tủ nhiều ngăn như thế nào? Máy tìm đồ ra sao?

  5. Vì sao đổi thứ tự duyệt mảng lại làm chương trình nhanh hay chậm hẳn?

  1. Why is SRAM used for caches and DRAM for main memory? State the trade-off from the book's table.

  2. Distinguish temporal and spatial locality. Give one code example with good spatial locality and one with poor.

  3. What does "each level caches the one below" mean? List levels L0–L6 in order.

  4. What is the size of a cache (S, E, B, m)? What are the three address fields and what is each used for?

  5. What is a conflict miss, why is it common with power-of-2 arrays, and how does associativity help?

Khép lại chương Closing the chapter

Bộ nhớ không phải mảng byte phẳng mà là một phân cấp nhanh–chậm chênh nhau nhiều bậc độ lớn; vì chương trình tốt có tính cục bộ, mỗi tầng làm cache cho tầng dưới. Hiểu điều đó, bạn viết được mã chạy trên đỉnh ngọn núi bộ nhớ thay vì dưới thung lũng.1

Bộ nhớ xếp thành tầng nhanh–chậm, và tầng trên giữ sẵn thứ hay dùng từ tầng dưới. Giúp dữ liệu nằm ở tầng nhanh và duyệt tuần tự thì chương trình bay. Nhớ nhé: gọn và tuần tự là chạy trên đỉnh.

Memory is not a flat array of bytes but a hierarchy whose speeds differ by orders of magnitude; because good programs have locality, each level caches the one below. Grasp that, and you write code that runs on the peaks of the memory mountain rather than in its valleys.1