Download Algoritmos paralelos básicos

Algoritmos paralelos básicos
Algoritmos paralelos
Glen Rodríguez
Integración

Se desea calcular la integral de la función f(x) de
x=a hasta x=b
∫
I=
b
f(x) dx
a

Implícitamente se asume que f(x) es
relativamente suave, se determina un conjunto
de puntos de “interpolación” o de malla xi en la
región a ≤ x ≤ b y se calcula la integral en
término de los valores de f(x) y los puntos de la
malla.
Regla de Simpson


Se asume que f(x) es una función
cuadrática
I = (b-a)*(f(a)+ 4f(xc)+f(b))/6
f(Xc)
f(a)
f(b)
X=a
xc =m = (a+ b)/2
X=b
x
Como sale la función cuadrática?

Por interpolación de Lagrange, la
curva se aproxima a una parábola P:

Prueba: P(x) claramente es de 2do
grado. Debo demostrar que pasa por
los 3 puntos (a, f(a)); (b, f(b)); (m, f(m))
Integrando la aproximación cuadrática

Si integro P(x) tengo:

El error en esta aproximación es
proporcional a:
Error en Simpson

Si se parte la integración en n
intervalos, el error es:

Donde h=(b-a)/n, epsilon es algún
número entre a y b con el máximo
modulo de la 4ta derivada de f.
Trapezoidal Iterativo y Simpson
iterativo

