Como um único thread é executado em vários núcleos?

Estou tentando entender, em alto nível, como threads únicos são executados em vários núcleos. Abaixo está o meu melhor entendimento. Eu não acredito que esteja correto.

Com base na minha leitura do Hyper-threading , parece que o sistema operacional organiza as instruções de todos os threads de forma que eles não estejam esperando um pelo outro. Em seguida, o front-end da CPU organiza ainda mais essas instruções distribuindo um encadeamento para cada núcleo e distribui instruções independentes de cada encadeamento entre quaisquer ciclos abertos.

Portanto, se houver apenas um thread, o sistema operacional não fará nenhuma otimização. No entanto, o front-end da CPU distribuirá conjuntos de instruções independentes entre cada núcleo.

De acordo com https://stackoverflow.com/a/15936270 , uma linguagem de programação específica pode criar mais ou menos threads, mas é irrelevante ao determinar o que fazer com esses threads. O sistema operacional e a CPU lidam com isso, então isso acontece independentemente da linguagem de programação usada.

Apenas para esclarecer, estou perguntando sobre um único thread executado em vários núcleos, não sobre a execução de vários threads em um único núcleo.

O que há de errado com o meu resumo? Onde e como as instruções de um thread são divididas em vários núcleos? A linguagem de programação é importante? Eu sei que este é um assunto amplo; Espero uma compreensão de alto nível disso.

O sistema operacional oferece intervalos de tempo de CPU para threads elegíveis para execução.

Se houver apenas um núcleo, o sistema operacional agendará o encadeamento mais qualificado para execução nesse núcleo por um intervalo de tempo. Após a conclusão de um intervalo de tempo, ou quando o encadeamento em execução é bloqueado no IO ou quando o processador é interrompido por eventos externos, o sistema operacional reavalia o encadeamento a ser executado a seguir (e pode escolher o mesmo encadeamento novamente ou outro diferente).

A elegibilidade para executar consiste em variações de justiça, prioridade e prontidão, e por esse método vários threads obtêm intervalos de tempo, alguns mais que outros.

Se houver vários núcleos, N, o sistema operacional agendará os N threads mais elegíveis para execução nos núcleos.

A afinidade do processador é uma consideração de eficiência. Cada vez que uma CPU executa um encadeamento diferente do que antes, tende a desacelerar um pouco porque seu cache é quente para o encadeamento anterior, mas frio para o novo. Portanto, executar o mesmo encadeamento no mesmo processador em vários intervalos de tempo é uma vantagem de eficiência.

No entanto, o sistema operacional é livre para oferecer intervalos de tempo de um encadeamento em diferentes CPUs e pode alternar entre todos os CPUs em diferentes intervalos de tempo. No entanto, como @ gnasher729 diz , não pode executar um thread em várias CPUs simultaneamente.

O Hyperthreading é um método no hardware pelo qual um único núcleo aprimorado da CPU pode suportar a execução de dois ou mais threads diferentes simultaneamente. (Essa CPU pode oferecer threads adicionais a um custo mais baixo no setor imobiliário do silício do que núcleos completos adicionais.) Esse núcleo aprimorado da CPU precisa oferecer suporte a estados adicionais para outros threads, como valores de registro da CPU, e também possui estado e comportamento de coordenação que permite o compartilhamento de unidades funcionais nessa CPU sem confundir os threads.

O Hyperthreading, embora tecnicamente desafiador do ponto de vista do hardware, do ponto de vista do programador, o modelo de execução é apenas o de núcleos adicionais da CPU, em vez de algo mais complexo. Portanto, o sistema operacional vê núcleos adicionais da CPU, embora haja alguns novos problemas de afinidade do processador, pois vários encadeamentos com hyperthread estão compartilhando a arquitetura de cache de um núcleo da CPU.

Podemos pensar ingenuamente que dois encadeamentos executados em um núcleo hiperencadeado rodam metade da velocidade que cada um com seu próprio núcleo completo. Mas esse não é necessariamente o caso, uma vez que a execução de um único encadeamento está cheia de ciclos frouxos, e alguns deles podem ser usados ​​pelo outro encadeamento com hiperencadeamento. Além disso, mesmo durante ciclos sem folga, um encadeamento pode estar usando unidades funcionais diferentes das outras, para que a execução simultânea possa ocorrer. A CPU aprimorada para hyperthreading pode ter um pouco mais de algumas unidades funcionais muito usadas especialmente para dar suporte a isso.

