Detalhes

Categoria: Art of Assembly

Atualização: Sábado, 27 Fevereiro 2010 17:06

Autor: vovó Vicki

Acessos: 7422

Embora os computadores modernos sejam muito rápidos e fiquem mais rápidos a todo o momento, eles ainda necessitam de uma quantidade finita de tempo para efetuar até as menores tarefas. Nas máquinas de Von Neumann, como o 80x86, muitas operações são serializadas. Isto significa que o computador executa comandos numa ordem pre-estabelecida.

Não precisaria ser assim. Por exemplo, para executar a instrução I:=I*5+2; antes da instrução I:=J; na seguinte sequência

I := J;
I := I * 5 + 2;

fica claro que precisa haver uma forma controlar qual instrução deve ser executada primeiro e qual deve ser executada depois.

É óbvio que, em computadores reais, as operações não ocorrem instantaneamente. Mover uma cópia de J para I leva um certo tempo. Da mesma forma, multiplicar I por cinco, depois adicionar dois e armazenar o resultado em I também gasta tempo. Como seria de esperar, a segunda instrução em Pascal leva um pouco mais de tempo para ser executada do que a primeira. Para aqueles interessados em escrever software rápido, uma das primeiras perguntas seria - "Como fazer o processador executar instruções e como medir o tempo gasto para serem executadas?"

A CPU é uma peça de circuito eletrônico muito complexa. Sem entrar em maiores detalhes, vamos apenas dizer que operações dentro da CPU devem ser coordenadas com muito cuidado ou a CPU produzirá resultados errados. Para garantir que todas as operações ocorram no momento certo, as CPUs do 80x86 utilizam um sinal alternado chamado clock do sistema.

No nível mais básico, o clock do sistema gerencia toda a sincronização dentro do computador. O clock do sistema é um sinal elétrico no barramento de controle que fica alternando entre zero e um de acordo com uma determinada taxa cíclica:

Fig.8 - O clock

As CPUs são um bom exemplo de um complexo sistema lógico sincronizado. O clock do sistema coordena muitas das portas lógicas que compõem a CPU permitindo que elas operem em sincronia.

A frequência com que o clock alterna entre zero e um é a frequência do clock do sistema. O tempo que ele leva para alternar de zero para um e voltar para zero é o período do clock. Um período completo é também chamado de ciclo do clock. Em muitos computadores modernos o clock do sistema alterna entre zero e um numa frequência que supera muitos milhões de vezes por segundo. Um chip 80486 comum cicla a 66 milhões de Hertz, ou seja, 66 MegaHertz (MHz). Frequências comuns para modelos 80x86 variam de 5 MHz até 200 MHz ou mais. Note que um período de clock (a quantidade de tempo para um ciclo completo) é o inverso da frequência do clock. Por exemplo, um clock de 1 MHz teria um período de clock de um microsegundo (1/1.000.000 de um segundo). Da mesma forma, um clock de 10 MHz teria um período de clock de 100 nanosegundos (100 bilhonésimos de um segundo). Uma CPU rodando a 50 MHz teria um período de clock de 20 nanosegundos. Note que usualmente expressamos períodos de clock em milhonésimos ou bilhonésimos de segundo.

Para garantir a sincronização, muitas CPUs iniciam uma operação numa borda descendente (quando o clock vai de um para zero) ou numa borda ascendente (quando o clock vai de zero para um). O clock do sistema gasta a maior parte do tempo no zero ou no um, e muito pouco tempo alternando entre os dois. Portanto, o momento da alternância do clock é o ponto perfeito para uma sincronização.

Uma vez que todas as operações da CPU são sincronizadas pelo clock, a CPU não pode efetuar nenhuma tarefa que seja mais rápida do que o clock. Contudo, o simples fato da CPU estar trabalhando numa determinada frequência de clock não significa que esteja executando uma operação a cada ciclo. Muitas operações precisam de vários ciclos de clock para serem completadas, o que significa que a CPU geralmente efetua operações numa taxa significantemente mais baixa.

