Tipos e Técnicas de Pipeline

(Resenha Capítulo 4)

         

            Com a constante necessidade de maquinas cada vez mais poderosas, o desperdício de tempo dentro do processador deve ser evitado ao máximo.  A técnica de Pipeline possibilita a execução paralela das micro-instruções. Ou seja, esta técnica permite uma sobreposição temporal das fases de execução de uma instrução. Diante do antigo paradigma onde cada instrução era executada separadamente, passando por todas as fazes de execução no processador (Por exemplo: leitura da memória principal, carregamento nos registradores, utilização da ULA para processamento, escrita no registrado e escrita na memória principal), a utilização do Pipeline dividir esta execução em etapas permitindo a serialização no processamento das instruções.

            Esta técnica foi evoluindo com o tempo e, com isso, incorporando novas idéias de implementação de forma a aumentar o desempenho do processador.  A seguir veremos alguns tipos de Pipeline e como elas funcionam resumidamente.

Superpipele:

            É fácil perceber que um grande número de divisões na execução de uma instrução (numero de estágios de Pipeline) resulta em um melhor desempenho de processamento, pois o numero de instruções executadas em série será maior. Isso se o Pipeline não tiver que ser esvaziado (todos os estágios devem esperar o encerramento de uma instrução especifica) com muita freqüência. O Superpipelining se baseia nestes princípios.

            A desvantagem desta técnica, quando comparado a um Pipeline, é que este possui uma maior complexidade de desenvolvimento e uma maior dependência de detecção de desvios, visto que o esvaziamento do Pipeline resultaria num desperdício de mais estágios.

Pipeline Super Escalar:

            Este Pipeline é obtido aumentando-se o numero de Pipelines. Ou seja, mais de um Pipeline trabalhando de forma paralela no processador. Para que ele tenha um bom desempenho as instruções não devem ter muita latência, facilitando o trabalho sincronizado dos Pipelines. Desta forma o processador deve possuir um bom algoritmo de tratamento de latências.

            A grande vantagem do Pipeline Super Escalar é que o paralelismo na execução das instruções acontece de forma real, possibilitando um grande aumento de desempenho. Os pontos negativos estão no fato de que as micro-instruções devem ser cuidadosamente estudadas e a complexidade no tratamento de desvios aumenta significativamente.

Pipeline com Predição de Desvio:

            Predição de desvios são técnicas utilizadas para evitar o esvaziamento do Pipeline, deixando o fluxo de processamento das instruções contínuo e sem quebras. Estas técnicas podem ser implementadas por Hardware ou Software e são fundamentais para um uso eficiente do Pipeline.

            A predição de desvio pode ser estática ou dinâmica. Na predição estática a unidade de controle assume que o desvio sempre ocorrerá, resultando numa taxa de 50% de acerto. Na predição dinâmica a unidade de controle utiliza informações coletadas em tempo de execução para decidir-se sobre o desvio.

Pipeline com Execução Fora de Ordem:

            A Execução Fora de ordem faz o processador reordenar as instruções para melhor aproveitar o Pipeline e evitar a seu esvaziamento. Esta reordenação é complexa devido ao fato de que instruções que dependem uma das outras devem ser tratadas de forma especial. O uso da execução fora de ordem necessita de um controle para reordenação das instruções após executá-las.

            Estes “tipos de Pipiline” são meramente teóricos, na prática eles podem possuir mais de uma dessas características a fim de obter um melhor de desempenho.

Principais Referências:

• Jourdan, Stéphan; Carrière, Dominique & Litaize, Daniel. A High Out-of-Order Issue Symmetric Superpipeline Superscalar Microprocessor. França.
• Sampaio, Daniel L. & Braz, Marco H. Arquiteturas Superescalares.

Arquiteturas Reconfiguráveis e Unidade de Controle

(Resenha Capítulo 3)

A Arquitetura Reconfigurável permite um tipo de computação semi-flexível que está entre computação dedicada (implementada por hardware) e a computação de propósito geral (implementado por software). Em termos gerais, a Arquitetura Reconfigurável tenta combinar a velocidade do Hardware e a flexibilidade do Software. Um Sistema de Arquitetura Reconfigurável possui a habilidade de modificar seu próprio hardware para se adequar à aplicação.

Pode-se utilizar este conceito de reconfigurabilidade em vários dispositivos físicos, entre eles o processador.  Na Literatura é fácil encontrar o conceito de Processadores com Conjunto de Instruções Reconfiguráveis. Estes possuem em seu núcleo de microprocessamento conjuntos de instruções implementado sob uma lógica reconfigurável, que pode sofrer alterações durante o tempo de execução, oferecendo ao processador a possibilidade de se adaptar à aplicação.

As instruções reconfiguráveis podem ser (e normalmente são) identificadas por um Código de Operação (CodOp) especial através de um campo extra contido na própria instrução. A forma mais utilizada de se fazer isto é através da utilização de um identificador que indexa uma tabela de configuração onde são armazenadas palavras de reconfiguração.

