Computer Systems: A Programmer's Perspective Chương 5 · Optimizing Program Performance

Chương 5 · Tối ưu hiệu năng chương trình Chapter 5 · Optimizing Program Performance

Viết mã mà trình biên dịch tối ưu được — rồi hiểu bộ xử lý đủ sâu để đi xa hơn Làm chương trình chạy nhanh hơn, từng bước một Write code the compiler can optimize — then understand the processor well enough to go further

Mục tiêu đầu tiên khi viết chương trình luôn là làm cho nó đúng; một chương trình chạy nhanh mà cho kết quả sai thì vô dụng.1 Nhưng có rất nhiều lúc tốc độ cũng quan trọng — xử lý khung hình video hay gói tin thời gian thực, hay một tác vụ tính toán nặng mất nhiều ngày. Bryant và O'Hallaron chỉ cho ta thấy: chỉ bằng mã C thường và một trình biên dịch chuẩn, người lập trình có thể tăng tốc một thủ tục gộp vector lên 10–20 lần, và thêm 4–8 lần nữa nếu dùng lệnh vector SIMD.1

Khi viết chương trình, điều quan trọng nhất là nó phải chạy đúng. Một chương trình nhanh mà sai thì chẳng để làm gì. Nhưng nhiều khi tốc độ cũng rất cần — ví dụ xử lý video hay chơi game mượt. Chương này cho thấy chỉ cần viết mã khéo hơn một chút, cùng một việc có thể chạy nhanh gấp cả chục, thậm chí cả trăm lần. Nhớ nhé: đúng trước đã, rồi mới tới nhanh.

The first objective in writing a program is always to make it correct; a program that runs fast but gives wrong results is useless.1 But speed matters on many occasions — processing video frames or network packets in real time, or a heavy computation that takes days. Bryant and O'Hallaron show that, using only ordinary C and a standard compiler, a programmer can speed a vector-combining routine up by 10–20×, with a further 4–8× from SIMD vector instructions.1

Lộ trình của chương là một chuỗi biến đổi trên một ví dụ chạy xuyên suốt — hàm gộp các phần tử của một vector. Hiệu năng được đo bằng chu kỳ mỗi phần tử (cycles per element, CPE). Phiên bản ngây thơ combine1 tốn khoảng 10–11 CPE sau khi bật -O1; sau nhiều biến đổi, combine6 đạt tới gần giới hạn thông lượng 0,50–1,00 CPE, và mã SIMD đẩy phép nhân số thực đơn chính xác từ 11,14 xuống 0,06 CPE — một mức tăng tốc tổng cộng hơn 180 lần.1 Điều mấu chốt: trình biên dịch mạnh đến đâu vẫn bị chặn bởi các bộ chắn tối ưu (optimization blockers) mà chỉ người lập trình mới gỡ được, và muốn vượt giới hạn độ trễ thì phải hiểu cách bộ xử lý thực thi ngoài thứ tự.1

Luận đề của chương: tối ưu hiệu năng là công việc chung của người lập trình và trình biên dịch. Người lập trình phải (1) gỡ các bộ chắn tối ưu như trùng lặp bộ nhớ và lời gọi hàm để trình biên dịch làm được việc; (2) hiểu vi kiến trúc ngoài thứ tự của bộ xử lý và hai giới hạn độ trễ/thông lượng; và (3) tái cấu trúc mã để lộ ra song song mức lệnh — tất cả được minh hoạ bằng việc kéo một hàm gộp vector từ ~20 CPE xuống gần giới hạn thông lượng.1

Ý chính: muốn chương trình nhanh, người lập trình và trình biên dịch phải cùng làm. Người lập trình dọn những chỗ cản trở, hiểu cái máy chạy ra sao, rồi sắp xếp mã để máy làm nhiều việc một lúc. Nhớ nhé: tốc độ đến từ việc viết mã sao cho máy và trình biên dịch cùng phát huy hết sức.

The chapter's thesis: optimization is a joint effort of programmer and compiler. The programmer must (1) remove optimization blockers such as memory aliasing and procedure calls so the compiler can work; (2) understand the processor's out-of-order microarchitecture and the latency/throughput bounds; and (3) restructure code to expose instruction-level parallelism — all illustrated by driving a vector-combining function from ~20 CPE down toward the throughput bound.1

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

Giúp trình biên dịch làm việc: gỡ bộ chắn tối ưu, dọn mọi lãng phí Trước hết, dọn những chỗ khiến máy phải làm việc thừa Help the compiler: remove optimization blockers and all waste

Trình biên dịch hiện đại dùng thuật toán tinh vi để đơn giản hoá biểu thức và giảm số lần tính một giá trị, nhưng chúng chỉ được phép làm các biến đổi an toàn — tức cho ra kết quả giống hệt bản chưa tối ưu trong mọi trường hợp.1 Ràng buộc đó, cộng với những đặc điểm của C như con trỏ và ép kiểu, tạo ra các bộ chắn tối ưu (optimization blockers) mà chỉ người lập trình mới gỡ nổi. Bước đầu tiên của tối ưu là loại bỏ công việc không cần thiết: bớt lời gọi hàm, bớt kiểm tra điều kiện, bớt truy cập bộ nhớ.1

Trình biên dịch là chương trình dịch mã của bạn sang mã máy, và nó cố làm cho mã chạy nhanh. Nhưng nó rất thận trọng: chỉ dám đổi khi chắc chắn kết quả không sai đi. Vì vậy nhiều khi nó đành để nguyên những chỗ chậm. Người lập trình phải tự dọn những chỗ đó. Nhớ nhé: trình biên dịch chỉ dám sửa khi chắc không làm sai — phần còn lại là việc của bạn.

