LINUX.ORG.RU

[C] [OpenMP]Параллельный генератор псевдослучайных чисел

 ,


0

2

Есть такая задача... нужно сосчитать кое-для чего интеграл монте-карло. Как подсчитывать - тут всё понятно... никаких вопросов нет. Более того, написал готовую программу - всё работает.

Один нюанс. Для неё нужны псевдослучайные числа. Чтобы получать псевдослучайные числа, воспользовался библиотекой GSL, функцией gsl_rng_uniform_int, если точнее.

И всё замечательно считается... но! Подсчёт интегральной суммы несложно распараллелить. А вот как сгенерировать параллельно (на нескольких нитях) случайные числа? Если просто вызывать функцию gsl - то так не проходит =) облом. ибо, я так понял, результат следующего вызова этой функции зависит от предыдущего.

Правильно ли я понял, что для этого придётся как-то самому этот алгоритм реализовывать? %)

Просто так уж и получается... что значительная часть времени тратится на генерацию случайных чисел, чем на подсчёт суммы (при большем количестве потоков). Узкое место.

ещё можно тупо форкнуться n-е кол-во раз. Но у всех потоков будут одни и те же «случайные» числа.

true_admin ★★★★★
()
Ответ на: комментарий от true_admin

«и так» - это как? :) оно работает. но медленно... ну как медленно. вот 600 миллисекунд уходит на генерацию псевдослучайных чисел, примерно 40 миллисекунд на суммирование. соответственно, если суммирование распараллелить - то ещё меньше.

То есть тупо взять вместо случайных чисел какие-нить 1,2,3,4,5,6? сомневаюсь, что этот фокус пройдёт. %( это не то немного...

BattleCoder ★★★★★
() автор топика
Ответ на: комментарий от Obey-Kun

Читай комменты там. Решение не всегда будет работать:

Jim Dempsey

For most implementations, the default rand() does not use thread local storage (for seed/last value) but rather does use a single seed and a critical section. Random numbers are repeatably returned in order of call (regardless of thread number)

For your suggestion to work, the programmer must write their own rand() function (not a big problem).

Тогда смотри в сторону rand_r или Boost.Random.

Obey-Kun ★★★★★
()
Ответ на: комментарий от Obey-Kun

вообще не доверяю я этому rand()

он не идеально равномерное распределение даёт. %( Хотя наверное и близкое к нему.

BattleCoder ★★★★★
() автор топика
Ответ на: комментарий от Obey-Kun

boost... я, кстати, думал его использовать. потом почему-то передумал... может, зря.. надо бы на него ещё разок глянуть.

BattleCoder ★★★★★
() автор топика
Ответ на: комментарий от Obey-Kun

Matthew Wolf

I agree completely with Jim's comment. However, most of the time the rand() family of functions will also have a rand_r( int *seed) that is reentrant & thread-safe, so you don't have to build your own rand(). (Same thing goes for drand48_r, etc.) You have to provide the thread-local storage for the seed, which is why you are passing a pointer into the function.

Obey-Kun ★★★★★
()
Ответ на: комментарий от BattleCoder

> он не идеально равномерное распределение даёт. %( Хотя наверное и близкое к нему.

Эм, а разве реализация rand рассмотрена в стандарте? Там может использоваться любой алгоритм генерации псевдослучайных чисел, а какой именно — выбирать тем, кто пишет реализацию libc.

Obey-Kun ★★★★★
()
Ответ на: комментарий от Obey-Kun

вот... может быть... этим и займусь. возможно.

пока на потом отложу... вроде и так работает. интегрирование само хорошо параллелится.

а псевдослучайные числа на потом отложу.

как вариант - один раз сгенерировать. и потом одни и те же числа использовать. в принципе, для данной задачи, думаю, вполне сойдёт.

посмотрим.

А вместо rand() я использовал gsl_rng_uniform из GSL-библиотеки.

BattleCoder ★★★★★
() автор топика
Ответ на: комментарий от BattleCoder

Ты главное seed разный на потоки дай, как в том решении предлагают. И не забудь к релизу исправить, ибо на некоторых реализациях стандартной библиотеки оно может тупо не заработать как надо.

как вариант - один раз сгенерировать. и потом одни и те же числа использовать. в принципе, для данной задачи, думаю, вполне сойдёт.

Интересная мысль

Obey-Kun ★★★★★
()
Ответ на: комментарий от Obey-Kun

А, ну gsl_rng_uniform-то везде одинаковый, так что работает и ладно.

Obey-Kun ★★★★★
()
Ответ на: комментарий от Obey-Kun

да... выбирать разработчикам libc =)

в моём случае алгоритм генерации могу выбрать я сам (из предложенных) или даже более того, во время выполнения программы можно выбирать.

или и вовсе свой написать... как вариант.

BattleCoder ★★★★★
() автор топика
Ответ на: комментарий от BattleCoder

Да свой напиши, делов-то. Алсо, для Монте-Карло можно носить готовый список чисел или генерировать их при инициализации программы.

Obey-Kun ★★★★★
()

А почему не инициализировать кучу генераторов (по одному на нить)? Нити надеюсь только один раз вначале создаются?

abalakin ★★
()
Ответ на: комментарий от abalakin

а будет ли тогда целиком весь набор равномерно распределён? а так можно, конечно...

вообще можно попробовать... и сравнить результат. что там будет.

BattleCoder ★★★★★
() автор топика
Ответ на: комментарий от BattleCoder

> а будет ли тогда целиком весь набор равномерно распределён? а так можно, конечно...

По идее да. Если конечно каждый генератор инициализировать случайным числом (например, число миллисекунд + 10*номер нити)

abalakin ★★
()

Можно так: один поток генерирует случайные числа, все остальные обсчитывают функцию от сгенерированных чисел. Выигрыш будет лишь если функция существенно сложнее, чем процедура генерации случайных чисел.

anonymous
()
Ответ на: комментарий от BattleCoder

как вариант gettimeofday(), но лучше погугли, где-то была хорошая статья на эту тему.

true_admin ★★★★★
()
Ответ на: комментарий от BattleCoder

> Кстати. как проще всего получить число миллисекунд?

omp_get_wtime() перед блоком и после, использовать разницу двух значений.

Для быстрого получения большого количества псевдослучайных чисел хорошего качества можно попробовать libDSFMT.

oami ★★
()
Ответ на: комментарий от Yareg

ну тут разницы особой нет... откуда именно заполнять.

а вариант да, хороший, и вполне подходящий. - один раз сгенерировать необходимое число случайных векторов и радоваться...

BattleCoder ★★★★★
() автор топика

Вольми любой понравившийся генератор и используй его инстанс в каждом потоке. Сидируй в том числе thread id'ом.

slovazap ★★★★★
()

А разные генераторы для разных потоков не пробовали задавать? gsl_rng_uniform_int, вроде как принимает на вход некий дескриптор - он должен быть различным для разных потоков, неужели их выход кореллирует между собой?

gandjubas
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.