O acesso à memória é provavelmente a atividade mais comum da CPU. Acesso à memória é, sem sombra de dúvida, uma operação sincronizada baseada no clock do sistema. Isto é, a leitura de um valor da memória ou a escrita de um valor na memória não pode ocorrer mais do que uma vez a cada ciclo do clock. De fato, em muitos processadores 80x86, vários ciclos de clock são necessários para se acessar uma posição de memória. O tempo de acesso à memória é o número de ciclos de clock que o sistema requer para acessar uma posição na memória. Uma vez que tempos prolongados para acesso à memória resultam numa performance baixa, este é um valor importante.

Fig.9 - Tempo de acesso à memória para leitura

Processadores 80x86 diferentes possuem tempos de acesso à memória diferentes, que vão de um a quatro ciclos de clock. Por exemplo, as CPUs do 8088 e do 8086 requerem quatro ciclos de clock para acessar a memória, o 80486 requer apenas um. Então, um 80486 executará programas que acessem memória mais rápido do que um 8086, mesmo quando operar na mesma frequência de clock.

O tempo de acesso à memória é a quantidade de tempo entre uma requisição de operação de memória (leitura ou escrita) e o tempo gasto para a operação ser completada. Numa CPU 8088/8086 de 50 MHz, o tempo de acesso à memória é um pouco menos do que 20 ns. Note que o tempo de acesso à memória no 80486 é 40 vezes mais rápido do que no 8088/8086. Isto porque a frequência de clock do 80486 é dez vezes mais rápida e ele utiliza quatro vezes menos ciclos de clock para acessar a memória.

Quando se lê da memória, o tempo de acesso à memória é a quantidade de tempo decorrido do momento em que a CPU coloca um endereço no barramento de endereços e do momento em que a CPU desloca o dado do barramento de dados. Na CPU do 80486, com um ciclo de tempo de acesso à memória, uma leitura se parece de certa forma com o que é mostrado na Fig.9

Fig.10 - Tempo de acesso à memória para escrita

A escrita de dados na memória é parecida (Fig.10). Note que a CPU não espera pela memória. O tempo de acesso é especificado pela frequência do clock. Se o subsistema de memória não trabalha com a rapidez suficiente, a CPU lerá uma "salada" de dados numa operação de leitura e não armazenará corretamente os dados numa operação de escrita. Isto certamente levará a uma falha no sistema.

Dispositivos de memória têm vários índices de avaliação, mas os dois principais são a capacidade e a velocidade (tempo de acesso). Dispositivos RAM (random access memory) comuns têm capacidades de quatro (ou mais) megabytes e velocidades de 50-100 ns. Pode-se comprar dispositivos maiores ou mais rápidos, mas eles são muito mais caros. Um sistema comum 80486 de 33 MHz utiliza dispositivos de memória de 70 ns.

Mas, espere aí! Em 33 MHz o período do clock é aproximadamente de 33 ns. Como pode um projetista de sistema conseguir acompanhar o clock usando memórias de 70 ns? A resposta está nos estados de espera (wait states).

Fig.11 - Retardos provocados pelo decodificador e pelo buffer

Um estado de espera não é nada mais do que um ciclo de clock extra para dar a algum dispositivo o tempo necessário para completar uma operação. Por exemplo, um sistema 80486 de 50 MHz tem um período do clock de 20 ns. Isto significa que necessitamos de uma memória de 20 ns. Na realidade, a situação é pior do que isto. Em muitos computadores há circuitos adicionais entre a CPU e a memória: decodificadores e buffers lógicos. Estes circuitos adicionais introduzem atrasos adicionais no sistema. No diagrama mostrado na Fig.11 o sistema perde 10 ns para a bufferização e para a decodificação. Então, se a CPU exigir que os dados retornem em 20 ns, a memória deveria responder em menos do que 10 ns.

É claro que podemos comprar memórias de 10 ns. Contudo, são muito mais caras, volumosas, consomem muito mais energia e geram mais calor. Estas são características ruins. Supercomputadores utilizam este tipo de memória. Entretanto, supercomputadores também custam milhões de dólares, ocupam salas inteiras, requerem refrigeração especial e têm fontes de eletricidade gigantescas. Não é exatamente o tipo de equipamento que você quer sobre a sua mesa, é?

