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.