¿Cómo se ejecuta un solo hilo en múltiples núcleos?

61

Estoy tratando de entender, a un alto nivel, cómo los hilos individuales se ejecutan en múltiples núcleos. A continuación se muestra mi mejor comprensión. Sin embargo, no creo que sea correcto.

Según mi lectura de Hyper-threading , parece que el sistema operativo organiza las instrucciones de todos los subprocesos de tal manera que no se estén esperando el uno al otro. Luego, el front-end de la CPU organiza aún más esas instrucciones distribuyendo un subproceso a cada núcleo y distribuye instrucciones independientes de cada subproceso entre los ciclos abiertos.

Entonces, si solo hay un hilo único, entonces el sistema operativo no hará ninguna optimización. Sin embargo, el front-end de la CPU distribuirá conjuntos de instrucciones independientes entre cada núcleo.

De acuerdo con https://stackoverflow.com/a/15936270 , un lenguaje de programación específico puede crear más o menos hilos, pero es irrelevante al determinar qué hacer con esos hilos. El sistema operativo y la CPU manejan esto, por lo que esto sucede independientemente del lenguaje de programación utilizado.

ingrese la descripción de la imagen aquí

Solo para aclarar, estoy preguntando sobre un solo hilo que se ejecuta en múltiples núcleos, no sobre la ejecución de múltiples hilos en un solo núcleo.

¿Qué hay de malo en mi resumen? ¿Dónde y cómo se dividen las instrucciones de un hilo entre múltiples núcleos? ¿Importa el lenguaje de programación? Sé que este es un tema amplio; Espero una comprensión de alto nivel de ello.

Evorlor
fuente
66
Un conjunto de instrucciones para un solo hilo de software puede ejecutarse en muchos núcleos, pero no a la vez.
Kroltan
1
Está mezclando subprocesos de software (que incluyen el programador del sistema operativo) y subprocesos de hardware o HyperThreading (una función de CPU que hace que un núcleo se comporte como dos).
ugoren 01 de
2
Tengo 20 conductores y 4 camiones. ¿Cómo es posible que un conductor pueda entregar paquetes con dos camiones? ¿Cómo es posible que un camión pueda tener múltiples conductores? La respuesta a ambas preguntas es la misma. Turnarse.
Eric Lippert

Respuestas:

84

El sistema operativo ofrece segmentos de tiempo de CPU a subprocesos que son elegibles para ejecutarse.

Si solo hay un núcleo, el sistema operativo programa el subproceso más elegible para que se ejecute en ese núcleo durante un intervalo de tiempo. Después de completar un intervalo de tiempo, o cuando el subproceso en ejecución se bloquea en E / S, o cuando el procesador se ve interrumpido por eventos externos, el sistema operativo reevalúa qué subproceso se ejecutará a continuación (y podría elegir el mismo subproceso o uno diferente).

La elegibilidad para ejecutar consiste en variaciones de equidad, prioridad y disponibilidad, y por este método varios hilos obtienen segmentos de tiempo, algunos más que otros.

Si hay varios núcleos, N, entonces el sistema operativo programa los N hilos más elegibles para que se ejecuten en los núcleos.

La afinidad del procesador es una consideración de eficiencia. Cada vez que una CPU ejecuta un subproceso diferente que antes, tiende a disminuir un poco porque su caché está caliente para el subproceso anterior, pero frío para el nuevo. Por lo tanto, ejecutar el mismo subproceso en el mismo procesador durante numerosos intervalos de tiempo es una ventaja de eficiencia.

Sin embargo, el sistema operativo es libre de ofrecer segmentos de tiempo de un hilo en diferentes CPU, y podría rotar a través de todas las CPU en diferentes segmentos de tiempo. Sin embargo, no puede, como dice @ gnasher729 , ejecutar un hilo en múltiples CPU simultáneamente.

Hyperthreading es un método en hardware mediante el cual un solo núcleo de CPU mejorado puede admitir la ejecución de dos o más subprocesos diferentes simultáneamente. (Dicha CPU puede ofrecer subprocesos adicionales a menor costo en bienes raíces de silicio que los núcleos completos adicionales). Este núcleo de CPU mejorado debe admitir un estado adicional para los otros subprocesos, como los valores de registro de la CPU, y también tiene un estado y comportamiento de coordinación que permite compartir unidades funcionales dentro de esa CPU sin combinar los hilos.

