¿Hay algo que DEBE hacerse en una CPU multinúcleo?

45

Al considerar cuán amigable debe ser nuestro programa con múltiples subprocesos, mi equipo se preguntó si hay algo que no se pueda hacer en una CPU de un solo núcleo. Postulé que el procesamiento de gráficos requiere un procesamiento paralelo masivo, pero argumentan que cosas como DOOM se hicieron en CPU de un solo núcleo sin GPU.

¿Hay algo que deba hacerse en un procesador multinúcleo?

Suponga que hay tiempo infinito para el desarrollo y la ejecución.

Ben Leggiero
fuente
8
Si bien las respuestas a continuación parecen ser en gran medida “no”, históricamente hay sistemas que, literalmente, no podrían haber funcionado sin un coprocesador que manejara algunas tareas. Un buen ejemplo que conozco es el Nintendo DS, que incluye una CPU ARM9 de 67MHz y una CPU ARM7 de 33MHz (también se usa para la compatibilidad inversa cuando se juegan juegos GBA). Para los juegos de DS, el ARM7 maneja la reproducción de audio y comunicación Wi-Fi porque el ARM9 no puede procesar y dibujar nada notable en la pantalla mientras se mantiene al día con la alimentación de audio al chip de sonido directamente. Entonces, como @jmite dice "bajo qué restricciones", la falta de velocidad puede requerir múltiples CPU.
Slipp D. Thompson
10
En mi trabajo utilizamos Xeons multinúcleo y las extensiones de Linux en tiempo real de Xenomai para realizar el procesamiento de audio de baja latencia. Tenemos una tubería de procesamiento de audio de tres etapas, y cada etapa tiene su propio núcleo dedicado, que utiliza ~ 70% de los ciclos de. Las tareas en tiempo no real pueden usar el cuarto núcleo, y cualquier ciclo que quede en los primeros tres. Esto solo sería posible en una CPU de un solo núcleo si ese único núcleo fuera 3 veces más rápido que un núcleo en la CPU actual de 4 núcleos; dado que la CPU actual funciona a 2 GHz, eso podría ser difícil de lograr.
Jeremy Friesner
19
El software en una CPU de un solo núcleo puede emular una CPU de varios núcleos. La diferencia es casi por completo la velocidad.
user253751
24
Una cosa que debe hacerse en un sistema multinúcleo es probar software multiproceso. Porque algunos defectos (casi) nunca sucederán en un sistema de un solo núcleo. Sin embargo, no estoy seguro de que eso califique como respuesta ...
Nikkie
13
@nikie Un sistema de un solo núcleo puede emular el pedido de memoria y las memorias caché obsoletas también, pero me imagino que esto sería extremadamente ineficiente (como 10 × desaceleración)
Nayuki

Respuestas:

47

Si no le importa el tiempo de ejecución, cualquier cosa que pueda hacer en una máquina de varios núcleos, puede hacerlo en una máquina de un solo núcleo. Una máquina multinúcleo es solo una forma de acelerar algunos tipos de cálculos.

Si puede resolver un problema en el tiempo en una máquina de múltiples núcleos con n núcleos, entonces puede resolverlo en el tiempo T n (o menos, observe la ley de Amdahl ) en una máquina de un solo núcleo. La máquina de un solo núcleo puede emular una máquina de múltiples núcleos utilizando el corte de tiempo / tiempo compartido .TnTn

DW
fuente
3
No estoy completamente seguro de que eso sea absolutamente correcto. No creo que se puedan generar errores de consistencia de memoria en un solo núcleo (Sí, uno podría emular un sistema multicache en unicore, pero esa indirección es una especie de trampa). (¿Quizás un equivalente a implementar el intercambio de registros mediante operaciones de movimiento en un VLIW, explotando el isma || garantizado?) Supongo que incluso en un núcleo de un solo subproceso aún sería posible extraer entropía de la variabilidad de temporización multiproceso, pero la cantidad de la entropía sería menor por unidad de tiempo (que en realidad es solo una cuestión de rendimiento como las otras diferencias).
Paul A. Clayton
66
@ PaulA.Clayton Los errores de consistencia de la memoria generalmente no son deseados y el software bien escrito no debe exhibirlos. Sin embargo, si realmente quisiera, podría emularlos en una sola CPU. (Aunque puede ser lento)
user253751
44
nn
11
"La máquina de un solo núcleo puede emular una máquina de múltiples núcleos mediante el uso de tiempo compartido / tiempo compartido". Y de hecho lo he hecho desde los albores del sistema operativo "moderno".
Lightness compite con Monica el
1
@ PaulA.Clayton Creo que podría tener problemas de consistencia de memoria (como un incremento no atómico) si tuviera dos procesos diferentes que modificaran la misma memoria compartida. Solo necesita una multitarea preventiva. Por supuesto, esto es generalmente por qué los sistemas operativos modernos no tienen procesos que compartan la misma memoria de escritura a menos que lo soliciten explícitamente.
Patrick M
58

