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

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.

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.

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.

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 .

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).

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.