Modern compilers use sophisticated algorithms to simplify expressions and reduce how often a value is computed, but they may apply only safe transformations — ones giving exactly the same result as the unoptimized version in every case.1 That constraint, plus C features like pointers and casting, creates optimization blockers that only the programmer can remove. The first step of optimization is eliminating unnecessary work: fewer function calls, conditional tests, and memory references.1

Định nghĩa. Chu kỳ mỗi phần tử (cycles per element, CPE) là thước đo hiệu năng cho các chương trình lặp qua một tập phần tử. Thời gian của một vòng lặp xấp xỉ một hằng số cộng một hệ số tỉ lệ với số phần tử; hệ số đó chính là CPE. Ví dụ, hai hàm tính tổng tiền tố có thời gian xấp xỉ 368 + 9,0n và 368 + 6,0n chu kỳ, tức CPE bằng 9,0 và 6,0.1

Nói đơn giản. CPE là “số nhịp máy tốn cho mỗi phần tử”. Số này càng nhỏ thì vòng lặp càng nhanh. Nhớ nhé: CPE nhỏ = nhanh.

Definition. Cycles per element (CPE) is a performance metric for programs that loop over a set of elements. A loop's time is roughly a constant plus a factor proportional to the number of elements; that factor is the CPE. For example, two prefix-sum functions run in about 368 + 9.0n and 368 + 6.0n cycles — CPEs of 9.0 and 6.0.1

combine1 (-O1): 10,12 | 10,12 | 10,17 | 11,14
combine2 (code motion): 7,02 | 9,03 | 9,02 | 11,03
combine3 (truy cập trực tiếp): 7,17 | 9,02 | 9,02 | 11,03
combine4 (biến tích luỹ): 1,27 | 3,01 | 3,01 | 5,01
[int+ | int* | fp+ | fp*]

combine1 → combine4
  ~10 CPE → ~1–5 CPE
  (càng nhỏ càng nhanh)