Não existe um único thread em execução em vários núcleos simultaneamente.

No entanto, isso não significa que instruções de um thread não possam ser executadas em paralelo. Existem mecanismos chamados pipelining de instruções e execução fora de ordem que permitem isso. Cada núcleo possui muitos recursos redundantes que não são utilizados por instruções simples; portanto, várias dessas instruções podem ser executadas juntas (desde que a próxima não dependa do resultado anterior). No entanto, isso ainda acontece dentro de um único núcleo.

O hiperencadeamento é uma espécie de variante extrema dessa idéia, na qual um núcleo não apenas executa instruções de um encadeamento em paralelo, mas combina instruções de dois encadeamentos diferentes para otimizar ainda mais o uso de recursos.

Entradas relacionadas da Wikipedia: pipeline de instruções , execução fora de ordem .

resumo: A localização e a exploração do paralelismo ( em nível de instrução) em um programa de thread único é feita exclusivamente em hardware, pelo núcleo da CPU em que está sendo executado. E apenas por uma janela de algumas centenas de instruções, sem reordenar em larga escala.

Os programas de thread único não se beneficiam das CPUs com vários núcleos, exceto que outras coisas podem ser executadas nos outros núcleos, em vez de perder tempo com a tarefa de thread único.

o sistema operacional organiza as instruções de todos os threads de forma que eles não estejam esperando um pelo outro.

O SO NÃO olha dentro dos fluxos de instruções dos threads. Ele agenda somente threads para núcleos.

