Computer Systems: A Programmer's Perspective Chương 4 · Processor Architecture

Chương 4 · Kiến trúc bộ xử lý Chapter 4 · Processor Architecture

Tự tay dựng một bộ xử lý: từ tập lệnh Y86-64 tới một đường ống năm tầng Ta cùng “chế” một con chip chạy lệnh — từng bước một Building a processor by hand: from the Y86-64 ISA to a five-stage pipeline

Bryant và O'Hallaron dành cả chương để trả lời một câu hỏi: phần cứng bên dưới thực thi các lệnh máy như thế nào? Hai ông định nghĩa một tập lệnh (ISA) tên là Y86-64 — một phiên bản đơn giản hơn của x86-64 — rồi thiết kế hai bộ xử lý chạy được nó: SEQ, chạy tuần tự trọn một lệnh mỗi chu kỳ đồng hồ, và PIPE, một bộ xử lý đường ống (pipeline) năm tầng nhanh hơn nhiều.1

Chương này giống như một lớp học “tự chế CPU”. Trước hết các tác giả bịa ra một bộ lệnh nhỏ gọn tên là Y86-64 cho dễ học. Rồi họ dựng hai con chip giả tưởng chạy nó: một con làm xong hẳn một lệnh rồi mới làm lệnh sau (chậm mà chắc), và một con làm nhiều lệnh gối đầu nhau như dây chuyền nhà máy (nhanh hơn nhiều). Nhớ nhé: muốn hiểu CPU, cách tốt nhất là thử tự dựng một cái.

Bryant and O'Hallaron devote the chapter to one question: how does the hardware underneath actually execute machine instructions? They define an instruction set (ISA) called Y86-64 — a simplified cousin of x86-64 — and then design two processors that run it: SEQ, which executes a full instruction every clock cycle in sequence, and PIPE, a much faster five-stage pipelined processor.1

Phương pháp của chương là biến đổi dần (refinement). Thay vì trình bày một bộ xử lý phức tạp ngay lập tức, các tác giả bắt đầu từ SEQ — một thiết kế đúng về chức năng nhưng chậm — rồi áp một loạt phép biến đổi để chèn các thanh ghi đường ống (pipeline register), tạo ra PIPE. Mỗi phép biến đổi lại làm lộ ra một vấn đề mới (phụ thuộc dữ liệu, phụ thuộc điều khiển) buộc ta phải xử lý, nên người đọc thấy rõ vì sao mỗi cơ chế của CPU hiện đại — chuyển tiếp dữ liệu, dự đoán nhánh, chèn bong bóng — lại cần thiết.1

Luận đề của chương: một bộ xử lý thật ra chỉ là phần cứng thực hiện trung thành một tập lệnh; bằng cách tổ chức mọi lệnh thành một dòng chảy đồng nhất qua vài tầng rồi để nhiều lệnh gối đầu nhau trong một đường ống, ta tăng mạnh thông lượng (throughput) — nhưng phải xử lý các nguy cơ (hazard) sinh ra khi lệnh này phụ thuộc lệnh kia, sao cho kết quả vẫn khớp đúng với mô hình ISA.1

Ý chính: CPU là phần cứng làm theo đúng một bộ lệnh đã thoả thuận. Cho các lệnh chạy gối đầu như dây chuyền thì nhanh hơn, nhưng phải khéo xử lý lúc lệnh sau cần kết quả của lệnh trước. Nhớ nhé: chạy gối đầu thì nhanh, miễn là đừng để lệnh sau “vượt đèn” kết quả chưa có của lệnh trước.

The chapter's thesis: a processor is just hardware faithfully implementing an instruction set; by organizing every instruction into a uniform flow through a few stages and letting several instructions overlap in a pipeline, we greatly raise throughput — but we must handle the hazards that arise when one instruction depends on another, so the result still matches the ISA model.1

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

Tập lệnh (ISA) Y86-64 và ngôn ngữ mô tả logic HCL Một bộ lệnh nhỏ gọn, và cách tả mạch điện bằng chữ The Y86-64 instruction set and the HCL logic language

Một tập lệnh (instruction set architecture, ISA) định nghĩa trạng thái lập trình viên thấy được (programmer-visible state), tập các lệnh cùng cách mã hoá, quy ước lập trình, và cách xử lý ngoại lệ. Y86-64 mượn cảm hứng từ x86-64 nhưng ít kiểu dữ liệu, ít lệnh và ít chế độ địa chỉ hơn, lại có cách mã hoá byte đơn giản — nhờ vậy việc thiết kế logic giải mã (decode) của CPU dễ hơn hẳn.1

“Tập lệnh” là bản hợp đồng giữa phần mềm và phần cứng: nó liệt kê những việc CPU biết làm và cách viết chúng ra thành byte. Y86-64 là một bộ lệnh thu nhỏ, cố tình làm cho gọn để người học tự dựng được CPU. Muốn mô tả các mạch điện bên trong, sách dùng một ngôn ngữ nhỏ tên là HCL. Nhớ nhé: tập lệnh là bản hợp đồng; làm nó gọn thì dựng phần cứng mới dễ.

An instruction set architecture (ISA) defines the programmer-visible state, the set of instructions and their encodings, the programming conventions, and the handling of exceptions. Y86-64 is inspired by x86-64 but has fewer data types, instructions, and addressing modes, plus a simple byte-level encoding — which makes the CPU's decoding logic far easier to design.1