Trapezoidal: Si tenemos N puntos N xi con
I= (b-a) (f(x0)+2f(x1)+2f(x2)+ ……
+2f(x(N-2))+f(x(N-1))/(2(N-1))

O con Simpson:
I= (b-a) (f(x0)+4f(x1)+2f(x2)+ ……
+4f(x(N-2))+f(x(N-1))/(3(N-1))


Se suman los f(xi) con diferentes pesos
Note que ambos aproximan su cálculo en una región
tamaño (b-a)/(N-1) (el doble de eso para Simpson) que
tiende a cero si N es grande, así que la aprox. Es mejor
si N se agranda.
Las funciones de peso



Se suman varios wi f(xi) y las diferentes
reglas sólo con diferentes wi
Trapezoidal: para índices = 0, 1, 2, 3,
..., N-1
Se usa el patrón
wi  1, 2, 2, … 2, 2, 1
Para los mismos índices, Simpson con N
impar tiene el patrón
wi  1, 2, 4, 2, 4, … 2, 4, 2, 4, 1
Computación paralela
0
x0


x4
x8
x12
2
x16
x20
3
x24
x28
x32
Diferentes procesadores calculan independientemente diferentes
puntos en la integral y luego se suman los resultados de cada
procesador
Lo más natural es el escenario de la figura de arriba, con cada
procesador calculando una integral sobre una subregión



1
x0 al x8 en proc. 0 … x24 to x32 en proc. 3 etc.
La integral total es la suma de las sub-integrales calculadas en cada procesador
Pero podría asignarse PUNTOS y no REGIONES a los procesadores


x0 x4 x8 .. x32 al proc. 0
x3 x7 x11 .. x31 al proc. 3
Método Monte Carlo




El Monte Carlo más sencillo, escoge puntos al azar
La Integral es la suma de los valores de la función
f(xRandom-i) en los valores escogidos al azar xRandom-i
multiplicados por el intervalo de integración (b-a) y
dividido por el número de puntos generados.
Esta da un método robusto (y sin preferencias) que es
fácil de usar en integrales de n-dimensiones o
integrales de funciones problemáticas
Se puede adaptar en límites complicados


a
Se integra sobre regiones más grandes de lo necesario
Se define f(x) =0 fuera del intervalo [a b]
b
Hallar pi por integración con
Monte Carlo
(x,y) es un punto aleatorio: x,y variables aleatorias U.D.
Otra forma de Monte Carlo: g es una función de densidad.
Ambas son equivalentes
Errores





Para una integral con N puntos en 1-D:
Monte Carlo tiene un error del orden de 1/N0.5
Trapezoidal iterativo : 1/N2
Simpson iterativo: 1/N4
Pero en d dimensiones, todos menos el Monte Carlo
deben usar una malla de N1/d puntos por lado; no funciona
bien para N>3



Monte Carlo aún tiene error 1/N0.5
Error de Simpson es 1/N4/d
Cuando usar Montecarlo? Cuando error de Montecarlo es
menor que error de Simpson para los mismos N puntos?
1/N0.5 < 1/N4/d  0.5>4/d , o sea d>8
Paradigmas de Monte Carlo
paralelo

Master-worker:
se genera los
números
aleatorios en el
nodo 0 y se
pasan a los
demás.
Todos los nodos
computan.
Paradigmas de Monte Carlo
paralelo

Cliente-servidor:
es un servidor de
números
aleatorios, no
procesa, sólo
crea y envía los
randoms
Paradigmas de Monte Carlo
paralelo

Full workers: cada
nodo genera sus
propios números
aleatorios. El nodo
0 sólo cuida que se
siembren diferentes
semillas o que se
use la misma
semilla pero
diferentes rangos.
Números pseudo-aleatorios





Elemento Central en la Simulación digital.
Definición formal controvertida.
Elemento esencial en muchas áreas del
conocimiento Ingeniería, Economía, Física,
Estadística, etc.
Definición intuitiva: Una sucesión de números
aleatorios puros, se caracteriza por que no existe
ninguna regla o plan que nos permita conocer sus
valores.
Los números aleatorios obtenidos a través de
algoritmos recursivos se llaman pseudoaleatorios
(pseudo= no son, pero parecen).
Mapa Conceptual
Xi+1=(aXi+c) mod m
Tabla de Nros.
aleatorios
Fenómenos Físicos
Procedimientos
Matemáticos
Números
Aleatorios
Validación de
Series de NA
Variables
U (0,1)
Variables
Aleatorias
Números aleatorios
Disponer de un buen generador de números
aleatorios es clave en:








Simulación física (Monte Carlo y famila)
Computación Aleatorizada
Computación Evolutiva
Algoritmos Aleatorizados (ej: algoritmos
de gossip)
Verificación de Algoritmos
Validación de Algoritmos
Criptografía
etc.
Algunas Propiedades de Nros Aleatorios
1. Distribución Uniforme
Cualquier
número
que
pertenezca al rango de interés
debe
tener
la
misma
probabilidad
de
resultar
sorteado.
2. NO Correlación Serial.
La aparición de un número en
la secuencia, no afecta la
probabilidad de que aparezca
otro (o el mismo) número. (si
x1,x2,…,xn son aleatorias  el
vector (x1,x2,…,xn) también
Algunas Propiedades de Nros
Aleatorios
3- Complejidad Computacional: La
aleatoriedad de Kolmogorov, también
denominada incomprensibilidad
computacional. Consiste en constatar
si la aleatoriedad de una sucesión de
números es incomprensible (problema
decidible).
4- Impredecibilidad
Algunas Propiedades de Nros
Aleatorios

DEF 1: Kolmogorov (1987) [Complejidad
Algorítmica] Una sucesión de números es aleatoria
sino puede producirse eficientemente de una
manera más corta (con un programa) que la propia
serie.

DEF 2: L’Ecuyer (1990) [Impredicibilidad] Una
sucesión de números es aleatoria si nadie que
utilice recursos computacionales razonables puede
distinguir entre la serie y una sucesión de números
verdaderamente aleatoria de una forma mejor que
tirando una moneda legal para decidir cuál es cuál.
Ejemplo
La sucesión 1,2,3,4,5,1,2,3,4,5,1,2,3,4,5...
es uniforme pero está correlacionada.
La sucesión 3,4,4,2,1,4,5,2,5,4,1,1,3,4,4,3,4
Es no correlacionada pero no es uniforme
Existen Tests que verifican las condiciones de uniformidad y
correlación serial.
Generación de “aleatorios”

Tablas de números aleatorios


Fenómenos físicos






RAND (1955), 100,000 números aleatorios (ruido electrónico)
Ruido blanco producido por circuitos electrónicos
Recuento de partículas radioactivas emitidas
Lanzamiento de monedas / dados
Rueda de la fortuna / ruleta
Java Lamps u otos sistemas caóticos
Procedimientos matemáticos  pseudo
aleatorios

Se usa algoritmos para la generación de números
aparentemente aleatorios, se entrega una semilla y se
generan los sucesores mediante una función
Propiedades para pseudo
aleatorios








Distribución uniforme
No correlación
Periodo largo (sin repetición).
Reproducibles y mutables.
Sencillo en su implementación.
Método rápido de generación.
Poca memoria para la generación
Portabilidad.
Método del cuadrado medio



Fue propuesto inicialmente por Von
Newman y Metrópolis en el año 1946.
Para generar el siguiente número
pseudo-aleatorio, se toman los n dígitos
centrales del cuadrado del número
anterior de n dígitos.
Se requiere una semilla.
Método del cuadrado medio
R(n)2
M.R(n)2
n
R(n)
Val 1
Val 2
0
154
23,716
371
371
0
1
371
137,641
3,764
376
764
2
376
141,376
4,137
413
137
3
413
170,569
7,056
705
056
4
705
497,025
9,702
970
702
5
970
940,900
4,090
409
090
6
409
167,281
6,728
672
728
7
672
451,584
5,158
515
158
8
515
265,225
6,522
652
522
9
652
425,104
2,510
251
510
10
251
63,001
300
300
0
11
300
90,000
0
0
0
12
0
0
0
0
0
Análisis



El problema con este método es que tiende a degenerar
rápidamente. Dependiendo del valor inicial el método
puede degenerar al cabo de ≈20 términos.
Por ejemplo, supóngase que se quiere generar una serie
de números pseudo-aleatorios de cuatro dígitos y se tiene
como i-ésimo termino generado es 3500, luego se tendrá:
n
R(n)
R(n)2
M.R(n)2
Random
i
3500
12250000
2500
2500
i+1
2500
6250000
2500
2500
Se puede observar que hemos llegado a una condición
degenerada. Por la tanto, es necesario verificar siempre la
serie de números y protegerse contra este fenómeno
Método del Producto Medio

Este método es muy similar al anterior
ya que se tomará como número
aleatorio siguiente de la serie, a los n
dígitos centrales del resultado de una
multiplicación previa.

Se requiere dos semillas.
Método del Producto Medio
n
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
R(n)
151
155
340
270
180
860
548
712
901
415
739
668
936
252
358
21
51
7
5
R(n+1)
155
340
270
180
860
548
712
901
415
739
668
936
252
358
21
51
7
5
0
R(n)2
23,405
52,700
91,800
48,600
154,800
471,280
390,176
641,512
373,915
306,685
493,652
625,248
235,872
90,216
7,518
1,071
357
35
0
M.R(n)2
340
270
180
860
5,480
7,128
9,017
4,151
7,391
668
9,365
2,524
3,587
21
51
7
5
0
0
Val 1
340
270
180
860
548
712
901
415
739
668
936
252
358
21
51
7
5
0
0
Val 2
0
0
0
0
480
128
017
151
391
0
365
524
587
0
0
0
0
0
0
Análisis

Una modificación para este método consiste en utilizar un
multiplicador constante, en lugar de dos números
aleatorios como se muestra a continuación:
Rn+1 = K * Rn

Estos métodos son similares al cuadrado medio.
Sin embargo los dos tienen periodos más extensos y los
números parecen estar distribuidos uniformemente.
Este método tiende a degenerar a un valor constante.
Tanto el método de cuadrados medios como el de
producto medio tienen un periodo corto para la cantidad
de números aleatorios que vamos a necesitaremos
generar en cada uno de nuestros Modelos.



Método Congruencial Lineal
(MCL)

Los generadores congruenciales lineales generan una
serie de números pseudo - aleatorios de tal forma que se
puede generar el siguiente a partir del ultimo número
derivado, es decir, que el número Xn+1 es generado a
partir de Xn.

La relación de recurrencia para el método congruencial
mixto es:
Xn+1 = (aXn + c) mod m
Donde:
X0
a
c
m
= semilla (X0 >0)
= multiplicador (a >0)
= constante aditiva (c >0)
= módulo (m >X0, m >a y m>c)
Método Congruencial Lineal
(MCL)

Si se quiere obtener números Uniformes (0,1)
normaliza el resultado:
Un = Xn /
se
m

En el MCL, si se repite un número ya se repite toda la
secuencia.

Ventajas:
1.
2.
utiliza poca memoria y es muy rápido.
fácil de volver a generar la misma secuencia, guardando un solo
número, (se alcanza con partir desde la misma semilla: X0).
Ejemplo
n
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a
1
X(n)
7
1
8
2
9
3
10
4
11
5
12
6
0
7
1
8
c
7
a*X(n)+c
14
8
15
9
16
10
17
11
18
12
19
13
7
14
8
15
m
13
[a*X(n)+c] mod m
1
8
2
9
3
10
4
11
5
12
6
0
7
1
8
2
Análisis



Si no se escogen los valores adecuados de los
parámetros el período del generador de números
pseudo – aleatorios, será menor que m.
En la Tabla A se muestra los valores obtenidos para un
generador con parámetros: a = 7, c = 9, X0 = 5 y m = 11.
Como puede apreciarse en la tabla el período del
generador es 10 que es menor que el módulo que es 11.
Si bien este caso no es crítico si lo es el que se presenta
en la Tabla B donde los parámetros toman los valores
de a = X0 = c = 7 y m=10 cuyo período es de 4, que es
un caso muy critico que nos puede llevar a resultados
no deseables y poco confiables
Tabla A
n
0
1
2
3
4
5
6
7
8
9
10
a
7
X(n)
5
0
9
6
7
3
8
10
2
1
5
c
9
a*X(n)+c
44
9
72
51
58
30
65
79
23
16
44
m
11
[a*X(n)+c] mod m
0
9
6
7
3
8
10
2
1
5
0
Tabla B
n
0
1
2
3
4
5
6
a
7
X(n)
7
6
9
0
7
6
9
c
7
a*X(n)+c
56
49
70
7
56
49
70
m
10
[a*X(n)+c] mod m
6
9
0
7
6
9
0
Selección de m, a, c, X0
a)
Selección de módulo (m). Existen dos opciones que
son las siguientes:
a.1) Escoger al azar el módulo m.
a.2) Tomar m de tal manera que sea el número primo más
grande posible y además que sea menor que pd-1,
donde p es la base del sistema que se esta usando y d
es el número de bits que tiene una palabra de
computadora en el sistema que se esta usando.
Por ejemplo una computadora Pentium2 que trabaja en
el sistema binario entonces se tiene que p = 2 y d = 32.
Selección de m, a, c, X0
b) Selección de a.
 El valor de a debe ser un número entero impar, que no
