Vì sao nên tránh “tối ưu hóa” di chuyển có điều kiện bằng `mix()+step()` trong shader

 (iquilezles.org)
1 điểm bởi GN⁺ 2025-02-10 | 1 bình luận | Chia sẻ qua WhatsApp
  • Trong GPU shader, đoạn mã chọn giá trị bằng toán tử ba ngôi hoặc if đơn giản thường không được xử lý như nhánh điều kiện, mà là di chuyển có điều kiện (select)
  • Kể cả khi đổi sang step() và che mặt nạ bằng số học thì cũng không có nhánh nào để loại bỏ, nên tiền đề của cái gọi là tối ưu hóa loại bỏ branch ngay từ đầu đã không đúng
  • Trong đầu ra của trình biên dịch AMD và Microsoft, xuất hiện các lệnh so sánh và mặt nạ/di chuyển có điều kiện, còn không thấy lệnh jump hay branch
  • Phiên bản step() tạo mặt nạ 0.0/1.0, rồi tổng hợp kết quả bằng phép nhân và cộng, nên làm tăng các phép toán không cần thiết so với mã di chuyển có điều kiện trực tiếp
  • Nhánh GPU để bỏ qua các khối tính toán lớn theo điều kiện vẫn hữu ích, nhưng với việc chọn giá trị đơn giản thì an toàn hơn là kiểm tra mã máy được tạo ra

Chọn giá trị đơn giản không phải là nhánh GPU

  • Hàm ví dụ snap45() tính x = abs(v.x) từ vector đầu vào, rồi dùng hai toán tử ba ngôi để trả về một trong ba kết quả vec2
  • Cùng logic đó vẫn được giữ nguyên nếu viết bằng câu lệnh if thông thường
  • “Tối ưu hóa” gây vấn đề là cách thay toán tử ba ngôi bằng step() và tổng hợp theo trọng số
    • Tạo w0, w1, w2 bằng step()
    • Tính riêng res0, res1, res2
    • Tổng hợp kết quả cuối bằng w0*res0 + w1*res1 + w2*res2
  • Cách chuyển đổi này xuất phát từ hiểu lầm rằng mã gốc tạo ra nhánh có điều kiện
  • Việc chọn giá trị thanh ghi đơn giản không làm đổi con trỏ lệnh, cũng không gây dự đoán sai, xóa pipeline hay vô hiệu hóa bộ nhớ đệm lệnh
  • Nhánh thực sự trên GPU vẫn có thể nhanh và hữu ích khi cần bỏ qua các khối tính toán lớn tùy theo điều kiện
  • Tuy nhiên, trong trường hợp chỉ chọn giá trị hoặc kết quả tính toán như ví dụ này, có thể xem là không sinh nhánh trong mã máy được tạo ra

Khác biệt thể hiện qua đầu ra trình biên dịch

  • Mã toán tử ba ngôi GLSL gốc được trình biên dịch AMD chuyển thành các lệnh so sánh và mặt nạ có điều kiện
    • So sánh: v_cmp_gt_f32, v_cmp_ngt_f32
    • Mặt nạ có điều kiện: v_cndmask_b32
  • Đầu ra của trình biên dịch Microsoft cũng cho thấy cùng một cấu trúc
    • So sánh: lt
    • Di chuyển có điều kiện: movc
  • Cả hai đầu ra trình biên dịch đều không có lệnh jump/branch