combine1 (-O1): 10.12 | 10.12 | 10.17 | 11.14
combine2 (code motion): 7.02 | 9.03 | 9.02 | 11.03
combine3 (direct access): 7.17 | 9.02 | 9.02 | 11.03
combine4 (accumulator): 1.27 | 3.01 | 3.01 | 5.01
[int+ | int* | fp+ | fp*]

  1. memory aliasing

    Trùng lặp bộ nhớ — vì sao trình biên dịch phải dè chừng Hai con trỏ chỉ cùng một chỗ — máy phải cẩn thận Memory aliasing — why the compiler must be cautious

    Xét hai hàm cùng cộng hai lần *yp vào *xp: twiddle1 đọc/ghi bộ nhớ sáu lần, còn twiddle2 chỉ ba lần. Trình biên dịch không được phép thay hàm chậm bằng hàm nhanh, vì nếu xp và yp trỏ cùng một ô, hai hàm cho kết quả khác nhau (nhân 4 so với nhân 3).1 Trường hợp hai con trỏ chỉ cùng một địa chỉ gọi là trùng lặp bộ nhớ (memory aliasing) — một bộ chắn tối ưu lớn.1

    Tưởng tượng hai cái nhãn cùng dán lên một hộp. Nếu máy không biết chắc hai nhãn có cùng hộp hay không, nó phải làm từng bước cẩn thận, không dám gộp lại cho nhanh. Nhớ nhé: khi hai con trỏ có thể trỏ cùng chỗ, trình biên dịch buộc phải chạy đường an toàn mà chậm.

    Consider two functions that each add *yp to *xp twice: twiddle1 reads/writes memory six times, twiddle2 only three. The compiler may not replace the slow one with the fast one, because if xp and yp point to the same cell, the two give different results (×4 versus ×3).1 Two pointers designating the same address is memory aliasing — a major optimization blocker.1

    Bạn gặp nó ở đâuWhere you meet it Khi gộp giá trị, combine4 dùng một biến tích luỹ nên có thể khác combine3 nếu đích ghi trùng phần tử cuối của vector: với [2,3,5], một bên cho 36, bên kia cho 30.1 Khi kết quả ghi đè lên chính dữ liệu đang đọc, hai cách viết có thể ra số khác nhau. When combining, combine4's accumulator can differ from combine3 if the destination aliases the last vector element: for [2,3,5], one yields 36, the other 30.1

    Hệ quả cho người lập trình

    Vì không đoán được ý định của người gọi, trình biên dịch chọn cách bảo thủ: giữ nguyên các lần đọc–ghi bộ nhớ. Muốn nhanh, người lập trình phải tự giới thiệu biến tạm để gom tích luỹ.1

    Một bộ chắn khác: con trỏ

    Với hai con trỏ p và q, giá trị đọc lại phụ thuộc chúng có trùng nhau hay không; nếu không xác định được, trình biên dịch phải giả định cả hai khả năng, thu hẹp tập tối ưu.1

  2. function calls & code motion

    Lời gọi hàm và di chuyển mã — bớt việc lặp lại vô ích Đừng gọi đi gọi lại một việc không đổi Procedure calls & code motion — stop repeating constant work

    Lời gọi hàm là bộ chắn tối ưu thứ hai: trình biên dịch không dám gộp bốn lần gọi f() thành 4*f() vì f có thể có tác dụng phụ (thay đổi trạng thái toàn cục).1 Ví dụ kinh điển là combine1 gọi vec_length trong điều kiện vòng lặp mỗi lần lặp, dù độ dài không đổi. Đưa lời gọi ra ngoài vòng lặp — gọi là di chuyển mã (code motion) — tạo ra combine2.1

    Nếu mỗi vòng lặp bạn đều đi hỏi lại một thứ không bao giờ đổi, thì bạn phí công. Hãy hỏi một lần rồi nhớ lấy. Đó là ý của “di chuyển mã”: dời việc không đổi ra khỏi vòng lặp. Nhớ nhé: thứ gì không đổi trong vòng lặp thì tính một lần thôi.

    Procedure calls are the second blocker: the compiler won't fold four calls to f() into 4*f() because f may have a side effect (changing global state).1 The classic example is combine1 calling vec_length in the loop test every iteration, though the length never changes. Hoisting the call out of the loop — code motion — gives combine2.1

    Bạn gặp nó ở đâuWhere you meet it Hàm lower1 gọi strlen trong điều kiện vòng lặp khiến thời gian chạy thành bậc hai: với chuỗi 1.048.576 ký tự nó cần hơn 17 phút, còn lower2 (đưa strlen ra ngoài) chỉ 2,0 mili-giây — nhanh hơn 500.000 lần.1 Một hàm đổi chữ hoa thành chữ thường, nếu viết vụng, có thể mất 17 phút thay vì vài mili-giây. lower1 calls strlen in the loop test, making its run time quadratic: for a 1,048,576-character string it needs over 17 minutes, while lower2 (strlen hoisted out) takes 2.0 ms — over 500,000× faster.1

    Vì sao trình biên dịch không tự làm

    Nó không chắc hàm có tác dụng phụ hay không, nên giả định có và để nguyên lời gọi. Với lower1, phân tích rằng strlen luôn trả về cùng giá trị nằm ngoài khả năng của cả những trình biên dịch tinh vi nhất.1

    Nội tuyến (inlining)

    gcc có thể thay lời gọi bằng thân hàm (inline substitution) ở mức -O1 trở lên, nhưng chỉ trong cùng một tệp — nên thường không áp dụng được cho hàm thư viện ở tệp khác.12

  3. eliminate memory refs

    Loại bỏ truy cập bộ nhớ thừa — tích luỹ trong thanh ghi Giữ kết quả tạm trong tay, đừng chạy về kho mỗi lần Eliminate needless memory refs — accumulate in a register

    combine3 gộp giá trị ngay tại ô nhớ dest, nên mỗi vòng lặp phải đọc rồi ghi lại bộ nhớ — một sự lãng phí, vì giá trị đọc ra đầu vòng chính là giá trị vừa ghi cuối vòng trước. combine4 đưa một biến tạm acc vào để gom kết quả, chỉ ghi ra dest sau khi vòng lặp xong.1 Số thao tác bộ nhớ mỗi vòng giảm từ hai đọc một ghi xuống chỉ một đọc.1

    Thay vì mỗi lần cộng xong lại chạy ra kho cất rồi lại chạy vào lấy, hãy giữ con số tạm trong tay cho tới khi xong hẳn mới cất. Đi lại ít thì nhanh hơn nhiều. Nhớ nhé: giữ kết quả tạm trong thanh ghi, chỉ ghi ra bộ nhớ một lần ở cuối.

    combine3 accumulates directly at memory location dest, so each iteration reads then writes memory — wasteful, since the value read at the start is the one written at the end of the previous iteration. combine4 introduces a temporary acc to gather the result, storing to dest only after the loop finishes.1 Memory operations per iteration drop from two reads and a write to a single read.1

    Bạn gặp nó ở đâuWhere you meet it Biến đổi này cho mức cải thiện từ 2,2× đến 5,7×; trường hợp cộng số nguyên rơi xuống chỉ 1,27 CPE.1 Chỉ một thay đổi nhỏ này khiến vòng lặp nhanh lên gấp vài lần. This transformation yields improvements of 2.2× to 5.7×; integer addition drops to just 1.27 CPE.1

    Vì sao trình biên dịch dè dặt

    Lại là trùng lặp bộ nhớ: combine3 và combine4 có thể khác nhau nếu dest trùng một phần tử của vector, nên trình biên dịch mặc định giữ cách đọc–ghi bộ nhớ mỗi vòng.1

    Khi -O2 bắt kịp

    Với -O2, gcc sinh một biến thể của combine3 giữ tích luỹ trong thanh ghi %xmm0 và chỉ ghi ra sau mỗi vòng, đạt CPE gần bằng combine4 cho hầu hết các trường hợp.12

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

Hiểu bộ xử lý hiện đại: ngoài thứ tự, và hai giới hạn hiệu năng Cái máy làm nhiều lệnh một lúc — và nhanh tới đâu là có giới hạn Understanding the modern processor: out-of-order, and two bounds

Nhìn ở mức mã máy, có vẻ các lệnh được chạy tuần tự từng cái một. Nhưng bên trong, bộ xử lý hiện đại đánh giá nhiều lệnh đồng thời — hiện tượng gọi là song song mức lệnh (instruction-level parallelism); có thiết kế giữ tới hơn 100 lệnh “đang bay”.1 Để tận dụng điều này, ta cần một mô hình của máy: nó siêu vô hướng (superscalar, làm nhiều thao tác mỗi chu kỳ) và thực thi ngoài thứ tự (out-of-order), với các đơn vị chức năng chuyên biệt.13