Định nghĩa. Trạng thái lập trình viên thấy được của Y86-64 gồm 15 thanh ghi chương trình (giống x86-64 nhưng lược bỏ %r15 cho gọn mã hoá), mỗi thanh ghi giữ một word 64-bit; ba mã điều kiện (condition code) một bit là ZF, SF, OF; bộ đếm chương trình PC; bộ nhớ; và mã trạng thái Stat cho biết chương trình đang chạy bình thường hay gặp ngoại lệ.1

Nói đơn giản. CPU Y86-64 có 15 “ngăn nhớ cực nhanh” gọi là thanh ghi, ba lá cờ nhỏ ghi lại kết quả phép tính vừa rồi, một cái kim chỉ tới lệnh kế tiếp, và một đèn báo “ổn / hỏng”. Nhớ nhé: thanh ghi là ngăn nhớ sát CPU; cờ điều kiện là mẩu ghi chú về phép tính vừa xong.

Definition. Y86-64's programmer-visible state has 15 program registers (like x86-64 but omitting %r15 to simplify encoding), each holding a 64-bit word; three single-bit condition codes ZF, SF, OF; the program counter PC; the memory; and a status code Stat telling whether the program runs normally or hit an exception.1

// HCL: so sánh hai bit
bool eq = (a && b) || (!a && !b);

// HCL: bộ chọn (MUX)
bool out = (s && a) || (!s && b);

a == b → eq = 1
s chọn giữa a và b
  → out

// HCL: bit equality
bool eq = (a && b) || (!a && !b);