Hyperthreading, aunque técnicamente es un desafío desde la perspectiva del hardware, desde la perspectiva del programador, el modelo de ejecución es simplemente el de núcleos de CPU adicionales en lugar de algo más complejo. Por lo tanto, el sistema operativo ve núcleos de CPU adicionales, aunque hay algunos nuevos problemas de afinidad con el procesador, ya que varios subprocesos con hiperprocesos comparten la arquitectura de caché de un núcleo de CPU.


Podríamos pensar ingenuamente que dos subprocesos que se ejecutan en un núcleo hiperprocesado corren la mitad de rápido que cada uno con su propio núcleo completo. Pero este no es necesariamente el caso, ya que la ejecución de un solo subproceso está llena de ciclos de holgura, y el otro subproceso hiperprocesado puede utilizar cierta cantidad de ellos. Además, incluso durante los ciclos sin holgura, un subproceso puede estar utilizando unidades funcionales diferentes que el otro, por lo que puede ocurrir una ejecución simultánea. La CPU mejorada para hyperthreading puede tener algunas unidades funcionales muy usadas, especialmente para soportar eso.

Erik Eidt
fuente
3
"Por lo tanto, ejecutar el mismo subproceso en el mismo procesador durante numerosos intervalos de tiempo es una ventaja de eficiencia". ¿No tendrían que ser segmentos de tiempo contiguos ? De lo contrario, los cachés serían borrados por otros hilos, ¿no? +1 para una buena explicación.
jpmc26
2
@Luaan: HT a menudo es bueno, pero la situación no es tan simple como usted describe. El ancho de banda del problema de front-end (4 uops por reloj en Intel, 6 en Ryzen) se comparte por igual entre los subprocesos (a menos que uno esté estancado). Si ese es el cuello de botella, entonces, como dije, HT no ayudará en absoluto. No es raro que Skylake se acerque a eso en un bucle bien ajustado, si hay una mezcla de cargas, ALU y tiendas ... Los transistores son baratos (y no todos pueden cambiar a la vez o la CPU se derretiría), así que las CPU x86 modernas tienen más puertos de ejecución de los que puede alimentar el front-end (con muchas unidades de ejecución que se replican ...
Peter Cordes
2
... en múltiples puertos) ... Esto puede parecer un desperdicio, pero a menudo un bucle solo usará un tipo de unidad de ejecución de ALU a la vez, por lo que tener duplicados de todo significa que cualquier tipo de código que se esté ejecutando, hay múltiples puertos para sus instrucciones. Entonces, la razón que citó para beneficiarse de HT no es tan común, ya que la mayoría del código tiene algunas cargas y / o tiendas que ocupan ancho de banda frontal, y lo que queda a menudo no es suficiente para saturar las unidades de ejecución.
Peter Cordes
2
@Luaan: Además, en las CPU Intel, las unidades de ejecución entera y FP / vector comparten los mismos puertos de ejecución . Por ejemplo, las unidades FP FMA / mul / add están en los puertos 0/1. Pero el multiplicador entero también está en el puerto 1, y las operaciones enteras simples pueden ejecutarse en cualquiera de los 4 puertos de ejecución (diagrama en mi respuesta). Un segundo subproceso que usa el ancho de banda del problema los ralentizará a ambos, incluso si no compiten por las unidades de ejecución, pero a menudo hay una ganancia de rendimiento neto si no compiten demasiado por el caché. Incluso el código de alto rendimiento bien sintonizado como x264 / x265 (codificadores de video) se beneficia alrededor del 15% en Skylake de HT.
Peter Cordes
3
@luaan Además de lo que dijo Peter, su afirmación de que "Ese fue el razonamiento original detrás de HT" es incorrecta. El razonamiento original detrás de HT era que la microarquitectura NetBurst había alargado la tubería hasta un punto tan extremo (con el propósito de aumentar la velocidad del reloj) que las predicciones erróneas de las ramas y otras burbujas de tubería mataron el rendimiento. HT fue una de las soluciones de Intel para minimizar la cantidad de tiempo que las unidades de ejecución de este gran y costoso chip permanecieron inactivas debido a las burbujas en la tubería: el código de otros hilos podría insertarse y ejecutarse en esos agujeros.
Cody Gray
24

No existe un solo subproceso que se ejecute en múltiples núcleos simultáneamente.