Nhìn từ ngoài, máy có vẻ làm từng lệnh một, theo đúng thứ tự. Thật ra bên trong nó khôn hơn nhiều: nó làm nhiều lệnh cùng lúc, và còn làm không đúng thứ tự viết, miễn kết quả vẫn đúng. Nhớ nhé: máy làm nhiều lệnh một lúc, nên nếu các lệnh không phụ thuộc nhau thì chạy nhanh hơn.

At the machine-code level, instructions appear to execute one at a time. But inside, a modern processor evaluates many instructions simultaneously — instruction-level parallelism; some designs keep over 100 instructions "in flight."1 To exploit this we need a model of the machine: it is superscalar (multiple operations per cycle) and out-of-order, with specialized functional units.13

Định nghĩa. Hai cận dưới đặc trưng cho hiệu năng. Giới hạn độ trễ (latency bound) xuất hiện khi các thao tác phải theo đúng chuỗi, vì kết quả của cái này cần cho cái kế tiếp. Giới hạn thông lượng (throughput bound) đặc trưng sức tính thô của các đơn vị chức năng — là trần cuối cùng của hiệu năng.1

Nói đơn giản. Có hai kiểu “chặn tốc độ”: một là khi phải làm nối đuôi nhau (phải xong cái trước mới tới cái sau); hai là khi máy đã dồn hết công suất mà vẫn chỉ làm được bấy nhiêu. Nhớ nhé: tốc độ bị chặn hoặc do phải xếp hàng, hoặc do hết công suất máy.

Definition. Two lower bounds characterize performance. The latency bound arises when operations must run in strict sequence, because one result is needed before the next can start. The throughput bound characterizes the raw computing capacity of the functional units — the ultimate limit.1

Độ trễ (Haswell): int+ =1, int* =3, fp+ =3, fp* =5
Giới hạn [độ trễ | thông lượng]:
  int+ : 1,00 | 0,50
  int* : 3,00 | 1,00
  fp+ : 3,00 | 1,00
  fp* : 5,00 | 0,50
Đường tới hạn ≈ L·n

nối đuôi nhau → chậm (L·n)
làm song song → nhanh
(tới trần công suất máy)

Latency (Haswell): int+ =1, int* =3, fp+ =3, fp* =5
Bounds [latency | throughput]:
  int+ : 1.00 | 0.50
  int* : 3.00 | 1.00
  fp+ : 3.00 | 1.00
  fp* : 5.00 | 0.50