Codificação das instruções através de identificador.

          O primeiro processador reconfigurável foi criado por Razdan e Smith em 1994 e chamado de PRISC (PRogrammable Instruction Set Computer). O PRISC contém um conjunto de instruções RISC e uma série de instruções de aplicação especifica que são implementadas em hardware por unidades funcionais programáveis (PFUs).

A fim de se combater tendências de se desenvolver diferentes formas de utilização de lógica reconfigurável, utiliza-se o padrão OCP (Open Core Protocol). Este padrão consiste em um conjunto de definições de sinais e protocolos de comunicação desenvolvido de modo a prover a interconexão de módulos de circuitos, tornando compatível a troca de informações entre eles. Este protocolo define uma série de sinais básicos para fim de sincronização, endereçamento de escrita, transferência de dados, entre outros.

[Augusto, 2005] Construiu a Unidade de Controle para um processador reconfigurável sob a forma de uma maquina de estados finitos. Desta forma, conjuntos distintos de instruções simples podem ser utilizados pelo processador. Cada código de operação corresponde a uma série de estados que podem estar associados a uma ou mais instruções distintas. Assim, cada conjunto executa uma instrução diferente a partir do mesmo código de operação. Foram criadas algumas operações para que o usuário pudesse mudar o conjunto de instruções utilizado.

Tendo em vista estes aspectos dos sistemas computacionais reconfiguráveis, conclui-se que estes, apesar de possuir certa complexidade em seu desenvolvimento, podem ser utilizados em aplicações hibridas que desejam se aproveita da flexibilidade dos sistemas de propósito geral e da velocidade dos sistemas dedicados.

Principais Referências:

• Bauer, L.  Shafique, M.  Henkel, J.Concepts, Architectures, and Run-time Systems for Efficient and Adaptive Reconfigurable Processors. Karlsruhe Inst. of Technol. (KIT), Karlsruhe, Germany. IEEE 2011.

• Augusto, L. Casillo. Projeto e Implementação em FPGA de um Processador com Conjunto de Instrução Reconfigurável Utilizando VHDL. Universidade Federal do Rio Grande do Norte. Natal - RN. Maio de 2005.

Políticas de Substituição de Cache

(Resenha do  Capítulo 2)

        Cache é um conceito utilizado na Computação que se refere ao mecanismo de acessar de forma mais rápida informações consideradas importantes levando em conta algum critério.  Este conceito é utilizado pelos navegadores Web, nas Redes de Computadores, nos Bancos de Dados, nos Servidores Web e etc.

Para fins desse micro artigo, cache se refere à memória de alta velocidade utilizada pelo processador a fim de evitar (ou reduzir) o acesso a “lenta” memória principal. Especificamente, abordaremos a forma (política) como as informações contidas na cache são substituídas por outras consideradas mais relevantes em um determinado momento.

A política de substituição das informações da memória cachê influencia consideravelmente o desempenho do processamento das informações em uma CPU. De acordo com Zebchuk et. al. (2008), as políticas de substituição comumente usadas em processadores modernos são em média 57% pior que uma “política de substituição ótima”. Abaixo citamos as políticas de substituição mais comuns.

Políticas de Substituição Não-Adaptativas:

LRU (Least-Recently Used): Este método utiliza uma pilha para acompanhar a ordem dos acessos mais recentes ao conjunto de linhas da cache. Quando uma linha é acessada, esta é movida para o topo da pilha. Ao escolher uma linha para ser substituída por uma informação vinda da memória principal a linha que estiver no fundo da pilha (a linha menos recentemente usada - Least-Recently Used) será substituída. Tradicionalmente, a nova linha é colocada no topo da pilha.

LFU (Least-Frequently Used): A política LFU mantém um contador de acesso para cada linha da memória. Ao escolher uma linha para a substituição, a linha com a contagem mais baixa (a linha menos freqüentemente usada - Least-frequently Used) é descartada. Políticas LFU devem implementar um mecanismo de envelhecimento que decrementa automaticamente o valor do contador de acessos de cada linha ao longo do tempo para evitar a poluição da cache com linhas obsoleto.

Políticas Aleatórias: Outras políticas não-adaptativas muito utilizadas são as políticas N-MRU e Aleatória. A Política Aleatória escolhe aleatoriamente uma linha para ser substituída. A vantagem deste método é que ele não necessita de nenhum metadado (como pilhas e filas) para o seu funcionamento. A Política N-MRU (Not Most Recently Used) é uma variação da Política Aleatória e escolhe aleatoriamente a linha a ser substituída com exceção da linha mais recentemente usada.

Políticas com Inserção Adaptativa: 

Nestas políticas novas linhas da cache são inseridas (e não necessariamente substituídas) na pilha. Estes métodos devem tratar o esgotamento da memória cachê (quando o working set for maior que tamanho disponível pela cache).

LIP (LRU Insertion Policy): É um método baseado em LRU onde novas linhas são inseridas abaixo da pilha (posição LRU) e só as promove para o topo da pilha (posição MRU) após um novo acesso a memória principal.

BIP (Bimodal Insertion Policy): É uma variação do LIP que utiliza um “parâmetro bimodal” que pode alterar o comportamento LIP inserindo a nova linha diretamente na posição MRU ou não.

