Skip to content

Appendix A: Numerical Considerations

This section is critical for engineers working in scientific computing, finance, and AI, as it explains why "the order of operations" matters and how floating-point math can lead to subtle errors in parallel code.

A.1 Floating-point Data Representation

  • The IEEE-754 Standard: Explains the universal standard for representing real numbers in binary.

  • Bit Patterns: A floating-point number is divided into three groups:

    1. Sign (S): 0 for positive, 1 for negative.
    2. Exponent (E): Determines the range of the number.
    3. Mantissa (M): Determines the precision.

  • Normalized Representation: In IEEE format, numbers are adjusted so the first bit is always "1" (e.g., \(1.M\)). This "hidden bit" saves space and increases precision.

  • Excess Encoding: The exponent uses a "bias" (Excess-N) so that even negative exponents are represented as positive integers. This allows the hardware to compare the size of two numbers using simple, fast integer logic.

A.2 Representable Numbers

  • The Number Line: Numbers are not spread evenly across the line. They are denser near zero and get further apart as they get larger.
  • Precision vs. Range: More bits in the mantissa increase precision (closeness to the real value); more bits in the exponent increase range (how big or small the number can be).

  • The Underflow Problem:

    • Abrupt Underflow: An old method where very small numbers are simply "flushed" to zero. This creates a large gap around zero where the algorithm becomes unstable.
    • Denormalization: The modern solution. It allows the "hidden bit" to be 0 for extremely tiny numbers, ensuring they "fade to zero" gracefully. Modern GPUs (Pascal and later) handle these in hardware with no speed penalty.

A.3 Special Bit Patterns

  • Infinity (\(\infty\)): Generated when a number exceeds the maximum range (Overflow) or when dividing by zero.

  • NaN (Not a Number): Generated by mathematically undefined operations (e.g., \(0/0\) or \(\infty - \infty\)).

    • Signaling NaN: Triggers an immediate error/exception (not supported by current GPUs during massive parallel execution).
    • Quiet NaN: Propagates through the calculation, allowing the programmer to see that something went wrong at the end without crashing the whole system.

A.4 Arithmetic Accuracy and Rounding

  • Rounding Error: Most decimal numbers (like 0.1) cannot be represented exactly in binary.
  • ULP (Unit in the Last Place): The smallest possible difference between two representable numbers. A perfectly designed hardware unit should have an error of no more than 0.5 ULP.
  • GPU Fast Math: CUDA offers "Intrinsic" functions (like __sin()) that are faster because they use specialized hardware (SFUs) but may have a higher ULP error than standard library functions.

A.5 Algorithm Considerations

  • The Associativity Trap: In pure math, \((a + b) + c = a + (b + c)\). In floating-point math, this is false.

  • Parallel Summation: In a reduction tree (Chapter 10), the order of addition changes compared to a serial CPU loop.

    • The Danger: If you add a tiny number to a very large number, the tiny number is "lost" because it falls below the precision of the large number.
    • The Fix: Parallel reduction trees are actually often more accurate than serial loops because they combine numbers of similar sizes first, preserving more precision.

A.6 Linear Solvers and Numerical Stability

  • Gaussian Elimination: Illustrates how an algorithm can be "mathematically correct" but "numerically unstable."
  • Pivoting: A technique to swap rows in a matrix to avoid dividing by very small numbers, which would blow up the error.
  • Communication-Avoiding Algorithms: Explains the trade-off in modern clusters—sometimes it is better to accept slightly less numerical accuracy to avoid the massive time delay of "pivoting" across multiple nodes in a cluster.

Key Takeaway for the Appendix: It warns that Parallelism changes the math. Because floating-point addition is not associative, your GPU result may differ slightly from your CPU result. For high-stakes engineering, you must understand ULP and Denormalization to ensure your massive speedup doesn't come at the cost of "garbage" results.

Phần này rất quan trọng đối với các kỹ sư làm việc trong lĩnh vực tính toán khoa học, tài chính và AI, vì nó giải thích tại sao "thứ tự các phép toán" lại quan trọng và cách toán học dấu phẩy động (floating-point) có thể dẫn đến các sai số tinh vi trong mã song song.

A.1 Biểu diễn dữ liệu dấu phẩy động

  • Tiêu chuẩn IEEE-754: Giải thích tiêu chuẩn phổ quát để biểu diễn các số thực trong hệ nhị phân.

  • Các mẫu bit: Một số dấu phẩy động được chia thành ba nhóm:

    1. Sign (S - Dấu): 0 cho số dương, 1 cho số âm.
    2. Exponent (E - Số mũ): Xác định phạm vi của số.
    3. Mantissa (M - Phần định trị): Xác định độ chính xác.

  • Biểu diễn chuẩn hóa: Trong định dạng IEEE, các số được điều chỉnh sao cho bit đầu tiên luôn là "1" (ví dụ: \(1.M\)). "Bit ẩn" này giúp tiết kiệm không gian và tăng độ chính xác.

  • Mã hóa dư (Excess Encoding): Số mũ sử dụng một "độ lệch" (bias - Excess-N) để ngay cả các số mũ âm cũng được biểu diễn thành các số nguyên dương. Điều này cho phép phần cứng so sánh kích thước của hai số bằng logic số nguyên đơn giản và nhanh chóng.

