multithreading - que - ¿Qué es lo opuesto a "embarazosamente paralelo"?
multithreading que es (20)
"Completamente en serie?"
Realmente no debería sorprenderte que los científicos piensen más sobre lo que se puede hacer que lo que no se puede hacer. Especialmente en este caso, donde la alternativa a la paralelización es hacer todo lo que uno normalmente haría.
Según Wikipedia, un problema "vergonzosamente paralelo" es aquel para el que se requiere poco o ningún esfuerzo para separar el problema en una serie de tareas paralelas. Raytracing se cita a menudo como un ejemplo porque cada rayo puede, en principio, procesarse en paralelo.
Obviamente, algunos problemas son mucho más difíciles de paralelizar. Algunos incluso pueden ser imposibles. Me pregunto qué términos se usan y cuáles son los ejemplos estándar para estos casos más difíciles.
¿Puedo proponer "molestamente secuencial" como un posible nombre?
"Gladdengly Sequential"
"ejemplos estándar" de procesos secuenciales:
- Hacer un bebé: "Los programas de choque fallan porque se basan en la teoría de que, con nueve mujeres embarazadas, puede tener un bebé por mes". - atribuido a Werner von Braun
- calculando pi, e, sqrt (2) y otros números irracionales a millones de dígitos: la mayoría de los algoritmos secuencial
- navegación: para ir del punto A al punto Z, primero debes pasar por algunos puntos intermedios B, C, D, etc.
- Método de Newton: necesita cada aproximación para calcular la próxima aproximación mejor
- autenticación desafío-respuesta
- fortalecimiento clave
- cadena hash
- Hashcash
¿"Serie testarudamente"?
Completamente no paraleilable? ¿Pimesimalmente paralelizable?
El término que he escuchado con más frecuencia es "estrechamente vinculado", ya que cada proceso debe interactuar y comunicarse a menudo para compartir datos intermedios. Básicamente, cada proceso depende de otros para completar su cálculo.
Por ejemplo, el procesamiento matricial a menudo implica el intercambio de valores límite en los bordes de cada partición de matriz.
Esto contrasta con problemas vergonzosamente paralelos (o poco compactos) donde cada parte del problema es completamente autónoma y no se necesita (o muy poco) IPC. Piensa en el paralelismo maestro / trabajador.
Estoy teniendo un momento difícil para no publicar esto ... porque sé que no agrega nada a la discusión ... pero para todos los fanáticos de Southpark por ahí
"Súper serial!"
Hay más de un opuesto a un problema "embarazosamente paralelo".
Perfectamente secuencial
Un opuesto es un problema no paralelizable , es decir, un problema para el que no se puede speedup utilizando más de un procesador. Varias sugerencias ya fueron publicadas, pero propongo otro nombre: un problema perfectamente secuencial .
Ejemplos: problemas I/O-bound problemas "calcular f 1000000 (x 0 )", cálculo de ciertas funciones hash criptográficas .
Comunicación intensiva
Otro opuesto es un problema paralelizable que requiere mucha comunicación paralela (un problema de comunicación intensiva ). Una implementación de tal problema se escalará correctamente solo en una supercomputadora con interconexión de baja latencia y ancho de banda alto. Compare esto con problemas vergonzosamente paralelos, cuyas implementaciones se ejecutan eficientemente incluso en sistemas con una interconexión muy pobre (por ejemplo, farms ).
Ejemplo notable de un problema de comunicación intensiva: resolver A x = b donde A es una matriz grande y densa. Como cuestión de hecho, una implementación del problema se utiliza para compilar el ranking TOP500 . Es un buen punto de referencia, ya que enfatiza tanto el poder computacional de las CPU individuales como la calidad de la interconexión (debido a la intensidad de la comunicación).
En términos más prácticos, cualquier modelo matemático que resuelva un sistema de ecuaciones diferenciales parciales en una cuadrícula regular usando un paso de tiempo discreto (piense: pronóstico del tiempo, pruebas de colisión in silico ), es paralelizable por la descomposición del dominio . Eso significa que cada CPU se ocupa de una parte de la red, y al final de cada paso de tiempo las CPU intercambian sus resultados en los límites de la región con las CPU "vecinas". Estos intercambios hacen que esta clase de problemas sean intensivos en comunicación.
Jactanciosamente secuencial.
Lo opuesto a lo embarazosamente paralelo es la Ley de Amdahl , que dice que algunas tareas no pueden ser paralelas, y que el tiempo mínimo que requerirá una tarea perfectamente paralela está dictado por la parte puramente secuencial de esa tarea.
Lo opuesto es "desconcertantemente serial".
P-complete (pero aún no se sabe con certeza).
Por supuesto, podrías, sin embargo, creo que los dos "nombres" no son un problema. Desde una perspectiva de programación funcional, podría decirse que la parte "molestamente secuencial" es la parte más pequeña, más o menos independiente, de un algoritmo.
Mientras que el "embarazosamente paralelo" si no se toma en realidad un enfoque paralelo es una mala práctica de codificación.
Por lo tanto, no veo un punto en que se le dé un nombre a estas cosas si una buena práctica de codificación es siempre frenar su solución en piezas independientes, incluso si en ese momento no aprovecha el paralelismo.
Si alguna vez uno debe especular sobre lo que sería tener problemas secuenciales naturales e incorregibles, intente
felizmente secuencial
para contrarrestar '' embarazosamente paralelo ''.
Siempre he preferido ''lamentablemente secuencial'' a los pasos de la partición en el quicksort.
Todo tiene que ver con las dependencias de datos. Los problemas embarazosamente paralelos son aquellos para los cuales la solución se compone de muchas partes independientes. Los problemas con lo contrario de esta naturaleza serían los que tienen dependencias masivas de datos, donde hay poco o nada que se pueda hacer en paralelo. Degenerativamente dependiente ?
Un ejemplo intrínsecamente secuencial problema. Esto es común en los paquetes CAD y en algunos tipos de análisis de ingeniería.
Recorrido de árbol con dependencias de datos entre nodos.
Imagine atravesar un gráfico y sumar pesos de nodos.
Simplemente no puedes paralelizarlo.
El software de CAD representa partes como un árbol, y para representar al objeto debe atravesar el árbol. Por esta razón, las estaciones de trabajo cad utilizan menos núcleos y más rápido, en lugar de muchos núcleos.
Gracias por leer.
Yo uso "Humillantemente secuencial"
Pablo
teniendo en cuenta que el paralelismo es el acto de hacer muchos trabajos en el mismo tiempo t. lo contrario podría ser problemas secuenciales
Inherentemente secuencial
Ejemplo: el número de mujeres no reducirá la duración del embarazo.