Computer Science › Como os Computadores Realmente Funcionam
Tempo de CPU = Contagem de Instruções × CPI × Tempo de Ciclo de Clock, a "Lei de Ferro" do desempenho de processadores, que divide a velocidade em três alavancas que se movem de forma independente (a ISA/compilador, a microarquitetura e o silício) e entre as quais toda decisão de projeto desta disciplina faz trocas.
A CPU de ciclo único já construída em Lógica Digital e Organização de Computadores é correta, mas desperdiçadora, porque o ciclo de clock de toda instrução precisa ser tão longo quanto a instrução mais lenta exige. O pipelining sobrepõe instruções em andamento, trocando uma latência maior por instrução por uma vazão drasticamente maior.
Dividir o datapath de ciclo único em cinco pontos naturais (Busca, Decodificação, Execução, Memória, Escrita de Volta), com um registrador de pipeline guardando o estado entre cada estágio, para que cinco instruções diferentes possam ocupar os cinco estágios ao mesmo tempo, com um ciclo de diferença entre si.
Duas instruções em estágios diferentes querem o mesmo recurso físico no mesmo ciclo (classicamente, a busca de uma instrução e o acesso à memória de outra querendo a única porta de memória), algo resolvido em projetos reais dando às instruções e aos dados suas próprias caches separadas.
Um registrador escrito por uma instrução é lido pela instrução seguinte antes de a escrita de fato chegar ao banco de registradores. É um hazard de leitura após escrita (RAW), corrigido não esperando, e sim encaminhando (forwarding) o resultado ainda não escrito diretamente para a entrada da ULA da instrução dependente.
Um hazard de dados que o forwarding não consegue apagar por completo. O valor de um load só fica disponível depois do estágio de Memória, então uma instrução que depende dele logo em seguida ainda precisa de um ciclo de bolha, uma parada que um compilador esperto muitas vezes consegue esconder por inteiro reordenando instruções independentes para essa lacuna.
O resultado tomado/não tomado de um desvio só é conhecido bem depois de as próximas instruções já terem sido buscadas. Descartar o pipeline de forma ingênua a cada desvio custa ciclos reais e quantificáveis, e é exatamente o problema que a previsão de desvios existe para reduzir.
Adivinhar o resultado de um desvio antes que ele seja conhecido (previsão estática, como sempre tomado ou tomado para trás, e previsão dinâmica com uma tabela de histórico de desvios de contadores saturantes de 1 ou 2 bits) transforma a maioria das penalidades de desvio no caso comum de um palpite certo, em vez de uma parada garantida.
Executar além de um desvio previsto antes de seu resultado ser confirmado e deixar instruções independentes serem emitidas fora da ordem do programa, contornando uma que está parada. Visto aqui só no nível conceitual (que problema resolve e quanto custa desfazer um erro de previsão), com a mecânica completa (reorder buffers, escalonamento no estilo de Tomasulo) deixada para um curso mais avançado.
Uma pirâmide de tecnologias de armazenamento (registradores, cache no chip, memória principal, disco) que troca capacidade por velocidade em cada nível; a localidade temporal e a espacial são as propriedades empíricas dos programas reais que permitem a uma cache pequena e rápida se comportar, na maior parte do tempo, como se toda a memória fosse tão rápida quanto ela.
Um endereço se divide em tag, índice e deslocamento no bloco; uma cache de mapeamento direto usa o índice para escolher exatamente um slot por endereço e a tag para verificar se o bloco residente é de fato o que está sendo pedido.
Relaxar a rigidez de um slot por endereço do mapeamento direto para N slots possíveis ("vias") por conjunto troca hardware extra de comparação por muito menos falhas por conflito; uma cache totalmente associativa é o caso-limite de um único conjunto gigante, com toda linha como candidata.
Quando um conjunto está cheio e um bloco novo precisa entrar, algo tem de ser despejado. O menos recentemente usado (LRU, e suas aproximações mais baratas em hardware), o FIFO e o aleatório são as políticas reais em uso, cada uma uma aposta diferente sobre qual linha residente tem menos chance de ser reutilizada em breve.
Uma escrita pode atualizar a memória principal na hora, toda vez (write-through), ou só marcar a linha como suja e adiar a atualização até ela ser despejada (write-back), em par com write-allocate/no-write-allocate para o que acontece numa falha de escrita. Exatamente essa contabilidade de linhas sujas é o que um protocolo de coerência multinúcleo depois precisa generalizar entre várias caches ao mesmo tempo.
AMAT = Tempo de Acerto + Taxa de Falha × Penalidade de Falha, aplicado recursivamente numa hierarquia real L1/L2/L3/DRAM com números de latência representativos. É a única fórmula em direção à qual todo este bloco vem construindo, e a que o CS2013 nomeia diretamente como uma habilidade de cálculo obrigatória.
A ordem de percurso por linhas (row-major) e o bloqueio de cache (tiling) transformam tudo o que este bloco viu num efeito real e mensurável. É o mesmo algoritmo, a mesma complexidade assintótica e um tempo de relógio drasticamente diferente, dependendo só da ordem em que a memória é tocada.
Por volta de 2004-2005, os fabricantes de chips bateram numa barreira física real. A Regra de Pollack (o desempenho escala só com a raiz quadrada da lógica acrescentada, enquanto a energia escala linearmente com ela) tornou os projetos de núcleo único cada vez mais ineficientes em energia, levando a indústria inteira a se voltar para vários núcleos mais simples, a virada histórica que Herb Sutter chamou de "o almoço grátis acabou" para o software.
Um chip multinúcleo típico dá a cada núcleo sua própria cache L1 privada (e muitas vezes L2), mas compartilha uma L3 e uma memória principal entre todos eles. É um layout que levanta de imediato uma pergunta nova de correção que esta disciplina ainda não tinha enfrentado, o que acontece quando dois núcleos guardam em cache a mesma linha.
O problema da coerência, enunciado com precisão: todo núcleo precisa, em algum momento, observar toda escrita numa linha compartilhada, em alguma ordem consistente. Os quatro estados por linha do MESI (Modified, Exclusive, Shared, Invalid) e as mensagens bisbilhotadas no barramento entre eles são o protocolo padrão que chips multinúcleo reais usam para garantir exatamente isso.
Duas threads que tocam duas variáveis completamente sem relação ainda podem brigar pela mesma linha de cache se essas variáveis por acaso caírem nela. O MESI mantém os dados corretos, mas a linha fica pingando entre Modified e Invalid entre os núcleos a cada acesso, transformando um protocolo de correção num bug de desempenho real e mensurável.
A classificação de Flynn das máquinas por fluxos de instruções e de dados (SISD, SIMD, MISD, MIMD) coloca o chip multinúcleo recém-visto diretamente em MIMD (muitos fluxos de instruções independentes); o SIMD é o eixo diferente para o qual este bloco se volta agora, um único fluxo de instruções conduzindo muitas faixas de dados ao mesmo tempo.
Uma GPU agrupa milhares de faixas simples em multiprocessadores de streaming, executando grupos de 32 threads (um warp) em sincronia sob o SIMT, o primo mais flexível do SIMD, que permite a threads individuais seguir desvios diferentes ao custo de serializar os caminhos divergentes. O escopo é só o modelo de execução do hardware; o modelo de programação CUDA/OpenCL pertence a `systems/parallel-computing`.
Três barreiras históricas reais, amarradas entre si. A barreira do ILP (a especulação e a emissão fora de ordem ficaram sem trabalho independente para explorar), a barreira da memória (o AMAT cada vez mais dominado por uma latência de DRAM que nenhum nível de cache esconde por completo) e a barreira da energia (a Regra de Pollack) são as mesmas três forças que encerraram o "almoço grátis" do núcleo único e fizeram da profundidade de pipeline, da hierarquia de cache, do multinúcleo e da arquitetura SIMD/GPU as quatro respostas reais que esta disciplina cobriu, na ordem em que as cobriu.
Part of the Computer Science curriculum.
Tempo de CPU = Contagem de Instruções × CPI × Tempo de Ciclo de Clock, a "Lei de Ferro" do desempenho de processadores, que divide a velocidade em três alavancas que se movem de forma independente (a ISA/compilador, a microarquitetura e o silício) e entre as quais toda decisão de projeto desta disciplina faz trocas.
A CPU de ciclo único já construída em Lógica Digital e Organização de Computadores é correta, mas desperdiçadora, porque o ciclo de clock de toda instrução precisa ser tão longo quanto a instrução mais lenta exige. O pipelining sobrepõe instruções em andamento, trocando uma latência maior por instrução por uma vazão drasticamente maior.
Dividir o datapath de ciclo único em cinco pontos naturais (Busca, Decodificação, Execução, Memória, Escrita de Volta), com um registrador de pipeline guardando o estado entre cada estágio, para que cinco instruções diferentes possam ocupar os cinco estágios ao mesmo tempo, com um ciclo de diferença entre si.
Duas instruções em estágios diferentes querem o mesmo recurso físico no mesmo ciclo (classicamente, a busca de uma instrução e o acesso à memória de outra querendo a única porta de memória), algo resolvido em projetos reais dando às instruções e aos dados suas próprias caches separadas.
Um registrador escrito por uma instrução é lido pela instrução seguinte antes de a escrita de fato chegar ao banco de registradores. É um hazard de leitura após escrita (RAW), corrigido não esperando, e sim encaminhando (forwarding) o resultado ainda não escrito diretamente para a entrada da ULA da instrução dependente.
Um hazard de dados que o forwarding não consegue apagar por completo. O valor de um load só fica disponível depois do estágio de Memória, então uma instrução que depende dele logo em seguida ainda precisa de um ciclo de bolha, uma parada que um compilador esperto muitas vezes consegue esconder por inteiro reordenando instruções independentes para essa lacuna.
O resultado tomado/não tomado de um desvio só é conhecido bem depois de as próximas instruções já terem sido buscadas. Descartar o pipeline de forma ingênua a cada desvio custa ciclos reais e quantificáveis, e é exatamente o problema que a previsão de desvios existe para reduzir.
Adivinhar o resultado de um desvio antes que ele seja conhecido (previsão estática, como sempre tomado ou tomado para trás, e previsão dinâmica com uma tabela de histórico de desvios de contadores saturantes de 1 ou 2 bits) transforma a maioria das penalidades de desvio no caso comum de um palpite certo, em vez de uma parada garantida.
Executar além de um desvio previsto antes de seu resultado ser confirmado e deixar instruções independentes serem emitidas fora da ordem do programa, contornando uma que está parada. Visto aqui só no nível conceitual (que problema resolve e quanto custa desfazer um erro de previsão), com a mecânica completa (reorder buffers, escalonamento no estilo de Tomasulo) deixada para um curso mais avançado.
Uma pirâmide de tecnologias de armazenamento (registradores, cache no chip, memória principal, disco) que troca capacidade por velocidade em cada nível; a localidade temporal e a espacial são as propriedades empíricas dos programas reais que permitem a uma cache pequena e rápida se comportar, na maior parte do tempo, como se toda a memória fosse tão rápida quanto ela.
Um endereço se divide em tag, índice e deslocamento no bloco; uma cache de mapeamento direto usa o índice para escolher exatamente um slot por endereço e a tag para verificar se o bloco residente é de fato o que está sendo pedido.
Relaxar a rigidez de um slot por endereço do mapeamento direto para N slots possíveis ("vias") por conjunto troca hardware extra de comparação por muito menos falhas por conflito; uma cache totalmente associativa é o caso-limite de um único conjunto gigante, com toda linha como candidata.
Quando um conjunto está cheio e um bloco novo precisa entrar, algo tem de ser despejado. O menos recentemente usado (LRU, e suas aproximações mais baratas em hardware), o FIFO e o aleatório são as políticas reais em uso, cada uma uma aposta diferente sobre qual linha residente tem menos chance de ser reutilizada em breve.
Uma escrita pode atualizar a memória principal na hora, toda vez (write-through), ou só marcar a linha como suja e adiar a atualização até ela ser despejada (write-back), em par com write-allocate/no-write-allocate para o que acontece numa falha de escrita. Exatamente essa contabilidade de linhas sujas é o que um protocolo de coerência multinúcleo depois precisa generalizar entre várias caches ao mesmo tempo.
AMAT = Tempo de Acerto + Taxa de Falha × Penalidade de Falha, aplicado recursivamente numa hierarquia real L1/L2/L3/DRAM com números de latência representativos. É a única fórmula em direção à qual todo este bloco vem construindo, e a que o CS2013 nomeia diretamente como uma habilidade de cálculo obrigatória.
A ordem de percurso por linhas (row-major) e o bloqueio de cache (tiling) transformam tudo o que este bloco viu num efeito real e mensurável. É o mesmo algoritmo, a mesma complexidade assintótica e um tempo de relógio drasticamente diferente, dependendo só da ordem em que a memória é tocada.
Por volta de 2004-2005, os fabricantes de chips bateram numa barreira física real. A Regra de Pollack (o desempenho escala só com a raiz quadrada da lógica acrescentada, enquanto a energia escala linearmente com ela) tornou os projetos de núcleo único cada vez mais ineficientes em energia, levando a indústria inteira a se voltar para vários núcleos mais simples, a virada histórica que Herb Sutter chamou de "o almoço grátis acabou" para o software.
Um chip multinúcleo típico dá a cada núcleo sua própria cache L1 privada (e muitas vezes L2), mas compartilha uma L3 e uma memória principal entre todos eles. É um layout que levanta de imediato uma pergunta nova de correção que esta disciplina ainda não tinha enfrentado, o que acontece quando dois núcleos guardam em cache a mesma linha.
O problema da coerência, enunciado com precisão: todo núcleo precisa, em algum momento, observar toda escrita numa linha compartilhada, em alguma ordem consistente. Os quatro estados por linha do MESI (Modified, Exclusive, Shared, Invalid) e as mensagens bisbilhotadas no barramento entre eles são o protocolo padrão que chips multinúcleo reais usam para garantir exatamente isso.
Duas threads que tocam duas variáveis completamente sem relação ainda podem brigar pela mesma linha de cache se essas variáveis por acaso caírem nela. O MESI mantém os dados corretos, mas a linha fica pingando entre Modified e Invalid entre os núcleos a cada acesso, transformando um protocolo de correção num bug de desempenho real e mensurável.
A classificação de Flynn das máquinas por fluxos de instruções e de dados (SISD, SIMD, MISD, MIMD) coloca o chip multinúcleo recém-visto diretamente em MIMD (muitos fluxos de instruções independentes); o SIMD é o eixo diferente para o qual este bloco se volta agora, um único fluxo de instruções conduzindo muitas faixas de dados ao mesmo tempo.
Uma GPU agrupa milhares de faixas simples em multiprocessadores de streaming, executando grupos de 32 threads (um warp) em sincronia sob o SIMT, o primo mais flexível do SIMD, que permite a threads individuais seguir desvios diferentes ao custo de serializar os caminhos divergentes. O escopo é só o modelo de execução do hardware; o modelo de programação CUDA/OpenCL pertence a `systems/parallel-computing`.
Três barreiras históricas reais, amarradas entre si. A barreira do ILP (a especulação e a emissão fora de ordem ficaram sem trabalho independente para explorar), a barreira da memória (o AMAT cada vez mais dominado por uma latência de DRAM que nenhum nível de cache esconde por completo) e a barreira da energia (a Regra de Pollack) são as mesmas três forças que encerraram o "almoço grátis" do núcleo único e fizeram da profundidade de pipeline, da hierarquia de cache, do multinúcleo e da arquitetura SIMD/GPU as quatro respostas reais que esta disciplina cobriu, na ordem em que as cobriu.