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

TV 3D sem óculos.

O Ethevaldo Siqueira, comentando os tópicos principais para discussão na CES 2011 elencou dentro da lista a evolução da tecnologia das TVs 3D em direção da eliminação da necessidade do uso de óculos especiais. A questão é: as tecnologias que permitiriam a dispensa dos óculos oferecem uma experiência de uso ao usuário que compense o sobrepreço sempre associado aos gadgets mais recentes do mercado?

Primeiro, para quem não sabe ainda sequer porque os óculos são usados hoje para proporcionar a sensação de profundidade nas imagens de cinema e TV, o fato principal que precisa ser entendido é que quem realmente "enxerga" o mundo exterior é o nosso cérebro, usando para isso um par de imagens formadas na retina de cada um dos olhos e transmitidas pelos nervos ópticos até o cortex visual do cérebro para processamento.

O que é a sensação de profundidade na nossa visão? É a capacidade de distinguir entre objetos próximos e distantes de nós. A chave disto é a capacidade de focar os olhos sobre os objetos de tal forma que o cérebro percebe as duas imagens superpostas como uma só. Para conseguir isso precisamos deslocar o eixo dos olhos, conforme a figura abaixo.

Nosso cérebro interpreta ângulos mais abertos (beta, na figura) como uma maior distância do objeto em relação a nós, e ângulos mais fechados (alfa, na figura) como objetos mais próximos. Isto é conhecido há muito tempo, e é a base para várias aplicações práticas (ex.: análise aerofotogramétrica estereoscópica e medidores ópticos de distância para uso civil e militar). O segredo é como conseguir isto em uma sala de cinema e (o que nos interessa mais) em um aparelho de TV.

Tudo se resume, sempre, a projetar em cada olho imagens sutilmente diferentes. No cinema usa-se o artifício da luz polarizada. Para entender isso (com um pouco de imaginação) imagine uma corda. Se você balança a corda em todas as direções (para cima e para baixo, esquerda e direita e todos os planos intermediários) a onda que se propaga na corda é dita não polarizada. As ondas luminosas comuns do nosso dia a dia (geradas ou refletidas do sol ou de fontes luminosas comuns) são assim, sem polarização. Porém, se você balançar a corda em um único plano, digamos de cima para baixo, a onda que se propaga na corda tem apenas um plano de vibração, portanto é dita poarizada. Com o uso de filtros apropriados podemos selecionar ondas luminosas que se propagam em apenas um plano de vibração, portanto luz polarizada.

Nossos olhos não distinguem entre luz polarizada ou não (o que é uma sorte, neste caso), então o que fazemos no cinema 3D é projetar dois filmes ao mesmo tempo, mas cada fotograma apresenta pequenas diferenças de posição dos objetos, e cada filme é projetada de forma a ter planos de polarização bem diferentes (idealmente 90°). Cada lente do óculos é um polaróide (filtro de polarização) que só deixa passar a luz de um determinado plano de polarização. Sintonizando os polaróides de cada olho com cada um dos dois planos de polarização usados na projeção temos estímulos visuais diferentes para cada olho e presto! sensação visual de tridimensionalidade.

Esta técnica não é muito prática para o uso em TV, mas podemos tirar partido de outras coisas. O sinal de TV gerado por uma transmissora aberta, pela transmissora de TV por assinatura (cabo ou DTH) ou por um aparelho reprodutor (video cassete - ainda existem alguns por aí - DVD ou Blu-Ray) sempre é formado por um certo número de quadros por segundo. O mesmo princípio da ilusão de movimento do cinema. Imagine então duplicar a taxa de transmissão de quadros por segundo e separar os quadros transmitidos em duas sequências de quadros alternados, cada uma delas formando um sinal ligeiramente diferente, e temos o material básico para a tridimensionalidade. O problema é fazer com que cada sequência diferente de quadros atinja cada olho separadamente.

Aí entram os tais óculos. O que eles fazem é sincronizar as lentes, que são pequenos painéis de cristal líquido, para ficarem transparentes e opacos alternadamente. O sinal de sincronismo entre a TV e o óculos pode ser transmitido por fio (argh!) ou via rádio (mais comum e elegante, desde que não haja interferência externa). Mas o efeito final é o desejado: tridimensionalidade.

