P LÓGICO DE COMPUTADORES Prof. Ricardo Rodrigues … · realização de cálculos com valores reais dispostos em arranjos de matrizes e vetores. ... várias UAL’s operando sobre

PROJETO LÓGICO DE COMPUTADORES Prof. Ricardo Rodrigues Barcelar

http://www.ricardobarcelar.com.br

1

- Aula 6 -

ARQUITETURAS AVANÇADAS DE COMPUTADORES

1. INTRODUÇÃO

As arquiteturas dos processadores têm evoluído ao longo dos anos, e junto com ela o conceito de arquitetura avançada tem se modificado.

Nos anos 60 os computadores ditos de grande porte (IBM, CDC) eram considerados exemplos de alto desempenho.

Um pouco depois surgiram os supercomputadores, arquiteturas específicas para a realização de cálculos com valores reais dispostos em arranjos de matrizes e vetores.

No início dos anos 80 surgiram os primeiros microcomputadores, com desempenho muito longe dos computadores de grande porte e supercomputadores.

A evolução das tecnologias de integração de componentes em larga escala permitiu que esses processadores evoluíssem em desempenho, atingindo um amplo espectro de aplicações comerciais.

2. REVISÃO DE CONCEITOS

2.1. Arquitetura CISC

A arquitetura CISC possui as seguintes características:

- Instruções complexas demandando um número grande e variável de ciclos de máquina para sua execução.

- Uso de diversos modos de endereçamento de operandos.

Instruções com formato muito variável.

- Diferentes tipos de instruções podem referenciar operandos na memória principal.

- Cada fase do processamento da instrução pode ter duração variável em função da complexidade.

Essa implementação traz alguns inconvenientes, como:

- Difícil implementação com uso de pipeline

- Baixas taxas médias de execução das instruções por ciclo

- A unidade de controle é em geral microprogramada.

- Códigos compactos podem ser gerados pelos compiladores.

2.2. Arquitetura RISC

A arquitetura RISC possui as seguintes características:



2

- Instruções mais simples demandando um número fixo de ciclos de máquina para sua execução;

- Uso de poucos modos simples de endereçamento de operandos;

- Poucos formatos diferentes de instruções;

- Apenas as instruções de “load” e “store” referenciam operandos na memória principal;

- Cada fase de processamento da instrução tem a duração fixa igual a um ciclo de máquina.

Assim como na arquitetura CISC, esta trás algumas conseqüências, como:

- São implementadas com o uso do pipeline;

- A taxa média de execução de instruções por ciclo de máquina também é baixa, porém superior a arquitetura CISC;

- A unidade de controle é em geral “hardwired”;

- Processo de compilação é complexo e requer cuidados especiais para otimização do desempenho do código gerado.

Essas arquiteturas são úteis para dar soluções as mais diversas necessidades do dia-a-dia. No entanto, algumas aplicações nas áreas de ciência, engenharia e na indústria demandam computadores com alto potencial de processamento (alta performance), mas a velocidade de operação dos circuitos eletrônicos está limitada, por alguns fatores:

- A velocidade dos sinais elétricos é aproximadamente igual à velocidade da luz;

- A proximidade dos componentes aumenta a dissipação de calor;

- Tamanho dos transistores tem limite físico (princípio da incerteza de Heisenberg).

3. ARQUITETURAS COM DESEMPENHO SUPERIOR A UMA INSTR UÇÃO POR CICLO

Existem diversas formas de melhorar o desempenho de computadores para atender necessidades de áreas específicas da ciência, engenharia e da indústria. Dentre elas podemos citar:

- Arquitetura superescalares: Possibilitam a execução de múltiplas instruções, escalonadas por “hardware” e/ou “software”, concorrentemente.

- Arquitetura VLIW ( Very Long Instruction Word): Possibilitam a execução de múltiplas operações, escalonadas por “software”, concorrentemente.

- Arquitetura Multithreading e SMT: Permitem a execução simultânea de mais de uma thread no processador.

- Arquiteturas Multicore: Permite o uso de vários processadores em um mesmo encapsulamento, compartilhando ou não a cache de nível 2.

Todas essas arquiteturas possibilitam a otimização na execução de instruções e/ou operações por meio de hardware ou de software.



3

3.1. Arquiteturas Superescalares

