Cecilia Urbina: Cálculo del pi en paralelo

En esta semana quise complementar lo de algoritmos paralelos haciendo un algoritmo que calcula el número Pi primero en paralelo y después en secuencial.

Metodo de Montecarlo

Este algoritmo consiste en generar experimentos aleatorios independientes consistentes en generar N puntos x, y que pertenezcan de 0 a 1 y contabilizar C los números que caen dentro del cuadrante de un circulo de radio 1.

El área del circulo es igual a pi*radio **2, el área del cuadrante es pi/4, y la probabilidad es C/N = pi/4 osea pi = 4C/N.

La aproximación más precisa es cuando N tiende al infinito.
Este es el algoritmo secuencial que desarrolle:

	#!/usr/bin/python
	import random
	import math

	def enCirculo(x, y):
	acierta = False
	resultado = x 2 + y 2
	if resultado <= 1:
	acierta = True
	return acierta

	def pi(n):
	c = 0
	for i in range(n):
	x = random.random()
	y = random.random()
	acierta = enCirculo(x, y)
	if acierta:
	c = c + 1
	return (4.0 * c)/n


	print pi(10000000)

view raw montecarlo secuencial hosted with ❤ by GitHub

Ejecución:

Paralelización

Este reparto consiste en la generacion de N experimentos en un conjunto de P procesadores. Cada procesador puede generar puntos y contar cuales C caen en el rango del círculo con 1 de radio.
Al iniciar solo el proceso principal conoce cuales son los valores de N, osea el número de pruebas que se quiere hacer, y cuantos procesadores se van a tener.
Después se envian a los procesos esclavos la N, para que empiezen a calcular.

Cada proceso realiza el trabajo que le corresponde

Y por último los procesos esclavos envían sus resultados al proceso maestro, para que el maestro calcule el numero de aciertos y lo multiplique por 4 (por la formula que acabamos de ver) y lo divida entre el total de experimentos N.

Mi programa en python emula este comportamiento con hilos, y queue de python para poder mandar cada suma al proceso maestro, este es el programa:

	#!/usr/bin/python

	import threading, time
	import math, random
	lock = threading.Lock()
	import Queue

	class pi(threading.Thread):
	def __init__(self, n, q):
	threading.Thread.__init__(self)
	self.n = n
	self.x = 0
	self.y = 0
	self.c = 0

	def enCirculo(self, x, y):
	acierta = False
	res = x 2 + y 2
	if res <= 1:
	acierta = True
	return acierta

	def run(self):
	for i in range(self.n):
	self.x = random.random()
	self.y = random.random()
	self.acierta = self.enCirculo(self.x, self.y)
	if self.acierta:
	self.c = self.c + 1
	pii = (4.0 * self.c)/self.n
	q.put(self.c)


	q = Queue.Queue()
	hilos = 5 #simula 5 procesadores
	n = 100000000 #numero de pruebas

	for i in range(hilos):
	h = pi(n/5, q)
	h.start()
	h.join()

	print q.qsize()
	i = 0
	total = 0
	for i in range(q.qsize()):
	num = q.get(i)
	print num #aqui se imprime la suma que obtiene cada hilo individual
	total = num + total

	pi = (4.0 * total)/n # formula para obtener el pi tomando el total de aciertos y dividiendo
	print "Pi en colaboracion " + str(pi)