Se memórias mais baratas não funcionam com um processador rápido, como as empresas conseguem vender PCs rápidos? Uma parte da resposta é o estado de espera. Por exemplo, se tivermos um processador de 20 MHz com um tempo de ciclo de memória de 50 ns e perdermos 10 ns para a bufferização e a decodificação, vamos precisar de memórias de 40 ns. O que fazer se apenas pudermos adquirir memórias de 80 ns para um sistema de 20 MHz? Adicionando um estado de espera para ampliar o ciclo da memória para 100 ns (dois ciclos do clock) resolverá este problema. Subtraindo os 10 ns para a decodificação e a bufferização ainda nos deixa com 90 ns. Portanto, uma memória de 80 ns, antes que a CPU requisite os dados, responderá bem.

Fig.12 - Inserção de estado de espera

Quase todas as CPUs de propósito geral usadas atualmente fornecem um sinal no barramento de controle que permite a inserção de estados de espera. Se necessário, é geralmente o circuito de decodificação que sinaliza para esta linha esperar um período do clock adicional. Isto dá à memória tempo de acesso suficiente e o sistema funciona apropriadamente (veja na Fig.12).

Algumas vezes um único estado de espera não é suficiente. Considere o 80486 rodando a 50 MHz. O tempo normal do ciclo de memória é menor do que 20 ns. Então, menos de 10 ns estão disponíveis depois de subtrair o tempo de decodificação e bufferização. Se estivermos utilizando memória de 60 ns no sistema, adicionar um único estado de espera não será o suficiente. Cada estado de espera nos dá 20 ns, portanto, com um único estado de espera, precisaríamos de uma memória de 30 ns. Para funcionar com a memória de 60 ns, precisaríamos adicionar três estados de espera (zero estados de espera = 10 ns, um estado de espera = 30 ns, dois estados de espera = 50 ns e três estados de espera = 70 ns).

É desnecessário dizer que, do ponto de vista da performance do sistema, estados de espera não são uma boa coisa. Enquanto a CPU está esperando por dados da memória, ela não pode operar nos dados. Adicionando um único estado de espera ao ciclo da memória em uma CPU 80486 dobra a quantidade de tempo necessária para acessar dados. Isto é a metade da velocidade de acesso à memória. Executar com um estado de espera em todos os acessos à memória é quase como cortar a frequência do clock do processador pela metade. Obtemos muito menos trabalho realizado na mesma quantidade de tempo.

Você provavelmente já viu anúncios do tipo "80386DX, 33 MHz, RAM de 8 megabytes e 0 estados de espera... apenas $1.000!" Se você olhar bem nas especificações, vai notar que os fabricantes utilizaram memórias de 80 ns. Como podem construir sistemas que rodam a 33 MHz e ter zero estados de espera? Fácil. Eles estão mentindo.

Não tem como um 80386 rodar a 33 MHz, executando um programa arbitrário, sem nunca inserir um estado de espera. É claramente impossível. Porém, é totalmente possível desenvolver um subsistema de memória que, sob certas circustâncias especiais, consiga operar sem estados de espera em parte do tempo.

Entretanto, não estamos fadados a execuções lentas devido à adição de estados de espera. Existem muitos truques que os desenvolvedores de hardware podem usar para alçancar zero estados de espera na maior parte do tempo. O mais comum deles é o uso de memória cache (pronuncia-se "cásh").

Se analisarmos um programa típico (como muitos pesquisadores analisaram), descobriremos que ele tende a acessar as mesmas posições de memória repetidamente. Além disto, também descobriremos que um programa frequentemente acessa posições de memória adjacentes. Os nomes técnicos dados a estes fenômenos são localidade temporal de referência e localidade espacial de referência. Quando demonstra localidade espacial, um programa acessa posições de memória vizinhas. Quando exibe localidade temporal de referência, um programa acessa repetidamente a mesma posição de memória durante um curto espaço de tempo. Ambas as formas de localidade ocorrem no seguinte segmento de código Pascal:

Há duas ocorrências de cada uma das localidades, espacial e temporal, dentro deste loop. Vamos considerar a primeira e a mais óbvia.

No código Pascal acima, o programa referencia a variável i muitas vezes. O loop for compara i com 10 para ver se o loop terminou. Ele também incrementa i no final do loop. A operação de atribuição também utiliza i como um índice de array. Isto mostra a localidade temporal de referência em ação, uma vez que a CPU acessa i em três pontos num curto intervalo de tempo.