Critical path ≈ L·n

  1. out-of-order superscalar

    Siêu vô hướng, ngoài thứ tự — ICU dự đoán, EU thực thi Máy đoán trước và làm sẵn nhiều việc một lúc Out-of-order superscalar — the ICU predicts, the EU executes

    Bộ xử lý chia làm hai phần: đơn vị điều khiển lệnh (instruction control unit, ICU) đọc lệnh và sinh ra các thao tác nguyên thuỷ, và đơn vị thực thi (execution unit, EU) thực hiện chúng.1 Khi gặp rẽ nhánh, ICU dùng dự đoán rẽ nhánh (branch prediction) và thực thi suy đoán (speculative execution) để chạy trước theo hướng nó đoán; đổi tên thanh ghi (register renaming) cho phép chuyển tiếp kết quả thẳng giữa các thao tác.1

    Máy có hai bộ phận: một bộ lo đọc và sắp xếp lệnh, một bộ lo tính toán. Khi tới chỗ rẽ (“nếu… thì…”), máy đoán sẽ rẽ hướng nào và làm trước; đoán đúng thì nhanh, đoán sai thì phải làm lại. Nhớ nhé: máy đoán trước để khỏi chờ, nhưng đoán sai thì tốn công làm lại.

    The processor has two parts: the instruction control unit (ICU) reads instructions and generates primitive operations, and the execution unit (EU) performs them.1 At a branch, the ICU uses branch prediction and speculative execution to run ahead down its guessed path; register renaming forwards results directly between operations.1

    Bạn gặp nó ở đâuWhere you meet it Máy tham chiếu Intel Core i7 Haswell có tám đơn vị chức năng (đánh số 0–7): bốn làm số nguyên, hai nạp (load), hai nhân số thực — quyết định bao nhiêu thao tác cùng loại chạy được một lúc.13 Máy có nhiều “bàn tay” chuyên việc; càng nhiều tay cùng loại thì càng làm được nhiều việc đó một lúc. The Intel Core i7 Haswell reference machine has eight functional units (0–7): four do integer work, two load, two do floating-point multiplication — setting how many same-type operations run at once.13

    Lịch sử ngoài thứ tự

    Thực thi ngoài thứ tự có từ máy CDC 6600 năm 1964 và IBM 360/91 năm 1966; Intel đưa nó vào dòng PentiumPro năm 1995, với vi kiến trúc gần giống máy tham chiếu của sách.1

    Nối với Chương 4

    Chương 4 nghiên cứu một ống dẫn (pipeline) trong-thứ-tự đơn giản; bộ xử lý ngoài thứ tự cần phần cứng phức tạp hơn nhiều nhưng đạt mức song song mức lệnh cao hơn.1

  2. latency vs throughput

    Giới hạn độ trễ và thông lượng — hai trần của hiệu năng Hai kiểu giới hạn tốc độ: xếp hàng và hết công suất Latency vs throughput bounds — two ceilings on performance

    Mỗi phép tính có độ trễ (latency — tổng số chu kỳ để làm xong), thời gian phát (issue time — khoảng cách tối thiểu giữa hai thao tác độc lập), và dung lượng (capacity — số đơn vị làm được phép đó). Trên Haswell, cộng số nguyên có độ trễ 1, nhân số nguyên 3, cộng số thực 3, nhân số thực 5.13 Thông lượng tối đa của một đơn vị bằng C/I; vì có hai đơn vị nạp, CPE không thể xuống dưới 0,50 khi mỗi phần tử cần đọc một giá trị.1

    Mỗi phép tính tốn một số nhịp để xong (độ trễ), và máy chỉ có vài “bàn tay” làm phép đó. Phép càng khó thì độ trễ càng lớn: nhân số thực tốn 5 nhịp, cộng số nguyên chỉ 1. Nhớ nhé: phép khó tốn nhiều nhịp hơn, và số bàn tay có hạn.

    Each operation has a latency (total cycles to finish), an issue time (minimum gap between two independent operations), and a capacity (how many units can do it). On Haswell, integer addition has latency 1, integer multiplication 3, FP addition 3, FP multiplication 5.13 A unit's maximum throughput is C/I; with two load units, the CPE cannot go below 0.50 when each element requires one memory read.1

    Bạn gặp nó ở đâuWhere you meet it Các đơn vị cộng/nhân đều có thời gian phát bằng 1 nhờ ống dẫn (pipelining): dù một phép nhân số thực mất 5 chu kỳ mới xong, máy vẫn bắt đầu một phép mới mỗi chu kỳ — nếu có đủ thao tác độc lập.1 Giống dây chuyền: một món mất 5 phút, nhưng mỗi phút vẫn cho một món mới ra lò, miễn là các món không phải chờ nhau. The add/multiply units have issue time 1 thanks to pipelining: even though an FP multiply takes 5 cycles to finish, the machine can start a new one every cycle — if there are enough independent operations.1

    Phép chia là ngoại lệ

    Bộ chia không dùng ống dẫn: độ trễ bằng thời gian phát (3–30 chu kỳ với số nguyên, 3–15 với số thực), nên chia là phép đắt đỏ cần tránh trong vòng trong.13

    Nguồn con số

    Các độ trễ, thời gian phát và dung lượng này được sách xác định bằng đo đạc thực tế đối chiếu với tài liệu Intel; chúng thay đổi giữa các thế hệ bộ xử lý.134

  3. critical path

    Đường tới hạn — chuỗi phụ thuộc dữ liệu định đoạt tốc độ Chuỗi việc phải nối đuôi nhau là chỗ quyết định tốc độ The critical path — the data-dependency chain sets the speed

    Dùng biểu diễn luồng dữ liệu (data-flow), ta vẽ cách các phụ thuộc dữ liệu ràng buộc thứ tự thực thi. Chuỗi dài nhất của các phụ thuộc này là đường tới hạn (critical path), đặt cận dưới cho số chu kỳ. Với combine4, mỗi giá trị acc mới phải chờ giá trị trước, tạo một đường tới hạn dài L·n — nên CPE bằng đúng độ trễ L.1

    Hãy hình dung một dây chuyền mà mỗi bước phải chờ bước trước xong mới làm được. Dây chuyền đó dài bao nhiêu thì cả việc chậm bấy nhiêu, dù máy rảnh rỗi. Chuỗi phải-chờ đó gọi là “đường tới hạn”. Nhớ nhé: chuỗi việc phải nối đuôi nhau quyết định tốc độ, không phải sức máy.

    Using a data-flow representation, we draw how data dependencies constrain execution order. The longest such chain is the critical path, setting a lower bound on cycles. In combine4, each new acc must wait for the previous one, forming a critical path of length L·n — so the CPE equals the latency L.1

    Bạn gặp nó ở đâuWhere you meet it Đo được cho thấy combine4 khớp giới hạn độ trễ ở mọi trường hợp trừ cộng số nguyên (1,27 thay vì 1,00) — đường tới hạn chỉ là cận dưới, còn các yếu tố khác cũng góp phần.1 Khi một vòng lặp chậm đúng bằng độ dài chuỗi phải-chờ của nó, không nhanh hơn được. Measurements show combine4 matches the latency bound in every case except integer addition (1.27 instead of 1.00) — the critical path is only a lower bound; other factors also contribute.1

    Bốn loại thanh ghi của vòng lặp

    Sách phân loại thanh ghi trong vòng lặp thành chỉ-đọc, chỉ-ghi, cục bộ, và vòng lặp (loop). Chỉ các thanh ghi loại loop — mang giá trị từ vòng này sang vòng khác — mới tạo nên phụ thuộc giới hạn hiệu năng.1

    Hướng đi tiếp theo

    Nếu đường tới hạn do việc cập nhật acc theo chuỗi, thì cách thoát là phá vỡ chuỗi đó — mục tiêu của cụm tiếp theo, đưa CPE về gần giới hạn thông lượng.1

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

Khai thác song song mức lệnh — và dùng trình phân tích để tìm nút cổ chai Chia việc ra làm song song, rồi đo xem chỗ nào còn chậm Exploit instruction-level parallelism — and profile to find bottlenecks

Để vượt giới hạn độ trễ, ta phải phá vỡ chuỗi phụ thuộc đơn nhất quanh biến acc. Hai kỹ thuật cốt lõi là nhiều biến tích luỹ (multiple accumulators) và tái kết hợp (reassociation), thường kết hợp với mở vòng lặp (loop unrolling).1 Khi đã tối ưu xong các vòng lặp nhỏ, câu hỏi với chương trình lớn là: tối ưu chỗ nào? — và đó là lúc cần đến trình phân tích hiệu năng (profiler).1

