Generator nomor pseudorandom paralel

Pertanyaan ini terutama terkait dengan masalah rekayasa-perangkat lunak praktis, tetapi saya ingin tahu jika para ahli teori dapat memberikan wawasan lebih dalam.

Sederhananya, saya memiliki simulasi Monte Carlo yang menggunakan generator nomor pseudorandom, dan saya ingin memparalelkannya sehingga ada 1000 komputer yang menjalankan simulasi yang sama secara paralel. Karena itu saya perlu 1000 aliran angka pseudorandom independen.

Bisakah kita memiliki 1000 stream paralel dengan properti berikut? Di sini harus menjadi PRNG yang sangat terkenal dan dipelajari secara luas dengan semua jenis sifat teoritis dan empiris yang bagus.$X$

1. Streaming terbukti sebaik apa yang akan saya dapatkan jika saya hanya menggunakan dan membagi aliran yang dihasilkan oleh X menjadi 1000 stream.$X$$X$

2. Menghasilkan nomor berikutnya dalam aliran apapun (hampir) secepat menghasilkan nomor berikutnya dengan .$X$

Jika tidak, bisakah kita mendapatkan beberapa aliran independen "gratis"?

Tentu saja jika kita hanya menggunakan , selalu membuang angka 999 dan memilih 1, maka kita pasti akan memiliki properti 1, tetapi kita akan kalah dalam waktu berjalan dengan faktor 1000.$X$

Gagasan sederhana akan menggunakan 1000 salinan , dengan biji 1, 2, ..., 1000. Ini tentu akan cepat, tetapi tidak jelas apakah aliran memiliki sifat statistik yang baik.$X$

Setelah beberapa Googling, saya telah menemukan, misalnya, yang berikut:

• The SPRNG perpustakaan tampaknya dirancang untuk persis tujuan ini, dan mendukung beberapa PRNGs .

• Twister Mersenne tampaknya menjadi PRNG yang populer saat ini, dan saya menemukan beberapa referensi untuk varian yang mampu menghasilkan beberapa aliran secara paralel.

Tetapi semua ini sangat jauh dari bidang penelitian saya sendiri, sehingga saya tidak dapat menemukan apa yang benar-benar canggih, dan konstruksi mana yang bekerja dengan baik tidak hanya dalam teori tetapi juga dalam praktiknya.

Beberapa klarifikasi: Saya tidak memerlukan segala jenis properti kriptografi; ini untuk perhitungan ilmiah. Saya akan membutuhkan miliaran angka acak, sehingga kita bisa melupakan generator apa pun dengan periode .$< 2^{32}$

Sunting: Saya tidak dapat menggunakan RNG sejati; Saya membutuhkan PRNG deterministik. Pertama, ini sangat membantu dengan debugging dan membuat semuanya berulang. Kedua, ini memungkinkan saya untuk melakukan, misalnya, mencari median sangat efisien dengan mengeksploitasi fakta bahwa saya dapat menggunakan model multi-pass (lihat pertanyaan ini ).

Sunting 2: Ada pertanyaan terkait erat @ StackOverflow: Pseudo-random number generator untuk lingkungan cluster .

Anda dapat menggunakan evolusi dari algoritma Mersenne Twister yang dikembangkan oleh Saito dan Matsumoto:

Fast Mersenne Twister (SFMT) yang berorientasi SIMD

SFMT adalah generator Linear Feedbacked Shift Register (LFSR) yang menghasilkan integer pseudorandom 128-bit pada satu langkah. SFMT dirancang dengan paralelisme terbaru dari CPU modern, seperti multi-stage pipelining dan instruksi SIMD (mis. 128-bit integer). Ini mendukung bilangan bulat 32-bit dan 64-bit, serta floating point presisi ganda sebagai output. SFMT jauh lebih cepat daripada MT, di sebagian besar platform. Tidak hanya kecepatan, tetapi juga dimensi kesetaraan pada presisi v-bit ditingkatkan. Selain itu, pemulihan dari kondisi awal 0-kelebihan jauh lebih cepat. Lihat Tesis Guru tentang Mutsuo Saito untuk detailnya .

Periode bervariasi dari hingga 2 216091 - 1 .$2^{607}-1$$2^{216091}-1$

