Semana 6

Paralelizando algoritmos

Criba de Eratóstenes

Es un aloritmo que encuentra numeros primos de 2 a N, empieza con el número 2 y tacha todos los elementos que son multiplos del 2, una vez que tacho todos estos sigue el elemento que no ha sido tachado despues de dos y así sucesivamente.

Primero desarrollé la versión en secuencial del algoritmo en Python:

	#!/usr/bin/python
	numeros = []
	primos = []
	for i in range(2, 100):
	numeros.append(i)
	while numeros != []:
	n = numeros[0]
	primos.append(n)
	n = (float(n))
	for j in numeros:
	if ((j % n) == 0.0):
	numeros.remove(j)
	print primos

view raw gistfile1.py hosted with ❤ by GitHub

Ejecución:

Para paralelizarla lo que intenté hacer fué que cada hilo buscara los múltiples de ciertos números en paralelo. Es decir mientras uno buscaba los múltiplos de 2 otro buscara los múltiplos de 3 y así sucesivamente.

	#!/usr/bin/python
	import threading, time
	import math, random
	import Queue
	class primos(threading.Thread):
	def __init__(self, n, q):
	threading.Thread.__init__(self)
	self.n = n
	self.numeros = []
	self.primos = []
	def run(self):
	while self.numeros != []:
	self.n = self.numeros[0]
	self.primos.append(self.n)
	self.n = (float(self.n))
	for j in self.numeros:
	if((j%self.n) == 0.0):
	q.get(j) # se elimina elemento de la lista
	q = Queue.Queue()
	for i in range(2, 100):
	q.put(i)
	for i in range(q.qsize()):
	num = q.get(i)
	#print num
	h = primos(100, q) #con un hilo
	h.start()
	h.join()
	for i in range(q.qsize()):
	num = q.get(i)
	print num

view raw gistfile1.py hosted with ❤ by GitHub

En el ejemplo lo hice con solo un hilo, con esta manera de implementación podemos crear tantos hilos como queramos y que empiecen a checar si es primo o no desde algún número, y así trabajar en paralelo, subiré la parte en donde muestro como se hace de esta forma que explico en otra entrada, esto es todo por ahora.

Nominaciones:
Por ahora solo, Roberto Martínez por la propuesta al uso de una herramienta útil para hacer sistemas distribuidos y Emmanuel por la explicación del uso de mpi4 de python ya que yo tenía pensado hablar de eso.