Latência, execução e penalidades

A idéia de que os processadores modernos executam instruções a uma velocidade de 1 instrução por ciclo de clock é totalmente errada. Primeiro porque o tempo de execução de instruções não é medida em “clocks”, mas em “ciclos de máquina” (cada ciclo de máquina equivale a 4 ciclos de clock). Segundo, porque a medição exata do tempo de execução é algo muito difícil de ser feito já que existem diversas variáveis envolvidas no processo de medir este tempo. Em geral, o tempo deve ser medido levando-se em conta:

  ttotal = tlatência + texecução + tpenalidades

Uma instrução simples como

  mov eax,ebx

Pode levar 1 ciclo de máquina para ser executada. Só que não estamos levando em conta o tempo de latência e as penalidades, só o tempo de execução. O “tempo de latência” tem haver com o paralelismo nas pipelines U e V (mas não só!) do processador. Se uma instrução que leva 5 ciclos de máquina estiver em execução em uma das pipelines e na outra tivermos uma instrução que leva somente 1 ciclo, então o tempo de execução de AMBAS as instruções será de 5 ciclos. Ou seja, vale o tempo de execução da instrução que demora mais, se estiverem em ambas as pipelines.

Curiosamente, graças a esse paralelismo, podemos, às vezes, ter o efeito de uma instrução sendo executada em apenas meio ciclo de máquina. Essa ilusão é simples de entender… Se duas instruções (nas pipelines U e V) executarem em apenas 1 ciclo, isso significa que cada uma executou na média de 0.5 ciclo (1 ciclo dividido por 2 instruções). Neste caso o tempo de latência é, supostamente, zero. Só que isso é raro….

Instruções um pouco mais complexas como:

  mov eax,[ebx]

Podem tomar 2 ciclos de máquina extras:  um para o calculo do endereço efetivo e outro para a leitura da memória. Acontece que os processadores modernos têm um recurso de calcular o endereço efetivo antes que a instrução seja executada e ai entra a penalidade. Por exemplo, fazemos:

  mov ebx,edx       ; U-pipe, V-pipe "parada".
  mov eax,[ebx]     ; U-pipe

O calculo do endereço efetivo, usado na segunda instrução, é invalidado pela inicialização de EBX na primeira instrução, forçando o processador a calculá-lo durante a execução da segunda instrução! Pra piorar a situação, já que EBX é usado em ambas as instruções, elas não podem ser emparelhadas nas pipelines. Dai, a primeira instrução toma 1 ciclo e a segunda toma 3 e a pipeline V fica “parada”.

A penalidade do ciclo extra para o cálculo do endereço efetivo pode ser evitado se inicializarmos EBX pelo menos 2 instruções antes de ele ser usado como ponteiro. Isso dá tempo para o processador fazer o cálculo do endereço efetivo e a instrução que usa EBX como ponteiro será executada em 2 ciclos, ao invés de 3.

Você deve estar se perguntando: Porque 2 instruções antes? Porque as duas instruções anteriores provavelmente serão executadas nas pipelines, em paralelo antes da instrução que desejamos otimizar e é durante este intervalo que o endereço efetivo é calculado com antecedência. Se modificarmos os registradores usados para o cálculo do endereço neste intervalo, então o processador será forçado a adicionar um ciclo extra (e, possivelmente, “parar” a pipeline V), como mostrei acima.

É interessante notar que existem algumas maneiras de calcular o endereço efetivo:

  [eax]
  [eax+8]
  [2*eax]
  [2*eax+4]
  [4*eax+ebx]
  [4*eax+ebx+8]

No caso mais extremo (o último), EAX e EBX não podem ter sido modificados no ciclo anterior, senão temos a penalidade de 1 ciclo.