Shepherd Cache: 

Este método propõe uma divisão lógica de uma cache em dois componentes. Um Shepherd Cache com política de substituição utilizando a filosofia FIFO (primeiro a entrar é o primeiro a sair), e um Main Cache que emula uma política de substituição ótima.

Pode-se encontrar na Literatura várias outras propostas de políticas de substituição das linhas da memória cache.  Zebchuk et. al. (2008) propõem duas novas políticas de substituição (Lightweight Shepherd Cache e Extra-Lightweight Shepherd Cache) baseadas no método Shepherd Cache.

Principais Referências:

• Zebchuk et. al. Re-Examining Cache Replacement Policies. Systems Technology Lab. Intel Corporation. IEEE. 2008.
• Zadnik,Martin & Canini, Marco. Evolution of Cache Replacement Policies to Track Heavy-hitter Flows. IEEE. 2011.
• Scoton, Filipe M. Power Laws na Modelagem de Caches de Microprocessadores. Universidade de São Paulo. São Paulo. 2011.

A História do Transistor

(Resenha do Capítulo 1)

Bardeen, Shockley e Brattain

Todo dia estamos constantemente em contato com diversos aparelhos e dispositivos como: carro, rádio, televisor, aparelho celular, microondas, computador e etc. Talvez a existência destes equipamentos não fosse possível sem o uso de uma interessante e minúscula peça eletrônica chamada Transistor.  O transistor é um triodo que pode ser usado para ampliar um sinal elétrico controlando a corrente ou a voltagem entre dois dos filamentos. Além disso, ele pode ser usado como uma chave elétrica (que abre e fecha), permitindo ou impedindo a passagem de corrente.

Oriundo de estudos sobre semicondutores na primeira metade do século XX, o transistor foi um dos grandes responsável pelo gigantesco desenvolvimento das indústrias de eletrônicos. Um semicondutor é um material que possui um comportamento bem particular quando submetida a uma ddp: a resistência de passagem de corrente varia conforme a diferença de potencial aplicada a sua polaridade produzindo um efeito de retificador (ou efeito transistor).

Estas propriedades dos semicondutores representaram uma grande oportunidade para substituir as antigas e antiquadas válvulas (tubos de vácuo). Visto que estas possuíam uma baixa vida útil e um grande consumo de energia, inviabilizando a construção de equipamentos eletrônicos mais complexos.

Os estudos sobre semicondutores possibilitaram um grande avanço na área de Física de Estados Sólidos. Na década de 20 e 30 foram publicados vários artigos e descobertas sobre o assunto por diversos estudiosos (entre eles H. Wilson, W. Schottky e E. Gruniesen). Estudos esses amplamente utilizados pelos pesquisadores da Bell Telephone Laboratories (J. Bardeen, W. Brattain e W. Shockley) que produziram o primeiro transistor (transfer resistor) em 1947. A partir daí várias melhorias foram aplicadas no processo de fabricação de transistores resultando num produto de qualidade o suficiente para substituir as válvulas e relés.

Por muitos anos os transistores permaneceram sendo construídos como componentes eletrônicos individuais que juntados com outros componentes (diodos, resistores, capacitores, indutores e etc.) formavam um circuito eletrônico. Porém, a complexidade dos circuitos estava ficando cada vez maiores tornando sua montagem difícil. Até que em 1958-1959 J. Kilby do Texas Instruments e R. Noyce da Fairchild solucionaram o problema do grande numero de componentes, e o circuito integrado foi desenvolvido. Neste processo, uma grande quantidade de transistores e outros componentes eletrônicos poderiam ser construídos ao mesmo tempo e na mesma peça de semicondutor.

Por mais de 30 anos, desde 1960, o número de transistor por unidade área vem dobrando a cada 1 ano e meio (Lei de Moore). Nos últimos anos muitas pesquisas apontam para uma chegada no limite desta redução no tamanho dos transistores, dando origem a investimentos de novas tecnologias na fabricação de transistores (Strained Silicon e high-k/metal gate).

Mais recentemente a Intel anunciou que sua nova geração de processadores conterá um novo formato de transistores, os transistores 3D (possuindo minúsculos 22nm). Pela primeira vez na história os transistores de silício serão inteiramente em três dimensões, proporcionando um maior controle do transistor: maximizando o fluxo de corrente quando o transistor estiver ligado e minimizando quando estiver desligado.

Mas será que este é o limite? Parece que não desta vez. Pesquisas na Austrália (University of New South Wales) anunciaram a construção de um transistor funcional substituindo sete átomos de cristal de silício por átomos de fósforo, criando um transistor de apenas 4 nm.

Principais Referencias: 

• Chiquito, Adenilson J. & Lanciotti, Francesco Jr. O Transistor, 50 Anos. Universidade Federal de São Carlos. Fevereiro de 1998.
• Intel Comporation. Over 6 Decades of Continued Transistor Shrinkage, Innovation. Santa Clara, Califórnia. Maio de  2011.
• Um Microcircuito Chamado Chip. Disponível em: <http://200.19.92.57/wschui/cix/chip.htm>. Ultimo Acesso em: 25 de Agosto de 2011.