deberá ser divisible por 3 ó 5. Pero además, para
asegurarnos que el generador tenga período completo, el
valor que se tome para a deberá escogerse según el
siguiente criterio:
(a-1) mod 4 = 0 si 4 es un factor de m.
(a-1) mod b = 0 si b es un factor primo de m.

Generalmente se toma a igual a 2k + 1 cuando se trabaja
en el sistema binario. En ambos casos el valor que se
asigne a k deberá ser mayor o igual que 2.
Selección de m, a, c, X0
c) Selección de c.
 Este parámetro puede tomar cualquier valor. Pero para
asegurarnos de tener buenos resultados se deberá
seleccionar según la siguiente regla:
c mod 8 = 5

En consecuencia c deberá tomar un valor entero impar y
relativamente primo a m.
Selección de m, a, c, X0
d) Selección de X0
 Se tiene que para el generador
congruencial el valor que tome X0 es
irrelevante y tiene poca o ninguna
influencia sobre las propiedades
estadísticas de las series de números
pseudo - aleatorios que se generen.
Método Congruencial Lineal
(MCL)

Para terminar esta parte se debe señalar
que existen otras formas matemáticas de
representar este generador, que son las
siguientes:
Xn = [anX0 + c{(an - 1)/(a - 1)}] mod m
Xn+k =[anXk + c{(an - 1)/(a - 1)}] mod m
Método Congruencial
Multiplicativo