As máquinas superescalares são conhecidas por possuírem mais de um pipeline em paralelo em sua arquitetura. Isso gera problemas de acesso aos recursos comuns, que precisam ser duplicados em sua maioria. Os barramentos devem possuir largura suficiente para a busca de mais de uma instrução por ciclo.

O uso de caches separadas para dados e instruções é uma solução para permitir leitura e escrita simultâneas à memória. É comum, também a existência de várias portas de leitura e de escrita no banco de registradores.

Devido a problemas de dependências de dados e controle pode acontecer que em alguns ciclos não haja instruções prontas para serem executadas. Esquemas mais simples de despacho, simplesmente congelam o pipeline nesse caso. Esquemas mais sofisticados continuam a busca e tentam executar as instruções fora-de-ordem, com mecanismos que posteriormente permitam a retirada dessas instruções, e atualização do estado da máquina, na mesma ordem estabelecida pelo programa objeto.

3.2. Arquiteturas VLIW ( Very Long Instruction Word)

Estas são máquinas que exploram o paralelismo no nível das instruções. Várias operações são executadas em paralelo em diferentes unidades funcionais, tais como em máquinas superescalares. A diferença está no controle do despacho e na terminação das operações.

Nas máquinas superescalares as dependências são resolvidas em tempo de execução por um hardware dedicado, nas máquinas VLIW as dependências são resolvidas em tempo de compilação pelo compilador.

Em uma máquina VLIW, várias operações são codificadas em uma mesma instrução. A palavra de instrução é bastante longa, podendo conter várias operações (que operam sobre vários operandos) independentes. A posição de cada operação dentro da palavra VLIW determina a unidade funcional que será usada. Deste modo, o hardware de despacho é simples.

Em uma máquina VLIW o compilador é responsável por determinar as operações que serão executadas em paralelo. As operações que possam ser executadas em paralelo são atribuídas a uma mesma palavra de instrução. Dentro de um mesmo bloco básico (seqüencial) as instruções podem ser escalonadas com base na dependência de dados.

3.3. Arquiteturas SMT

SMT é uma técnica que permite múltiplas threads despacharem múltiplas instruções a cada ciclo para unidades funcionais de um processador superescalar.

O SMT combina a capacidade de despacho de múltiplas instruções das arquiteturas superescalares, com a habilidade de esconder latência das arquiteturas multithreading.

A cada instante de tempo instruções de diferentes threads podem estar sendo executadas simultaneamente. Busca reduzir o número de slots de despacho não ocupados a cada ciclo (elevado em arquiteturas multithreading) e o número de ciclos em que nenhuma instrução é despachada (elevado em arquiteturas superescalares).



4

As arquiteturas SMT podem ser de três tipos básicos:

- Full Simultaneous issue: modelo ideal, mas de difícil realização, onde não há restrição sobre o número de instruções de cada thread que pode ser despachada a cada ciclo.

- Limited Simultaneous Issue: apenas um número limitado (1 a 4 tipicamente) de instruções de cada thread pode ser despachado a cada ciclo.

- Limited Connection: restringem o número de unidades funcionais de cada tipo que podem estar conectadas a cada contexto.

Figura 1 - Threads



5

Figura 2 - Thread

3.3. Arquiteturas Multicore

Vários processadores encapsulados em uma mesma pastilha, podendo compartilhar ou não a cache de nível. Normalmente são processadores idênticos, tanto em termos de arquitetura quanto em velocidade de processamento. As tarefas podem ser executadas indistintamente em cada um dos processadores.

O sistema operacional é responsável pelo escalonamento das tarefas (processos e/ou threads) para cada um dos processadores. É uma alternativa muito adotada recentemente devido aos ganhos de consumo de energia que podem ser obtidos, sem perda de desempenho quando há um número adequado de tarefas para serem executadas em paralelo.

4. PROJETO DE MÁQUINAS PARALELAS

Possíveis soluções para aumento de performance seriam o uso de paralelismo em nível de instruções (~10x), através de pipeline ou arquitetura superescalar, ou o paralelismo real (~100x, 1000x), onde vários processadores trabalham juntos e com eficiência.

Os projetos de computadores paralelos diferem basicamente na quantidade de elementos (processadores e memórias), no tamanho desses elementos, no tipo de elementos usados e na maneira de interconectá-los.



6

4.1. Aspectos Importantes

Os Sistemas de Memória, em computação paralela estão divididos em módulos que operam de modo independente entre si, porém em paralelo para permitir que vários processadores acessem as informações simultaneamente. Com isso, podem estar integrados ao processador ou localizados em placas separadas, sendo possível serem projetados com 2, 3 ou, às vezes, 4 níveis de cache.

