¿Qué es lo contrario de & # 8220; embarazosamente paralelo & # 8221 ;?

Question

Según Wikipedia, un " vergonzosamente paralelo " El problema es uno para el que se requiere poco o ningún esfuerzo para separar el problema en una serie de tareas paralelas. El trazado de rayos se cita a menudo como 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 "Annoyingly Sequential"? como un posible nombre?

Answer 1

Inherentemente secuencial .

Ejemplo: El número de mujeres no reducirá la duración del embarazo.

Answer 2

Hay más de un opuesto a un " vergonzosamente paralelo " problema.

Perfectamente secuencial

Un opuesto es un problema no paralelizable , es decir, un problema para el que no speedup se puede lograr utilizando más de un procesador. Ya se publicaron varias sugerencias, pero propondría otro nombre: un problema perfectamente secuencial

Ejemplos: problemas de E / S vinculados , " calcule f ^1000000 (x ₀ ) " tipo de problemas, calculando 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 alto ancho de banda y baja latencia. Contraste esto con problemas vergonzosamente paralelos, cuyas implementaciones se ejecutan de manera eficiente incluso en sistemas con interconexiones muy deficientes (por ejemplo, granjas ).

Ejemplo notable de un problema de uso intensivo de la comunicación: resolver A x = b donde A es una matriz grande y densa. De hecho, se utiliza una implementación del problema para compilar el ranking TOP500 . Es un buen punto de referencia, ya que enfatiza tanto la potencia de cálculo 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 utilizando pasos de tiempo discretos (piense: pronóstico del tiempo, in silico pruebas de choque), es paralelizable por descomposición del dominio . Eso significa que cada CPU se ocupa de una parte de la cuadrícula y, al final de cada paso de tiempo, las CPU intercambian sus resultados en los límites de la región con " adyacente " CPUs. Estos intercambios hacen que esta clase de problemas sean intensivos en comunicación.

Answer 3

Me está costando mucho no publicar esto ... porque sé que no agrega nada a la discusión ... pero para todos los fanáticos de southpark

" ¡Super serie! "

Answer 4

" Stubbornly serial " ;?

Answer 5

Lo contrario de vergonzosamente paralelo es Ley de Amdahl , que dice que algunas tareas no pueden ser paralelo, y que el tiempo mínimo que requerirá una tarea perfectamente paralela está dictado por la parte puramente secuencial de esa tarea.

Answer 6

" ejemplos estándar " de procesos secuenciales:

• haciendo un bebé: "Los programas de bloqueo fallan porque se basan en la teoría de que, con nueve mujeres embarazadas, puedes tener un bebé por mes". - atribuido a Werner von Braun
• calcular pi, e, sqrt (2) y otros números irracionales a millones de dígitos: la mayoría de los algoritmos secuenciales
• 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 siguiente, mejor aproximación
• autenticación de desafío-respuesta
• fortalecimiento de la clave
• cadena de hash
• Hashcash

Answer 7

P-completo (pero eso no se sabe con seguridad todavía).

Answer 8

Uso " Humillante secuencial "

Paul

Answer 9

" Gladdengly Secuencial "

Answer 10

Todo tiene que ver con las dependencias de datos. Los problemas vergonzosamente paralelos son aquellos para los cuales la solución se compone de muchas partes independientes. Los problemas con el opuesto de esta naturaleza serían los que tienen dependencias de datos masivas, donde hay poco o nada que se puede hacer en paralelo. ¿Dependiente degenerativamente ?

Answer 11

El término que he escuchado con más frecuencia es "estrechamente acoplado", en el sentido de 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 compartir valores de límites en los bordes de cada partición de matriz.

Esto contrasta con los problemas vergonzosamente paralelos (o débilmente acoplados) en los que cada parte del problema es completamente independiente y no se necesita (o muy poco) el IPC. Pensar paralelismo maestro / trabajador.

Answer 12

Sencillamente secuencial.

Answer 13

Siempre he preferido 'tristemente secuencial' para el paso de partición en quicksort.

Answer 14

Si alguna vez se debe especular cómo sería tener problemas naturales e incorregibles, intente

maravillosamente secuencial

para contrarrestar ' vergonzosamente paralelo '.

Answer 15

" ¿Completamente en serie? "

Realmente no debería sorprenderte que los científicos piensen más en lo que se puede hacer que en lo que no se puede hacer. Especialmente en este caso, donde la alternativa a la paralelización es hacer todo como uno lo haría normalmente.

Answer 16

¿Completamente no paralelizable? Pesimalmente paralelizable?

Answer 17

El opuesto es " desconcertantemente serial " ;.

Answer 18

teniendo en cuenta que el paralelismo es el acto de hacer muchos trabajos al mismo tiempo, paso t. lo contrario podría ser problemas de tiempo secuencial

Answer 19

Un ejemplo de problema inherentemente secuencial. Esto es común en los paquetes CAD y en algunos tipos de análisis de ingeniería.

Recorrido del árbol con dependencias de datos entre nodos.

Imagine atravesar un gráfico y sumar pesos de nodos.

No puedes paralelizarlo.

El software CAD representa partes como un árbol, y para renderizar un objeto debe atravesar el árbol. Por esta razón, las estaciones de trabajo cad usan menos núcleos y más rápido, en lugar de muchos núcleos.

Gracias por leer.

Answer 20

Por supuesto que podría, sin embargo, creo que ambos "nombres" no son un problema. Desde una perspectiva de programación funcional, se podría decir que la parte 'molesta secuencial' es la parte más pequeña o más independiente de un algoritmo.

Mientras que el 'vergonzosamente paralelo', si no se toma en cuenta un enfoque paralelo, es una mala práctica de codificación.

Por lo tanto, no veo un punto en el que se le dé un nombre a estas cosas si una buena práctica de codificación es siempre romper tu solución en partes independientes, incluso si en ese momento no te aprovechas del paralelismo.