¿Cómo paralelizar un algoritmo secuencial?

7

¿Qué proceso de pensamiento se debe seguir para convertir un algoritmo secuencial en uno paralelo? ¿Hay algún patrón de código específico que pueda ser paralelizado? Algunos patrones que normalmente uso son:

  • Buscando bucles que puedan paralelizarse.
  • Intente dividir algo en alguna forma de formato de reducción de mapa.
  • Buscando un patrón de productor-consumidor.
pregunta Saurabh Saxena 07.12.2011 - 19:53

2 respuestas

7

Ian Foster describe cuatro pasos básicos en su libro "Diseño y creación de programas paralelos":

  1. Partición: encuentre formas posibles de dividir los datos entre los trabajadores de la forma más precisa posible.
  2. Comunicación: identifica los patrones de comunicación.
  3. Aglomeración: reduce las particiones iniciales a tareas de grano grueso de acuerdo con los recursos disponibles.
  4. Asignación: asigne las tareas a las unidades de procesamiento.

El libro es gratuito en línea, puede encontrarlo aquí: enlace

    
respondido por el Tudor 07.12.2011 - 20:59
1

Para formalizar de alguna manera lo que ya ha dicho sobre la búsqueda de bucles que puedan paralizarse, el concepto clave que se está explotando es el paralelismo de datos planos. La mayoría de las bibliotecas paralelas (que yo sepa) parecen exhibir esto (por ejemplo, la biblioteca paralela de tareas de Microsoft para .NET, la biblioteca de patrones paralelos de Microsoft para C ++)

El paralelismo de datos planos ocurre cuando tiene una parte de los datos (planos) (por ejemplo, una matriz) en la que desea realizar el trabajo, luego divide los datos en partes de cuántos procesadores tiene, funciona de manera independiente en paralelo para cada uno de esos fragmentos, y finalmente, potencialmente agregue / combine el resultado de cada fragmento para obtener su resultado final.

Un artículo de muestra sobre esto: enlace

    
respondido por el ryaner 07.12.2011 - 20:22

Lea otras preguntas en las etiquetas