En forma semejante al método anterior el generador
congruencial multiplicativo genera el próximo número
pseudo - aleatorio a partir del último número calculado,
siguiendo la siguiente relación de recurrencia:
Xn+1 = aXnmod m

Para este generador también se deben escoger
adecuadamente los valores de a, X0, y m, con la finalidad
de que se pueda asegurar un período máximo para la
series pseudo - aleatorias generadas por este método. A
continuación se dan las reglas que indican como se deben
escoger estos valores.
Selección de m, a, X0

Para trabajar en el sistema binario los valores de los
parámetros deberán escogerse siguiendo las siguientes
reglas:





El valor de X0 debe ser un número entero impar y relativamente
primo a m.
El valor de a debe ser obtenido a partir de la siguiente expresión:
a = 8t ± 3
Donde t es cualquier entero.
El valor de m puede ser 2d .
Si m = 2d el período del generador es 2d-2 ó m/4.
A modo de ejemplo se obtendremos el período de un
generador cuyos parámetros son: a = 5, X0 = 5 y m = 32. En
la siguiente tabla se muestra los elementos que componen
la serie generada cuyo período es de 8
Tabla C
a
5
n
0
1
2
3
4
5
6
7
8
9
10
X(n)
5
25
29
17
21
9
13
1
5
25
29
m
32
[a*X(n)] mod m
a*X(n)
25
125
145
85
105
45
65
5
25
125
145
25
29
17
21
9
13
1
5
25
29
17
Tabla D
Caso
1
2
3
4
5
Caso
1
2
3
4
5
6
5
12
2
7
10
9
8
3
9
a
6
7
5
7
6
8
11
1
10
10
9
12
5
4
5
Parámetros
b
m
0
13
0
13
0
13
0
11
0
11
2
6
12
6
8
xo
1
10
5
5
3
Salidas
12
7
3
8
8
1
9
8
4
2
3
4
5
1
1
5
2
12
7
6
4
1
8
5
3
11
7
1
2
7
1
10
5
3
9
6
5
12
10
10
10
9
8
4
4
Otros métodos