// HCL: multiplexor (MUX)
bool out = (s && a) || (!s && b);

  1. programmer-visible state

    Trạng thái thấy được — điều ISA hứa, chứ không phải cách hiện thực Trạng thái thấy được — những gì bộ lệnh cam kết Visible state — what the ISA promises, not how it is built

    Mỗi lệnh Y86-64 đọc và sửa một phần trạng thái lập trình viên thấy được. Điểm then chốt: bộ xử lý không cần tổ chức trạng thái bên trong y hệt như ISA ngụ ý, miễn là chương trình máy trông như truy cập đúng trạng thái ấy. Đây là cánh cửa mở ra mọi mẹo tăng tốc phần cứng.1

    Bộ lệnh chỉ hứa “sau khi chạy xong, các thanh ghi và bộ nhớ sẽ ra thế này”. Còn bên trong CPU xoay xở ra sao thì tuỳ nó, miễn kết quả nhìn thấy đúng như hứa. Nhớ nhé: ISA hứa kết quả cuối, không bắt buộc cách làm bên trong.

    Each Y86-64 instruction reads and modifies part of the programmer-visible state. The key point: the processor need not organize its internal state exactly as the ISA implies, as long as machine programs appear to access that state. This is the doorway to every hardware speed-up trick.1

    Bạn gặp nó ở đâuWhere you meet it Chính nguyên tắc này cho phép CPU hiện đại chạy lệnh không theo thứ tự (out-of-order) mà vẫn cho kết quả đúng — chủ đề của Chương 5.1 Nhờ nó mà chip xịn có thể đổi thứ tự làm việc cho nhanh mà kết quả vẫn đúng. This principle lets modern CPUs execute out of order yet still be correct — a theme of Chapter 5.1

    Một ví dụ bất ngờ

    Ở bản SEQ+ chuyển tiếp sang đường ống, các tác giả chỉ ra rằng không có thanh ghi phần cứng nào lưu PC cả — giá trị PC được tính lại động từ trạng thái của lệnh trước, một minh hoạ sống động cho việc hiện thực khác với mô hình ISA.1

    Vì sao điều này quan trọng

    Tách bạch “cái ISA hứa” khỏi “cách phần cứng làm” là tư duy nền để hiểu vì sao hai CPU rất khác nhau về mạch vẫn chạy đúng cùng một chương trình.1

  2. instruction encoding

    Mã hoá lệnh — mỗi lệnh dài 1 tới 10 byte, có nghĩa duy nhất Mã hoá lệnh — mỗi lệnh là một chuỗi byte riêng biệt Instruction encoding — 1 to 10 bytes, uniquely decodable

    Mỗi lệnh Y86-64 dài từ 1 đến 10 byte. Byte đầu tách thành hai nửa 4-bit: nửa cao là mã lệnh (code), nửa thấp là hàm (function). Theo sau có thể là một byte chỉ định thanh ghi (các trường rA, rB) và một word hằng 8 byte. Mỗi lệnh có một tổ hợp code–function duy nhất, nên từ byte đầu ta suy ra ngay độ dài và ý nghĩa — byte mã hoá có cách diễn giải duy nhất.1

    Mỗi câu lệnh được viết thành một chuỗi byte dài ngắn tuỳ loại. Byte đầu như một “mã bưu chính” cho biết đây là lệnh gì và còn phải đọc thêm mấy byte nữa. Không có hai lệnh nào trùng mã đầu, nên máy không bao giờ đọc nhầm. Nhớ nhé: nhìn byte đầu là biết ngay lệnh gì, dài bao nhiêu.

    Each Y86-64 instruction is 1 to 10 bytes. The first byte splits into two 4-bit halves: the high half is the code, the low half is the function. It may be followed by a register specifier byte (fields rA, rB) and an 8-byte constant word. Every instruction has a unique code–function combination, so from the first byte we know its length and meaning — the byte encoding has a unique interpretation.1

    Bạn gặp nó ở đâuWhere you meet it Sách dựng mẫu: lệnh rmmovq %rsp,0x123456789abcd(%rdx) mã hoá thành chuỗi byte 4042cdab896745230100 — byte đầu 40, byte thanh ghi 42, rồi hằng 8 byte ở dạng đảo byte (little-endian).1 Mỗi khi bạn xem mã máy dạng hex, bạn đang nhìn đúng những byte lệnh này. The book works an example: rmmovq %rsp,0x123456789abcd(%rdx) encodes to the byte string 4042cdab896745230100 — first byte 40, register byte 42, then the 8-byte constant in little-endian (reversed) order.1

    So với x86-64

    Mã hoá Y86-64 đơn giản hơn nhưng kém gọn: các trường thanh ghi luôn ở vị trí cố định, còn hằng số thì luôn chiếm 8 byte, trong khi x86-64 có thể mã hoá hằng trong 1, 2, 4 hoặc 8 byte.1

    Vì sao tính “giải mã duy nhất” quan trọng

    Nếu biết điểm bắt đầu của một chuỗi byte, ta luôn tách được nó thành đúng dãy lệnh. Nếu không biết điểm bắt đầu, việc tách trở nên mơ hồ — đây chính là bài toán đau đầu của trình dịch ngược (disassembler).1

  3. logic design + HCL

    Thiết kế logic và HCL — mô tả mạch tổ hợp bằng biểu thức HCL — viết mạch điện ra như viết công thức Logic design and HCL — describing circuits as expressions

    Một hệ thống số cần ba thành phần: logic tổ hợp (combinational logic) để tính hàm trên các bit, phần tử nhớ (memory element) để lưu bit, và tín hiệu đồng hồ (clock) điều phối việc cập nhật. Với công nghệ hiện nay, mức logic 1 ứng với điện áp cao khoảng 1,0 vôn và mức 0 ứng với khoảng 0,0 vôn. Các tác giả dùng ngôn ngữ HCL (hardware control language) để mô tả phần điều khiển.13

    Mạch điện của CPU ghép từ ba thứ: khối tính toán (cổng logic), ô nhớ để giữ số, và một nhịp đồng hồ để báo “giờ cập nhật”. Thay vì vẽ từng cổng, sách viết mạch ra bằng những công thức ngắn gọn gọi là HCL. Nhớ nhé: mạch số = khối tính + ô nhớ + nhịp đồng hồ, và ta tả nó bằng công thức.

    A digital system needs three components: combinational logic to compute functions on bits, memory elements to store bits, and a clock signal to regulate updates. In current technology, logic value 1 is a high voltage around 1.0 volt and value 0 is a low voltage around 0.0 volt. The authors use the HCL (hardware control language) to describe the control logic.13

    Bạn gặp nó ở đâuWhere you meet it Mạch so sánh bit viết trong HCL là bool eq = (a && b) || (!a && !b); bộ chọn một bit (multiplexor) là bool out = (s && a) || (!s && b) — nền tảng để lắp mọi đường điều khiển của CPU.1 Khi một tín hiệu “chọn” quyết định lấy giá trị A hay B, đó chính là một bộ chọn (MUX). The bit-equality circuit in HCL is bool eq = (a && b) || (!a && !b); the single-bit multiplexor is bool out = (s && a) || (!s && b) — the basis for every control path in the CPU.1

    Logic tổ hợp khác biểu thức C

    Cổng logic luôn hoạt động: đầu vào đổi thì sau một khoảng trễ nhỏ đầu ra đổi theo. Không có “tính toán ngắn mạch” như C — biểu thức (a && !a) && func(b,c) trong C bỏ qua func, còn mạch thì mọi cổng cứ phản ứng với đầu vào.1

    HDL và tổng hợp logic

    HCL chỉ tả phần điều khiển. Trong công nghiệp, người ta mô tả toàn bộ phần cứng bằng ngôn ngữ mô tả phần cứng (HDL) như Verilog hay VHDL, rồi dùng công cụ tổng hợp logic (logic synthesis) sinh ra thiết kế mạch thực.13

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

SEQ — bộ xử lý tuần tự xử lý trọn một lệnh mỗi chu kỳ SEQ — con chip làm xong hẳn một lệnh rồi mới sang lệnh sau SEQ — the sequential processor, one full instruction per cycle

SEQ (viết tắt của “sequential”) là bước đầu tiên: mỗi chu kỳ đồng hồ, nó thực hiện trọn vẹn mọi việc cần cho một lệnh. Bí quyết là tổ chức việc xử lý thành một chuỗi tầng (stage) đồng nhất, dù các lệnh rất khác nhau về hành vi. Nhờ dòng chảy chung này, cả bộ xử lý dùng chung một lượng nhỏ phần cứng — ví dụ chỉ một khối ALU được dùng theo nhiều cách tuỳ loại lệnh.1

