¿Cuáles son los ejemplos canónicos de cómputo paralelo?

Question

Estoy escribiendo un documento para probar una nueva aplicación que demostrará los beneficios del cálculo paralelizado (en comparación con la versión serializada tradicional de esta aplicación). Quiero usar el canonical examples para el cálculo paralelo en mi documento.

Mi primer ejemplo es the parallel computation of pi. Idealmente me gustaría un ejemplo en el que cada iteración consuma mucho tiempo (debido a la sobrecarga adicional asociada con la paralelización); mi primer pensamiento es una simulación bayesiana con muestreo MCMC y Gibbs.

¿Qué otros problemas se discuten normalmente en este contexto? ¿Cuáles son buenos ejemplos de grandes problemas de embarassingly parallel?

Answer 1

Un ejemplo que he utilizado en el pasado de un problema embarazoso paralelo es visualizar el conjunto de Mandelbrot. Cada píxel se puede calcular de forma independiente.

Conway's Life también es interesante, ya que cada valor de la "próxima" placa se puede calcular de forma independiente, pero dependerá de los bits relevantes de la placa "actual" que se esté realizando.

Answer 2

conteo de palabras parece ser el ejemplo canónico de MapReduce.

http://en.wikipedia.org/wiki/MapReduce#Example

Answer 3

sólo unos pocos más -

• matrices Multiplicando
• matrices Inversión de
• FFT
• cadena coincidente
• Rendering escenas 3D (a través de la conversión de línea de exploración o trazado de rayos)

Answer 4

Mi ejemplo favorito es simulación de Monte Carlo.

Answer 5

Encontrar colisiones en funciones hash utilizando Paul C. van Oorschot y Michael J. Weiner's method (PDF) aparece a menudo en varios ajustes criptográficos.

Answer 6

sugeriría que ejemplos canónicos de computación paralela yproblemas embarazosamente paralelos son, si no completamente, a continuación, casi, conjuntos disjuntos. Para decirlo de otra manera, las personas que trabajan en cómputo paralelo no están terriblemente entusiasmadas con problemas embarazosamente paralelos; los llamamos así porque estaríamos avergonzados de estar trabajando en ellos.

estaría buscando, si yo fuera usted, en estos (una lista no del todo original):

• álgebra lineal en grandes matrices densas, ambos enfoques directos e iterativos;
• álgebra lineal en matrices dispersas enormes
• enfoques de ramificación y ligado a problemas de programación lineal (y relacionados);
• coincidencia de secuencia para bioinformática (fuera de mi campo, puede haber expresado mal esto);
• optimización continua.

espero que hay muchos más.

EDIT: Usted puede estar interesado en this list of problems que han sido seleccionados para la evaluación comparativa de la próxima generación de superordenadores Europea (académicos). Te dará una idea de hacia dónde se dirige ese nicho.

Answer 7

dinámica simluations moleculares permiten cambiar el tamaño del problema hasta que se agoten sus recursos informáticos (es decir, 256 partículas frente a 256.000.000 partículas). Su realmente un ejemplo "canónica" si ejecuta las simulaciones MD NVT bajo condiciones ;-)

Answer 8

Es posible que desee echar un vistazo a la tabla de contenidos de Parallel Programming in C with MPI and OpenMP

Answer 9

he usado el conjunto de Mandelbrot demostración para explicar a mi mamá lo que la programación en paralelo es de aproximadamente: http://www.ateji.com/px/demo.html

Todos los ejemplos que menciona son los códigos de datos en paralelo sobre todo pesados. Probablemente desee mencionar también los códigos orientados a tareas, como los servidores que responden a muchas solicitudes en paralelo, y los ejemplos de flujo de datos o de programación de flujo (MapReduce es un buen representante de esta clase).