Series retardadas de Fibonacci


Series aritméticas:



In = In-r – In-s mod 224, r, s grandes (cientos, miles), r>s
I – k, I – 2k, I – 3k…, mod (224 - 3), k = 7654321
Mersenne Twister (MT19937): periodo de 219937-1.
No tiene correlación en 623 dimensiones.
Combinación de 2 o más métodos. Ej: Masaglia es
combinación de Fibonacci y Aritméticas
Mersenne Twister

Basado en recurrencia y modulo 2

l, s, t, u son enteros, b, c son
máscaras de bits, x[0:n-1] es un array
de n enteros sin signo, ll, a son
constantes enteras sin signo

Paso 0


Paso 1


Crear una máscara para bits superiores y otra para los inferiores
El array x se inicializa con una semilla
Paso 2

y : bits superiores de x[i] concadenados con los bits inferiores de
x[i+1].

Paso 3



Paso 4


y * A.
A se escoje tal que sea fácil de calcular con shift derecho y xor.
Multiplica por T (tempering matrix) para mejor equidistribución
y buena precisión.
Paso 5 & 6:

Sumar 1 a i , repetir el proceso
Streams - Torrentes

Un generador de números aleatorios que comience con
la misma semilla, siempre producirá la misma torrente o
secuencia de números.

Diferentes semillas generarán diferentes secuencias. Si
las semillas se eligen con valores no cercanos (en el
ciclo del generador), entonces las secuencias de
números generados (torrentes) parecerán y actuarán
como números aleatorios independientes entre sí con lo
que colaborarán en la generación de v.a. Independientes
entre sí.
Generadores Paralelos de
nums. pseudo aleatorios

Cómo hago para Montecarlo Paralelo?



Generación centralizada (master-worker y
cliente servidor)
Generación descentralizada (full workers)
El problema de la 1ra opción es que hay
que comunicar data por memoria
compartida o por la red: se gasta tiempo.
Además no se usaría paralelismo en la
producción de los pseudo aleatorios.
Generación descentralizada
(full workers)

Asumamos que se usa el mismo método
en todos los cores. Hay 3 formas:



Todos los cores usan la misma semilla,
generan la misma secuencia, pero usan solo
una parte de los números: r1, r2, r3, r4, r5, r6,
r7, r8, … (1 sólo stream)
Cada core usa una semilla diferente (varios
streams independientes).
Usar un generador especialmente diseñado
para computación paralela (varios streams
independientes).
Generación descentralizada
(full workers)



La primera opción: si son np cores, se computa
por gusto un ratio de np-1/np . A veces no se
podría usar con hilos.
Puede ser que el generador no sea “thread
safe” (cada llamada a random, no importa el
hilo, usa la misma variable en memoria 
necesita un mutex en Multicores) .
La segunda: no hay garantía que las
secuencias de 2 diferentes cores no tengan
correlación (“Solo Dios sabe si no tienen
correlación”). Para np cores, hay np(np-1)/2
chances de correlación. A veces no se podría
usar con hilos.
Generadores especialmente
diseñados para paralelismo

Series de Fibonnaci con diferentes
parámetros para cada core:


In = In-r – In-s mod 224, r, s diferentes. O los I
iniciales diferentes.
“Dynamic Creator” para Mersenne Twister:

Usando un ID (ej.: número de proceso),
tamaño el random, periodo, se generan
diferentes semillas para ell Mersenne Twister,
que generan streams sin correlación.
Si quiero 100 generadores sin correlación, llamo a esta función 100 veces,
con ID=0,1,2,…,99, y obtengo 100 seeds.