Từ LCG đến PCG64DXSM: trạng thái, hoán vị và sinh số song song

1. Vì sao cần đi xa hơn LCG?

Trong bức tranh tổng quan về sinh số ngẫu nhiên, PCG thuộc nhánh PRNG tất định, tối ưu cho mô phỏng nhanh và có thể tái lập. Bài này phóng to riêng nhánh đó để theo dõi các quyết định thiết kế dẫn tới PCG64DXSM.

Trong bài Bộ sinh số giả ngẫu nhiên LCG, ta bắt đầu với hệ thức rất gọn:

LCG hấp dẫn vì nhanh, ít trạng thái và dễ nhảy tới một vị trí xa trong chuỗi. Nhưng nếu xuất thẳng $X_n$, ta cũng để lộ gần như nguyên vẹn cấu trúc tuyến tính đã sinh ra nó: các bit thấp có thể có chu kỳ ngắn, còn những bộ số liên tiếp tạo thành mạng lưới trong không gian nhiều chiều.

Một hướng khắc phục là thay hẳn cơ chế chuyển trạng thái bằng một thuật toán phức tạp hơn. Họ PCG (Permuted Congruential Generator) chọn một hướng tinh tế hơn: giữ lại phần đồng dư vốn rẻ và đã được hiểu rất rõ, nhưng không dùng trạng thái thô làm đầu ra.

Ý tưởng này dẫn từ LCG tới PCG, rồi tới hai bộ sinh 64 bit quen thuộc trong NumPy là PCG64 và PCG64DXSM:

Đây là một tuyến phát triển về ý tưởng thiết kế, không phải danh sách mọi thành viên của họ PCG. Chẳng hạn, PCG32 và PCG64 là hai cấu hình khác nhau của cùng một họ; PCG32 không phải một phiên bản cũ bắt buộc phải đi qua trước PCG64.

2. Bước ngoặt của PCG: chia công việc làm hai

Một bộ sinh PCG có hai bộ phận tách biệt:

Trong đó $s_n$ là trạng thái nội bộ, còn $r_n$ mới là số được trả cho người dùng. Hàm $\pi$ là một phép hoán vị bit: thường kết hợp XOR, dịch bit, nhân hoặc xoay bit để trộn thông tin từ nhiều phần của trạng thái.

Sự phân công khá đẹp:

• LCG chuyển trạng thái chịu trách nhiệm về chu kỳ, số luồng và khả năng nhảy nhanh tới một vị trí khác trong chuỗi.
• Hàm đầu ra che bớt cấu trúc tuyến tính của LCG và phân tán ảnh hưởng của từng bit trạng thái ra toàn bộ kết quả.

Theo bài báo PCG của Melissa O’Neill, chữ P trong PCG là permuted, còn CG là congruential generator. Một hàm đầu ra tốt không “sinh thêm ngẫu nhiên” và cũng không biến PCG thành bộ sinh an toàn mật mã; nó sắp xếp lại không gian đầu ra để các nhược điểm dễ thấy của trạng thái không đi thẳng tới người dùng.

Trực giác về hiệu ứng avalanche

Ta mong muốn một thay đổi nhỏ trong trạng thái — thậm chí chỉ lật một bit — có thể làm thay đổi nhiều bit ở đầu ra. Hiện tượng này thường được gọi là hiệu ứng avalanche. Nếu hàm đầu ra trộn chưa đủ mạnh, hai trạng thái có quan hệ đơn giản vẫn có thể tạo ra hai luồng đầu ra còn tương quan. Nếu hàm trộn tốt, quan hệ ấy khó sống sót qua lớp đầu ra.

3. PCG32: thành viên nhỏ và nổi tiếng

Một cấu hình PCG rất phổ biến là PCG-XSH-RR 64/32, thường được gọi ngắn là PCG32:

• trạng thái LCG rộng 64 bit;
• đầu ra rộng 32 bit;
• hàm đầu ra dùng xorshift và một phép xoay phụ thuộc trạng thái.