Chegamos então à questão central: como conseguir o mesmo efeito sem o uso dos óculos? A propósito, isto é chamado autoestereoscopia. Excluindo o uso de holografia (que é uma tecnologia possível, porém ainda longe de ter um preço razoável) existem hoje duas tecnologias competindo pela dominância do mercado: barreiras de paralaxe e telas lenticulares (incluídas aí as soluções de integral imaging). Ambas tem o que eu considero um grande defeito: a percepção de profundidade só ocorre para alguns ângulos de visão em relação à tela. Ainda está um pouco longe a situação ideal de um usuário circundando ao longo da sala e olhando para a tela e tendo a percepção contínua de profundidade e de mudança do ponto de visão da cena.

As apostas dos analistas é que estas tecnologias, que estão chegando ao mercado agora, deverão maturar ao ponto de oferecer uma experiência de uso decente até o final de 2015. E, até lá, talvez algo diferente ainda apareça e venha a dominar o mercado. Quem sabe? Vale a pena acompanhar o desenvolvimento de tecnologias de acompanhamento dos olhos, como esta aqui anunciada algum tempo atrás pela SeeReal Technologies, ou o filtro 3D apresentado pela CubicVue na competição i-Stage 2009.

Ou, quem sabe, algum tipo de exibição volumétrica venha a tornar-se viável em vez das telas planas de hoje em dia. De qualquer forma, eu não gastaria meu suado dinheirinho, ainda, em uma TV 3D que anuncie que ela não precisa de óculos.

Sistemas de Numeração 2 - Conversão de Representação

Considere dois sistemas de numeração posicionais com as seguintes características:

O TGE (ver o post anterior desta série) garante que qualquer número inteiro possui representação nos dois sistemas. Vamos supor que estamos habituados a realizar operações aritméticas com as representações b-árias dos números inteiros (no próximo artigo desta série vamos tratar disso). Então temos duas situações que precisamos analisar:

• Conhecida a representação b-ária de um número inteiro N, como encontrar a sua representação B-ária equivalente?
• Conhecida a representação B-ária de um número inteiro N, como encontrar a sua representação b-ária equivalente?

Vejamos o primeiro problema. Pelo TGE sabemos que N = P(b) = P(B). Dividindo N[b] por B[b] obtemos o quociente q[b] e o resto r[b]. Mas:

E estas operações evidenciam as seguintes equivalências:

Então vemos que a divisão da representação b-ária de N resultou em um quociente e um resto (expressos como números b-ários), onde o resto corresponde ao valor do coeficiente do termo de mais baixa ordem do polinônio de potências de B equivalente a N. Se substituirmos este valor do resto b-ário pelo símbolo de valor equivalente no conjunto dos algarismos do sistema B-ário teremos o dígito de mais baixa ordem da representção B-ária de N.

Repetindo este processo sobre o quociente b-ário obtido na primeira divisão, o resto b-ário nos dá condição de determinar o segundo dígito de mais baixa ordem da representação B-ária de N. E, assim por diante, enquanto o quociente b-ário obtido não for menor que B, obtemos os dígitos restantes da representação B-ária de N, em ordem crescente de grandeza. Quando o quiciente b-ário obtido for menor que B ele representa o dígito de mais alta ordem da representação B-ária de N.

O procedimento (algoritmo) abaixo formaliza a solução para o nosso primeiro problema:

1. Obter N[b], B[b] e Alg(B) - conjunto dos algarismos do sistema B-ário;
2. Considere G - ordem de grandeza - igual a zero;
3. Efetue a divisão de N[b] por B[b];
4. Procure em Alg(B) o símbolo de valor equivalente ao resto obtido no passo 3;
5. Escreva o algarismo obtido no passo 4 como o dígito de ordem B^G da representação B-ária de N;
6. O quociente obtido no passo 4 é menor que B?
   SIM: vá para o passo 10,
   NÃO: vá para o passo 7;
7. Incremente o valor de OG em uma unidade;
8. Atribua a N[b] o valor do quociente encontrado no passo 3;
9. Volte ao passo 3;
10. Procure em Alg(B) o símbolo de valor equivalente ao quociente obtido no passo 3;
11. Incremente o valor de G em uma unidade;
12. Escreva o algarismo obtido no passo 4 como o dígito de ordem B^G da representação B-ária de N.

A título de exemplo, vamos aplicar este algoritmo para obter a representação hexadecimal equivalente do número decimal 95207.

