RNG แบบขนาน
ทฤษฎี: RNG หลายตัว
หากคุณต้องการใช้ตัวสร้างแบบสุ่มในเธรดทำงานหลายตัวพร้อมกัน คุณจะต้องใช้ RNG หลายตัว วิธีที่แนะนำมีดังนี้:
- ใช้
rng()ในแต่ละเธรดทำงาน ตัวสร้างนี้จะถูกซีดโดยอัตโนมัติ (แบบประเมินเมื่อต้องการ/lazy และได้ค่าซีดที่ไม่ซ้ำกัน) ในแต่ละเธรดที่ใช้งาน - ใช้
rng()(หรือ RNG หลักตัวอื่น) เพื่อซีด RNG ที่กำหนดเองในแต่ละ เธรดทำงาน ข้อดีหลักคือความยืดหยุ่นในการเลือก RNG ที่ใช้ - ใช้ RNG ที่กำหนดเองต่อ ชิ้นงานย่อย (work unit) ไม่ใช่ต่อ เธรดทำงาน (worker thread) หาก RNG เหล่านี้ ถูกซีดอย่างดีเทอร์มินิสติก ก็จะได้ผลลัพธ์ที่กำหนดได้เช่นกัน น่าเสียดายที่ การซีด RNG ใหม่สำหรับแต่ละชิ้นงานย่อยจากตัวสร้างหลักไม่สามารถทำแบบขนานได้ จึงอาจช้า
- ใช้ซีดหลักเพียงค่าเดียว สำหรับแต่ละชิ้นงานย่อย ให้ซีด RNG ด้วยซีดหลัก แล้วตั้งสตรีมของ RNG เป็นหมายเลขชิ้นงานย่อย วิธีนี้อาจเร็วกว่า (3) และยังคงกำหนดผลลัพธ์ได้ แต่ไม่ใช่ RNG ทุกตัวรองรับ
หมายเหตุ: อย่าแค่โคลน RNG ให้เธรดทำงานหรือชิ้นงานย่อย สำเนาจะให้ลำดับเอาต์พุตเดิมเหมือนต้นฉบับ อย่างไรก็ตาม คุณใช้สำเนาได้หากตั้งสตรีมที่ไม่ซ้ำกันให้แต่ละตัว
สายธาร
ตระกูล RNG ใดรองรับหลายสตรีม?
- ChaCha: RNG ตระกูล ChaCha รองรับซีด 256 บิต สตรีม 64 บิต และตัวนับ 64 บิต (ต่อบล็อก 16 คำ) จึงรองรับ 264 สตรีม สตรีมละ 268 คำ
- Hc128 เป็น RNG เชิงรหัสลับที่ รองรับซีด 256 บิต; เราอาจสร้างซีดนี้จาก (เช่น) คีย์ 192 บิตที่เล็กกว่า บวกกับสตรีม 64 บิตได้
โปรดทราบว่าวิธีสร้างซีดจากคีย์ที่เล็กกว่าบวกกับตัวนับสตรีมข้างต้น แนะนำได้เฉพาะกับ PRNG เชิงรหัสลับเท่านั้น เนื่องจาก RNG แบบง่ายมักมีสหสัมพันธ์ในเอาต์พุตเมื่อใช้คีย์สองค่าที่คล้ายกัน และอาจต้องใช้ซีดที่ “ดูสุ่ม” เพื่อให้ได้เอาต์พุตคุณภาพสูง
PRNG ที่ไม่ใช่เชิงรหัสลับอาจยังรองรับหลายสตรีมได้ แต่น่าจะมีข้อจำกัดที่สำคัญ (โดยเฉพาะอย่างยิ่ง เมื่อคำแนะนำทั่วไปของ PRNG เหล่านี้คือไม่ควรใช้เกินรากที่สองของคาบของตัวสร้าง)
-
Xoshiro: RNG ตระกูล Xoshiro รองรับเมธอด
jumpและlong_jumpซึ่งใช้แบ่งเอาต์พุตของ RNG เดียว ออกเป็นหลายสตรีมได้อย่างมีประสิทธิผล ในทางปฏิบัติสิ่งนี้มีประโยชน์เฉพาะ เมื่อมีสตรีมจำนวนน้อย เพราะต้องเรียกjumpจำนวนnครั้งเพื่อเลือกสตรีมที่ n -
Pcg: RNG เหล่านี้รองรับ การสร้างด้วยพารามิเตอร์
stateและstreamอย่างไรก็ตาม โปรดทราบว่า RNG เหล่านี้ถูกวิจารณ์ว่าหลายสตรีมที่ใช้คีย์เดียวกันมักมีสหสัมพันธ์กันอย่างมาก ดูความเห็นของผู้เขียน PCG เองRNG ตระกูล PCG ยังรองรับเมธอด
fn advance(delta)ซึ่งอาจใช้แบ่ง สตรีมเดียวออกเป็นหลายสตรีมย่อยได้เช่นเดียวกับjumpของ Xoshiro (แต่ดีกว่าเพราะระบุออฟเซตได้)
ภาคปฏิบัติ: แบบหลายเธรดที่ไม่กำหนดได้
เราใช้อิเทอเรเตอร์แบบขนาน (parallel iterators) ของ Rayon โดยใช้ map_init เพื่อเริ่มต้น RNG ในแต่ละเธรดทำงาน หมายเหตุ: RNG นี้อาจถูกใช้ซ้ำข้ามหลายชิ้นงานย่อย ซึ่งอาจถูกแบ่งระหว่างเธรดทำงานแบบไม่กำหนดได้
use rand::distr::{Distribution, Uniform};
use rayon::prelude::*;
static SAMPLES: u64 = 1_000_000;
fn main() {
let range = Uniform::new(-1.0f64, 1.0).unwrap();
let in_circle = (0..SAMPLES)
.into_par_iter()
.map_init(|| rand::rng(), |rng, _| {
let a = range.sample(rng);
let b = range.sample(rng);
if a * a + b * b <= 1.0 {
1
} else {
0
}
})
.reduce(|| 0usize, |a, b| a + b);
// prints something close to 3.14159...
println!(
"π is approximately {}",
4. * (in_circle as f64) / (SAMPLES as f64)
);
}
ภาคปฏิบัติ: แบบหลายเธรดที่กำหนดได้
เราใช้วิธี (4) ข้างต้นเพื่อให้ได้ผลลัพธ์ที่กำหนดได้: เริ่มต้น RNG ทั้งหมดจากซีดเดียว แต่ใช้หลายสตรีม
เราใช้ ChaCha8Rng::set_stream เพื่อทำเช่นนี้
โปรดทราบเพิ่มเติมว่าเราจัดกลุ่มชิ้นงานย่อยหลายหน่วยด้วยกันตาม BATCH_SIZE ด้วยมือ สิ่งนี้สำคัญเพราะค่าใช้จ่ายในการเริ่มต้น RNG สูงเมื่อเทียบกับค่าใช้จ่ายของชิ้นงานย่อยเรา (สร้างค่าสุ่มสองค่าบวกการคำนวณเล็กน้อย) การจัดกลุ่มด้วยมืออาจช่วยเพิ่มประสิทธิภาพของการจำลองแบบไม่กำหนดได้ข้างต้นด้วย
(หมายเหตุ: ตัวอย่างนี้อยู่ที่ https://github.com/rust-random/rand/blob/master/examples/rayon-monte-carlo.rs)
use rand::distr::{Distribution, Uniform};
use rand::{SeedableRng, rngs::ChaCha8Rng};
use rayon::prelude::*;
static SEED: u64 = 0;
static BATCH_SIZE: u64 = 10_000;
static BATCHES: u64 = 1000;
fn main() {
let range = Uniform::new(-1.0f64, 1.0).unwrap();
let in_circle = (0..BATCHES)
.into_par_iter()
.map(|i| {
let mut rng = ChaCha8Rng::seed_from_u64(SEED);
rng.set_stream(i);
let mut count = 0;
for _ in 0..BATCH_SIZE {
let a = range.sample(&mut rng);
let b = range.sample(&mut rng);
if a * a + b * b <= 1.0 {
count += 1;
}
}
count
})
.reduce(|| 0usize, |a, b| a + b);
// prints 3.1409052 (deterministic and reproducible result)
println!(
"π is approximately {}",
4. * (in_circle as f64) / ((BATCH_SIZE * BATCHES) as f64)
);
}