La pregunta es: ¿bajo qué restricciones?

Ciertamente, hay problemas en los que, si hacemos la pregunta "¿podemos resolver este problema en el hardware X en el tiempo dado", la respuesta será no.

Pero esta no es una respuesta "a prueba de futuro": las cosas que en el pasado no se podían hacer lo suficientemente rápido en un solo núcleo probablemente puedan ser ahora, y no podemos predecir de qué será capaz el hardware futuro.

En términos de computabilidad, sabemos que una máquina de Turing de una sola cinta es capaz de calcular las mismas funciones que una computadora de uno o varios núcleos, por lo que, aparte del tiempo de ejecución, no hay problemas que una computadora de varios núcleos pueda resolver que un solo núcleo no puede.

En términos de algo como gráficos, literalmente todo lo que está en la GPU podría hacerse en la CPU ... si está dispuesto a esperar lo suficiente.

jmite
fuente
3
@ JanDvorak De hecho, diría que esto no lo hace la GPU;)
TomTom
15
Si el tiempo no es una limitación, puede hacer todos los cálculos a mano, lápiz y papel.
mathreadler
2
@mathreadler Sí, porque el cerebro está Turing completo. Algo que se convirtió en un largo debate sobre Physics Stackexchange.
JBentley
44
En realidad, @JanDvorak, generando VGA es bastante sencillo y se puede realizar en software en un controlador de micro humilde 16 MHz, ya que este proyecto shows: pyroelectro.com/tutorials/arduino_basic_vga
axello
3
@mathreadler Esa es en realidad una pregunta más complicada de lo que parece. Una respuesta corta podría ser "sí" porque una máquina especializada puede construir una computadora sin requerir herramientas completas para hacerlo. Una respuesta más larga podría ser "no", porque la capacidad de construir una máquina de turing puede implicar que uno tiene una máquina de turing más grande que está en un estado de "inicialización" donde construye el resto de la máquina de estados. La respuesta completa es aún más complicada porque nunca hemos construido un dispositivo Turing Complete. Hemos desarrollado ideas abstractas para máquinas que son ...
Cort Ammon
17

Como han señalado otras respuestas, una sola CPU siempre puede emular múltiples CPU al reducir el tiempo y desempeñar el papel de cada CPU virtual. Esta emulación ciertamente calculará las respuestas correctas.

En el mundo real, el tiempo de ejecución puede ser importante. Podría significar la diferencia entre una velocidad de fotogramas mediocre y una experiencia visual estelar. O la diferencia entre ganancias y pérdidas en el comercio.

Una situación patológica en la que un multiprocesador es mucho más rápido que un uniprocesador es donde el procesamiento es una tubería de datos, el cambio de contexto es costoso y el código de máquina para cada etapa de tubería apenas cabe en el caché de una CPU.

Déjame ilustrar con algunos números. Suponga que tiene una tubería de datos (representación 3D, etc.) que tiene 4 etapas de procesamiento, cada etapa tiene 256 KiB de código de programa y convenientemente tiene 4 CPU con 256 KiB de caché L2. Si intenta ejecutar este procesamiento en una sola CPU, cambiar entre las 4 tareas será costoso e implicará grandes errores de caché. Por otro lado, si lo ejecuta en un sistema de 4 núcleos, el cálculo podría ser muy sencillo, las pérdidas de caché son mínimas y los cambios de contexto son inexistentes. (Como nota al margen, esto está relacionado con la noción de fijar ciertas aplicaciones a ciertos núcleos, por ejemplo, solo realizar operaciones del núcleo del sistema operativo en un núcleo, o manejo de TCP / IP, etc.)

Nayuki
fuente
7

Es mucho más difícil desarrollar carreras de datos realmente nefastas con una sola CPU. Quiero decir, claro, puedes lograr un desgarro entre palabras si interrumpes una sola CPU, pero ¿puedes construir escenarios exóticos donde no haya un solo entrelazado de hilos que haga lo que quieres?