SEQ làm việc kiểu “chậm mà chắc”: nó làm hết mọi bước của một lệnh trong một nhịp đồng hồ, xong mới bắt lệnh sau. Mẹo của nó là ép mọi lệnh đi qua cùng một dãy bước giống nhau, nhờ vậy tái dùng được rất ít phần cứng cho tất cả. Nhớ nhé: mọi lệnh đi chung một con đường thì phần cứng mới gọn.

SEQ (short for "sequential") is the first step: on each clock cycle it performs everything a single instruction needs. The trick is to organize processing into a uniform sequence of stages, even though instructions differ greatly in behavior. Thanks to this shared flow, the whole processor uses a small amount of hardware — for example a single ALU used in different ways depending on the instruction.1

Định nghĩa. SEQ xử lý mỗi lệnh qua sáu tầng theo thứ tự: Fetch (nạp) đọc byte lệnh từ bộ nhớ qua PC; Decode (giải mã) đọc toán hạng từ tệp thanh ghi; Execute (thực thi) cho ALU tính toán và đặt cờ điều kiện; Memory (bộ nhớ) đọc hoặc ghi dữ liệu; Write back (ghi lại) ghi kết quả vào thanh ghi; PC update đặt PC tới lệnh kế tiếp.1

Nói đơn giản. Mỗi lệnh đi qua sáu bước: lấy lệnh về, đọc số cần dùng, tính toán, đụng vào bộ nhớ nếu cần, cất kết quả, rồi chỉ sang lệnh sau. Nhớ nhé: nạp → giải mã → tính → bộ nhớ → ghi lại → sang lệnh kế.

Definition. SEQ processes each instruction in six stages in order: Fetch reads instruction bytes from memory via the PC; Decode reads operands from the register file; Execute has the ALU compute and set condition codes; Memory reads or writes data; Write back writes results to registers; PC update sets the PC to the next instruction.1

Fetch    → icode:ifun, rA:rB, valC, valP
Decode   → valA, valB
Execute  → valE (đặt CC)
Memory   → valM
Write back → R[ ] ← valE / valM
PC update → PC ← valP / valC / valM

6 bước, lặp mãi:
  lấy → đọc → tính
  → nhớ → cất → tiếp

Fetch    → icode:ifun, rA:rB, valC, valP
Decode   → valA, valB
Execute  → valE (set CC)
Memory   → valM
Write back → R[ ] ← valE / valM
PC update → PC ← valP / valC / valM

  1. six stages

    Sáu tầng — một khuôn chung cho mọi lệnh Sáu bước — khuôn chung cho tất cả lệnh Six stages — one common template for every instruction

    Mỗi lệnh, dù là phép cộng, lệnh nhảy hay lệnh gọi hàm, đều được ép vào cùng sáu tầng. Ở tầng Fetch, SEQ tách byte đầu thành icode (mã lệnh) và ifun (hàm), đọc thêm byte thanh ghi và hằng valC nếu có, rồi tính valP — địa chỉ lệnh kế tiếp theo thứ tự tuần tự.1

    Dù là cộng, nhảy hay gọi hàm, lệnh nào cũng đi đúng sáu bước như nhau. Bước đầu tiên là “lấy lệnh về và đọc hiểu đầu byte xem đây là lệnh gì”. Nhớ nhé: một khuôn sáu bước dùng chung cho mọi lệnh.

    Every instruction — be it an add, a jump, or a call — is forced into the same six stages. In Fetch, SEQ splits the first byte into icode and ifun, reads a register byte and constant valC if present, and computes valP — the address of the next instruction in sequential order.1

    Bạn gặp nó ở đâuWhere you meet it Với lệnh số học như subq %rax,%rdx, tầng Execute tính valE ← valB OP valA và đặt cờ, còn bộ nhớ không làm gì — chỉ Write back ghi valE vào thanh ghi đích.1 Một phép trừ chỉ dùng bước “tính” và bước “cất kết quả”; bước “bộ nhớ” nghỉ. For an arithmetic instruction like subq %rax,%rdx, Execute computes valE ← valB OP valA and sets the flags, while Memory does nothing — only Write back stores valE into the destination register.1

    Chọn PC kế tiếp

    Tầng PC update chọn giá trị PC mới: dùng hằng valC cho call và nhánh được lấy, dùng valM (giá trị lấy từ ngăn xếp) cho ret, còn mặc định là valP.1

    Dễ ánh xạ xuống phần cứng

    Các bảng mô tả (Hình 4.18–4.21 trong sách) viết mỗi tầng như một dãy phép gán tín hiệu. Dạng này ánh xạ thẳng xuống các khối phần cứng, nên thiết kế logic trở nên có hệ thống.1

  2. shared hardware

    Dùng chung phần cứng — vì sao dòng chảy phải đồng nhất Dùng chung phần cứng — nên mọi lệnh đi chung một đường Shared hardware — why the flow must be uniform

    Có một lượng xử lý đáng ngạc nhiên ẩn sau mỗi lệnh: không chỉ làm phép tính, mà còn tính địa chỉ, cập nhật con trỏ ngăn xếp, và xác định lệnh kế tiếp. Giữ dòng chảy giống nhau cho mọi lệnh là cách tối thiểu hoá phần cứng — vì nhân bản một khối logic trong phần cứng tốn kém hơn nhiều so với sao chép một đoạn mã trong phần mềm.1

    Một lệnh tưởng đơn giản nhưng kéo theo bao việc lặt vặt: tính địa chỉ, chỉnh con trỏ, tìm lệnh sau. Nếu mỗi loại lệnh có một mạch riêng thì tốn phần cứng khủng khiếp; ép chung một đường thì tiết kiệm. Nhớ nhé: trong phần cứng, nhân bản mạch đắt hơn nhiều so với nhân bản mã.

    There is a surprising amount of processing behind each instruction: not only the operation, but also address computation, stack-pointer updates, and finding the next instruction. Keeping the flow identical across instructions minimizes hardware — because duplicating a block of logic in hardware costs far more than copying a block of code in software.1

    Bạn gặp nó ở đâuWhere you meet it Cả bộ xử lý chỉ có một khối ALU; lệnh số học dùng nó để tính, lệnh truy cập bộ nhớ dùng nó để tính địa chỉ, lệnh push/pop dùng nó để tăng–giảm con trỏ ngăn xếp.1 Một cái máy tính số (ALU) duy nhất được tận dụng cho đủ mọi việc. The whole processor has just one ALU; arithmetic instructions use it to compute, memory instructions use it for addresses, and push/pop use it to adjust the stack pointer.1
  3. SEQ is too slow

    SEQ quá chậm — lý do phải nghĩ tới đường ống SEQ chậm — nên ta cần một cách nhanh hơn SEQ is too slow — the reason to reach for pipelining

    Vấn đề duy nhất của SEQ là nó quá chậm. Đồng hồ phải chạy đủ chậm để tín hiệu kịp lan qua tất cả các tầng trong một chu kỳ. Ví dụ với lệnh ret: trong một chu kỳ phải đọc lệnh, đọc con trỏ ngăn xếp, cho ALU tăng nó lên 8, rồi đọc địa chỉ trả về từ bộ nhớ — tất cả xong trước khi chu kỳ kết thúc. Mỗi khối phần cứng chỉ bận một phần nhỏ của chu kỳ.1

    SEQ chắc chắn đúng nhưng phí thời gian: một nhịp đồng hồ phải dài bằng toàn bộ hành trình sáu bước. Trong lúc một khối đang làm, các khối khác ngồi chơi. Thật lãng phí. Nhớ nhé: SEQ đúng nhưng chậm vì mỗi lúc chỉ một khối làm việc.

    SEQ's only problem is that it is too slow. The clock must run slowly enough for signals to propagate through all stages in one cycle. Take ret: in one cycle it must read the instruction, read the stack pointer, have the ALU add 8, and read the return address from memory — all before the cycle ends. Each hardware block is busy only a fraction of the cycle.1

    Bạn gặp nó ở đâuWhere you meet it Đây đúng là động lực lịch sử của đường ống: thay vì để phần cứng rảnh rỗi phần lớn thời gian, hãy cho nhiều lệnh dùng các khối khác nhau cùng lúc.1 Ý tưởng cứu cánh: để các khối cùng bận, mỗi khối lo một lệnh khác nhau. This is exactly the motivation for pipelining: rather than leaving hardware idle most of the time, let several instructions use different blocks at once.1

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