Sin embargo, no significa que las instrucciones de un hilo no puedan ejecutarse en paralelo. Existen mecanismos llamados canalización de instrucciones y ejecución fuera de orden que lo permiten. Cada núcleo tiene muchos recursos redundantes que no se utilizan con instrucciones simples, por lo que se pueden ejecutar múltiples instrucciones juntas (siempre que la siguiente no dependa del resultado anterior). Sin embargo, esto todavía ocurre dentro de un solo núcleo.

Hyper-threading es una variante extrema de esta idea, en la que un núcleo no solo ejecuta instrucciones de un hilo en paralelo, sino que mezcla instrucciones de dos hilos diferentes para optimizar aún más el uso de los recursos.

Entradas relacionadas de Wikipedia: Canalización de instrucciones , ejecución fuera de orden .

Frax
fuente
3
¿No pueden correr simultáneamente, pero pueden correr en paralelo? ¿No son estos lo mismo?
Evorlor
10
@Evorlor La clave aquí es la diferencia entre un núcleo y una unidad de ejecución. Un solo subproceso solo puede ejecutarse en un núcleo, pero un procesador puede usar análisis dinámico para determinar qué instrucciones ejecutadas por un núcleo no dependen unas de otras y ejecutarlas simultáneamente en diferentes unidades de ejecución. Un núcleo puede tener varias unidades de ejecución.
user1937198
3
@Evorlor: una CPU desordenada puede encontrar y explotar el paralelismo a nivel de instrucción dentro del flujo de instrucciones de un solo hilo. por ejemplo, a menudo las instrucciones que actualizan un contador de bucle son independientes de otros trabajos que realiza un bucle. O en un a[i] = b[i] + c[i]bucle, cada iteración es independiente, por lo que cargas, adiciones y almacenes de diferentes iteraciones pueden estar en vuelo a la vez. Tiene que preservar la ilusión de que las instrucciones se ejecutan en orden de programa, pero por ejemplo, una tienda que se pierde en la memoria caché no retrasa el hilo (hasta que se quede sin espacio en el búfer de la tienda).
Peter Cordes
3
@ user1937198: La frase "análisis dinámico" se adaptaría mejor a un compilador JIT. Las CPU fuera de servicio realmente no analizan; Es más como un algoritmo codicioso que ejecuta cualquier instrucción que haya sido decodificada y emitida y tenga sus entradas listas. (La ventana de reordenamiento fuera de orden está limitada por unos pocos recursos de microarquitectura, por ejemplo, Intel Sandybridge tiene un tamaño de Reorden Buffer de 168 uops. Consulte también la medición experimental del tamaño de ROB ). Todo implementado con máquinas de estado de hardware para manejar 4 uops por reloj.
Peter Cordes
3
@Luaan, sí, fue una idea interesante, pero los compiladores de AOT todavía no son lo suficientemente inteligentes como para explotarla por completo. Además, Linus Torvalds (y otros) han argumentado que exponer que gran parte de la parte interna de la tubería es una gran restricción para los diseños futuros. por ejemplo, realmente no puede aumentar el ancho de la tubería sin cambiar el ISA. O bien, crea una CPU que rastrea las dependencias de la manera habitual, y tal vez emite dos grupos VLIW en paralelo, pero luego ha perdido el beneficio de la complejidad de la CPU de EPIC pero aún tiene las desventajas (ancho de banda de problemas perdidos cuando el compilador no puede llenarse) una palabra).
Peter Cordes
22

resumen: encontrar y explotar el paralelismo (nivel de instrucción) en un programa de subproceso único se realiza únicamente en hardware, por el núcleo de la CPU en el que se ejecuta. Y solo a través de una ventana de un par de cientos de instrucciones, no reordenamiento a gran escala.

Los programas de un solo subproceso no obtienen ningún beneficio de las CPU de varios núcleos, excepto que otras cosas pueden ejecutarse en los otros núcleos en lugar de quitarle tiempo a la tarea de un solo subproceso.


El sistema operativo organiza las instrucciones de todos los subprocesos de tal manera que no se estén esperando el uno al otro.

El sistema operativo NO mira dentro de las secuencias de instrucciones de subprocesos. Solo programa hilos a núcleos.

