PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
- 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:
1
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
- 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-adia. 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 INSTRUÇÃ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.
2
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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).
3
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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
4
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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.
5
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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:
6
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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.
7
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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.
8
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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).
9
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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.
10
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
- 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.
11
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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.
12
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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).
13
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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
14
PROJETO LÓGICO DE COMPUTADORES
Prof. Ricardo Rodrigues Barcelar
http://www.ricardobarcelar.com.br
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
15