Đường ống, PIPE, và cách xử lý nguy cơ Chạy gối đầu như dây chuyền, và cách tránh rối Pipelining, PIPE, and handling hazards

Đường ống (pipeline) quen thuộc với bất cứ ai từng xếp hàng ở căng-tin hay đưa xe qua trạm rửa tự động: công việc được chia thành nhiều chặng, và nhiều “khách” cùng đi qua hệ thống một lúc. Điểm mấu chốt: đường ống tăng thông lượng (throughput — số lệnh hoàn thành mỗi đơn vị thời gian) dù có thể hơi tăng độ trễ (latency — thời gian phục vụ một lệnh từ đầu tới cuối).1

Hãy hình dung dây chuyền rửa xe: xe này đang được xịt nước thì xe kia đã vào kỳ cọ, xe nữa đang sấy khô — nhiều xe cùng lúc. CPU đường ống cũng vậy: trong khi lệnh này đang tính thì lệnh sau đã được nạp. Nhờ thế số lệnh xong mỗi giây tăng vọt. Nhớ nhé: đường ống không làm một lệnh nhanh hơn, mà làm được nhiều lệnh hơn mỗi giây.

A pipeline is familiar to anyone who has been through a cafeteria line or an automated car wash: the work is split into stages, and several "customers" move through the system at once. The key point: pipelining raises throughput (instructions completed per unit time) even though it may slightly increase latency (the time to serve one instruction end to end).1

Định nghĩa. Với một hệ chưa đường ống gồm logic tổ hợp mất 300 picô-giây (ps) và một thanh ghi mất 20 ps, chu kỳ là 320 ps nên thông lượng chỉ khoảng 3,12 GIPS (tỉ lệnh mỗi giây). Chia việc thành ba tầng 100 ps, chèn thanh ghi đường ống giữa các tầng, chu kỳ còn 120 ps: thông lượng lên 8,33 GIPS — nhanh gấp 2,67 lần — dù độ trễ tăng nhẹ lên 360 ps.1

Nói đơn giản. Một việc dài 300 ps làm một mạch thì mỗi giây xong được chừng 3 tỉ lần. Chẻ việc thành ba chặng rồi cho chạy gối đầu, mỗi giây xong được hơn 8 tỉ lần — nhanh gần gấp ba. Nhớ nhé: chẻ nhỏ công việc rồi chạy gối đầu thì làm được nhiều hơn mỗi giây.

