1. No category

Números aleatorios
Clase 8, 4/5/2015
http://fsica.cab.cnea.gov.ar/gpgpu/index.php/en/icnpg/clases
Un tour sobre tres herramientas
C++ template library
(parallel) Random Numbers
Random123:
a Library of Counter-Based
Random Number Generators
GPU y CPU multicore
GPU y CPU multicore
CUFFT
Cual elegimos?
Generar números aleatorios en paralelo
"anyone who considers arithmetical methods of producing random
digits is, of course, in a state of sin"
John von Neumann
Generar números (pseudo)aleatorios en
paralelo
Muchos algoritmos que usan números aleatorios son muy paralelizables
El problema es que usualmente necesitamos muchísimos, y garantizar
que estos satisfagan ciertas condiciones … (batería de tests)
Calculando
usando números aleatorios
4 Azules/(Negros + Azules) → ?
Calculando usando números aleatorios
1
Versión Serial
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi = 0.25*Azules/Totales
0
1
¿ Que cuidados hay que tener con los RNs ?
¿ Versión Paralela ?
¿ Porque conviene ?
¿ Que cuidados hay que tener ?
4 Azules/(Negros + Azules) →
Calculando usando números aleatorios
¿Versión Paralela? → M tiradores tiran N dardos
¿Porque conviene?
→ Debería ser como si un solo tirador tirara NxM
¿Que cuidados hay que tener? → que los tiradores y sus tiros sean descorrelacionados.
Calculando usando números aleatorios
Semilla[0], Semilla[1], Semilla[2], Semilla[3], Semilla[4], Semilla[5]
Transformación
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[0] = 0.25*Azules/Totales
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[1] = 0.25*Azules/Totales
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[2] = 0.25*Azules/Totales
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[3] = 0.25*Azules/Totales
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[4] = 0.25*Azules/Totales
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[5] = 0.25*Azules/Totales
Reducción
Reducción: Pi = (Pi[0] + Pi[1] + Pi[2] + Pi[3] + Pi[4] + Pi[5])/6
Counter-based RNGs
Parallel Random Numbers: As Easy as 1, 2, 3
John K. Salmon, Mark A. Moraes, Ron O. Dror, David E. Shaw
“.. We demonstrate that independent, keyed transformations of counters produce a large
alternative class of PRNGs with excellent statistical properties... are ideally suited to modern multicore
CPUs, GPUs, clusters, and special-purpose hardware because they vectorize and parallelize well, and
require little or no memory for state. ... All our PRNGs pass rigorous statistical tests and produce at least
2^64 unique parallel streams of random numbers, each with period 2^128 or more.
In addition to essentially unlimited parallel scalability, our PRNGs offer excellent single-chip performance:
Philox is faster than the CURAND library on a single NVIDIA GPU.
http://www.thesalmons.org/john/random123/releases/1.06/docs/
[koltona@gpgpu-fisica examples]$ ls /share/apps/codigos/Random123-1.07/examples/
Cual elegimos?
Calculando usando números aleatorios
Semilla[0], Semilla[1], Semilla[2], Semilla[3], Semilla[4], Semilla[5]
Transformación
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[0] = 0.25*Azules/Totales
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[1] = 0.25*Azules/Totales
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[2] = 0.25*Azules/Totales
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[3] = 0.25*Azules/Totales
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[4] = 0.25*Azules/Totales
while(Totales < N)
{
x, y números random en [0,1]
Azules += ((x*x + y*y) < 1)
Totales ++;
}
Pi[5] = 0.25*Azules/Totales
Reducción
Reducción: Pi = Pi[0] + Pi[1] + Pi[2] + Pi[3] + Pi[4] + Pi[5]
Hands-on
"Hands-on" refers to human interaction, often with technology. It implies
active participation in a direct and practical way.
[koltona@gpgpu-fisica]$ cp -r
/share/apps/codigos/alumnos_icnpg2015/Simple_Pi .
[koltona@gpgpu-fisica]$ cd Simple_Pi/
[koltona@gpgpu-fisica Simple_Pi]$ ls
[koltona@gpgpu-fisica Simple_Pi]$ make
[koltona@gpgpu-fisica Simple_Pi]$ ls
¿ Que compila el make ?
Hands-on
Pi.cu
struct estimate_pi{
__device__
float operator()(unsigned int thread_id){
RNG philox; RNG::ctr_type c={{}}; RNG::key_type k={{}}; RNG::ctr_type r;
k[0]=thread_id;
float sum = 0;
unsigned int N = 10000; // muestras por thread
for(unsigned int i = 0; i < N; ++i){
c[0]=i;
r = philox(c, k);
Una “key” distinta
Para cada tirador
Un “counter” distinto
Para cada dardo del tirador
float x=(u01_closed_closed_32_53(r[0]));
float y=(u01_closed_closed_32_53(r[1]));
float dist = sqrtf(x*x + y*y); // distancia al origen
if(dist <= 1.0f)
sum += 1.0f;
}
sum *= 4.0f;
return sum / N;
}
};
Estimación de Pi del tirador
Tira el dardo
Hands-on
Pi.cu
struct estimate_pi{
__device__
float operator()(unsigned int thread_id){
RNG philox; RNG::ctr_type c={{}}; RNG::key_type k={{}}; RNG::ctr_type r;
k[0]=thread_id;
float sum = 0;
unsigned int N = 10000; // muestras por thread
for(unsigned int i = 0; i < N; ++i){
c[0]=i;
r = philox(c, k);
float x=(u01_closed_closed_32_53(r[0]));
float y=(u01_closed_closed_32_53(r[1]));
float dist = sqrtf(x*x + y*y); // distancia al origen
Una “key” distinta
Para cada tirador
Un “counter” distinto
Para cada dardo del tirador
Tira el dardo
if(dist <= 1.0f)
sum += 1.0f;
}
sum *= 4.0f;
return sum / N;
}
};
Estimación de Pi del tirador
Hands-on
struct estimate_pi{...}
using namespace thrust;
int main(void)
{
//uso 30K tiradores independientes, y cada uno tira 10K dardos
int M = 30000;
float estimate;
estimate = transform_reduce(
counting_iterator<int>(0),
counting_iterator<int>(M),
estimate_pi(),
0.0f,
thrust::plus<float>()
);
Pi.cu
Una secuencia (implícita)
de semillas 0,1,2,..., M-1
Qué se genera con cada semilla
Valor inicial y operación de reducción
estimate /= M; // 300K dardos tirados...(comparar tiempos con CPU)
std::cout << "pi es aproximadamente " << estimate << std::endl;
return 0;
}
Hands-on
[koltona@gpgpu-fisica Simple_Pi]$ cat submit_gpu.sh
[koltona@gpgpu-fisica Simple_Pi]$ qsub submit_gpu.sh
[koltona@gpgpu-fisica Simple_Pi]$ cat submit_cpu.sh
[koltona@gpgpu-fisica Simple_Pi]$ qsub submit_cpu.sh
¡Comparar resultados!
Calculando usando números aleatorios
Calculando usando números aleatorios
transform
N
N
CORES
reduce
semillas
semillas
N
Estimaciones de pi
+
DRAM
Estimaciones de Pi
k
CORES
k+1
DRAM
1
HRAM
Transform_reduce + implicit sequence
Adaptado de suma
de cuadrados de
1
k
CORES
k+1
DRAM
HRAM