Quem sou eu

Minha foto
Salvador, BA, Brazil
Analista de sistemas, expert em telecom, formado em Eng. Elétrica e nerd assumido

terça-feira, 9 de novembro de 2010

Sistemas de Computação 6 - Melhorando a performance

Peo que vimos nos artigos anteriores desta série aprendemos que as instruções de máquina que compõem o programa em execução são executadas de forma sequencial, exceto quando são executadas instruções de desvio (na verdade há outra razão para a quebra da sequência de execução, mas isso é assunto para mais tarde), e cada instrução é executada em uma sequência de passos conhecida como ciclo fetch-execute.

O tempo total de execução de uma instrução será, então, determinado pela soma dos tempos necessários para que ela passe por cada etapa do ciclo fetch-execute. Todas as mudanças de estado lógico dos circuitos da CPU ocorrem em intervalos de tempo fixos, regulados por um relógio (clock). Então já podemos visualizar um caminho óbvio para melhorar a performance da máquina: fazer o relógio "bater" mais rápido, ou seja, aumentar a frequência do clock.

Infelizmente, por razões físicas, existe um limite prático para o aumento da frequência do clock para melhoria da performance. Mas, ainda assim, existe margem para melhorar o desempenho. Uma delas nós vimos no final do terceiro artigo desta série: diminuir o tempo necessário para executar operações de acesso à memória através da criação de uma hierarquia de memórias intermediárias de maior velocidade - os caches de primeiro, segundo e terceiro níveis (L1, L2 e L3). Desta fora podemos melhorar o tempo de execução das etapas de instruction fetch, operand fetch e result store do ciclo fetch-execute (ver o artigo anterior desta série).

Mas ainda existem alguns truques na manga para aumentar o desempenho da máquina. O primeiro deles deriva da observação que os circuitos necessários para a execução de cada fase do ciclo fetch-execute ficam essencialmente ociosos quando outra fase está em execução. Então manter a CPU ocupada com apenas uma instrução de máquina de cada vez é um desperdício de tempo. A técnica de executar paralelamente várias instruções de máquina em estágios diferentes do ciclo fetch-execute é conhecida como pipelining.


Como podemos ver na figura acima, supondo que a passagem de cada instrução por cada fase do ciclo fetch-execute demore exatamente um ciclo do clock (normalmente é mais, e as fases não tem todas a mesma duração, mas esta hipótese serve como exemplo aceitável), para cinco estágios de pipelining, cada um associado a uma das fases do ciclo fetch-execute, obtivemos um ganho de performance tal que em 15 ciclos do clock passamos de 3 para 11 o número de instruções executadas (ainda mais, se considerarmos que ao final do 15º ciclo do clock existirão mais quatro instruções cuja execução ainda não se completou).

O que nos leva naturalmente à pergunta: qual o ganho hipotético de performance pode ser obtido pelo uso de execução das instruções de máquina com pipelining em relação à execução convencional?

Existem duas variáveis chave para tereminar o ganho G do uso do pipelining: o número N de instruções de máquina a executar e o número P de estágios de pipelining. Chamando de t o tempo médio para execução de cada estágio do pipeline, As expressões para o tempo T de execução das N instruções sem pipelining, para o tempo TP de execução das mesmas N instruções com pipelining, e para o ganho de performance G devido ao uso do pipeline são:


Considerando que o número P de estágios do pipeline é uma constante, o ganho máximo teórico de performance Gmax é dado por:


A título de exemplo o gráfico abaixo mostra o comportamento de G em função de N para P = 5.


Vemos então que o ganho real de performance pelo uso do pipelining converge para o ganho máximo teórico mesmo para valores razoavelmente pequenos da sequência de instruções a executar. Porém existem alguns probleminhas ocultos aqui. Considere, por exemplo a seguinte sequência de operações aritméticas, supondo que cada uma delas possa ser representada por uma única instrução de máquina:


A execução da segunda operação depende de conhecermos o resultado da primeira operação, e a execução da terceira operação depende de conhecermos o resultado da segunda operação. Ou seja, execução da segunda operação é dependente da ´primeira, assim como a execução da terceira operação é dependente da segunda. Porém este é um caso onde a dependência surge do fato que o resultado de uma operação é usada como operando de entrada na próxima instrução. Considere agora o caso da construção lógica chamada IF-THEN-ELSE mostrada abaixo na forma de um fluxograma.


Este tipo de construção tipicamente usa instruções de máquina de desvio condicional para a sua implementação no nível de linguagem de máquina. Mas como o valor da expressão lógica (VERDADEIRO ou FALSO) só é conhecido depois da sua interpretação, isto também cria uma dependência entre instruções, porque a próxima instrução a executar depende do valor lógico resultante da avaliação da expressão.


Dependência entre instruções é um problema sério para o pipelining, porque cria uma "bolha" onde a execução de instruções tem que retornar à forma sequencial pura, prejudicando o ganho de performance. A dependência causada por operandos que são resultados em operações anteriores pode ser contornada intercalando-se as instruções dependentes com outras instruções do programa, de forma a dar tempo para que a execução da instrução dependente só comece depois que o resultado da instrução da qual ela depende já seja conhecido. Isto exige que, depois que a sequência das instruções de máquina do programa esteja definida, seja feita uma análise das relações de dependência e que as instruções dependentes que estejam muito próximas daquelas das quais elas dependem sejam reposicionadas. Isto envolve o uso consciencioso de instruções de desvio incondicional e/ou instruções nulas (isto, em si, já é uma curiosidade: como fazer uma instrução de máquina que apenas ocupa tempo do processador mas não executa nada de verdade? Basta codificar uma instrução de desvio condicional com uma condição de desvio que nunca ocorre). Na prática isto é bastante complicado de fazer, por isso normalmente esta tarefa fica a cargo dos compiladores, dos quais trataremos em outro artigo desta série.

Para o caso da dependência do valor lógico os contornos são implementado na Unidade de Controle da CPU, e são conhecidos como previsão de desvios (branch prediction) e execução especulativa (speculative execution). Neste caso, quando existe uma instrução de desvio condicional no código do programa a Unidade de Controle seleciona um dos possíveis resultados para a instrução de desvio e começa a executar aquela sequência de instruções mesmo antes do resultado correto do desvio ser conhecido (daí o nome execução especulativa). Caso o desvio seja mesmo para a sequência de instruções escolhida, então os resultados especulativos são validaddos. Caso contrário eles são descartados e a execução é retomada a partir da sequência correta de instruções apontada pelo desvio condicional (e assume-se o dano da formação de uma "bolha" no pipelining).

Para finalizar este artigo (que já está bem longo) existe mais um aspecto relativo ao pipelining que precisamos observar. Na nossa descrição anterior sobre o tempo de execução das instruções e o ganho do pipelining usamos o tempo médio de duração de cada fase do ciclo fetch-execute (e associamos a cada uma destas fases um estágio do pipeline). Só que, normalmente, a fase execute é a mais demorada de todas, podendo, a depender da instrução, durar mais do que todas as outras fases juntas. Uma maneira de manter o ganho do pipeline nestas circunstâncias é construir a CPU com mais de uma ALU. Veja o exemplo da figura abaixo.


Supondo que a fase execute tem duração média três vezes superior à duração média das outras fases (isto é uma aproximação, claro), uma CPU com uma única ALU torna-se claramente um gargalo para o desemepenho da máquina. Com o acréscimo de duas ALUs o gargalo é removido, e o ganho do pipeliniing é preservado Este tiipo de solução é o início da evolução da construção dos processadores em direção aos atuais chips multicore, mas isso também é assunto para mais tarde

Nenhum comentário:

Postar um comentário