Definition. For a nonpipelined system with 300 picoseconds (ps) of combinational logic and a 20 ps register, the cycle is 320 ps, giving only about 3.12 GIPS (giga-instructions per second). Splitting the work into three 100 ps stages with pipeline registers between them makes the cycle 120 ps: throughput rises to 8.33 GIPS — a 2.67× speedup — even though latency grows slightly to 360 ps.1

Throughput = 1 / (20 + 300) ps
  ≈ 3,12 GIPS  (chưa đường ống)

3 tầng: 1 / (20 + 100) ps
  ≈ 8,33 GIPS  (×2,67)

1 mạch dài → ~3 tỉ/giây
3 chặng gối đầu → ~8 tỉ/giây

Throughput = 1 / (20 + 300) ps
  ≈ 3.12 GIPS  (nonpipelined)

3 stages: 1 / (20 + 100) ps
  ≈ 8.33 GIPS  (×2.67)

  1. throughput vs latency

    Thông lượng và giới hạn — đường ống sâu không miễn phí Thông lượng — và vì sao chẻ mãi cũng có giới hạn Throughput and its limits — deeper pipelines are not free

    Chia càng nhiều tầng thì chu kỳ càng ngắn, nhưng lợi ích giảm dần. Chia thành sáu tầng 50 ps, chu kỳ còn 70 ps cho 14,29 GIPS — nhưng so với ba tầng chỉ nhanh hơn 1,71 lần, chứ không gấp đôi. Lý do: độ trễ của thanh ghi đường ống không chia nhỏ được, ở đây chiếm tới 28,6% chu kỳ. CPU hiện đại vẫn dùng đường ống rất sâu (15 tầng trở lên) để đẩy xung nhịp lên cao.1

    Chẻ việc thành nhiều chặng hơn thì nhanh thêm, nhưng mỗi lần chẻ phải cộng thêm chi phí “bàn giao” giữa các chặng. Chẻ quá nhỏ thì chi phí bàn giao ăn hết phần lợi. Nhớ nhé: chẻ nhỏ giúp nhanh hơn, nhưng mỗi mối nối đều tốn chút phí, nên có giới hạn.

    More stages mean a shorter cycle, but returns diminish. Six 50 ps stages give a 70 ps cycle and 14.29 GIPS — yet only 1.71× faster than three stages, not double. The reason: the pipeline-register delay cannot be subdivided and here consumes 28.6% of the cycle. Modern CPUs still use very deep pipelines (15 or more stages) to push the clock rate higher.1

    Bạn gặp nó ở đâuWhere you meet it Phân chia không đều cũng giới hạn đường ống: nếu các tầng lệch nhau (50/150/100 ps) thì chu kỳ bị tầng chậm nhất quyết định (170 ps), chỉ đạt 5,88 GIPS.1 Nếu một chặng chậm hơn hẳn thì cả dây chuyền phải chờ nó. Uneven partitioning also limits a pipeline: if stages differ (50/150/100 ps), the cycle is set by the slowest stage (170 ps), reaching only 5.88 GIPS.1

    Năm tầng của PIPE

    Bộ xử lý đường ống PIPE chia việc thành năm tầng — Fetch, Decode, Execute, Memory, Write back — bằng cách chèn các thanh ghi đường ống F, D, E, M, W giữa chúng. Nó dùng gần như cùng bộ phần cứng với SEQ, chỉ thêm các thanh ghi ngăn tầng.1

    SEQ+ và “tái định thời”

    Trước khi chèn thanh ghi, các tác giả dời tầng PC update lên đầu chu kỳ, tạo ra SEQ+. Đây là một ví dụ của tái định thời mạch (circuit retiming): đổi cách bố trí phần tử trạng thái mà không đổi hành vi logic.1

  2. data hazards + forwarding

    Nguy cơ dữ liệu và chuyển tiếp — khi lệnh sau cần kết quả chưa ghi xong Nguy cơ dữ liệu — lệnh sau cần số mà lệnh trước chưa cất xong Data hazards and forwarding — when a later instruction needs a not-yet-stored result

    Khác với xe trong trạm rửa, các lệnh có thể phụ thuộc nhau. Nguy cơ dữ liệu (data hazard) xảy ra khi một lệnh cần kết quả mà lệnh ngay trước còn chưa kịp ghi vào thanh ghi. Giải pháp là chuyển tiếp dữ liệu (data forwarding, hay bypassing): thay vì bắt lệnh sau chờ, phần cứng chuyển thẳng giá trị vừa tính từ một tầng sau về tầng Decode. PIPE có năm nguồn chuyển tiếp và hai đích (cho hai toán hạng).1

    Xe rửa thì độc lập, còn lệnh thì hay “nhờ vả” nhau: lệnh sau cần đúng con số mà lệnh trước vừa tính nhưng chưa kịp cất. Thay vì bắt nó đứng chờ, phần cứng “chuyền tay” con số đó tới ngay. Nhớ nhé: thay vì bắt lệnh sau chờ, hãy chuyền thẳng kết quả vừa tính cho nó.

    Unlike cars in a car wash, instructions can depend on each other. A data hazard occurs when an instruction needs a result that the immediately preceding one has not yet written to a register. The fix is data forwarding (bypassing): rather than making the later instruction wait, hardware passes the just-computed value directly from a later stage back to Decode. PIPE has five forwarding sources and two destinations (for the two operands).1

    Bạn gặp nó ở đâuWhere you meet it Có một loại không chuyển tiếp hết được: nguy cơ nạp/dùng (load/use hazard). Khi một lệnh đọc giá trị từ bộ nhớ rồi lệnh ngay sau cần dùng, giá trị chưa có kịp — chuyển tiếp lúc này nghĩa là “gửi ngược về quá khứ”, điều bất khả. Phải chèn một bong bóng (bubble) dừng một chu kỳ, rồi mới chuyển tiếp.1 Riêng khi lệnh trước phải lấy số từ bộ nhớ (chậm), lệnh sau đành chờ đúng một nhịp rồi mới nhận được số. One kind cannot be fully forwarded: the load/use hazard. When one instruction reads a value from memory and the very next needs it, the value is not ready in time — forwarding would mean "sending back in time," which is impossible. A one-cycle bubble must be injected, then forwarding applies.1

    Năm nguồn chuyển tiếp

    Giá trị có thể chuyển tiếp từ: đầu ra ALU trong tầng Execute (e_valE), giá trị vừa đọc bộ nhớ (m_valM), và các giá trị đang nằm trong thanh ghi đường ống M và W (M_valE, W_valM, W_valE) — tổng cộng năm nguồn, hai đích là valA và valB.1

    Dừng (stall) so với bong bóng

    Dừng là giữ một lệnh ở nguyên tầng; bong bóng là chèn một “lệnh rỗng” không làm gì vào tầng kế để lấp chỗ trống. PIPE kết hợp dừng một chu kỳ với chuyển tiếp để xử lý nguy cơ nạp/dùng mà tổn thất ít nhất.1

  3. control hazards + prediction

    Nguy cơ điều khiển và dự đoán nhánh — đoán trước lệnh kế tiếp Nguy cơ điều khiển — khi chưa biết lệnh sau là lệnh nào Control hazards and branch prediction — guessing the next instruction

    Một nguy cơ điều khiển (control hazard) xuất hiện khi chưa biết lệnh kế tiếp nằm ở đâu — với nhánh có điều kiện, phải tới tầng Execute mới biết nhánh có được lấy hay không; với ret, phải tới tầng Memory. Để không bỏ trống đường ống, PIPE dự đoán nhánh (branch prediction): nó đoán và nạp sẵn lệnh theo hướng đoán. Thiết kế của sách dùng chiến lược “luôn lấy nhánh” (always taken).1

    Khi gặp một lệnh rẽ nhánh, CPU chưa biết sẽ đi hướng nào — nhưng đường ống không thể đứng chờ. Nên nó đoán hướng và nạp sẵn; đoán đúng thì lợi, đoán sai thì bỏ đi làm lại. Nhớ nhé: tới ngã rẽ mà chưa rõ hướng, CPU cứ đoán rồi chạy tiếp cho khỏi phí thời gian.

    A control hazard arises when the next instruction's location is unknown — for a conditional branch we only know at Execute whether it is taken; for ret, only at Memory. To avoid leaving the pipeline empty, PIPE uses branch prediction: it guesses and prefetches along the predicted direction. The book's design uses an "always taken" strategy.1

    Bạn gặp nó ở đâuWhere you meet it Mỗi khi đoán sai, các lệnh đã nạp nhầm phải bị huỷ — đây là lý do Chương 3 khuyên dùng chuyển dữ liệu có điều kiện (cmov) thay cho rẽ nhánh khi có thể.1 Đoán sai thì phí công nạp nhầm, nên tránh rẽ nhánh khó đoán là một mẹo tăng tốc. Every misprediction means the wrongly-fetched instructions must be cancelled — which is why Chapter 3 advises conditional moves (cmov) over branches when possible.1

    Các chiến lược dự đoán

    Theo các nghiên cứu mà sách dẫn, “luôn lấy nhánh” đúng khoảng 60% số lần; chiến lược “nhánh lùi thì lấy, nhánh tiến thì không” (BTFNT) đạt khoảng 65%, vì vòng lặp thường đóng bằng một nhánh lùi và lặp nhiều lần.14

    Riêng lệnh ret

    Với ret, địa chỉ trả về gần như không đoán được trước, nên thiết kế của sách đơn giản là tạm dừng không nạp thêm lệnh cho tới khi ret qua tầng Write back. CPU hiệu năng cao thì dùng một ngăn xếp địa chỉ trả về trong phần cứng để đoán.1

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

