viernes, 23 de marzo de 2012

Embarazosamente paralelos

En los llamados problemas embarazosamente paralelos, un cálculo consiste en una serie de tareas que pueden ejecutar más o menos independiente, sin la comunicación. Estos problemas suelen ser fáciles de adaptar para la ejecución en paralelo. Un ejemplo es un estudio de parámetros, en la que el mismo cálculo debe llevarse a cabo utilizando una gama de parámetros de entrada diferentes. Los valores de los parámetros se leen de un archivo de entrada, y los resultados de los cálculos diferentes se escriben en un fichero de salida.


Trabajadores (W) parámetros de la petición de la tarea de entrada (I) y enviar los resultados a la tarea de salida (O). Tenga en cuenta las conexiones de muchos a uno: este programa no es determinista en el que las tareas de entrada y salida de recibir los datos de los trabajadores en el orden que los datos que se generan. Canales de respuesta, representadas como líneas discontinuas, se utilizan para comunicar los parámetros de la tarea de entrada para los trabajadores.
Si el tiempo de ejecución por problema es constante y cada procesador tiene la misma potencia de cálculo, a continuación, basta con problemas de partición disponibles en conjuntos de igual tamaño y asignar un conjunto tal que cada procesador.  Las tareas de entrada y salida son responsables de la lectura y escritura de los archivos de entrada y salida, respectivamente. Cada tarea de los trabajadores (por lo general una por procesador) varias veces pide valores de los parámetros de la tarea de entrada, calcula el uso de estos valores, y envía los resultados a la tarea de salida. Debido a los tiempos de ejecución varían, las tareas de entrada y salida no se puede esperar para recibir los mensajes de los distintos trabajadores en ningún orden en particular. En su lugar, una estructura de comunicación de muchos a uno se utiliza que les permite recibir mensajes de los diversos trabajadores en orden de llegada.

La tarea de entrada responde a una petición de los trabajadores mediante el envío de un parámetro con el trabajador. Por lo tanto, un trabajador que ha enviado una solicitud a la tarea de entrada, simplemente espera a que el parámetro para llegar a su canal de respuesta. En algunos casos, la eficiencia puede ser mejorada por prebúsqueda, es decir, que solicita el parámetro siguiente, antes de que sea necesario. El trabajador puede realizar el cálculo, mientras que su petición está siendo procesada por la tarea de entrada.

Debido a que este programa utiliza muchos-a-uno las estructuras de comunicación, el orden en que los cálculos se realizan no se determina necesariamente. Sin embargo, esto no determinismo sólo afecta a la asignación de los problemas a los trabajadores y la clasificación de los resultados en el archivo de salida no, los resultados reales calculadas.

Programar !! Python secuencial:

#!/usr/bin/python                                                                                                                                      
contador = 1
lista = []
resultados = []
f = open("entradas.txt")

#este rollo para sacar del archivo de entrada los numeritos                                                                                            
while True:
      linea = f.readline()
      if not linea: break
      print linea
      if contador % 2 != 0:
            lista.append(int(linea)) #amo python                                                                                                       

f.close()

print linea
f = open("salida.txt", "w")
for m in range(len(lista)):
      res = (lista[m])**2 #variable auxiliar que me ayuda a escribir en el array                                                                       
      resultados.append(res) #guardo en un arreglo, solo para debug                                                                                    
      cadena = str(res) + "\n" #lo que voy a poner en el archivo                                                                                       
      f.write(cadena) # escribo en el archivo                                                                                                          
f.close #lo cierro                                                                                                                                     

print lista
print resultados

Resultado :

Teminal


Archivo Salida.txt que se creo:

Python paralelo:
#!/usr/bin/python                                                                                                                                                                                                                                                               
import threading, time
import Queue

q = Queue.Queue()
o = Queue.Queue()
contador = 1

class cuadrado(threading.Thread):
      def __init__(self, num):
            threading.Thread.__init__(self)
            self.num = num
            self.res = 0

      def run(self):
            print "Calculando paralelamente los cuadrados"
            self.res = self.num ** 2
            o.put(self.res)



f = open("entradas.txt")

#este rollo para sacar del archivo de entrada los numeritos                                                                                                                                                                                                                     
while True:
      linea = f.readline()
      if not linea: break
      print linea
      if contador % 2 != 0:
            q.put(int(linea)) #ponemos en la cola                                                                                                                                                                                                                               
            print("Mando a llamar al hilo para que ejecute el cuadrado")
            h = cuadrado(int(linea))
            h.start()
            h.join()
f.close()


f = open("SALIDA.txt", "w")
print "Empiezo a escribir en el archivo"
for i in range(o.qsize()):
      cadena = str(o.get(i)) + "\n" #lo que voy a poner en el archivo                                                                                                                                                                                                           
      f.write(cadena) # escribo en el archivo                                                                                                                                                                                                                                   
f.close #lo cierro                                                                                                                                                                                                                                                              

Resultados:

Terminal



Archivo SALIDAS.txt







Más ejemplos

Algunos ejemplos de los problemas embarazosamente paralelos incluyen:


  • Consultas distribuidas de bases de datos relacionales utilizando el procesamiento distribuido conjunto
  • Servir archivos estáticos en un servidor web.
  • El conjunto de Mandelbrot y otros cálculos fractales, donde cada punto se puede calcular de forma independiente.
  • Representación de los gráficos por ordenador . En el trazado de rayos , cada píxel puede ser prestado de manera independiente. En la animación por ordenador , cada fotograma pueden ser prestados de manera independiente (véase la representación en paralelo )
  • Fuerza bruta búsquedas en la criptografía . Un notable ejemplo del mundo real es distributed.net .
  • BLAST búsquedas en bioinformática para las consultas de varios (pero no para consultas individuales de gran tamaño)
  • A gran escala de reconocimiento facial que consiste en la comparación de miles de entradas se enfrenta con el número igualmente grande de caras.
  • Las simulaciones por ordenador comparación de numerosos escenarios independientes, como los modelos climáticos.
  • Los algoritmos genéticos y otros de computación evolutiva metaheurísticas .
  • Ensemble cálculos de predicción numérica del tiempo .
  • Evento de simulación y reconstrucción de la física de partículas .
  • Tamizado paso de la criba cuadrática y el tamiz de número de campo .
  • Árbol de paso el crecimiento del bosque al azar técnica de aprendizaje automático.

Referencias

1 comentario:

  1. y este al lab de semana 8, con 8 puntos - aclarada la confusión

    ResponderEliminar