A.2 Các số có thể biểu diễn

  • Đường số: Các số không được rải đều trên đường số. Chúng dày đặc hơn ở gần số không và cách xa nhau hơn khi giá trị lớn dần.
  • Độ chính xác vs. Phạm vi: Nhiều bit hơn trong phần định trị giúp tăng độ chính xác (mức độ gần với giá trị thực); nhiều bit hơn trong số mũ giúp tăng phạm vi (số có thể lớn hoặc nhỏ đến mức nào).

  • Vấn đề Underflow (Tràn dưới):

    • Abrupt Underflow: Một phương pháp cũ trong đó các số cực nhỏ được "ép" trực tiếp về không. Điều này tạo ra một khoảng trống lớn xung quanh số không, nơi thuật toán trở nên không ổn định.
    • Denormalization (Phi chuẩn hóa): Giải pháp hiện đại. Nó cho phép "bit ẩn" bằng 0 đối với các số cực nhỏ, đảm bảo chúng "mờ dần về không" một cách mượt mà. Các GPU hiện đại (Pascal trở về sau) xử lý việc này bằng phần cứng mà không làm giảm tốc độ.

A.3 Các mẫu bit đặc biệt

  • Vô cùng (\(\infty\)): Được tạo ra khi một số vượt quá phạm vi tối đa (Tràn trên - Overflow) hoặc khi chia cho không.

  • NaN (Not a Number - Không phải là một số): Được tạo ra bởi các phép toán không xác định về mặt toán học (ví dụ: \(0/0\) hoặc \(\infty - \infty\)).

    • Signaling NaN: Kích hoạt một lỗi/ngoại lệ ngay lập tức (không được hỗ trợ bởi các GPU hiện tại trong quá trình thực thi song song khổng lồ).
    • Quiet NaN: Được truyền đi trong suốt quá trình tính toán, cho phép lập trình viên thấy rằng có gì đó không ổn ở kết quả cuối cùng mà không làm sập toàn bộ hệ thống.

A.4 Độ chính xác số học và Làm tròn

  • Sai số làm tròn: Hầu hết các số thập phân (như 0.1) không thể được biểu diễn chính xác trong hệ nhị phân.
  • ULP (Unit in the Last Place): Sự khác biệt nhỏ nhất có thể có giữa hai số có thể biểu diễn. Một đơn vị phần cứng được thiết kế hoàn hảo phải có sai số không quá 0.5 ULP.
  • GPU Fast Math: CUDA cung cấp các hàm "Nội tại" (như __sin()) nhanh hơn vì chúng sử dụng phần cứng chuyên dụng (SFU) nhưng có thể có sai số ULP cao hơn các hàm thư viện tiêu chuẩn.

A.5 Xem xét về Thuật toán

  • Bẫy tính kết hợp: Trong toán học thuần túy, \((a + b) + c = a + (b + c)\). Trong toán học dấu phẩy động, điều này là sai.

  • Phép cộng song song: Trong một cây reduction (Chương 10), thứ tự của phép cộng thay đổi so với một vòng lặp tuần tự của CPU.

    • Mối nguy hiểm: Nếu bạn cộng một số cực nhỏ vào một số cực lớn, số nhỏ sẽ bị "mất" vì nó nằm dưới giới hạn độ chính xác của số lớn.
    • Giải pháp: Các cây reduction song song trên thực tế thường chính xác hơn các vòng lặp tuần tự vì chúng kết hợp các số có kích thước tương tự nhau trước, giúp giữ lại nhiều độ chính xác hơn.

A.6 Các bộ giải tuyến tính và Độ ổn định số học

  • Khử Gauss: Minh họa cách một thuật toán có thể "đúng về mặt toán học" nhưng "không ổn định về mặt số học".
  • Xoay vòng (Pivoting): Một kỹ thuật để tráo đổi các hàng trong ma trận nhằm tránh việc chia cho các số cực nhỏ, vốn sẽ làm sai số bùng phát.
  • Thuật toán tránh truyền thông (Communication-Avoiding Algorithms): Giải thích sự đánh đổi trong các cụm máy tính hiện đại—đôi khi chấp nhận độ chính xác số học thấp hơn một chút để tránh sự chậm trễ khổng lồ của việc "xoay vòng" trên nhiều nút trong một cụm.

Điểm chính cho Phụ lục: Nó cảnh báo rằng Tính song song làm thay đổi toán học. Bởi vì phép cộng dấu phẩy động không có tính kết hợp, kết quả GPU của bạn có thể khác một chút so với kết quả CPU. Đối với các dự án kỹ thuật quan trọng, bạn phải hiểu về ULP và Denormalization để đảm bảo việc tăng tốc khổng lồ không phải trả giá bằng các kết quả "rác".