Подтвердить что ты не робот

Как получить "случайный" номер в OpenCL

Я хочу получить случайное число в OpenCL. Он не обязательно должен быть случайным или даже случайным. Просто что-то простое и быстрое.

Я вижу, что в OpenCL существует тонна случайных алгоритмов случайных алгоритмов случайных распараллелированных случайных случайностей, которые похожи на тысячи и тысячи строк. Мне не нужно ничего подобного. Простой "random()" был бы хорош, даже если в нем легко увидеть шаблоны.

Я вижу, что есть функция Noise? Любой простой способ использовать это для получения случайного числа?

4b9b3361

ОТВЕТЫ

Ответ 1

Я решал эту "случайную" проблему за последние несколько дней, и я придумал три разных подхода:

  • Xorshift - Я создал генератор на основе этого. Все, что вам нужно сделать, это предоставить один uint2 номер (семя) для всего ядра, и каждый рабочий элемент будет вычислять свой собственный номер rand

    // 'randoms' is uint2 passed to kernel
uint seed = randoms.x + globalID;
uint t = seed ^ (seed << 11);  
uint result = randoms.y ^ (randoms.y >> 19) ^ (t ^ (t >> 8));

  • Java random - я использовал код из метода .next(int bits) для генерации случайного числа. На этот раз вы должны указать один ulong номер в качестве семени.

    // 'randoms' is ulong passed to kernel
ulong seed = randoms + globalID;
seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
uint result = seed >> 16;

  • Просто сгенерируйте все на CPU и передайте его в ядро ​​в одном большом буфере.

Я тестировал все три подхода (генераторы) в своем эволюционном алгоритме, вычисляющем минимальный доминантный набор в графах.

Мне нравятся сгенерированные числа из первого, но похоже, что мой алгоритм эволюции этого не делает.

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

Но третий подход показывает, что абсолютно точно просто предоставить все номера из хоста (CPU). Во-первых, хотя в генерации (в моем случае) 1536 номеров int32 и передачи их на GPU в каждом вызове ядра было бы слишком дорого (для вычисления и передачи на GPU). Но, оказывается, это так же быстро, как и мои предыдущие попытки. И загрузка процессора остается ниже 5%.

Кстати, я также пробовал MWC64X Random, но после установки нового драйвера графического процессора функция mul_hi начинает вызывать сбои сборки (даже если весь AMD Kernel Analyzer разбился).

Ответ 2

приведен алгоритм, используемый классом java.util.Random в соответствии с doc:

(seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

См. документацию по ее различным реализациям. Передача идентификатора рабочего места для семени и цикл за несколько раз должна приводить к созданию случайной случайности

или другой метод должен состоять в том, чтобы иметь некоторые случайные операции, которые являются довольно цератными для переполнения:

 long rand= yid*xid*as_float(xid-yid*xid);
 rand*=rand<<32^rand<<16|rand;
 rand*=rand+as_double(rand);

с xid=get_global_id(0); и yid= get_global_id(1);

Ответ 3

В настоящее время я реализую трассировщик пути в реальном времени. Возможно, вы уже знаете, что Path Tracing требует много много случайных чисел.
Прежде чем генерировать случайные числа на графическом процессоре, я просто сгенерировал их на CPU (используя rand(), который отсасывает) и передал их на GPU.
Это быстро стало узким местом.
Теперь я генерирую случайные числа на графическом процессоре с помощью генератора псевдослучайных чисел Park-Miller (PRNG).
Это очень просто реализовать и добиться очень хороших результатов.
Я взял тысячи образцов (в диапазоне от 0.0 до 1.0) и усреднил их вместе.
Результирующее значение было очень близко к 0,5 (что и следовало ожидать). Между различными прогонами расхождение от 0,5 составляло около 0,002. Поэтому он имеет очень равномерное распределение.


Вот документ, описывающий алгоритм:
http://www.cems.uwe.ac.uk/~irjohnso/coursenotes/ufeen8-15-m/p1192-parkmiller.pdf
И вот статья об этом алгоритме, оптимизированном для CUDA (который легко переносится на OpenCL): http://www0.cs.ucl.ac.uk/staff/ucacbbl/ftp/papers/langdon_2009_CIGPU.pdf


Вот пример того, как я его использую: 

int rand(int* seed) // 1 <= *seed < m
{
    int const a = 16807; //ie 7**5
    int const m = 2147483647; //ie 2**31-1

    *seed = (long(*seed * a))%m;
    return(*seed);
}

kernel random_number_kernel(global int* seed_memory)
{
    int global_id = get_global_id(1) * get_global_size(0) + get_global_id(0); // Get the global id in 1D.

    // Since the Park-Miller PRNG generates a SEQUENCE of random numbers
    // we have to keep track of the previous random number, because the next
    // random number will be generated using the previous one.
    int seed = seed_memory[global_id];

    int random_number = rand(&seed); // Generate the next random number in the sequence.

    seed_memory[global_id] = *seed; // Save the seed for the next time this kernel gets enqueued.
}

Код служит в качестве примера. Я не тестировал его.
Массив "seed_memory" заполняется rand() только один раз перед первым исполнением ядра. После этого на GPU происходит генерация всех случайных чисел. Я думаю, что также можно просто использовать идентификатор ядра вместо инициализации массива с помощью rand().

Ответ 6

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

Ответ 7

У графических процессоров нет хороших источников случайности, но это можно легко преодолеть, посеяв ядро ​​случайным семенем от хоста. После этого вам нужен только алгоритм, который может работать с большим количеством параллельных потоков.

Эта ссылка описывает реализацию Mersenne Twister с использованием OpenCL: Parallel Mersenne Twister. Вы также можете найти реализацию в SDK NVIDIA.

Ответ 9

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