De acuerdo, tal vez hacer errores insidiosos no cuenta como un uso válido de los avances de múltiples códigos. Como resultado, no hay mucho que mutli-core pueda hacer que un solo núcleo no pueda dar tiempo. El motivo es simple. Si intenta evitar esas razas de datos malvados, debe tener puntos de sincronización en su código. Si modela su código como una red de cómputos donde las entradas deben estar completas y sincronizadas antes de que pueda calcular y producir salidas, es fácil ver que una sola CPU simplemente puede avanzar a lo largo de la red, calculando el siguiente bloque de trabajo disponible .

De hecho, si puede demostrar que su algoritmo puede ser resuelto por una máquina de Turing (que es prácticamente todos los algoritmos que nos interesan), se puede demostrar que el algoritmo puede hacerlo no solo una CPU de núcleo único, sino que de hecho máquina de estado con un trozo de cinta muy largo para la memoria!

El AJEDREZ detector de carrera realmente aprovecha esto para encontrar casos de carrera. Ejecuta todo de una sola hebra y explora sistemáticamente todas las posibles intercalaciones entre subprocesos, tratando de encontrar casos en los que una prueba falle debido a un caso de carrera. CHESS depende del hecho de que puede ejecutar cualquier aplicación multiproceso en un solo núcleo.

Los casos en los que necesita multinúcleo aparecen cuando comienza a extender los límites del hardware. La obvia es cuando tienes limitaciones de tiempo. Algunos problemas con restricciones de tiempo real son imposibles de hacer con un solo núcleo porque simplemente no pueden manejar el reloj de un solo núcleo lo suficientemente rápido. Hay una razón por la cual las CPU subieron hasta 4Ghz y luego se asentaron un poco, prefiriendo más núcleos a velocidades más bajas.

Una versión más exótica de esta restricción de tiempo está en los sistemas de tiempo real duro. En algunos sistemas difíciles en tiempo real, el servicio de interrupciones es tan exigente que realmente tiene que elegir una CPU de múltiples núcleos que le permita dividir las interrupciones en los núcleos, o se encuentra con limitaciones de tiempo.

Otro límite surge con los buses de datos. Considere el Blue Gene / P como ejemplo. JUGENE, una supercomputadora Blue Gene / P particular, tiene 144 terabytes de memoria. Simplemente no hacen computadoras con una sola CPU que puedan acceder a toda esa memoria.

Cort Ammon
fuente
1
Re, simplemente no hacen computadoras con una sola CPU que puedan acceder a [tanta] memoria. "No" no es lo mismo que "no puedo". Usted podría diseñar y construir un solo procesador con 144 terabytes o más de memoria principal. La única razón por la que las personas no lo hacen es por los rendimientos decrecientes: el valor incremental y práctico de agregar más memoria a un diseño de procesador único alcanza un pico en algún momento y luego disminuye a medida que aumenta el tamaño de la memoria, mientras que el costo incremental permanece constante .
Solomon Slow
@jameslarge Esa sería la razón por la que esa oración apareció en la parte de mi respuesta sobre el hardware práctico de la vida real, y por qué no apareció en los primeros 2/3 de la respuesta que discutió las capacidades teóricas.
Cort Ammon
"No" versus "No puedo" se ilustra con dos sistemas en mi sótano. Si pudiera agregar físicamente tanta memoria a sus configuraciones de hardware, sus CPU "podrían" acceder a cada byte. Pero no puedo, así que ellos "no pueden". Las capacidades de las CPU están más allá de lo práctico.
user2338816
Estaba pensando en algo como esta respuesta. Parece que las condiciones de carrera serían imposibles (o sucederían el 100% del tiempo) en un entorno de un solo núcleo. En cuanto a una aplicación práctica, teorizo ​​que un desarrollador de software podría diseñar una forma única de protección de copia mediante la codificación de alguna prueba de condición de carrera extraña que siempre pasaría en el hardware objetivo específico, pero fallaría en el hardware emulado ejecutado por un solo núcleo . En este caso, la emulación por un sistema de múltiples núcleos probablemente pasaría a veces, pero de manera poco confiable.
Dan Henderson
6

Si necesita observar un proceso que se ejecuta en un solo elemento de procesamiento sin alterar su comportamiento en tiempo real (o lo menos posible), como para la evaluación comparativa o el registro de actividades, probablemente necesitará un recurso de procesamiento separado.

Yves Daoust
fuente
Bonito y conciso ejemplo de algo que requeriría una emulación precisa si no múltiples procesadores
Ben Leggiero
Oye, ¿es esta tu cuenta? ¿Te gustaría fusionarlo?
Mal
4