Os esquemas de interconexão podem ser, a grosso modo, de dois tipos:

- Estáticos: ligam os componentes do sistema de maneira física: em estrela, em anel ou em grade.

- Dinâmicos: componentes estão ligados a elementos comutadores que roteiam mensagem entre eles.

Outro aspecto importante é a granularidade no paralelismo, pois se refere aos tipos de algoritmos e softwares (aplicações) que são rodados no computador e tem reflexo direto no hardware e podem ser:

- Paralelismo de granularidade alta (ou grossa): existentes nos sistemas que rodam programas grandes em paralelo com pouca, ou nenhuma, comunicação entre eles. Rodam em regime de tempo compartilhado e podem atender a milhares de usuários remotos. São exemplos deste tipo de paralelismo sistemas de transição de bancos, de empresas aéreas, etc.

- Paralelismo de granularidade baixa (ou fina): implementado nos sistemas de processamento vetorial, onde se usa um alto grau de processamento pipeline, ou por meio de várias UAL’s operando sobre a mesma instrução ao mesmo tempo. O objetivo é ganhar velocidade na solução de um único tipo de problema. São exemplos computadores que rodam jogo de xadrez, previsão de tempo, etc.

- Paralelismo de granularidade média: possui as características dos dois modelos anteriores.

Além do paralelismo no processamento, há que se considerar o nível de acoplamento no paralelismo que se relaciona as características de hardware:

- Sistemas fracamente acoplados: possuem pequena quantidade de processadores grandes, independentes e com conexões de baixa velocidade entre si.

- Sistemas fortemente acoplados: compostos de processadores de pouca potência computacional, fisicamente próximos uns dos outros e que interagem freqüentemente por meio de redes de comunicação de alta velocidade.

4.2. Modelos de Comunicação

O Modelo de Comunicação refere-se à maneira como os processadores se comunicam entre si para trocar informações quando da execução de diferentes partes de uma mesma tarefa. Nesse sentido, é importante separar a forma como se dá a comunicação de acordo com a organização do processamento:



7

4.2.1. MULTIPROCESSADORES (ou Sistemas de Memória Compartilhada)

Neste modelo todos os processadores compartilham de uma única memória física. Dois processos se comunicam escrevendo/lendo (Load/Store) dados na memória compartilhada. A Figura abaixo ilustra que cada processador é responsável pelo processamento de uma parte da imagem. Essa arquitetura requer algum tipo de coordenação na execução da tarefa, pois alguns objetos ocupam mais do que uma seção da imagem.

Figura 3 - (a) Sistema multiprocessador com 16 processadores compartilhando uma única memória. (b) Imagem

dividida em 16 seções, cada uma delas sendo analisada por um processador diferente

4.2.2. MULTICOMPUTADORES (ou Sistemas de Memória Distribuída)

Diferente do modelo anterior, cada processador tem sua própria memória, com exclusividade para leitura e escrita diretas. Dois processos trocam mensagens entre si usando a rede de interconexão e as primitivas send e receive, implementadas por software.

Quando um processador A precisa de dados de outro processador B:

- O processador A envia (send) uma mensagem requisitando uma cópia da memória de B.

- O processador A fica bloqueado até receber (receive) uma resposta do processador B.

A divisão correta dos dados e sua colocação em posições ótimas é um aspecto muito importante para eficiência dos multicomputadores. Isto é responsabilidade do programador.



8

Figura 4 - (a) Sistema multicomputador com 16 processadores, cada qual com a sua própria memória. (b) O mapa de

bits da Figura 1 dividido entre as 16 memórias do sistema.

É importante observar que programar um multicomputador é muito mais difícil do que programar um multiprocessador.

Multicomputadores de grande porte são muito mais simples de serem construídos, e muito mais baratos do que multiprocessadores com o mesmo número de processadores

Assim, é muito complicado implementar compartilhamento de memória para centenas de processadores e, mais simples construir multicomputadores com 10.000 processadores.

Assim sendo, solução híbrida seria uma alternativa interessante como forma de combinar dos pontos fortes de cada arquitetura, ou seja, a busca de computadores fáceis de construir e de programar.

A figura abaixo demonstra algumas soluções que podem ser usadas para implementação de memória compartilhada em diferentes níveis da máquina.



9