“Đường ống làm mỗi lệnh chạy nhanh hơn” “Pipelining makes each instruction faster”

Ngộ nhận: có đường ống thì một lệnh xong nhanh hơn.

Thực tế: đường ống tăng thông lượng (số lệnh mỗi giây), còn độ trễ của một lệnh thậm chí nhích lên do chi phí thanh ghi đường ống — ba tầng khiến độ trễ tăng từ 320 lên 360 ps.1

Myth: with a pipeline, one instruction finishes faster.

Reality: pipelining raises throughput (instructions per second); the latency of one instruction even grows slightly from the register overhead — three stages push latency from 320 to 360 ps.1

“Cứ chẻ thật nhiều tầng là nhanh gấp bội” “Just add more stages for proportional speedup”

Ngộ nhận: gấp đôi số tầng thì nhanh gấp đôi.

Thực tế: gấp đôi tầng (ba lên sáu) chỉ nhanh hơn 1,71 lần vì độ trễ thanh ghi đường ống không chia nhỏ được, chiếm tới 28,6% chu kỳ.1

Myth: doubling the stages doubles the speed.

Reality: doubling stages (three to six) gives only 1.71× because the pipeline-register delay cannot be subdivided and consumes 28.6% of the cycle.1

“Phần cứng phải sao chép đúng y trạng thái của ISA” “Hardware must mirror the ISA's state exactly”