Muốn nhanh hơn nữa, ta chia công việc ra thành vài phần làm song song, thay vì một chuỗi nối đuôi. Và với chương trình lớn, trước khi tối ưu, hãy đo xem phần nào ngốn nhiều thời gian nhất — đừng đoán mò. Nhớ nhé: chia việc ra làm song song, và luôn đo trước khi tối ưu.

To beat the latency bound we must break the single dependency chain around acc. The two core techniques are multiple accumulators and reassociation, usually combined with loop unrolling.1 Once the small loops are optimized, the question for a large program is: what to optimize? — and that is when you need a profiler.1

Định nghĩa. Mở vòng lặp k×1 gộp k phần tử mỗi vòng để giảm thao tác điều khiển vòng lặp. Mở vòng lặp k×k còn giữ k biến tích luỹ song song. Muốn đạt giới hạn thông lượng, cần hệ số mở k ≥ C·L (dung lượng nhân độ trễ) — ví dụ nhân số thực có C=2, L=5 nên cần k≥10.1

Nói đơn giản. “Mở vòng lặp” là làm nhiều phần tử trong một vòng thay vì một. Thêm nhiều “ô nhớ tạm” chạy song song thì máy mới làm hết công suất. Nhớ nhé: nhiều ô tích luỹ song song mới lấp đầy được dây chuyền.

Definition. k×1 loop unrolling combines k elements per iteration to cut loop-control operations. k×k unrolling also keeps k parallel accumulators. To reach the throughput bound you need unrolling factor k ≥ C·L (capacity times latency) — e.g. FP multiply has C=2, L=5, so k≥10.1

combine4: 1,27 | 3,01 | 3,01 | 5,01
combine5 (2×1): 1,01 | 3,01 | 3,01 | 5,01
combine6 (2×2): 0,81 | 1,51 | 1,51 | 2,51
combine7 (2×1a): 1,01 | 1,51 | 1,51 | 2,51
SIMD fp* đơn: 11,14 → 0,06 (>180×)

một ô tích luỹ → chậm
nhiều ô song song → nhanh
SIMD → nhanh hơn nữa