PCG32 cho thấy rõ triết lý “trạng thái đơn giản, đầu ra được hoán vị”. Nó nhỏ, nhanh và phù hợp với nhiều ứng dụng tổng quát. Tuy nhiên, khi một thư viện số học chạy chủ yếu trên máy 64 bit và cần trả trực tiếp số nguyên 64 bit, một cấu hình 128/64 tự nhiên hơn.

4. PCG64: đưa PCG vào NumPy hiện đại

numpy.random.PCG64 là cấu hình PCG XSL-RR 128/64:

• trạng thái chính rộng 128 bit;
• mỗi lần sinh trả về 64 bit;
• chu kỳ của từng luồng là $2^{128}$;
• một số cộng lẻ 128 bit xác định luồng, cho phép tới $2^{127}$ luồng khác nhau;
• có thể dùng advance() để nhảy một số bước tuỳ ý hoặc jumped() để tạo đoạn chuỗi cách xa.

Trạng thái công khai của PCG64 được biểu diễn bằng hai số nguyên 128 bit: một số là trạng thái LCG, số còn lại là hệ số cộng lẻ cố định của luồng. Seed do người dùng cung cấp không được chép thẳng vào hai số này; NumPy đưa nó qua SeedSequence để khuếch tán entropy vào toàn bộ trạng thái.

Hàm đầu ra XSL-RR XOR hai nửa của trạng thái rồi xoay kết quả theo một phần khác của trạng thái. Nó đủ nhanh và có chất lượng thống kê tốt trong sử dụng thông thường. Theo tài liệu NumPy hiện tại, np.random.default_rng() vẫn dùng PCG64 làm BitGenerator mặc định.

1
2
3
4
5

import numpy as np

rng = np.random.default_rng(20260803)  # Mặc định hiện tại: PCG64
u = rng.random(5)                      # 5 số trong [0, 1)
z = rng.standard_normal(5)             # 5 số chuẩn tắc

Lưu ý rằng Generator và BitGenerator làm hai việc khác nhau. PCG64 tạo ra các bit giả ngẫu nhiên; Generator biến luồng bit ấy thành phân phối đều, chuẩn, Poisson và nhiều phân phối khác.

5. Vấn đề chỉ xuất hiện ở quy mô song song cực lớn

PCG64 được tạo bởi một hàm chuyển trạng thái 128 bit và hàm đầu ra XSL-RR. Với một luồng chạy tuần tự, đây là một bộ sinh tốt. Vấn đề tinh tế xuất hiện khi ta tạo rất nhiều luồng được khởi tạo độc lập, rồi lấy lượng dữ liệu rất lớn từ từng luồng.

Các LCG có hệ số cộng khác nhau tạo ra những quỹ đạo khác nhau nhưng vẫn có quan hệ đại số. Nếu hai trạng thái tình cờ gần nhau ở đủ nhiều bit thấp, XSL-RR có thể chưa trộn mạnh đến mức xoá sạch quan hệ này. Khi ghép một cặp luồng không may như vậy, các kiểm định thống kê rất nghiêm ngặt có thể phát hiện tương quan.

Điều này cần được hiểu đúng mức độ. Hướng dẫn nâng cấp của NumPy phân biệt khá rõ:

Vì vậy, PCG64DXSM là một nâng cấp an toàn và chủ động, không phải lời tuyên bố rằng mọi kết quả từng sinh bằng PCG64 đều không đáng tin.

6. PCG64DXSM cải tiến điều gì?

PCG64DXSM vẫn giữ kiến trúc hai tầng của PCG nhưng thay đổi cả hai tầng ở mức triển khai:

1. Dùng hàm đầu ra DXSM mạnh hơn. Đây là một cấu trúc xorshift–multiply có hiệu ứng avalanche tốt hơn XSL-RR.
2. Dùng một “cheap multiplier” 64 bit trong bước chuyển LCG để bù lại chi phí của hàm đầu ra mạnh hơn.
3. Lấy đầu ra từ trạng thái trước khi cập nhật, thay vì cập nhật rồi mới xuất như PCG64.