Este programa também apresenta localidade espacial de referência. O próprio loop zera os elementos do array A escrevendo um zero na primeira posição de A, depois na segunda posição de A, e assim por diante. Assumindo que o Pascal armazena os elementos de A dentro de posições de memória consecutivas, cada iteração do loop acessa posições de memória adjacentes.

Há um exemplo adicional de localidade temporal e espacial no exemplo acima, embora ele não seja tão óbvio. Instruções de computador que indicam uma tarefa específica que o sistema deve realizar também aparecem na memória. Essas instruções aparecem sequencialmente na memória - a localidade espacial. O computador também executa estas instruções repetidamente, uma vez para cada iteração - a localidade temporal.

Se olharmos para o perfil de execução de um programa comum, descobriremos que, em geral, o programa executa menos da metade das instruções. Um programa comum, geralmente, utilizaria apenas 10 a 20% da memória destinada a ele. Num dado momento, um programa de um megabyte poderia talvez acessar de quatro a oito kilobytes de dados e código. Então, se gastamos uma soma escandalosa de dinheiro por uma RAM cara de zero estados de espera, não estaremos utilizando a maior parte dela em qualquer dado momento! Não seria melhor se pudéssemos comprar uma pequena quantidade de RAMs rápidas e redeterminar dinamicamente seus endereços à medida que o programa fosse sendo executado?

É exatamente isto o que a memória cache faz. A memória cache fica entre a CPU e a memória principal. É uma pequena porção de memória muito rápida (com zero estados de espera). Ao contrário da memória convencional, os bytes que aparecem dentro de uma cache não têm endereços fixos. A memória cache pode redeterminar o endereço de um dado. Isto permite que o sistema mantenha os valores acessados recentemente na cache. Endereços que a CPU nunca acessou ou não acessou recentemente ficam na memória principal (lenta). Já que a maior parte dos acessos à memória correspondem a variáveis acessadas recentemente (ou em posições próximas de posições acessadas recentemente), o dado geralmente aparece na memória cache.

A memória cache não é perfeita. Embora um programa possa gastar um tempo considerável executando código num local, ele eventualmente chamará um procedimento ou desviará para alguma seção distante de código, fora da memória cache. Nestes casos, a CPU precisa acessar a memória principal para buscar os dados. Como a memória principal é lenta, haverá a necessidade de inserir estados de espera.

Um acerto de cache ("cache hit") ocorre sempre que a CPU acessar a memória e encontrar o dado procurado na cache. Neste caso, a CPU pode realmente acessar o dado com zero estados de espera. Uma falha de cache ("cache miss") ocorre se a CPU acessar a memória e o dado não estiver presente na cache. Então a CPU precisa ler o dado da memória principal, causando uma perda de performance. Para tirar vantagem da localidade de referência, a CPU copia dados para dentro da cache sempre que ela acessar um endereço ausente na cache. Como é provável que o sistema acesse aquela mesma posição pouco tempo depois, aquele dado na cache faz com que o sistema economize estados de espera.

Como descrito acima, a memória cache trata dos aspectos temporais de acesso à memória, mas não dos aspectos espaciais. Armazenar posições da memória quando estas são acessadas não agilizará o programa se acessarmos constantemente posições consecutivas (localidade espacial). Para resolver este problema, muitos sistemas de cache lêem muitos bytes consecutivos da memória quando ocorre uma falha de cache. O 80486, por exemplo, lê 16 bytes de uma vez quando a cache falha. Se lermos 16 bytes, porque lê-los em blocos ao invés de quando precisarmos deles? Muitos chips de memória disponíveis atualmente têm modos especiais que permitem o acesso rápido de várias posições de memória consecutivas no chip. A cache tira proveito desta capacidade para reduzir o número médio de estados de espera necessários para acessar a memória.

Se escrevermos um programa que acessa a memória randomicamente, utilizar a memória cache, na verdade, pode torná-lo mais lento. Ler 16 bytes a cada falha de cache é caro se apenas acessarmos uns poucos bytes na linha de cache correspondente. Apesar de tudo, os sistemas de memória cache funcionam muito bem.