Essa é apenas uma das penalidades. Outra é a falta de alinhamento dos dados… Se um dado não estiver totalmente dentro de uma QWORD (64 bits), o processador terá que fazer duas leituras para montar o dado, adicionando 1 ciclo extra de penalidade. Por exemplo:

  #pragma pack(1)
  struct X
  {
    int a;    /* 32 bits */    
    short b;  /* 16 bits */    
    char c;   /* 8 bits. */    
    int d;    /* 32 bits. 'd' cruza a barreira dos 64 bits! */  
  };

Uma instrução que leia o conteúdo da variável ‘d’ dentro de uma estrutura X necessariamente tomará 1 ciclo extra de execução, penalizada por cruzar a fronteira dos 64 bits. Por que 64 bits? Porque esse é o tamanho do barramento de dados do processador!
Outras penalidades que você pode considerar:

  • Cache misses (dados ou instruções que ainda não estão no cache L1);
  • Cruzamento de barreira dos 64 bytes de uma linha de cache L1;
  • Page Faults;
  • Task switching
  • Excessões

Tudo isso afeta a performance do seu programa (não necessariamente uma instrução em particular! Então essa história de que “otimização” não é necessária é – em minha opinião – totalmente absurda!

Algumas otimizações são feitas automaticamente pelo compilador: Scheduling é feito pelo compilador para aproveitar as pipelines U e V, tentando diminuir as penalidades a zero (embora pouca coisa possa ser feita para minimizar o tempo de latência). O compilador também tenta arranjar o uso dos registradores de forma tal que o calculo antecipado do endereço efetivo não seja comprometido. Mas outras otimizações não são feitas pelo compilador… É o caso da estrutura X que mostrei acima… É sua tarefa arranjar as variáveis de forma tal que não aconteça um cruzamento de fronteira.

Dito tudo isso, deixe-me dizer também que eu não descobri isso sozinho… Todo esse material está disponível — de uma forma bem obscura, devo dizer — no guia de otimização da Intel (aqui). Também estão descritas no excelente livro de Michael Abrash: Zen of Code Optimization (de forma bem clara!). O livro já é meio “velho”, mas apresenta diversas dicas importantes até hoje.

Anúncios

2 comentários sobre “Latência, execução e penalidades

  1. Estive lendo o material sobre memória, confesso que pulei muitas partes, mas consegui absorver muita informação útil. Creio que com mais umas 10 ou 20 leituras, eu consiga absorver uns 20%. Digo isto feliz, pois o assunto é – como disse vocẽ – pra lá obscuro. Eu diria magia negra, terceiro dan.
    Mas conhecer memória ajuda no processo, se não no de programar, pelo menos de comprar ou configurar computadores.
    Vi que algumas otimizações podem envolver – além do citado arranjo e revisão do alinhamento de estruturas – o uso consciencioso de loops. Há diferenças quando se inverte a escrita de CxL por LxC, por exemplo, assim como devem existir outras como jumps e inserções inline de assmebly.
    Sobre o livro do Michael Abrash, vi alugns usados no amazon, por preço acessível. Vale à pena comprar ou as técnicas somente servem para antigos pentium?

    1. O livro, como eu disse, é meio velho… começa abordando “quirks” do 8088 e 8086, passa para o 286, 386, 486 e termina no Pentium… Mas, tudo o que está por lá é aplicável ainda hoje. Michael, inclusive, mostra otimizações em C (ele faz isso com dois “algorítmos” – Um código de pesquisa de texto, usando o algorítmo Boyer-More e o “jogo” LIFE).

      O livro vale muito a pena para quem quer entender otimizações em assembly e em geral. Foi desse livro que surgiu a “sigla” TANSTATFC (There Are Not Such Thing As The Fastest Code).

      Se o interesse é ver como Michael lida com otimização de código, o livro vale a pena sim… (Proce, my Friend, eu empresto… mas só proce! hehe).

      Eu vou, por exemplo, dar uma relida num capítulo que fala sobre o problema do Cache e aproveitar os dados do manual da Intel sobre Otimização para escrever um artigo agui…

      O livro é bom…. eu realmente acho isso!

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s