En realidad, cada núcleo ejecuta la función del planificador del sistema operativo cuando necesita averiguar qué hacer a continuación. La programación es un algoritmo distribuido. Para comprender mejor las máquinas multinúcleo, piense que cada núcleo ejecuta el núcleo por separado. Al igual que un programa de subprocesos múltiples, el núcleo está escrito de modo que su código en un núcleo pueda interactuar de manera segura con su código en otros núcleos para actualizar las estructuras de datos compartidos (como la lista de subprocesos que están listos para ejecutarse.

De todos modos, el sistema operativo está involucrado en ayudar a los procesos de subprocesos múltiples a explotar el paralelismo a nivel de subproceso que debe exponerse explícitamente escribiendo manualmente un programa de subprocesos múltiples . (O mediante un compilador de paralelización automática con OpenMP o algo así).

Luego, el front-end de la CPU organiza aún más esas instrucciones distribuyendo un subproceso a cada núcleo y distribuye instrucciones independientes de cada subproceso entre los ciclos abiertos.

Un núcleo de la CPU solo ejecuta una secuencia de instrucciones, si no se detiene (dormido hasta la próxima interrupción, por ejemplo, la interrupción del temporizador). A menudo es un subproceso, pero también podría ser un controlador de interrupción del kernel o un código de kernel misceláneo si el kernel decidió hacer algo más que simplemente regresar al subproceso anterior después de manejar e interrumpir o llamar al sistema.

Con HyperThreading u otros diseños SMT, un núcleo de CPU físico actúa como múltiples núcleos "lógicos". La única diferencia desde la perspectiva del sistema operativo entre una CPU quad-core-with-hyperthreading (4c8t) y una máquina simple de 8 núcleos (8c8t) es que un sistema operativo compatible con HT intentará programar subprocesos para separar los núcleos físicos para que no No compiten entre ellos. Un sistema operativo que no sabía sobre hyperthreading solo vería 8 núcleos (a menos que desactive HT en el BIOS, entonces solo detectaría 4).


El término " front-end" se refiere a la parte de un núcleo de CPU que obtiene código de máquina, decodifica las instrucciones y las emite en la parte fuera de servicio del núcleo . Cada núcleo tiene su propio front-end, y es parte del núcleo como un todo. Las instrucciones que obtiene son lo que la CPU está ejecutando actualmente.

Dentro de la parte fuera de orden del núcleo, las instrucciones (o uops) se envían a los puertos de ejecución cuando sus operandos de entrada están listos y hay un puerto de ejecución libre. Esto no tiene que suceder en el orden del programa, así es como una CPU OOO puede explotar el paralelismo a nivel de instrucción dentro de un solo hilo .

Si reemplaza "núcleo" con "unidad de ejecución" en su idea, está cerca de corregir. Sí, la CPU distribuye instrucciones / uops independientes a las unidades de ejecución en paralelo. (Pero hay una confusión de terminología, ya que dijiste "front-end" cuando realmente es el programador de instrucciones de la CPU, también conocido como Reservation Station, que selecciona las instrucciones listas para ejecutar).

La ejecución fuera de orden solo puede encontrar ILP en un nivel muy local, solo hasta un par de cientos de instrucciones, no entre dos bucles independientes (a menos que sean cortos).


Por ejemplo, el equivalente asm de este

int i=0,j=0;
do {
    i++;
    j++;
} while(42);

funcionará casi tan rápido como el mismo bucle, incrementando solo un contador en Intel Haswell. i++solo depende del valor anterior de i, mientras que j++solo depende del valor anterior de j, por lo que las dos cadenas de dependencia pueden ejecutarse en paralelo sin romper la ilusión de que todo se ejecuta en el orden del programa.

En x86, el bucle se vería así:

top_of_loop:
    inc eax
    inc edx
    jmp .loop

Haswell tiene 4 puertos de ejecución de enteros, y todos ellos tienen unidades sumadoras, por lo que puede soportar un rendimiento de hasta 4 incinstrucciones por reloj si son independientes. (Con latencia = 1, solo necesita 4 registros para maximizar el rendimiento manteniendo 4 incinstrucciones en vuelo. Compare esto con el vector-FP MUL o FMA: latencia = 5 rendimiento = 0.5 necesita 10 acumuladores de vectores para mantener 10 FMA en vuelo para maximizar el rendimiento. Y cada vector puede ser 256b, con 8 flotadores de precisión simple).

La rama tomada también es un cuello de botella: un bucle siempre toma al menos un reloj completo por iteración, porque el rendimiento de la rama tomada está limitado a 1 por reloj. Podría poner una instrucción más dentro del ciclo sin reducir el rendimiento, a menos que también lea / escriba eaxo edxen cuyo caso alargaría esa cadena de dependencia. Poner 2 instrucciones más en el bucle (o una instrucción compleja multi-uop) crearía un cuello de botella en el front-end, ya que solo puede emitir 4 uops por reloj en el núcleo fuera de servicio. (Consulte estas preguntas y respuestas sobre SO para obtener algunos detalles sobre lo que sucede con los bucles que no son múltiplos de 4 uops: el bucle de bucle y el caché de uop hacen que las cosas sean interesantes)


En casos más complejos, encontrar el paralelismo requiere mirar una ventana más grande de instrucciones . (por ejemplo, tal vez hay una secuencia de 10 instrucciones que dependen unas de otras, luego algunas independientes).

La capacidad del búfer de reordenamiento es uno de los factores que limita el tamaño de la ventana fuera de orden. En Intel Haswell, son 192 uops. (E incluso puede medirlo experimentalmente , junto con la capacidad de cambio de nombre de registro (tamaño de archivo de registro)). Los núcleos de CPU de baja potencia como ARM tienen tamaños de ROB mucho más pequeños, si es que se ejecutan fuera de orden.

También tenga en cuenta que las CPU deben ser canalizadas, así como fuera de servicio. Por lo tanto, tiene que buscar y decodificar las instrucciones mucho antes de las que se están ejecutando, preferiblemente con un rendimiento suficiente para rellenar las memorias intermedias después de perder cualquier ciclo de recuperación. Las ramas son complicadas, porque no sabemos de dónde buscarlas si no sabemos en qué dirección se fue una rama. Es por eso que la predicción de ramas es tan importante. (Y por qué las CPU modernas usan ejecución especulativa: adivinan en qué dirección irá una rama y comienzan a buscar / decodificar / ejecutar ese flujo de instrucciones. Cuando se detecta una predicción errónea, vuelven al último estado bueno conocido y se ejecutan desde allí).

Si desea leer más sobre los componentes internos de la CPU, hay algunos enlaces en el wiki de la etiqueta Stackoverflow x86 , incluida la guía de microarquitectura de Agner Fog y las descripciones detalladas de David Kanter con diagramas de CPU de Intel y AMD. De su informe de microarquitectura Intel Haswell , este es el diagrama final de toda la tubería de un núcleo Haswell (no todo el chip).

Este es un diagrama de bloques de un solo núcleo de CPU . Una CPU de cuatro núcleos tiene 4 de estos en un chip, cada uno con sus propios cachés L1 / L2 (compartiendo un caché L3, controladores de memoria y conexiones PCIe a los dispositivos del sistema).

Tubería completa de Haswell

Sé que esto es abrumadoramente complicado. El artículo de Kanter también muestra partes de esto para hablar sobre la interfaz por separado de las unidades de ejecución o los cachés, por ejemplo.

Peter Cordes
fuente
2
"Encontrar y explotar el paralelismo (nivel de instrucción) en un programa de un solo subproceso se realiza únicamente en hardware" Tenga en cuenta que esto solo se aplica a los ISA convencionales, no a los VLIW en los que el compilador o programador determina la ILP completamente, o cooperativamente entre el hardware y software.
Hadi Brais
1
@ user7813604: sí. Hyperthreading no puede paralelizar un solo hilo. Hace lo contrario: ejecuta múltiples subprocesos en un núcleo, lo que reduce el rendimiento por subproceso pero aumenta el rendimiento general.
Peter Cordes
1
@ user7813604: El objetivo principal de ILP es encontrar qué instrucciones se pueden ejecutar en paralelo mientras se mantiene la ilusión de que cada instrucción se ejecutó en orden, cada una terminando antes de que comience la siguiente. Una CPU canalizada escalar puede necesitar detenerse a veces por dependencias si la latencia es mayor que 1. Pero es un problema aún mayor para las CPU superescalares.
Peter Cordes
1
@ user7813604: sí, mi respuesta literalmente lo usa como ejemplo. Haswell, por ejemplo, puede ejecutar hasta 4 incinstrucciones en el mismo ciclo de reloj, a sus 4 unidades enteras de ejecución de ALU.
Peter Cordes
1
@ user7813604: Sí, ILP es cuánto se puede ejecutar en paralelo. Una CPU real tendrá una capacidad limitada para encontrar y explotar ILP ejecutándola en paralelo en un solo núcleo, por ejemplo, superescalar de hasta 4 de ancho en Intel. Esta respuesta trata de explicar eso con ejemplos.
Peter Cordes