Não deve ser surpresa que a proporção entre acertos e falhas de cache aumenta com o tamanho (em bytes) do subsistema de memória cache. O chip 80486, por exemplo, tem 8.192 bytes de cache por chip. A Intel declara obter uma taxa de acerto de 80 a 95% com esta cache (significa que em 80 a 95% das vezes a CPU encontra o dado na cache). Isto parece muito impressionante. Contudo, se brincarmos um pouco com os números, veremos que isto não é tão impressionante assim. Suponha que consideremos os 80% do número. Então, na média, um em cada cinco acessos à memória não estará na cache. Se tivermos um processador de 50 MHz e um tempo de acesso à memória de 90 ns, quatro dos cinco acessos precisam de apenas um ciclo de clock (já que eles estão na cache) e o quinto necessitará de aproximadamente 10 estados de espera. No total, o sistema necessitará de 15 ciclos de clock para acessar cinco posições de memória ou, em média, três ciclos de clock por acesso. Isto é o equivalente a dois estados de espera adicionados a cada acesso à memória. Você acredita agora que sua máquina roda com zero estados de espera?

Há duas formas de melhorar a situação. Primeiro, podemos adicionar mais memória cache. Isto melhora a taxa de acerto de cache, reduzindo o número de estados de espera. Por exemplo, aumentando a taxa de acerto de 80% para 90% permite que 10 posições de memória sejam acessadas em 20 ciclos. Isto reduz o número médio de estados de espera por acesso à memória para um estado de espera - uma melhora substancial. Só que não podemos desmontar um chip 80486 e soldar mais memória cache no chip. Contudo, a CPU do 80586/Pentium tem uma cache significantemente maior do que a do 80486 e opera com muito menos estados de espera.

Fig.13 - Cache de dois níveis

Uma outra forma de melhorar a performance é construir um sistema de cache de dois níveis. Muitos sistemas 80486 funcionam assim. O primeiro nível é a chache de 8.192 bytes no chip. O nível seguinte, entre a cache no chip e a memória principal, é uma cache secundária construída no sistema de circuitos da placa do computador.

Uma cache secundária comum possui algo em torno de 32.768 bytes a um megabyte de memória. Tamanhos comuns em subsistemas de PC são 65.536 e 262.144 bytes de cache.

Você poderia perguntar "Por que se incomodar com uma cache de dois níveis? Por que não utilizar uma cache que tenha 262.144 bytes?" Bem, a cache secundária geralmente não opera com zero estados de espera. Circuitos que oferecem 262.144 bytes de memória de 10 ns (com tempo total de acesso de 20 ns) seriam muito caros. Por isso a maioria dos projetistas de sistemas utilizam memórias mais lentas que requerem um ou dois estados de espera. Isto ainda é muito mais rápido do que a memória principal. Combinada com a cache no chip da CPU, obtém-se uma melhor performance do sistema.

Considere o exemplo anterior, com uma taxa de acerto de 80%. Se a cache secundária precisar de dois ciclos para cada acesso à memória e de três ciclos para o primeiro acesso, então uma falha de cache na cache do chip precisará de seis ciclos de clock. Tudo indica que a média da performance do sistema será de dois clocks por acesso à memória, o que é um pouco mais rápido do que os três necessários pelo sistema sem a cache secundária. Além do mais, a cache secundária pode atualizar seus valores em paralelo com a CPU. Deste modo, o número de falhas de cache (o que afeta a performance da CPU) diminui.

Você provavelmente está pensando "Até agora tudo isto parece interessante, mas o que tem a ver com programação?" Na verdade, pouco. Escrevendo seus programas cuidadosamente para tirar vantagem da forma como o sistema de memória cache funciona, você pode melhorar a performance dos mesmos. Colocando as variáveis usadas com mais frequência na mesma linha de cache, você pode forçar o sistema de cache a carregar essas variáveis como um grupo, economizando estados de espera extras em cada acesso.

Se você organizar seu programa do forma que ele tenha a tendência de executar a mesma sequência de instruções repetidamente, ele terá um alto grau de localidade temporal de referência e, desta forma, será executado mais rapidamente.

Fonte

• Art of Assembly de Randall Hyde.
• Tradução meio que livre da vovó Vicki.