combine4: 1.27 | 3.01 | 3.01 | 5.01
combine5 (2×1): 1.01 | 3.01 | 3.01 | 5.01
combine6 (2×2): 0.81 | 1.51 | 1.51 | 2.51
combine7 (2×1a): 1.01 | 1.51 | 1.51 | 2.51
SIMD single fp*: 11.14 → 0.06 (>180×)

  1. loop unrolling

    Mở vòng lặp — giảm chi phí điều khiển, nhưng chưa phá chuỗi Làm nhiều phần tử một vòng để bớt việc lặt vặt Loop unrolling — cuts overhead, but doesn't break the chain

    Mở vòng lặp (loop unrolling) giảm số vòng lặp bằng cách xử lý nhiều phần tử mỗi vòng, qua đó bớt các thao tác không trực tiếp tạo kết quả như đánh chỉ số và rẽ nhánh. combine5 áp dụng “mở 2×1”. Kết quả: cộng số nguyên cải thiện xuống 1,01 CPE (chạm giới hạn độ trễ), nhưng ba trường hợp còn lại không đổi — vì đường tới hạn vẫn gồm n phép toán nối đuôi nhau.1

    Thay vì mỗi vòng làm một phần tử, ta làm hai, ba phần tử một vòng. Nhờ đó bớt được các việc lặt vặt của vòng lặp. Nhưng riêng việc này chưa đủ phá chuỗi phải-chờ. Nhớ nhé: mở vòng lặp bớt việc thừa, nhưng chưa làm máy chạy song song.

    Loop unrolling reduces iterations by handling several elements per iteration, cutting operations that don't directly produce results such as indexing and branching. combine5 applies "2×1 unrolling." Result: integer addition improves to 1.01 CPE (reaching the latency bound), but the other three are unchanged — the critical path still has n operations in sequence.1

    Bạn gặp nó ở đâuWhere you meet it Khi tăng hệ số mở lên tới k=10, không trường hợp nào xuống dưới giới hạn độ trễ của nó — bằng chứng rằng mở vòng lặp đơn thuần không phá được chuỗi phụ thuộc.1 Mở nhiều hơn nữa cũng không giúp, nếu các phép vẫn phải nối đuôi nhau. Increasing the factor up to k=10, no case goes below its latency bound — evidence that plain unrolling cannot break the dependency chain.1

    Xử lý phần dư

    Vì độ dài vector thường không chia hết cho k, mã đặt cận trên là n−k+1 và thêm một vòng phụ xử lý nốt vài phần tử cuối, chạy từ 0 đến k−1 lần.1

    Trình biên dịch cũng làm được

    gcc tự mở vòng lặp ở mức -O3 trở lên; nhưng ví dụ của sách cố tình dùng -O1 để cho thấy người lập trình có thể giúp gì.12

  2. multiple accumulators

    Nhiều biến tích luỹ và tái kết hợp — phá vỡ giới hạn độ trễ Dùng nhiều ô tạm song song để máy chạy hết sức Multiple accumulators & reassociation — break the latency bound

    Với phép kết hợp vừa giao hoán vừa kết hợp, ta chia tập phần tử thành nhiều phần và gộp riêng. combine6 dùng “2×2”: tích luỹ phần tử chỉ số chẵn vào acc0, chỉ số lẻ vào acc1, tạo hai đường tới hạn mỗi đường n/2 phép — CPE giảm còn ~một nửa (fp* xuống 2,51).1 combine7 dùng tái kết hợp (reassociation): chỉ đổi vị trí dấu ngoặc acc OP (data[i] OP data[i+1]) mà cũng đạt kết quả tương đương.1

    Thay vì một ô tạm, ta dùng hai ô tạm chạy song song: một ô lo phần tử chẵn, một ô lo phần tử lẻ, cuối cùng gộp lại. Thế là hai dây chuyền chạy cùng lúc, nhanh gấp đôi. Nhớ nhé: nhiều ô tạm song song thì phá được chuỗi phải-chờ.

    For an operation that is both commutative and associative, we split the elements into parts and combine separately. combine6 uses "2×2": even-indexed elements into acc0, odd into acc1, forming two critical paths of n/2 each — CPE roughly halves (fp* down to 2.51).1 combine7 uses reassociation: merely moving parentheses to acc OP (data[i] OP data[i+1]) achieves an equivalent gain.1

    Bạn gặp nó ở đâuWhere you meet it Với mở k×k đủ lớn, cộng số nguyên đạt 0,54 CPE (k=7), nhân số thực đạt 0,51 (k=10) — gần sát giới hạn thông lượng 0,50.1 Dùng đủ nhiều ô tạm, chương trình chạy gần hết công suất máy. With large enough k×k unrolling, integer addition reaches 0.54 CPE (k=7) and FP multiply 0.51 (k=10) — close to the throughput bound of 0.50.1

    Cảnh báo về số thực

    Cộng và nhân số thực không có tính kết hợp, nên combine6/combine7 có thể cho kết quả khác do làm tròn hay tràn số. Sách theo khung của chính nó — coi khác biệt là không đáng kể với hầu hết ứng dụng — nhưng khuyên người phát triển phải kiểm với người dùng. Vì lẽ đó, đa số trình biên dịch không tự tái kết hợp mã số thực.1

    Điều kiện đạt thông lượng

    Để lấp đầy ống dẫn của mọi đơn vị làm phép đó, cần hệ số mở k ≥ C·L. Số nguyên có tính kết hợp (kể cả khi tràn), nên trình biên dịch có thể tự biến đổi; với số thực thì không.1

  3. SIMD, spilling, profiling

    SIMD, các yếu tố giới hạn, và trình phân tích hiệu năng Làm cả bó số một lệnh; biết khi nào hết lợi; và đo chỗ chậm SIMD, limiting factors, and the profiler

    Lệnh SIMD (single instruction, multiple data) của AVX dùng thanh ghi vector 32 byte, xử lý cùng lúc tám số 32 bit hay bốn số 64 bit. Kết hợp SIMD với mở vòng lặp và nhiều biến tích luỹ, nhân số thực đơn chính xác tụt từ 11,14 xuống 0,06 CPE — tổng cộng hơn 180 lần.13 Nhưng song song có giới hạn: nếu số biến vượt quá 16 thanh ghi, trình biên dịch phải tràn thanh ghi (register spilling) ra ngăn xếp và mất hết lợi thế.1

    Có loại lệnh đặc biệt làm cả một bó số cùng lúc (SIMD), nhanh gấp bội. Nhưng không thể thêm ô tạm mãi: máy chỉ có 16 thanh ghi, vượt quá là chậm lại. Và với chương trình lớn, hãy dùng công cụ đo (profiler) để biết chỗ nào thật sự chậm. Nhớ nhé: tối ưu phần tốn nhiều thời gian nhất — hãy đo, đừng đoán.

    AVX SIMD (single instruction, multiple data) instructions use 32-byte vector registers, processing eight 32-bit or four 64-bit numbers at once. Combining SIMD with unrolling and multiple accumulators, single-precision FP multiply drops from 11.14 to 0.06 CPE — over 180× overall.13 But parallelism has limits: if variables exceed the 16 registers, the compiler must spill to the stack and lose the advantage.1

    Bạn gặp nó ở đâuWhere you meet it Trình phân tích gprof giúp kéo một chương trình đếm bigram từ 3,5 phút xuống 0,2 giây — tăng tốc khoảng 1.000 lần — bằng cách chỉ ra nút cổ chai thật sự: sắp xếp, duyệt danh sách, rồi hàm băm.15 Nhờ công cụ đo, một chương trình chậm 3,5 phút rút còn 0,2 giây. The gprof profiler helped cut a bigram-counting program from 3.5 minutes to 0.2 seconds — about 1,000× — by exposing the real bottlenecks: sorting, list scanning, then the hash function.15

    Rẽ nhánh và nước đi có điều kiện

    Rẽ nhánh đoán sai tốn khoảng 19 chu kỳ trên máy tham chiếu. Viết theo lối “hàm” để trình biên dịch sinh lệnh di chuyển có điều kiện (conditional move) giúp tránh phạt: minmax2 đạt 4,0 CPE bất kể dữ liệu, còn minmax1 lên tới 13,5 với dữ liệu ngẫu nhiên.1

    Hiệu năng bộ nhớ

    Máy tham chiếu có hai đơn vị nạp và một đơn vị lưu. Hàm list_len đạt CPE 4,00 — đúng bằng độ trễ truy cập cache L1. Một phụ thuộc ghi/đọc (write/read dependency) khi địa chỉ trùng nhau có thể làm chậm thêm khoảng 6 chu kỳ.1

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