Cấu hình cụ thể trong NumPy có tên PCG CM-DXSM 128/64. Nó vẫn có chu kỳ $2^{128}$, hỗ trợ $2^{127}$ luồng, advance() và jumped(). Điểm khác biệt cốt lõi không phải “thêm nhiều trạng thái hơn”, mà là dùng lớp đầu ra mạnh hơn để tách các luồng có quan hệ trong không gian trạng thái. Tài liệu NumPy mô tả PCG64DXSM là biến thể có tính chất thống kê tốt hơn trong bối cảnh song song.

DXSM tốn thêm phép trộn, nhưng tối ưu ở bước LCG bù lại phần lớn chi phí. Các phép đo của NumPy cho thấy PCG64DXSM có hiệu năng cùng cấp với PCG64 trên nền tảng 64 bit; lựa chọn cuối cùng vẫn phụ thuộc phần cứng và phân phối cần sinh.

7. Dùng PCG64DXSM trong NumPy

Khác với default_rng(seed), muốn chọn PCG64DXSM một cách rõ ràng, ta khởi tạo BitGenerator rồi bọc nó trong Generator:

1
2
3
4
5
6

from numpy.random import Generator, PCG64DXSM

rng = Generator(PCG64DXSM(20260803))

uniform_samples = rng.random(1_000)
normal_samples = rng.standard_normal(1_000)

Cùng seed và cùng lớp PCG64DXSM sẽ tái tạo cùng luồng số nguyên. Nhưng PCG64(42) và PCG64DXSM(42) không cho cùng chuỗi. Nếu một dự án cần tái lập bit-for-bit, tên bộ sinh phải được lưu cùng seed.

Sinh nhiều luồng đúng cách

Khi chạy song song, không nên tự đặt seed thành seed, seed + 1, seed + 2, v.v. Hãy để SeedSequence.spawn() tạo trạng thái con:

1
2
3
4
5
6
7
8

from numpy.random import Generator, PCG64DXSM, SeedSequence

root_seed = SeedSequence(20260803)
child_seeds = root_seed.spawn(4)
rngs = [Generator(PCG64DXSM(seed)) for seed in child_seeds]

# Mỗi worker dùng một Generator riêng
worker_samples = [rng.standard_normal(100_000) for rng in rngs]

Mẫu này tách trách nhiệm rõ ràng: SeedSequence phân phối entropy giữa các worker; PCG64DXSM sinh bit; Generator tạo phân phối cần dùng.

8. PCG64DXSM hay scrambled Sobol?

Hai công cụ này không thay thế nhau. Chúng trả lời hai câu hỏi khác nhau:

Nếu mô hình mô tả từng lần tung xúc xắc, từng khách hàng đến hệ thống hoặc từng cú sốc độc lập, PCG64DXSM phù hợp với giả thiết xác suất hơn. Nếu bài toán chủ yếu là lấy trung bình của một hàm trên hình hộp nhiều chiều, hãy cân nhắc scrambled Sobol.

Cả PCG64DXSM lẫn scrambled Sobol đều không phải CSPRNG. Không dùng chúng để tạo mật khẩu, token phiên, khoá hoặc nonce mật mã.

9. Tổng kết

Con đường từ LCG đến PCG64DXSM không phải là vứt bỏ công thức đồng dư, mà là phân công lại nhiệm vụ:

1. LCG cung cấp chuyển trạng thái nhanh, chu kỳ dài và khả năng nhảy.
2. PCG tách trạng thái khỏi đầu ra bằng một hàm hoán vị.
3. PCG64 mở rộng cấu hình lên trạng thái 128 bit và đầu ra 64 bit.
4. PCG64DXSM gia cố lớp đầu ra để các luồng song song được cách ly tốt hơn về mặt thống kê.

Đó là một bài học thiết kế đáng nhớ: một lõi toán học đơn giản không nhất thiết phải bị loại bỏ. Khi biết rõ lõi làm tốt việc gì và đặt đúng một lớp biến đổi ở đầu ra, ta có thể xây dựng một bộ sinh vừa nhanh, gọn, dễ tái lập, vừa phù hợp với các hệ thống tính toán hiện đại.