Na verdade, cada núcleo executa a função de agendador do sistema operacional quando precisa descobrir o que fazer a seguir. O agendamento é um algoritmo distribuído. Para entender melhor as máquinas com vários núcleos, pense em cada núcleo como executando o kernel separadamente. Assim como um programa multithread, o kernel é escrito para que seu código em um núcleo possa interagir com segurança com seu código em outros núcleos para atualizar estruturas de dados compartilhadas (como a lista de threads que estão prontos para execução.

De qualquer forma, o sistema operacional está envolvido em ajudar processos multiencadeados a explorar o paralelismo no nível de encadeamento, que deve ser explicitamente exposto escrevendo manualmente um programa multiencadeado . (Ou por um compilador de paralelismo automático com o OpenMP ou algo assim).

Em seguida, o front-end da CPU organiza ainda mais essas instruções distribuindo um encadeamento para cada núcleo e distribui instruções independentes de cada encadeamento entre quaisquer ciclos abertos.

Um núcleo de CPU está executando apenas um fluxo de instruções, se não for interrompido (adormecido até a próxima interrupção, por exemplo, interrupção do timer). Freqüentemente isso é um encadeamento, mas também pode ser um manipulador de interrupção do kernel ou um código diverso do kernel se o kernel decidir fazer algo diferente de apenas retornar ao encadeamento anterior após o tratamento e a interrupção ou chamada do sistema.

Com o HyperThreading ou outros designs SMT, um núcleo físico da CPU atua como vários núcleos "lógicos". A única diferença da perspectiva do sistema operacional entre uma CPU quad-core com hyperthreading (4c8t) e uma máquina simples de 8 núcleos (8c8t) é que um sistema operacional compatível com HT tentará agendar threads para separar núcleos físicos, para que não Não competir entre si. Um sistema operacional que não sabia sobre hyperthreading veria apenas 8 núcleos (a menos que você desabilitasse o HT no BIOS, ele detectaria apenas 4).

O termo " front-end" refere-se à parte de um núcleo da CPU que busca o código da máquina, decodifica as instruções e as emite na parte com defeito do núcleo . Cada núcleo tem seu próprio front-end e faz parte do núcleo como um todo. As instruções que busca são as que a CPU está executando no momento.

Dentro da parte fora de ordem do núcleo, instruções (ou uops) são despachadas para portas de execução quando seus operandos de entrada estão prontos e há uma porta de execução livre. Isso não precisa acontecer na ordem do programa; portanto, é assim que uma CPU OOO pode explorar o paralelismo no nível de instrução em um único encadeamento .

Se você substituir "núcleo" por "unidade de execução" em sua ideia, estará quase correto. Sim, a CPU distribui instruções independentes / unidades para unidades de execução em paralelo. (Mas há uma confusão de terminologia, já que você disse "front-end" quando realmente é o agendador de instruções da CPU, também conhecido como Estação de Reserva, que escolhe as instruções prontas para execução).

A execução fora de ordem só pode encontrar o ILP em um nível muito local, apenas algumas centenas de instruções, não entre dois loops independentes (a menos que sejam curtos).

Por exemplo, o equivalente asm deste

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

funcionará tão rápido quanto o mesmo loop, incrementando apenas um contador no Intel Haswell. i++depende apenas do valor anterior de i, enquanto j++depende apenas do valor anterior de j, portanto, as duas cadeias de dependência podem ser executadas em paralelo sem interromper a ilusão de que tudo está sendo executado na ordem do programa.

No x86, o loop seria algo como isto:

top_of_loop:
    inc eax
    inc edx
    jmp .loop

O Haswell possui 4 portas de execução inteira e todas elas possuem unidades somadoras, portanto, ele pode sustentar uma taxa de transferência de até 4 incinstruções por relógio, se todas forem independentes. (Com latência = 1, você precisa apenas de 4 registros para maximizar a taxa de transferência mantendo 4 incinstruções em voo. Compare isso com vetor FP-MUL ou FMA: latência = taxa de transferência 5 = 0,5 precisa de 10 acumuladores de vetor para manter 10 FMAs em vôo para maximizar a taxa de transferência e cada vetor pode ter 256b, mantendo 8 flutuadores de precisão única).

A ramificação obtida também é um gargalo: um loop sempre leva pelo menos um relógio inteiro por iteração, porque o rendimento da ramificação obtida é limitado a 1 por relógio. Eu poderia colocar mais uma instrução dentro do loop sem reduzir o desempenho, a menos que ele também lesse / gravasse eaxou edx, nesse caso, aumentaria a cadeia de dependência. Colocar mais duas instruções no loop (ou uma instrução multi-uop complexa) criaria um gargalo no front-end, pois ele só pode emitir 4 uops por relógio no núcleo fora de ordem. (Veja estas perguntas e respostas para obter mais detalhes sobre o que acontece com loops que não são múltiplos de 4 uops: o buffer de loop e o cache uop tornam as coisas interessantes.)

Em casos mais complexos, encontrar o paralelismo requer uma janela maior de instruções . (por exemplo, talvez exista uma sequência de 10 instruções que dependam uma da outra, depois algumas independentes).

A capacidade do buffer de reordenação é um dos fatores que limita o tamanho da janela fora de ordem. No Intel Haswell, são 192 uops. (E você pode até medi-lo experimentalmente , juntamente com a capacidade de renomeação de registros (tamanho do arquivo de registro).) Os núcleos de CPU de baixa potência, como o ARM, têm tamanhos de ROB muito menores, se executar de maneira fora de ordem.

Observe também que as CPUs precisam ser canalizadas e estar fora de ordem. Portanto, ele precisa buscar e decodificar instruções bem antes das que estão sendo executadas, de preferência com taxa de transferência suficiente para reabastecer os buffers depois de perder qualquer ciclo de busca. Os ramos são complicados, porque não sabemos de onde buscar, se não sabemos para que lado um ramo foi. É por isso que a previsão de ramificação é tão importante. (E por que as CPUs modernas usam a execução especulativa: elas adivinham o caminho que uma ramificação seguirá e começarão a buscar / decodificar / executar esse fluxo de instruções. Quando uma imprevisão é detectada, elas retornam ao último estado de bom estado e são executadas a partir daí.)

Se você quiser ler mais sobre os internos da CPU, existem alguns links no wiki da tag Stackoverflow x86 , incluindo o guia de microarquitetura de Agner Fog e os escritos detalhados de David Kanter com diagramas de CPUs Intel e AMD. A partir de sua descrição da microarquitetura Intel Haswell , este é o diagrama final de todo o pipeline de um núcleo Haswell (não o chip inteiro).

Este é um diagrama de blocos de um único núcleo de CPU . Uma CPU quad-core possui 4 delas em um chip, cada uma com seus próprios caches L1 / L2 (compartilhando um cache L3, controladores de memória e conexões PCIe aos dispositivos do sistema).

Eu sei que isso é esmagadoramente complicado. O artigo de Kanter também mostra partes disso para falar sobre o frontend separadamente das unidades de execução ou dos caches, por exemplo.