Menggunakan satu generator nomor acak yang sama untuk menghasilkan beberapa aliran independen dengan mengubah nilai awal dapat menyebabkan masalah (dengan probabilitas sangat kecil). Untuk menghindari masalah, lebih baik menggunakan parameter yang berbeda untuk setiap generasi. Teknik ini disebut pembuatan dinamis dari parameter MT.

Dalam kode sumber SFMT Anda dapat menemukan beberapa contoh set parameter (periode variabel) dan skrip awk untuk mengonversi file CSV ke set parameter yang dapat dikompilasi. Ada juga alat yang disebut " Penciptaan Dinamis generator Mersenne Twister ".

Para penulis baru-baru ini mengembangkan versi modifikasi lain dari Mersenne Twister - Mersenne Twister untuk Prosesor Grafis - yang dirancang untuk berjalan dalam GPU dan memanfaatkan untaian eksekusi paralel asli mereka. Fitur utamanya adalah kecepatan: bilangan bulat acak setiap 4,6 ms pada GeForce GTX 260.$5 \times 10^7$

Periode urutan yang dihasilkan adalah , 2 23209 - 1 dan 2 44497 - 1 untuk versi 32-bit, dan 2 23209 - 1 , 2 44497 - 1 , 2 110503 - 1 untuk versi 64-bit. Ini mendukung 128 set parameter untuk setiap periode, dengan kata lain, dapat menghasilkan 128 urutan nomor pseudorandom independen untuk setiap periode. Kami telah mengembangkan Pencipta Dinamis untuk MTGP, yang menghasilkan lebih banyak set parameter$2^{11213}-1$$2^{23209}-1$$2^{44497}-1$$2^{23209}-1$$2^{44497}-1$$2^{110503}-1$

Memang mereka menyediakan alat MTGPDC untuk membuat hingga set parameter (yaitu aliran independen).$2^{32}$

Algoritma melewati tes keacakan utama seperti Diehard dan NIST.

Makalah pendahuluan juga tersedia di arXiv: Varian Mersenne Twister yang Cocok untuk Prosesor Grafis

$x_{i+1} = x_i^2 \mbox{ mod }N$$N$$x_i$$x_{i+k} = x_i^{2^k}\mbox{ mod }N = x_i^{2^k \mbox{ mod } \lambda(N)}\mbox{mod }N$$k$$O(\log(N)^3)$$M$$y$$x_{i+1,y} = x_i^{2^M \mbox{mod }\lambda(N)}\mbox{ mod }N$$x_{0,y} = x_0^{2^y \mbox{ mod }\lambda(N)}\mbox{ mod }N$$x_0$

$M$$N$$2^M \mbox{ mod }\lambda(N)$

$s$$n$$X$$1000n$$s_1,s_2,\ldots,s_{1000}$$1\le i \le 1000$$s_i$$n$

$X$

$s_i$$i$$X$

$X$$s$$1 \le i < j \le 1000$$s_i$$s_j$$s$

$f$$M = 1000$$\{ 0, 1, \ldots, M - 1 \}$$j$$i$$f(i + jM)$$M$

Ini akan memberi Anda RNG kriptografi pada setiap proses, tetapi itu tidak harus datang dengan biaya kinerja. AES cepat jika Anda memiliki perangkat keras yang mendukungnya, dan ChaCha cepat terlepas. Tentu saja, Anda ingin mengukur ini di pengaturan spesifik Anda untuk memastikan.

$f$

Sekarang ada fungsi lompatan untuk SFMT (implementasi Mersenne Twister yang cepat).

Ini memungkinkan saya untuk menginisialisasi 1000 MTs sehingga tidak ada siklus yang tumpang tindih. Dan SFMT harus lebih cepat dari MTGP. Hampir sempurna untuk tujuan saya.

Anda bisa menggunakan 1000 instance dari Mersenne Twister yang diinisialisasi dengan biji yang berbeda.

Anda dapat mencicipi benih dari Mersenne Twister lain, atau, untuk memastikan independensi mereka, dari OS pseudorandom number generator OS (/ dev / urandom di Linux).

Mersenne Twister selalu beroperasi pada urutan siklik yang sama, seed mengontrol di mana Anda mulai membuatnya. Dengan benih yang diambil secara terpisah, masing-masing generator akan mulai pada titik yang berbeda, biasanya sangat jauh, dengan kemungkinan persimpangan yang sangat kecil.