Figura 5 - As diversas camadas nas quais a memória compartilhada pode ser implementada.

(a) hardware. (b) O sistema operacional. (c) O ambiente de execução da linguagem.

4.3. Redes de Interconexão

As redes de interconexão usam mecanismos de troca de mensagens (pacotes) para implementar a comunicação entre seus componentes. Além dos processadores e dos módulos de memória possuem outros três componentes:

- Interfaces

- Links

- Comutadores

As interfaces são dispositivos responsáveis pelo envio e recepção das mensagens. São representados pelos chips ou placas ligadas a cada barramento local dos processadores. Podem se comunicar tanto com o processador quanto com a memória local e faz a leitura e escrita em várias memórias, o que possibilita a transferência de blocos de dados.

Os links são canais físicos sobre os quais os bits se movimentam. Consiste em banda passante máxima (# de bits que pode ser transferidos por segundo). A transferência dos dados pode ocorrem de três modos distintos, transmissões em uma, duas ou ambas as direções simultaneamente:

- Simplex

- Half duplex

- Full duplex

Os comutadores são dispositivos com várias portas de entrada e de saída (transferem entradas para determinadas saídas).



10

Ao se projetar ou analisar uma rede de interconexão deve-se considerar, ainda, a topologia, o funcionamento dos comutadores e o algoritmo de roteamento de mensagens.

4.3.1. TOPOLOGIA

A topologia de uma rede de interconexão descreve a organização de seus links e de seus comutadores. Geralmente são modelados como grafos, com os links sendo os arcos e os comutadores os nós.

Figura 6 - Diversas topologias. Os pontos representam os comutadores. Os processadores e as memórias não

aparecem na figura. Topologia: (a) em rede. (b) rede totalmente conectada. (c) em árvore. (d) em anel. (e) em

grade. (f) double torus. (g) em cubo. (h) hipe

- Cada nó da rede tem certo número de links ligados a ele, conhecido como grau do nó .

- O diâmetro da rede é definido como a distância, medida em números de links a serem percorridos, entre dois nós mais afastados.



11

- A dimensão da rede é determinada pelo número de escolhas que podem ser feitas para se ir de uma fonte para um destino. Quando se tem uma única escolha, a dimensão é zero. A dimensão é n-1 quando se tem n escolhas.

4.3.2. COMUTADORES

Uma rede de interconexão é composta de comutadores e de fios que os conectam. Sua tarefa é aceitar pacotes que chegam a qualquer uma das portas de entrada, enviando-os para a porta de saída correta, de acordo com seu destino final.

Cada porta de saída é ligada a uma porta de entrada de outro comutador por intermédio de um link serial ou paralelo, conforme linhas pontilhadas abaixo.

Figura 7 - Rede de interconexão em forma de uma grade quadrada com 4 comutadores.

Somente dois dos quatro processadores aparecem na figura

Os comutadores podem ser empregados de diversas formas de acordo com as estratégias de uso dos comutadores.

4.3.2.1. Comutação de circuitos

Reservam-se, a priori, todos os recursos (portas e buffers) do caminho entre a origem e o destino antes que o pacote possa ser enviado. Assim, os bits são enviados pela fonte na velocidade máxima, passando por todos os comutadores até chegar ao seu destino. A Figura 7, exposta acima, ilustra bem essa estratégia onde são reservadas três portas de entrada e três de saída.



12

A desvantagem desta abordagem é que os recursos alocados ficam bloqueados para outras transmissões até que a transmissão corrente termine.

4.3.2.2. Comutação de pacotes store-and-forward:

Nesta abordagem não há a necessidade de reserva antecipada de recursos.

Figura 8 - Rede de comutação de pacotes store-and-forward

Na ilustração acima os comutadores utilizam buffers para armazenar os pacotes evitando perda de informação. Existem três estratégias de armazenamento:

- Armazenamento na entrada: O pacote é armazenado em 1 fila (FIFO) e espera porta de saída ser liberada. O problema nesta abordagem é o bloqueio pelo cabeça da fila que segura outros pacotes até que sua porta seja liberada.

- Armazenamento na saída: Na medida em que os bits vão chegando, eles vão sendo armazenados nos buffers das respectivas portas de saída. Isso evita o bloqueio pelo cabeça de fila, pois pacotes da porta m não são bloqueados pelos da porta n. Este modelo pode ter problemas com tamanhos dos buffers com perdas de pacotes.

- Armazenamento comum: Um único pool de buffers é alocado dinamicamente às portas, conforme o necessário. O problema é que implementa um modelo de gerenciamento mais complexo. Sofre, ainda, o problema de latência (retardo) ao longo da rede de interconexão, uma vez que cada pacote só pode mudar de buffer após ter sido armazenado por completo no buffer anterior.

- Solução híbrida: A Comutação de pacotes divide o pacote em subpacotes

4.3.3 ALGORITMOS DE ROTEAMENTO

A regra para se determinar qual a sequência de nós que um pacote deve seguir para sair da fonte e chegar ao destino é chamado de algoritmo de roteamento .



13

Um bom algoritmo de roteamento deve dividir a carga da rede sobre seus diversos links, de maneira a utilizar totalmente a banda passante disponível. O algoritmo de roteamento deve evitar ocorrência de deadlock. Um deadlock ocorre quando vários pacotes em trânsito requisitam, ao mesmo tempo, um conjunto de recursos, mas nenhum deles consegue obter todos os recursos. Nesse caso todos os pacotes ficam bloqueados (travados) para sempre.

Figura 9 - Ocorrência do deadlock em uma rede de comutação de circuitos

4.4. Desempenho

O desempenho de máquinas paralelas pode seguir duas abordagens de medida: por hardware ou por software.

4.4.1. MEDIDAS NO HARDWARE

Na medida no hardware considera-se

- Velocidade do processador

- Velocidade dos dispositivos de E/S

- Performance da rede de interconexão

Essa última depende das medidas de desempenho conhecidas como latência e da banda passante .

A Latência total é o tempo gasto por um processador para enviar um pacote e receber uma resposta (depende da topologia da rede e dos tempos de inicialização e de transmissão).



14

A Banda passante agregada é a quantidade máxima de bits que podem transitar pela rede de uma só vez.

A Banda passante média de cada processador limita a quantidade de dados que cada processador pode alocar em sua saída.

Nesse contexto a latência é mais importante que a banda passante.

4.4.2. MEDIDAS DO SOFTWARE

Para o usuário interessa saber quão mais rápido seu programa vai rodar numa arquitetura em paralelo, em relação a um único processador utilizaremos a figura baixo para ilustrar a performance de 3 programas e o quanto eles se afastam do ganho perfeito.

Figura 10 - Os programas reais não conseguem chegar ao ganho perfeito, indicado pela linha pontilhada.

A razão de não se ter um ganho perfeito deve-se à:

- Componentes sequenciais (nas inicializações, leitura de dados e obtenção de resultados) de programas

- Latências nas comunicações

- Bandas passantes finitas

- Nem todos os processadores são usados

- Ineficiências de algoritmos: nem todos os algoritmos ótimos são paralelizáveis



15

4.5. Software

Sem um software paralelo, o hardware paralelo tem pouco ou nenhum uso. Dessa forma é de suma importância que os programas e aplicativos sejam construídos para suportar hardware que opera em paralelo.

Existem quatro metodologias para produção de software para máquinas paralelas:

a) Adicionam-se bibliotecas para tratamento de números às linguagens de programação seqüencial, como inversores de matrizes, soluções para equações diferenciais, etc. Os Cálculos podem ser realizados por diversos processadores, em paralelo. O problema é que somente os cálculos especiais são realizados em paralelo, o resto do programa é seqüencial.

b) Adicionam-se bibliotecas especiais com primitivas de comunicação e controle. O programador é responsável por criar e gerenciar o paralelismo, usando as primitivas

c) Adicionam-se à linguagem de programação convencional, algumas estruturas especiais para criação de processos paralelos, execução de operações aritméticas sobre todos os elementos de um vetor ao mesmo tempo e execução, em paralelo, das iterações de um loop.

d) Desenvolve-se uma linguagem de programação nova, totalmente voltada para a programação paralela. A vantagem é que se tem uma linguagem dedicada à programação paralela, poremos desenvolvedores de programas devem aprender essa nova linguagem.

Existem cinco aspectos que formam o coração de todos os softwares para computadores paralelos, a saber:

- Modelos de Controle

- Granularidade do paralelismo

- Paradigmas computacionais

- Métodos de comunicação

- Primitivas de sincronização

Documents

P LÓGICO DE COMPUTADORES Prof. Ricardo Rodrigues … · realização de cálculos com valores reais dispostos em arranjos de matrizes e vetores. ... várias UAL’s operando sobre