“Cứ bật -O3 là trình biên dịch lo hết” “Just enable -O3 and the compiler handles everything”

Ngộ nhận: tối ưu là việc của trình biên dịch.

Thực tế: trình biên dịch chỉ làm biến đổi an toàn và bị chặn bởi trùng lặp bộ nhớ và lời gọi hàm; người lập trình phải tự gỡ các bộ chắn này.1

Myth: optimization is the compiler's job.

Reality: the compiler makes only safe transformations and is blocked by memory aliasing and procedure calls; the programmer must remove those blockers.1

“Mở vòng lặp là đủ để chạy nhanh” “Loop unrolling alone makes code fast”

Ngộ nhận: cứ mở vòng lặp thật nhiều là CPE giảm.

Thực tế: mở k×1 đơn thuần chỉ giúp cộng số nguyên; muốn phá giới hạn độ trễ phải dùng nhiều biến tích luỹ hoặc tái kết hợp để tạo nhiều đường tới hạn.1

Myth: unroll a lot and the CPE drops.

Reality: plain k×1 unrolling helps only integer addition; breaking the latency bound needs multiple accumulators or reassociation to form several critical paths.1

“Nhanh thì phải tối ưu mọi dòng mã” “Fast means optimizing every line”

Ngộ nhận: tối ưu khắp nơi là cách để nhanh.

Thực tế: định luật Amdahl cho thấy chỉ phần được tăng tốc mới có lợi; hãy đo bằng trình phân tích rồi nhắm vào nút cổ chai thật sự.16

Myth: optimizing everywhere is how you get fast.

Reality: Amdahl's law shows only the sped-up fraction helps; measure with a profiler, then target the real bottleneck.16

Tự kiểm Self-check

Năm câu hỏi để biết bạn đã nắm nghệ thuật tối ưu Năm câu hỏi kiểm tra nhanh Five questions to check you grasped optimization

Trả lời được những câu này nghĩa là bạn đã theo trọn hành trình kéo một hàm gộp vector từ ~20 CPE xuống gần giới hạn thông lượng.

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

Answering these means you followed the whole journey of driving a vector-combining function from ~20 CPE toward the throughput bound.

  1. Hai bộ chắn tối ưu lớn là gì, và vì sao chúng ngăn trình biên dịch sinh mã nhanh hơn?

    Gợi ý sâu hơn: với [2,3,5], vì sao combine3 và combine4 cho 36 và 30 khi đích ghi trùng phần tử cuối?

  2. CPE là gì, và nó khác gì với “số chu kỳ mỗi vòng lặp”? Vì sao ta đo theo phần tử?

    Gợi ý sâu hơn: hai hàm tổng tiền tố cho CPE 9,0 và 6,0 được rút ra từ các phương trình nào?

  3. Phân biệt giới hạn độ trễ và giới hạn thông lượng. Vì sao combine4 khớp giới hạn độ trễ?

    Gợi ý sâu hơn: đường tới hạn dài L·n hình thành từ chuỗi phụ thuộc nào quanh biến acc?

  4. Vì sao mở vòng lặp đơn thuần không phá được giới hạn độ trễ, còn nhiều biến tích luỹ thì có?

    Gợi ý sâu hơn: vì sao tái kết hợp mã số thực lại cần cân nhắc, trong khi với số nguyên thì không?

  5. Trình phân tích hiệu năng giúp gì, và định luật Amdahl nói gì về việc chọn chỗ để tối ưu?

    Gợi ý sâu hơn: với α=0,974, vì sao mức tăng tốc dự đoán là 39,0× và đo được 38,5×?

  1. Vì sao đôi khi trình biên dịch không dám làm mã nhanh hơn? Kể một lý do.

  2. CPE là gì? Số này nhỏ thì tốt hay xấu?

  3. Có hai kiểu giới hạn tốc độ. Kể tên và giải thích ngắn gọn.

  4. Vì sao dùng nhiều “ô nhớ tạm” song song lại làm vòng lặp nhanh hơn?

  5. Trước khi tối ưu một chương trình lớn, nên làm gì đầu tiên? Vì sao?

  1. What are the two major optimization blockers, and why do they stop the compiler from generating faster code?

  2. What is CPE, and how does it differ from "cycles per iteration"? Why measure per element?

  3. Distinguish the latency bound from the throughput bound. Why does combine4 match the latency bound?

  4. Why can't plain loop unrolling break the latency bound, while multiple accumulators can?

  5. What does a profiler help with, and what does Amdahl's law say about where to optimize?

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

Tối ưu bắt đầu bằng việc gỡ các bộ chắn để trình biên dịch làm được việc, rồi đòi hỏi ta hiểu bộ xử lý đủ để lộ ra song song mức lệnh. Chỉ bằng mã C thường, một hàm gộp vector đi từ ~20 xuống gần 0,5 CPE — và bài học lớn nhất: hãy đo trước khi tối ưu.1

Muốn nhanh, trước hết dọn những chỗ cản trở trình biên dịch, rồi sắp xếp mã để máy làm nhiều việc một lúc. Và luôn đo xem chỗ nào thật sự chậm. Nhớ nhé: đúng trước, rồi đo, rồi mới tối ưu đúng chỗ.

Optimization begins by removing blockers so the compiler can work, then demands that we understand the processor enough to expose instruction-level parallelism. Using only ordinary C, a vector-combining function goes from ~20 down toward 0.5 CPE — and the biggest lesson: measure before you optimize.1