O sistema binário possui uma peculiaridade: todos os termos não nulos dos polinômios de representação dos números neste sistema são potências de dois, porque os coeficientes dos termos do polinômio de representação neste sistema só podem ser zero ou um. Isto permite um algoritmo alternativo para o caso da conversão de números representados no sistema b-ário (lembrando: este é sistema no qual estamos habituados a executar operações aritméticas) para o sistema binário:

1. Obter N[b];
2. Encontre o maior k para o qual 2^k seja menor ou igual a N[b];
3. Considere o dígito de N[2] de ordem 2^k igual a 1;
4. Calcule a diferença N[b] - 2^k;
5. A diferença obtida no passo 4 é igual a zero? SIM: vá para o passo 8,
   NÃO: vá para o passo 6;
6. Atribua a N[b] o valor da diferença obtida no passo 4;
7. Vá para o passo 2;
8. Considere todos os dígitos de N[2] de ordens de grandeza menores que o maior k obtido no passo 2 e diferentes dos valores de k obtidos no passo 2 como iguais a zero.

Vamos exemplificar o uso deste algoritmo obtendo a representação binária equivalente ao mesmo número decimal que usamos no exemplo anterior:

Existe outro caso particular de algoritmo de conversão, usado quando as bases dos sistemas de numeração para os quais desejamos fazer conversões de representação são tais que existe a relação:

Então (não vou fazer a demonstração disto) existe uma relação bijetora entre os elementos do conjunto de algarismos B-ários e o conjunto de todos os arranjos de k elementos, com repetição, que podem ser formados a partir dos elementos do conjunto de algarismos b-ários.

Por exemplo: no caso dos sistemas binário (base 2) e hexadecimal (base 16) temos este tipo de relação, com k = 4, conforme mostrado na tabela abaixo.

O algoritmo para conversão de representações no sistema b-ário para o sistema B-ário é:

1. Obter N[b] e a tabela de correspondência entre algarismos B-ários e grupos de k algarismos b-ários;
2. Se o número de dígitos de N[b] é um múltiplo de k,
   SIM: vá para o passo 4,
   NÃO: vá para o passo 3;
3. Acrescente à esquerda de N[b] o menor número de algarismos b-ários que representam a quantidade nula que sejam suficientes para que o número de dígitos de N[b] torne-se um múltiplo de k;
4. Separe (da esquerda para a direita) os dígitos de N[b] em grupos de k elementos;
5. Substitua cada um dos grupos formados no passo 2 pelos seus algarismos B-ários correspondentes.

Como exemplo, vamos usar este algoritmo e a tabela de correspondência binário-hexadecimal acima para obter  representação hexadecimal equivalente de 10111001111100111[2].

Então: 10111001111100111[2] = 173E7[16], o que é coerente (conforme esperado) com o que já tínhamos visto nos exemplos anteriores.

Passando agora à análise do nosso segundo problema (obter a representação b-ária a partir da representação B-ária). E, já que estamos com a mão na massa, o caso inverso da conversão binário para hexadecimal apresentada acima é um algoritmo que replica os mesmos passos, porém na ordem inversa:

1. Obter N[B] e a tabela de correspondência entre algarismos B-ários e grupos de k algarismos b-ários;
2. Substitua cada algarismo da representação B-ária pelo grupo de k algarismos b-ários correspondente;
3. Elimine evntuais algarismos nulos não significativos.

O próprio exemplo anterior pode ser usado para demonstrar este algoritmo. Basta acompanhar a sequência de operações de baixo para cima.

Para o caso genérico de conversão B-ário para b-ário usamos o seguinte algoritmo:

1. Obter N[B];
2. Escreva o polinômio P(B) conforme o TGE, substituindo os coeficientes e a base das potências pelos seus valores equivalentes b-ários;
3. Execute as operações de potneciação, multiplicação e soma para obter Obter N[b].

Como exemplo da aplicaçõe deste algoritmo vamos executar o caso inverso do primeiro exemplo apresentado acima: obter a representação decimal equivalente de 173E7[16].

E obtemos, como esperado, o valor decimal 95207.

No primeiro artigo desta série elencamos dois assuntoa a tratar. Com este artigo encerramos o assunto conversão de representação. O próximo artigo deverá tratar da generalização dos procedimentos da aritmética para que eles sejam aplicáveis a qualquer sistema de numeração.