Как получить «случайное» число в OpenCL

Question

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

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

Я вижу, что есть функция шума? Есть ли простой способ использовать это, чтобы получить случайное число?

Answer 1

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

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

   // '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));
   

2. 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;
   

3. Просто сгенерируйте все на процессоре и передайте ядру в один большой буфер.

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

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

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

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

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

Answer 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);

Answer 3

В настоящее время я внедряю трассировщик путей в реальном времени.Возможно, вы уже знаете, что для отслеживания пути требуется много много случайных чисел.Перед генерацией случайных чисел на GPU я просто сгенерировал их на CPU (с помощью rand (), который отстой) и передал их в GPU.Это быстро стало узким местом.Теперь я генерирую случайные числа на графическом процессоре с помощью генератора псевдослучайных чисел Парк-Миллера (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 () только один раз перед первым выполнением ядра.После этого все генерации случайных чисел происходит на графическом процессоре.Я думаю, что также возможно просто использовать идентификатор ядра вместо инициализации массива с помощью rand ().

Answer 4

Кажется, OpenCL не предоставляет такой функциональности. Однако некоторые люди провели некоторое исследование по этому вопросу и предоставляют лицензионный код BSD для создания хороших случайных чисел на графическом процессоре.

Answer 5

Это моя версия псевдослучайного шума OpenCL с использованием тригонометрической функции

//noise values in range if 0.0 to 1.0
static float noise3D(float x, float y, float z) {
    float ptr = 0.0f;
    return fract(sin(x*112.9898f + y*179.233f + z*237.212f) * 43758.5453f, &ptr);
}

__kernel void fillRandom(float seed, __global float* buffer, int length) {
    int gi = get_global_id(0);
    float fgi = float(gi)/length;
    buffer[gi] = noise3D(fgi, 0.0f, seed);
}

Вы можете генерировать 1D или 2D шум, передавая noise3D нормализованные индексные координаты в качестве первых параметров и случайное начальное число (например, генерируемое на CPU) в качестве последнего параметра.

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

Answer 6

У меня была такая же проблема. www.thesalmons.org/john/random123/papers/random123sc11.pdf

Вы можете найти документацию здесь. http://www.thesalmons.org/john/random123/releases/latest/docs/index.html

Вы можете скачать библиотеку здесь: http://www.deshawresearch.com/resources_random123.html

Answer 7

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

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

Answer 8

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

Answer 9

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