Vraag Hoe een "willekeurig" nummer in OpenCL te krijgen


Ik ben op zoek naar een willekeurig nummer in OpenCL. Het hoeft niet echt willekeurig te zijn of zelfs maar willekeurig. Gewoon iets eenvoudigs en snel.

Ik zie dat er een hoop echte willekeurige geparametriseerde fancy-pants willekeurige algoritmen in OpenCL zijn die lijken op duizend en duizenden lijnen. Ik heb Niets dergelijks nodig. Een eenvoudige 'random ()' zou prima zijn, zelfs als het gemakkelijk is om patronen erin te zien.

Ik zie dat er een ruisfunctie is? Elke gemakkelijke manier om dat te gebruiken om een ​​willekeurig nummer te krijgen?


30
2018-03-28 16:49


oorsprong


antwoorden:


Ik loste deze "geen willekeurige" kwestie op voor de laatste paar dagen en ik bedacht drie verschillende benaderingen:

  1. Xorshift - Ik heb op basis hiervan een generator gemaakt. Het enige wat u hoeft te doen is er een te verstrekken uint2 nummer (seed) voor de gehele kernel en elk werkitem zal zijn eigen randnummer berekenen

    // '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 willekeurig - Ik gebruikte code van .next(int bits) methode om willekeurig nummer te genereren. Deze keer moet je er een opgeven ulong nummer als zaad.

    // 'randoms' is ulong passed to kernel
    ulong seed = randoms + globalID;
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    uint result = seed >> 16;
    
  3. Genereer alles op de CPU en geef het door aan de kernel in één grote buffer.

Ik heb alle drie de benaderingen (generatoren) getest in mijn evolutie-algoritme voor het berekenen van Minimale dominante set in grafieken.

Ik hou van de gegenereerde nummers van de eerste, maar het lijkt erop dat mijn evolutie-algoritme dat niet doet.

De tweede generator genereert getallen die een zichtbaar patroon hebben, maar mijn evolutiealgoritme vindt het op die manier sowieso leuk en het hele ding loopt iets sneller dan met de eerste generator.

Maar de derde benadering laat zien dat het absoluut prima is om alleen alle nummers van host (cpu) aan te leveren. Ten eerste vond ik dat het genereren van (in mijn geval) 1536 int32-nummers en doorgeven aan GPU in elk kernel-gesprek te duur zou zijn (om te berekenen en over te zetten naar GPU). Maar het blijkt dat het net zo snel is als mijn vorige pogingen. En CPU-belasting blijft onder de 5%.

Trouwens, ik heb het ook geprobeerd MWC64X willekeurig maar nadat ik een nieuwe GPU-driver heb geïnstalleerd, de functie mul_hi start met build fail (zelfs hele AMD Kernel Analyer is gecrasht).


15
2018-04-21 10:16



het volgende is het algoritme dat wordt gebruikt door de java.util.Random klasse volgens de dokter:

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

Raadpleeg de documentatie voor de verschillende implementaties. De id van de werknemer doorgeven voor het zaad en een paar keer herhalen, zou een behoorlijke willekeur moeten produceren

of een andere metode zou zijn om een ​​aantal willekeurige operaties te laten plaatsvinden die tamelijk vaak overlopen:

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

met xid=get_global_id(0); en yid= get_global_id(1);


11
2018-01-03 23:49



Ik implementeer momenteel een Realtime Path Tracer. Je weet misschien al dat padtracering veel veel willekeurige getallen vereist.
Voordat ik willekeurige getallen op de GPU genereerde, genereerde ik ze eenvoudig op de CPU (met behulp van rand (), die sucks) en gaf ze door aan de GPU.
Dat werd al snel een knelpunt.
Nu genereer ik de willekeurige nummers op de GPU met de Park-Miller Pseudorandom Number Generator (PRNG).
Het is uiterst eenvoudig te implementeren en behaalt zeer goede resultaten.
Ik nam duizenden monsters (in het bereik van 0,0 tot 1,0) en matigde ze samen.
De resulterende waarde was bijna 0,5 (wat je zou verwachten). Tussen verschillende runs was de afwijking van 0,5 ongeveer 0,002. Daarom heeft het een zeer uniforme verdeling.

Hier is een paper die het algoritme beschrijft:
http://www.cems.uwe.ac.uk/~irjohnso/coursenotes/ufeen8-15-m/p1192-parkmiller.pdf
En hier is een artikel over het bovenstaande algoritme dat is geoptimaliseerd voor CUDA (dat gemakkelijk kan worden geporteerd naar OpenCL): http://www0.cs.ucl.ac.uk/staff/ucacbbl/ftp/papers/langdon_2009_CIGPU.pdf

Hier is een voorbeeld van hoe ik het gebruik:

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.
}

De code dient slechts als een voorbeeld. Ik heb het niet getest.
De array "seed_memory" wordt maar één keer gevuld met rand () vóór de eerste uitvoering van de kernel. Daarna gebeurt het genereren van willekeurige nummers op de GPU. Ik denk dat het ook mogelijk is om gewoon de kernel-ID te gebruiken in plaats van de array te initialiseren met rand ().


9
2018-02-27 09:07



het sluiten van de lus op een AMD devgurus-discussie [link died] en Aankondiging:

https://github.com/clMathLibraries/clRNG


4
2018-05-08 03:27



Het lijkt erop dat OpenCL niet zo'n functionaliteit biedt. Echter, sommige mensen hebben wat onderzoek gedaan daarop en verstrek BSD-licentiecode voor het produceren van goede willekeurige nummers op GPU.


3
2018-05-30 13:14



GPU heeft geen goede bronnen van willekeur, maar dit kan gemakkelijk worden verholpen door een kernel te zaaien met een willekeurig zaadje van de host. Daarna hebt u alleen een algoritme nodig dat met een groot aantal gelijktijdige threads kan werken.

Deze link beschrijft een Mersenne Twister-implementatie met OpenCL: Parallel Mersenne Twister. U kunt ook een implementatie vinden in de NVIDIA SDK.


1
2018-03-30 08:16



Ik had hetzelfde probleem. www.thesalmons.org/john/random123/papers/random123sc11.pdf

U kunt de documentatie hier vinden. http://www.thesalmons.org/john/random123/releases/latest/docs/index.html

U kunt de bibliotheek hier downloaden: http://www.deshawresearch.com/resources_random123.html


1
2018-04-02 03:53