Generación de números pseudo aleatorios en la GPU

Question

Idea

Para un Trazado de aplicación que se necesita para generar una buena calidad de números pseudo-aleatorios en el intervalo cerrado [0~1]. Porque estoy haciendo esto en el GPU (HLSL Shader Model 5) sólo puedo usar 32 bits variables. Mi planteamiento inicial es la siguiente:

1. Siempre Marco el pixel shader recibir una buena pseudo random number ([0~1]) de la CPU, el uso de C++s' std::mt19937 generador y std::uniform_real_distribution.

2. Porque para cada píxel de este número es el mismo yo también uso las coordenadas de la pantalla u y v de cada píxel estos también se encuentran en [0~1].

3. Llamo al Multiplicar Con el método del Llevar, como el de abajo.

Algoritmo

// seed is the value given from the cpu
float3 random = Random(seed + u, seed + v)l

// Multiply With Carry, returns 3 floating point values {x, y, z}
// x: the random number
// y, z: new seeds for the next time we need a random number
float3 Random(float seed_a, float seed_b)
{   
    uint m_z = asuint(seed_a);
    uint m_w = asuint(seed_b);

    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);  

    float r = ((m_z << 16) + m_w) / (float)0xFFFFFFFF;
    return float3(r, asfloat(m_z), asfloat(m_w));
}

Esto produce la siguiente salida. (La parte de la izquierda es el número aleatorio obtenido a partir del método Aleatorio para este píxel, la parte derecha es la visualización de u y v como el Rojo y el Verde.

Resultado

Como usted puede ver, hay claramente un patrón, por lo que la aleatoriedad no es bueno en absoluto. Lo que perjudica el rendimiento de mi algoritmo enormemente. Esto es probablemente debido al hecho de que el original se Multiplica a Llevar método supone m_z y m_w son enteros de 64 bits, no de 32 bits.

Lo que quiero

Lo que estoy buscando es una solución a la implementación de mi Multiplicar con Llevar método de forma que se produce razonablemente bien los números pseudo-aleatorios y trabaja en el cerrado [0~1] el intervalo en lugar de el abierto [0~1] intervalo. Sin embargo, puesto que es muy posible que este método sólo puede trabajar a la derecha con 64 bits enteros estoy también estaría muy contento si alguien puede sugerir otro pseudo random number generator algoritmo que:

• Funciona con 32 bits de los números
• Produce uniformemente distribuida resultados en el cerrado [0~1] intervalo de
• No requiere demasiada información de estado, (por eso elegí el MwC ya que sólo necesita para almacenar 2 variables), ya que es difícil en la GPU. 16 de 32 bits variables sería el máximo creo que desde que la tienda que en la matriz de 4x4 que es fácil pasar de todo.

Answer 1

Me preguntó compañeros y que trajo a mi atención a este artículo: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch37.html

Ya que el papel es bastante largo y puede no estar en línea para siempre de abajo es la idea general:

Lineal de Congruencia de los Generadores son ideales para su uso en la GPU porque son simples y no requieren de mucho estado (sólo los generados anteriormente número). pero ellos no son "lo suficientemente aleatorios" para, por ejemplo, Monte Carlo basado en simulación. Un generador como una de Mersenne Twister sería mejor, pero requiere demasiado estado para ser almacenados.

La solución propuesta por el papel es la combinación de varias LCGs uso de una combinación de Tausworthe Generador (como el usado por el Mersenne Twister) esto garantiza una mejor aleatoriedad sin tener que almacenar tanto el estado como el Mersenne Twister. El final del algoritmo se parece a esto:

struct RandomResult
{
    uint4 state;
    float value;
};

uint TausStep(uint z, int S1, int S2, int S3, uint M)
{
    uint b = (((z << S1) ^ z) >> S2);
    return (((z & M) << S3) ^ b);    
}

uint LCGStep(uint z, uint A, uint C)
{
    return (A * z + C);    
}

RandomResult Random(uint4 state)
{
    state.x = TausStep(state.x, 13, 19, 12, 4294967294);
    state.y = TausStep(state.y, 2, 25, 4, 4294967288);
    state.z = TausStep(state.z, 3, 11, 17, 4294967280);
    state.w = LCGStep(state.w, 1664525, 1013904223);

    RandomResult result;
    result.state = state;
    result.value = 2.3283064365387e-10 * (state.x ^ state.y ^ state.z ^ state.w);

    return result;
}

Tenga en cuenta que el germen inicial de los valores de state debe ser mayor que 128! (Para obtener información de fondo reed el papel) y que debe llenar la semilla con 4 buenos números al azar de la CPU + cuatro valores únicos para ese píxel para obtener un buen resultado.

Answer 2

Hay un código de ruido Perlin en el siguiente sitio que produce un número entre -1 y +1 que he usado en el pasado. Estoy seguro de que podría cambiarse para producir 0 a 1. http://www.gamedev.net/page/resources/_/technical/game-programming/simple-clouds-part-1-r2085