Ngộ nhận: CPU phải lưu trạng thái đúng như ISA mô tả.

Thực tế: chỉ cần chương trình trông như truy cập đúng trạng thái; ở SEQ+ còn không có thanh ghi PC nào cả — PC được tính lại động.1

Myth: the CPU must store state exactly as the ISA describes.

Reality: programs need only appear to access that state; in SEQ+ there is no PC register at all — the PC is recomputed dynamically.1

Tự kiểm Self-check

Năm câu hỏi để biết bạn đã nắm cách dựng một bộ xử lý Năm câu hỏi kiểm tra nhanh Five questions to check you grasped processor design

Trả lời được những câu này nghĩa là bạn đã theo trọn hành trình từ tập lệnh Y86-64, qua bộ xử lý tuần tự SEQ, tới đường ống PIPE và cách nó xử lý nguy cơ.

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

Answering these means you followed the whole path from the Y86-64 ISA, through the sequential SEQ, to the PIPE pipeline and how it handles hazards.

  1. Trạng thái lập trình viên thấy được của Y86-64 gồm những gì? Vì sao Y86-64 chỉ có 15 thanh ghi mà không phải 16?

    Gợi ý sâu hơn: vì sao phần cứng không buộc phải lưu trạng thái đúng như ISA mô tả?

  2. Kể tên sáu tầng của SEQ theo thứ tự. Với lệnh số học subq, tầng nào tính kết quả và tầng nào ghi nó vào thanh ghi?

    Gợi ý sâu hơn: vì sao giữ dòng chảy đồng nhất lại giúp tiết kiệm phần cứng?

  3. Đường ống tăng thứ gì — thông lượng hay độ trễ? Vì sao gấp đôi số tầng lại không làm nhanh gấp đôi?

    Gợi ý sâu hơn: con số 28,6% trong sách nói về điều gì?

  4. Nguy cơ dữ liệu là gì, và chuyển tiếp (forwarding) giải quyết nó ra sao? Vì sao nguy cơ nạp/dùng cần thêm một bong bóng?

    Gợi ý sâu hơn: PIPE có mấy nguồn và mấy đích chuyển tiếp?

  5. Nguy cơ điều khiển sinh ra từ đâu, và dự đoán nhánh giúp gì? Chiến lược “luôn lấy nhánh” đúng khoảng bao nhiêu phần trăm?

    Gợi ý sâu hơn: vì sao lệnh ret được xử lý khác với nhánh có điều kiện?

  1. Thanh ghi là gì? CPU Y86-64 có mấy cái?

  2. Một lệnh đi qua mấy bước trong SEQ? Kể vài bước bạn nhớ.

  3. Vì sao cho các lệnh chạy gối đầu lại làm được nhiều việc hơn mỗi giây?

  4. Khi lệnh sau cần số mà lệnh trước chưa cất xong, CPU làm gì để khỏi phải chờ lâu?

  5. Gặp một ngã rẽ mà chưa biết hướng, CPU làm gì để không đứng chờ?

  1. What makes up Y86-64's programmer-visible state? Why does it have 15 registers, not 16?

  2. Name SEQ's six stages in order. For an arithmetic subq, which stage computes the result and which writes it to a register?

  3. Does pipelining raise throughput or latency? Why doesn't doubling the stages double the speed?

  4. What is a data hazard, and how does forwarding resolve it? Why does a load/use hazard need an extra bubble?

  5. Where do control hazards come from, and how does branch prediction help? How often is "always taken" correct?

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

Một bộ xử lý chỉ là phần cứng thực hiện trung thành một tập lệnh; nhưng phần cứng ấy không cần bắt chước ISA một cách trực tiếp. Bằng cách cho các lệnh gối đầu trong một đường ống rồi khéo léo xử lý các nguy cơ, ta đổi lấy thông lượng cao mà vẫn giữ đúng điều ISA đã hứa.1

CPU là phần cứng làm đúng theo một bộ lệnh; nhưng bên trong nó được tổ chức rất khéo để chạy nhanh. Cho các lệnh chạy gối đầu như dây chuyền là bí quyết, miễn là xử lý gọn những lúc lệnh này cần lệnh kia. Nhớ nhé: hiểu CPU chạy ra sao thì bạn mới hiểu vì sao mã của mình nhanh hay chậm.

A processor is just hardware faithfully implementing an instruction set; yet that hardware need not mirror the ISA directly. By overlapping instructions in a pipeline and carefully handling hazards, we trade for high throughput while still honoring what the ISA promised.1