Las otras respuestas se adhieren a la visión limitada del paralelismo como "concurrencia distribuida". Esto da algunas respuestas: en un modelo limpio de cómputo a la Turing, los núcleos múltiples no ofrecen una ventaja; La única ventaja que puede obtener es la eficiencia.

Hay las múltiples unidades de procesamiento de una cosa (pus) pueden hacer que uno solo no puede, sin embargo: ejecutar operaciones en paralelo , que es al mismo tiempo .

Eso es muy útil si ejecuta varios programas al mismo tiempo. Por supuesto, es muy raro que necesite absolutamente más que la ejecución concurrente, y la mayoría de los usos se reducen a una mayor eficiencia. Pero no es esta diferencia.

Supongamos que necesita procesar datos del sensor de datos de múltiples fuentes en tiempo real. Sea lo que sea que eso signifique precisamente en su aplicación, una PU solo puede manejar tantos flujos de entrada simultáneamente sin violar su límite de tiempo de respuesta. Por lo tanto, necesita múltiples PU una vez que tenga demasiados sensores para su generación actual de PU.

k

kkk

Rafael
fuente
0

desde un punto de vista de CS, "multinúcleo" no es tan diferente en teoría que "computación distribuida". El concepto básico es "elementos informáticos independientes (que computan en paralelo". Por lo tanto, reformular ligeramente la pregunta ("multinúcleo" no es realmente un concepto teórico en CS) conduce a otras posibilidades. Como se señaló en otras respuestas, la programación secuencial es equivalente a la programación paralela desde un punto de vista de CS. Esto se remonta a la definición del sistema teórico para la computación, es decir, una máquina de Turing. El análisis teórico del rendimiento de CS es, en última instancia, en términos de TMs donde la distinción de paralelo versus secuencial no se aplica realmente ( aunque existe una analogía aproximada con TM multitape ).

pero teniendo en cuenta esta pregunta de manera menos abstracta, la computación distribuida es de hecho superior o posiblemente casi necesaria para algunos problemas relacionados con la tolerancia a fallas . En esta área hay un concepto que se aplica cuando / donde se considera que los elementos informáticos independientes tienen cierto grado de falta de fiabilidad (esto no es realmente una suposición universalmente aplicable para todos los contextos). Aquí hay varios casos donde la tolerancia a fallas se mejora o incluso requiere elementos informáticos independientes.

  • tenga en cuenta que cada procesador tiene una probabilidad independiente "[x]%" de fallar durante el cálculo. Se puede diseñar un sistema mediante el cual, a través de la comunicación, la tolerancia general a fallas del sistema sea superior a los componentes individuales. Esto se aplicó hace muchas décadas, por ejemplo, en los sistemas de transbordadores espaciales. Más recientemente, existen protocolos básicos diseñados para utilizarlo, por ejemplo, Paxos, que resuelven el llamado problema de consenso . Un ejemplo más realista es Google, que tiene muchos algoritmos patentados para construir esencialmente su (s) supercomputadora (s) a partir de elementos no confiables individualmente junto con algoritmos tolerantes a fallas.

  • Bitcoin implica transacciones distribuidas para calcular el libro mayor y eso no se debe simplemente a problemas de carga de procesamiento. El algoritmo está cuidadosamente diseñado para frustrar los nodos corruptos. en resumen, "resuelve" / implementa el problema de los generales bizantinos que no se trata simplemente de maximizar el rendimiento paralelo, implica que las entidades independientes "se controlen" entre sí y "algorítmicamente / criptográficamente / de manera segura" rechacen los cálculos inválidos, también conocidos como una especie de "trampa" o " corrupción".

  • un análisis clásico de paralelismo concluye que hay alrededor de 7 tipos de patrones de problemas "fundamentales" que se descomponen en desgloses particulares de ejecución paralela. ver El panorama de la investigación en computación paralela: una visión desde Berkeley

  • Aquí hay algún elemento de una pregunta teórica abierta que incluye consideraciones de rendimiento en la mayoría de las otras respuestas. La cuestión de si hay algún problema que sea "inherentemente más rápido" en paralelo que secuencial también se conoce más o menos como el problema P =? NC donde NC se considera la clase de algoritmos "eficientemente paralelizables" y P es algoritmos "eficientes [secuenciales] "

vzn
fuente
1
¡Me encanta esta respuesta! Aprendí mucho de tus ejemplos: D
Ben Leggiero
+1 para tolerancia a fallas en entornos de misión crítica con radiación, -1 por falta de límites y redundancia.
Cees Timmerman