Vì sao cách dùng step() đắt hơn

  • Cách làm dựa trên step() trước hết tạo mặt nạ 0.0 hoặc 1.0 bằng di chuyển có điều kiện, rồi che nhiều kết quả ứng viên bằng phép nhân và cộng
  • Mã gốc di chuyển trực tiếp giá trị cần thiết có điều kiện, nên ít lãng phí hơn cách step() phải thêm bước tạo mặt nạ và tổng hợp số học
  • Trên nhiều phần cứng khác nhau, phiên bản dùng step() có thể được đo là chậm hơn đáng kể so với phiên bản gốc
  • Một số lời gọi abs() GLSL trong mã ví dụ không phải là lệnh GPU riêng biệt, mà đi vào dưới dạng modifier của lệnh; trong những trường hợp như vậy, lời gọi abs() có thể được xem là gần như miễn phí
  • Khuyến nghị float a = mix(b, c, step(y, x)); như một tối ưu hóa cho float a = x < y ? b : c; là một cách tiếp cận sai

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-02-10
Các ý kiến trên Hacker News

  • Kết luận của TFA có vẻ đúng, nhưng lập luận có lẽ sẽ thuyết phục hơn nếu họ không chỉ đưa ra kết quả sinh mã của phiên bản tốt hơn, mà cho thấy kết quả sinh mã của cả hai phiên bản
    Trong đoạn trích, họ nói “phiên bản được cho là đã tối ưu hóa chậm hơn nhiều so với phiên bản gốc… lãng phí hai phép nhân và một hoặc hai phép cộng… hãy xem mã máy được sinh ra”, nhưng thực tế lại chỉ cho thấy phiên bản tốt, không có phép nhân hay phép cộng nào
    Điều đó chỉ chứng minh rằng phiên bản tốt là ổn, chứ chưa chứng minh phiên bản xấu tệ hơn

    • Điểm cốt lõi là câu điều kiện không tạo ra nhánh thực sự
      Ngay cả nếu đưa ra mã được sinh của phiên bản kia, có lẽ cũng chỉ cho thấy nó dài hơn, và vì phía đó cũng không được kỳ vọng sẽ phát sinh nhánh nên có lẽ giá trị không lớn
    • Mã được sinh cho RDNA 1 ở đây: https://shader-playground.timjones.io/5d3ece620f45091678dcee...

  • Giá mà có một cách tốt để biết khi nào if thực sự buộc tạo nhánh, và khi nào thì không
    Lý do mọi người dùng mix/lerp, vốn có thể đắt hơn, là vì họ sợ phát sinh nhánh dù có phải chịu một chút overhead
    Thật tốt khi đoạn mã rõ ràng nhất như v = x > y ? a : b; thực sự hoạt động tốt, nhưng việc cùng một cú pháp if lúc thì là nhánh, lúc thì không khiến người ta bất an
    Trong những ngữ cảnh thật sự không được phép rẽ nhánh, tôi muốn branch-if và if không rẽ nhánh là các từ khóa khác nhau; từ khóa không rẽ nhánh phải khiến biên dịch thất bại nếu compiler không thể tạo ra mã không có nhánh, còn từ khóa rẽ nhánh thì nên cảnh báo nếu có thể tạo được mà không cần nhánh

    • Bối cảnh của chuyện đó là tài liệu hóa rối rắm của NVIDIA và các compiler cg/CUDA
      Ban đầu, có vẻ họ không muốn làm lập trình viên hoảng sợ nên đã che giấu mô hình thực thi và giải thích bằng trừu tượng “thread”; về sau, trong quảng bá GPU họ cũng tiếp tục dùng kiểu “có cực nhiều CUDA thread”
      Kết quả là trong lập trình GPU xuất hiện những mê tín kỳ lạ
      Thực tế, nhiều khi có nhánh trong mã lại là tốt, và bản thân nhánh thì nhanh
      Vấn đề là các lane SIMD không thể tự tách sang các nhánh khác nhau, nên compiler sẽ phát ra mã cho cả hai phía thay vì rẽ nhánh, rồi masking kết quả theo điều kiện
      Vì vậy các phép tính dựa trên giá trị đầu vào shader, đỉnh, chỉ số compute shader, v.v. không thực sự rẽ nhánh, mà được thực thi tuần tự bằng masking
      Trong ví dụ của TFA, cả hai giá trị ở hai phía của toán tử ? đều được tính, và câu điều kiện trên giá trị SIMD nói chung cũng như vậy
      Dù có thể xuất hiện nhánh tắt để nhanh chóng bỏ qua tính toán khi mọi lane đều có cùng giá trị, thông thường cả hai phía đúng/sai đều được tính
      Chỉ các câu điều kiện dựa trên thanh ghi scalar, tức hằng số shader hoặc giá trị uniform, mới tạo ra nhánh thực sự, và những nhánh như vậy rất nhanh
    • Trên CPU scalar cũng vậy
      Ví dụ, lệnh CMOV được đưa vào từ nhân P6 năm 1995
      Nhánh cũng đắt trên kiến trúc scalar, và compiler cố gắng phán đoán tối đa khi nào nên dùng chiến lược thay thế
      Đôi khi nó sai, nhưng không sai quá thường xuyên
    • Trên GPU thì nên nhìn theo hướng ngược lại
      Di chuyển có điều kiện là mặc định, còn nhánh thực sự chỉ là tối ưu hóa hiệu năng có thể dùng khi đó là nhánh uniform, tức toàn bộ workgroup đi cùng một hướng
    • Có thể nghĩ tới ví dụ này: a = f(z); b = g(z); v = x > y ? a : b;
      Nếu chi phí gọi f() và g() tương đối lớn, việc phát ra mã điều kiện hay tính cả hai rồi chọn là một bài toán đánh đổi
      Đây không phải một lựa chọn đơn giản, và quyết định là do compiler đưa ra
    • Sẽ khá thú vị nếu shader language có tính năng như vậy
      Có thể phân loại mọi hàm trong mã như tô màu thành có thể rẽ nhánh/không rẽ nhánh, và hàm được đánh dấu không rẽ nhánh sẽ yêu cầu if phải được biên dịch thành di chuyển có điều kiện, đồng thời chỉ được gọi các hàm không rẽ nhánh

  • Một phần đáng kể của mê tín “nhánh trên GPU chậm” là vì vào thời PlayStation 3 xa xưa, nó thực sự khá chậm
    PS3 dùng RSX GPU của NVIDIA; tôi nhớ tài liệu ghi nhánh mất 6 chu kỳ, nhưng đo đạc thực tế luôn cho kết quả chậm hơn thế
    Ngay cả với nhánh hoàn toàn coherent, nơi mọi thread trong warp đi cùng một đường, cũng như vậy; còn nhánh incoherent thì chậm hơn nữa vì lệnh IFEH mất 6 chu kỳ và GPU phải thực thi cả hai phía nhánh
    Tôi nghĩ mê tín “nhánh GPU chậm” kéo dài đến nay bắt nguồn từ đó
    Nhánh trên GPU ngày nay, đặc biệt là nhánh coherent, khá rẻ

    • Nếu ai đó chỉ nói “nhánh” chung chung, nên hiểu là họ đang nói tới nhánh incoherent
      Overhead của cơ chế rẽ nhánh ngày nay có thể đã thấp hơn, nhưng ràng buộc vật lý rằng thông lượng của hai phía nhánh giảm theo tỷ lệ thread đang hoạt động thì vẫn còn nguyên
      Nếu cả hai phía nhánh đều được thực thi và độ dài lệnh cũng bằng nhau, hiệu năng trung bình của hai phía sẽ giảm ít nhất một nửa
      Vì vậy niềm tin rằng nhánh trên GPU chậm vẫn tồn tại lâu dài, và thực tế cũng đúng
      Nếu có thể, đáng bỏ thêm công để tái cấu trúc bài toán theo hướng không cần nhánh
    • Nhánh coherent gần như “miễn phí”, nhưng các lệnh bổ sung làm tăng áp lực thanh ghi
      Lý do chính để tránh nhánh động không hẳn là bản thân nhánh vốn chậm, mà gần với điểm này hơn

  • Kiểu tối ưu hóa tránh rẽ nhánh này từng có thời hiệu quả
    Tôi từng profile trên Xbox 360 và GPU tích hợp Intel đời cũ, nhưng giờ thì không nên làm vậy nữa
    Trích xuất bit và các phép toán số nguyên khác cũng tương tự
    Trước đây mô phỏng bằng toán dấu phẩy động nhanh hơn, nhưng giờ mọi GPU đều có phép toán số nguyên nhanh

    • Tôi tò mò câu “giờ mọi GPU đều có phép toán số nguyên nhanh” đúng đến mức nào
      Ví dụ, nếu nhìn vào RDNA2 ISA, kiến trúc của PS5 và Xbox Series S|X, có vẻ như với số nguyên chỉ thấy các lệnh scalar 32-bit
      [0] https://www.amd.com/content/dam/amd/en/documents/radeon-tech...
    • Ít nhất trên các GPU “lớn” thì chuyện này không còn là vấn đề lớn như trước, nhưng bài này thật ra không nói về việc tránh rẽ nhánh nói chung
      Đoạn mã được đưa ra vốn đã là mã không rẽ nhánh
      Có vẻ những người đưa lời khuyên chỉ nhìn xem trong mã nguồn có cú pháp trông giống câu điều kiện hay không để phán đoán đó là mã rẽ nhánh, rồi nghĩ rằng họ đang né nó như một tối ưu hóa

  • Bài này cũng liên quan: https://medium.com/@jasonbooth_86226/branching-on-a-gpu-18bf...
    “Nếu hỏi Internet cách viết rẽ nhánh trên GPU, họ có thể nói như thể bạn đang mở cổng địa ngục để thả quỷ vào. Họ sẽ bảo phải tránh bằng mọi giá, và có thể né bằng các mẹo toán học kỳ quặc như toán tử ba ngôi hay step(). Phần lớn lời khuyên này, nói nhẹ thì đã lỗi thời, còn nhiều trường hợp thì đơn giản là sai. Hãy sửa lại cho đúng.”

  • Bộ xử lý thay đổi, trình biên dịch cũng thay đổi
    Nếu những chi tiết này quan trọng, cách tốt nhất là phân phối nhiều biến thể và chọn phiên bản nhanh nhất lúc chạy
    Như tôi từng nói vài lần trước đây, đã có trường hợp tôi loại bỏ assembly viết tay, thay bằng C bình thường hoặc mã tương tự, và làm nó nhanh hơn nhiều
    Đoạn assembly đó có thể đã nhanh hơn 10–20 năm trước, nhưng bây giờ tình hình đã khác

    • Tôi nghĩ việc xác định phiên bản shader nhanh nhất lúc chạy là rất khó
      Tôi không biết nhiều game hay engine thực sự làm như vậy
      Về nguyên tắc thì có thể làm được
      Hầu hết API như D3D, GL, Vulkan đều expose performance counter, và tuy độ tin cậy tùy vendor, bạn có thể tạo các cảnh test đại diện rồi phát lại nhiều lần để đo tối ưu hóa
      Nhưng nhiều game dùng cảnh được tạo động và shader được tạo động, nên số tổ hợp cần test có thể trở thành trở ngại
      Có khi còn phải bắt người dùng chờ đến khi benchmark kết thúc
      Nếu có phần cứng, bạn có thể đo trước trên nhiều thế hệ GPU của từng vendor và hard-code những quyết định quan trọng, nhưng tôi không rõ có hạ tầng sẵn có như vậy không
    • Thú vị là driver NVIDIA phần nào làm việc kiểu đó
      Nó chặn shader của game và thay bằng shader tùy chỉnh đã được NVIDIA tối ưu hóa
      Vì vậy trong changelog driver NVIDIA bạn thấy những câu như “tối ưu hóa game X, chạy nhanh hơn 40%”
    • Nếu chỉ thêm một shader nữa thì còn ổn, nhưng trong các API đồ họa “hiện đại”, đôi khi cùng một shader cần hàng nghìn hoán vị, và mỗi biến thể thêm vào lại làm con số đó tăng gấp đôi
      Bạn cũng không thể dành vô hạn thời gian cho từng shader
      Hãy profile trên phần cứng bạn quan tâm; nếu phương án đã chọn chậm hơn trên một bộ xử lý tương lai giả định nào đó thì đành chịu
      Hy vọng bộ xử lý đó đủ nhanh để vấn đề không đáng kể

  • Có vẻ những sai lầm và nhầm lẫn mà bài viết này muốn sửa đang lặp lại ngay ở đây
    Bài viết không khẳng định rẽ nhánh có điều kiện là miễn phí
    Theo tôi, đây cũng không phải là bài nói về chi phí hiệu năng của mã rẽ nhánh
    Ý chính của bài là logic điều kiện ở dạng được đưa ra không biên dịch thành mã rẽ nhánh có điều kiện
    Và không nên tiếp tục lan truyền lời khuyên có hại là cố che mọi biểu thức điều kiện nhìn thấy được
    Với mã rẽ nhánh thực sự, rõ ràng việc thực thi mã rẽ nhánh phức tạp hơn
    Không có rẽ nhánh miễn phí, và nếu tránh rẽ nhánh trong phạm vi hợp lý thì mã nào cũng có khả năng nhanh hơn
    May thay, mã gốc vốn đã là mã không rẽ nhánh
    Như mọi khi, không có thước đo phổ quát nào cho bạn biết một tối ưu hóa có đáng làm hay không
    [0] Ở đây “nhìn thấy được” là điểm quan trọng. Ý là các trường hợp không quan tâm đến mã được sinh ra, mà chỉ quan tâm mã nguồn có trông giống câu điều kiện hay không
    [1] Tất nhiên không phải là may mắn. Tôi đoán ai đó đã gửi cho IQ một đề xuất cải tiến shader trông có vẻ hiển nhiên nhưng lại sai

  • Vậy tại sao compiler không đủ thông minh để nhận ra phiên bản “đã tối ưu hóa” là cùng một đoạn mã?
    Chẳng phải nó nên hiểu step() và tối ưu riêng các trường hợp step() = 0.0, step() == 1.0 sao?
    Ít nhất cũng có thể loại bỏ một phép nhân, nên thông thường dù có bị đổi thành load/store có điều kiện hay thứ gì khác thì có vẻ lúc nào cũng có lợi

    • Thực tế có thể đúng như vậy
      Một số compiler hoàn toàn có khả năng thực hiện tối ưu hóa này trong một số trường hợp, nhưng rõ ràng cũng có thể viết một phiên bản mà compiler không hiểu được
    • Một vấn đề khác của tối ưu hóa là không được mất quá nhiều thời gian để thử mọi khả năng
      Phần lớn tối ưu hóa diễn ra ở phía driver, và các tác vụ mất quá lâu sẽ lộ ra dưới dạng khựng khi biên dịch shader
      Tôi không thể nói tối ưu hóa này hiện có thực sự diễn ra hay không, nhưng đó luôn là yếu tố phải cân nhắc

  • Lý do phiên bản “tối ưu hóa” đang bàn lại chậm hơn là vì hàm step() thực ra được triển khai kiểu như sau:
    float step( float x, float y ) { return x < y ? 1.0 : 0.0; }
    Làm sao biết một hàm OpenGL có gọi primitive của GPU hay chỉ được mô phỏng?

    • Cách duy nhất là như bài gốc: biên dịch shader, dịch ngược assembly, rồi đọc assembly đó
      Tôi đã thường làm như vậy với shader HLSL, và học được rất nhiều về tập lệnh ảo
      Chẳng hạn, khá thú vị là GPU có lệnh sincos, nhưng các hàm lượng giác ngược lại được mô phỏng trong quá trình biên dịch
    • Việc có cần biết hay không còn tùy mục đích
      Nếu hiệu năng quan trọng thì có thể cần biết
      Nhưng chỉ riêng việc step được triển khai như một hàm thư viện dựa trên điều kiện chứ không phải lệnh chuyên dụng cũng chưa nói được hiệu năng của nó so với lệnh chuyên dụng, nên không cần quá bám vào bản thân cách triển khai
      Nếu tò mò về kiến trúc GPU, hãy xem bản dịch ngược assembly, mã driver nguồn mở, LLVM và tài liệu ISA
    • Ngoài các hàm kiểu thường thấy trong assembly kiểu PC, tôi chưa từng thấy GPU có primitive đặc biệt nào
      Mỗi lần xem shader đã decompile, nhìn chung nó khá giống những gì ta nghĩ trong C
      Các đặc tả như OpenGL quy định hành vi của nhiều hàm tích hợp, còn phần triển khai thì dùng các lệnh assembly chuẩn để đáp ứng đặc tả đó
      Có thể tìm các trang online decompile sang nhiều kiến trúc khác nhau
    • Đây là một câu hỏi hay thường gặp trong lập trình nói chung, và cũng là lý do cốt lõi vì sao khi tối ưu hóa phải đo trước
      Thông thường ta không cần biết, cũng không cần quan tâm, hàm tích hợp được triển khai ra sao
      Nếu bạn đang quan tâm, có lẽ là vì đang nghĩ đến tối ưu hóa, và khi đó câu trả lời là “hãy đo để kiểm chứng cái nào tốt hơn”
    • Điểm tôi thấy lẫn lộn có lẽ là “rẽ nhánh” có một nghĩa được định nghĩa theo từng phần cứng rõ ràng hơn so với nghĩa tôi từng học khi lớn lên
      Theo nghĩa tôi đã học, câu điều kiện là rẽ nhánh
      Ở mức mã máy, luồng điều khiển được chọn lúc runtime, nên nhảy có điều kiện theo định nghĩa là rẽ nhánh
      Tôi nhìn việc dùng step() không phải là biến logic thành số học, mà chỉ là giấu logic bên trong một lời gọi hàm thư viện
      Việc step() là hàm tích hợp hay là một hàm xuất hiện trong bài báo toán học cũng không làm điều đó khác đi
      Trong toán học, định nghĩa của step() đúng nghĩa cũng là một câu điều kiện
      Nếu muốn tối ưu hóa đúng cách mà không dùng điều kiện, cần chọn một hàm liên tục gần giống kết quả mong muốn, rồi điều chỉnh tham số để khớp mục tiêu nhất có thể
      Thường là chọn một đa thức, chạy các phương pháp xấp xỉ lặp chuẩn, rồi tạo ra một f(x) không có nhánh, chỉ gồm phép cộng, phép nhân và các hằng số “cụ thể một cách kỳ lạ”
      Tôi không hiểu lắm đoạn tác giả khẳng định mạnh rằng conditional move không phải là “rẽ nhánh”
      Việc abs() không hạ xuống thành lệnh GPU mà thành modifier của lệnh và do đó miễn phí là nhờ biểu diễn bù 2 của số nguyên và biểu diễn số thực IEEE-754, cho phép coi bit dấu là bit cao nhất
      Vì vậy abs() chỉ cần luôn đặt bit cao nhất thành 0, hoặc che nó khi lệnh đọc
      Nhưng step(), hay toán tử ba ngôi tùy ý, và theo tôi biết cả lệnh conditional move, không phải là các trường hợp đặc biệt như vậy
      Những thứ cơ bản như abs(), sqrt() và các hàm lượng giác thì gần như là kiến thức chuẩn; còn những thứ khác thì dù sao cũng không chắc có quan trọng không
      step() chắc chắn phải có điều kiện ở đâu đó; dù tự làm, giao cho thư viện hay giao cho phần cứng, bản chất cơ bản của nó không thay đổi

  • Tôi từng mắc cái bẫy này
    Claude hay ChatGPT cũng thường đề xuất đây là một cách tối ưu hóa
    Nhưng mỗi lần đo thử thì hiệu năng đều giảm, đôi khi giảm khá mạnh

    • Điều này không lạ
      LLM chỉ lặp lại nội dung có trong kho ngữ liệu huấn luyện
      Nếu phần lớn Internet khuyến nghị những nội dung sai kiểu “tối ưu hóa” bằng conditional move như thế này, LLM cũng sẽ khuyến nghị như vậy
    • LLM lặp lại lời người trên Internet nói, mà con người thì thường sai