PROCESSAMENTO PARALELO E DISTRIBUIDO

Prévia do material em texto

PROCESSAMENTO 
PARALELO E 
DISTRIBUÍDO
OBJETIVOS DE APRENDIZAGEM
 > Apresentar a classificação das arquiteturas.
 > Diferenciar os fluxos de controle de execução.
 > Comparar os tipos de comunicação: memória compartilhada e distribuída.
Introdução
Neste capítulo, você conhecerá os componentes de um computador, a arquite-
tura de computadores e a maneira como esses componentes se interligam e se 
comunicam. Além disso, você poderá compreender as diferentes formas como 
as instruções podem ser executadas, bem como o modo de funcionamento da 
comunicação de memória compartilhada e distribuída.
Os conceitos que serão aqui apresentados servirão de base para a com-
preensão de como um computador funciona, como ele processa instruções e 
o papel que cada componente desempenha. O entendimento desses conceitos 
é imprescindível para a construção de programas paralelos e distribuídos que 
tirem o melhor proveito dessas arquiteturas.
Arquiteturas de 
computadores
Maycon Viana Bordin
Componentes e arquiteturas de 
computadores
Computadores são compostos basicamente por uma unidade central de pro-
cessamento (CPU, do inglês central processing unit), memória, disco, unidades 
de entrada/saída e um barramento que interliga esses componentes, como 
pode ser visto na Figura 1. A CPU é o módulo principal de um computador, pois 
é onde todo o processamento ocorre. Ela é composta por três submódulos: 
a unidade lógica e aritmética (ULA), os registradores e a unidade de controle 
(FERNANDEZ, 2015).
Figura 1. Arquitetura de um computador.
Fonte: Adaptada de Fernandez (2015).
Segundo Stallings (2010), a ULA é responsável por realizar as operações de 
soma e subtração, por exemplo, além de operações lógicas. Em alguns casos, 
as ULAs podem realizar também operações de multiplicação e divisão. Já os 
registradores são uma memória pequena e rápida utilizada para a realização 
de operações na CPU. Além dos registradores, muitas CPUs possuem também 
uma memória de rascunho, chamada “cache”, que serve para melhorar o 
desempenho do processamento, evitando acesso à memória externa da CPU.
A unidade de controle controla o funcionamento da CPU e de todo o com-
putador, controla o processamento entre a ULA e os registradores, além de 
interagir com o barramento externo e com os periféricos a ele conectados. 
A unidade de controle também é responsável por interpretar o código do 
programa em instruções para a CPU (FERNANDEZ, 2015).
Arquiteturas de computadores2
Já o barramento interliga todos os componentes do computador, como 
pudemos observar na Figura 1. Barramentos geralmente funcionam de forma 
paralela, permitindo o envio simultâneo de diversas informações, e podem ser 
divididos em barramento de dados, barramento de endereço (informação de 
onde os dados estão localizados) e barramento de controle (STALLINGS, 2010).
A memória é um local para armazenamento de dados, geralmente tem-
porário, que fornece uma velocidade maior que a de memória em disco e 
menor que a de registradores da CPU. Se, por um lado, a memória perde 
os dados quando o computador é desligado, por outro, o disco os mantém 
salvos (STALLINGS, 2010).
Por fim, os módulos de entrada e saída fazem a ligação entre o computador 
e o mundo externo, como a ligação com periféricos (p. ex.: mouse, teclado e 
impressoras).
Arquitetura de Harvard
A arquitetura de Harvard (Figura 2) é uma arquitetura com separação da me-
mória onde ficam armazenadas as instruções da memória de dados, inclusive 
com separação dos caminhos de comunicação para tais memórias. O nome 
dessa arquitetura se deve às características do computador eletromecânico 
Mark I, que foi desenvolvido na Universidade de Harvard. Nesse computador, 
as instruções eram armazenadas em uma fita perfurada, ao passo que os 
dados eram armazenados em contadores eletromecânicos (STALLINGS, 2010).
Figura 2. Arquitetura de Harvard.
Fonte: Adaptada de Fernandez (2015).
Arquiteturas de computadores 3
Uma particularidade interessante da arquitetura de Harvard é que, por 
serem apartadas, as memórias de instrução e de dados podem ter caracterís-
ticas distintas, como largura de palavra, sincronismo, estrutura de endereço 
e tecnologia de execução.
Em alguns casos, as instruções ficam armazenadas em memórias de so-
mente leitura (ROM, do inglês read only memory), ao passo que a memória 
de dados utiliza uma memória que permite tanto a leitura quanto a escrita 
(RAM, do inglês random access memory).
Uma diferença entre a arquitetura de Harvard e a de von Neumann (que será 
apresentada a seguir) é que essa última não permite a leitura de uma instrução 
ao mesmo tempo em que ocorre a leitura/escrita de um dado, pois ambas as 
memórias utilizam o mesmo barramento. A arquitetura de Harvard, por sua 
vez, permite que o processador central simultaneamente leia uma instrução 
e leia/escreva um dado, uma vez que as memórias utilizam barramentos 
diferentes. No entanto, por necessitar de dois barramentos, a arquitetura de 
Harvard precisa de um circuito eletrônico maior e mais complexo do que o 
demandado pela arquitetura de von Neumann (STALLINGS, 2010).
A arquitetura de Harvard possui, ainda, uma versão modificada, que é 
conhecida como “arquitetura de Harvard modificada”. Essa versão permite 
que o processador central trate dados de instruções como dados de somente 
leitura, evitando, assim, a cópia de dados constantes para a memória de dados 
a fim de que possam ser lidos. Isso garante a essa arquitetura mais espaço 
em memória para variáveis de leitura e escrita, mas exige o uso de instruções 
especiais (FERNANDEZ, 2015).
A principal vantagem da arquitetura de Harvard é, sem dúvidas, o acesso 
simultâneo à memória de instrução e à memória de dados. Contudo, essa 
vantagem foi superada por sistemas modernos baseados na arquitetura de von 
Neumann que usam a memória cache. Apesar disso, a arquitetura de Harvard 
ainda é muito utilizada em aplicações específicas, como processadores de 
sinal digital (DSPs) e microcontroladores.
Arquitetura de von Neumann
Proposta pelo matemático e cientista da computação John von Neumann, 
a arquitetura de von Neumann é uma arquitetura de computador digital na 
qual programas são armazenados no mesmo espaço de memória que os 
dados, o que permite a manipulação desses programas.
Arquiteturas de computadores4
Na arquitetura de von Neumann, as instruções de programa e os seus 
dados ficam armazenados na memória RAM. Segundo Stallings (2010), essa 
arquitetura é composta por uma unidade de processamento, que contém 
uma unidade aritmética e lógica e registradores de processo; uma unidade de 
controle, que contém registradores de instrução e contadores; uma memória, 
que armazena dados e instruções; e mecanismos de entrada e saída (Figura 3).
Figura 3. Arquitetura de von Neumann.
Fonte: Adaptada de Fernandez (2015).
Uma desvantagem dessa arquitetura é o chamado “gargalo de von Neu-
mann”, isto é, o fato de o mesmo barramento ser utilizado para leitura de 
dados e de instruções, o que geralmente limita o desempenho do sistema 
devido à limitação na taxa de transferência dos dados (STALLINGS, 2010). 
Em outros termos, a taxa de transferência do barramento é muito menor que 
a taxa com a qual o processador pode trabalhar, e, desse modo, a velocidade 
efetiva do processador fica limitada, sobretudo quando ele precisa ler grandes 
volumes de dados em memória.
O aumento na velocidade dos processadores, bem como no tamanho e 
na velocidade das memórias só ampliou esse problema. Para mitigá-lo, uma 
alternativa é o uso de memória cache, que está situada entre o processador 
e a memória principal, além do desenvolvimento de algoritmos de predição 
de desvio, a fim de reduzir ao máximo as idas até a memória principal.
Arquiteturas de computadores 5
Tipos de fluxo de controle de execução
Até hoje em dia, a maneira mais comum para se categorizarem sistemas 
com capacidade de processamento paralelo é a taxonomia de Flynn, criada 
em 1966. Essa taxonomia classifica programase computadores em relação 
à forma como instruções são executadas e dados são buscados, que pode 
corresponder a um fluxo individual ou múltiplo. O fluxo de instruções é a se-
quência de instruções executadas pela unidade de processamento, ao passo 
que o fluxo de dados é definido como o tráfego de dados que ocorre entre a 
memória e a unidade de processamento (STALLINGS, 2010).
O Quadro 1 lista os quatro tipos de fluxo de controle de execução segundo 
a taxonomia de Flynn, os quais serão detalhados a seguir.
Quadro 1. Taxonomia de Flynn
Instrução única
(Single instruction)
Múltiplas instruções
(Multiple instruction)
Dado único (Single data) SISD MISD
Múltiplos dados (Multiple data) SIMD MIMD
Fonte: Adaptado de Fernandez (2015).
Single instruction, single data (SISD)
Esse tipo de fluxo representa um programa inteiramente sequencial, que 
executa uma única instrução por vez, correspondendo à arquitetura de von 
Neumann. Exemplos dessa arquitetura incluem processadores de pipeline e 
processadores superescalares.
A técnica de pipelining consiste em manter cada parte do processador 
ocupada com alguma instrução por meio da divisão das instruções, as quais 
chegam em passos sequenciais que podem ser executados por unidades 
de processamento diferentes. Já processadores superescalares conseguem 
executar mais de uma instrução por ciclo de clock, o que é possível porque são 
disparadas instruções simultâneas para diferentes unidades do processador 
(STALLINGS, 2010).
Arquiteturas de computadores6
Single instruction, multiple data (SIMD)
O SIMD é uma aplicação que realiza a mesma operação repetidamente so-
bre uma grande quantidade de dados, explorando o paralelismo de dados, 
mas não a concorrência. Entre os exemplos desse tipo de processamento, 
podem-se citar as aplicações de processamento de sinais, como ocorre no 
tratamento de som e imagem, em que a mesma operação é aplicada sobre 
fluxos contínuos de dados.
Os principais exemplos de SIMD foram os supercomputadores vetoriais dos 
anos 1970, como o CDC Star-100 e o Texas Instruments ASC, que eram capazes 
de operar em vetores de dados com uma única instrução. O processamento 
de vetores foi popularizado pela Cray nos anos 1970 e 1980. Hoje em dia, 
as arquiteturas de processamento de vetores são consideradas de forma 
separada de computadores SIMD, pois, antigamente, elas processavam vetores 
uma palavra por vez, ao passo que processadores SIMD modernos processam 
simultaneamente todos os elementos do vetor (FERNANDEZ, 2015).
Apesar da sua história com supercomputadores, as últimas gerações de 
processadores SIMD são focadas em computadores desktop. A Intel introduziu 
as extensões SIMD à sua arquitetura x86, chamada “MMX”. Extensões seme-
lhantes e mais poderosas também foram introduzidas por seus concorrentes, 
como foi o caso do Motorola PowerPC e do IBM Power. Em resposta, a Intel 
introduziu o sistema SSE. E a AMD introduziu o 3DNow!. Todas essas extensões 
foram orientadas para o suporte a gráficos em tempo real. A maioria dos 
processadores de SIMD atuais são, na realidade, processadores MIMD com 
pequenas extensões com instruções SIMD (STALLINGS, 2010).
Instruções SIMD são largamente empregadas no processamento de gráficos 
3D, com placas gráficas que lançam mão de SIMD para substituir as CPUs nessa 
tarefa. A utilização de SIMD vem se amplificando com o uso de unidades de 
processamento gráfico de propósito geral (GPGPUs, do inglês general purpose 
graphics processing units).
A GPGPU é considerada um modelo de execução SIMT — do inglês 
single instruction, multiple threads (em português: instrução única, 
múltiplas threads). No SIMT, o modelo SIMD é combinado com o multithreading 
para a execução de instruções em todas as threads em lock-steps.
Arquiteturas de computadores 7
Multiple instruction, single data (MISD)
A categoria MISD é uma classificação raramente utilizada. No entanto, alguns 
pesquisadores consideram o pipeline um exemplo dessa categoria, e, além 
disso, os computadores de controle de voo do Space Shuttle eram compu-
tadores do tipo MISD.
Multiple instruction, multiple data (MIMD)
A MIMD é a mais comum das classificações e se aplica à maioria dos progra-
mas paralelos. Essa categoria de processadores é considerada de uso geral, 
em que cada um é capaz de executar todas as instruções necessárias para 
a transformação de dados. Na classificação MIMD, estão computadores com 
múltiplos cores, multiprocessadores e multicomputadores (FERNANDEZ, 2015).
A categoria MIMD pode ser classificada em SPMD — do inglês same pro-
gram, multiple data (em português: mesmo programa, múltiplos dados) — 
e MPMD — do inglês multiple program, multiple data (em português: múl-
tiplos programas, múltiplos dados). A classificação SPMD corresponde a 
múltiplos processadores executando o mesmo programa em pontos de exe-
cução diferentes. Já na MPMD, existem pelo menos dois programas (mestre 
e trabalhadores).
Comunicação com memória compartilhada 
e distribuída
A forma como processadores MIMD se comunicam pode ser classificada em 
processadores que compartilham uma memória em comum, processadores 
que acessam programas e dados na memória compartilhada e processadores 
que se comunicam por meio da memória compartilhada. O tipo mais comum 
desse sistema são os multiprocessadores simétricos (SMP, do inglês symmetric 
multiprocessor), que são múltiplos processadores que compartilham uma 
única memória ou um pool de memória através de um barramento que é 
compartilhado entre eles, sendo, para cada processador, aproximadamente 
o mesmo o tempo de acesso a qualquer região da memória (STALLINGS, 2010).
Arquiteturas de computadores8
As características que definem um sistema de SMP, cujo surgimento se 
deveu à demanda por maior desempenho e por redução dos preços dos 
processadores, são as seguintes:
 � existência de dois ou mais processadores de capacidade semelhante;
 � compartilhamento da mesma memória, conexão ao mesmo barramento 
e tempo semelhante de acesso à memória;
 � acesso compartilhado aos recursos de entrada e saída;
 � execução das mesmas funções por todos os processadores;
 � controle por um sistema operacional (SO) integrado que fornece in-
terfaces para interagir com os processadores.
Uma das vantagens do SMP é o desempenho, pois esse tipo de sistema 
permite que tarefas possam ser executadas de forma paralela, reduzindo 
o tempo total de execução. Outra de suas vantagens é a disponibilidade: 
uma vez que todos os processadores desempenham as mesmas funções, 
um processador pode assumir o lugar de outro em caso de falha. E, por 
fim, há a vantagem de crescimento incremental por meio da adição de mais 
processadores para melhorar o desempenho e garantir a escalabilidade do 
sistema (STALLINGS, 2010).
A existência de vários processadores é transparente para o usuário, e isso 
é gerenciado pelo sistema operacional mediante o escalonamento de threads 
e processos e a sincronização entre os processadores. Na Figura 4, pode-se 
ver em detalhes a taxonomia das arquiteturas de processadores paralelos, 
desde os processadores SISD com um único processador; os SIMD, que são 
representados por processadores vetoriais e de matrizes; os MISD; até os 
MIMD, que podem ser de memória compartilhada (podendo ser, nesse caso, 
SMP ou NUMA) ou de memória distribuída, como os clusters de computadores.
Geralmente, computadores SMP utilizam memória compartilhada, a qual 
é organizada de modo a permitir o acesso simultâneo a blocos separados 
de memória. Existem configurações em que cada processador possui sua 
própria memória e seus próprios canais de entrada e saída.
Arquiteturas de computadores 9
Figura 4. Taxonomia de arquiteturas de processadores paralelos.
Fonte: Adaptada de Stallings (2010).
A forma mais comum utilizada por computadores pessoais, estações de 
trabalho e servidores é o barramento de tempo compartilhado, sendo esse o 
mecanismo mais simples para a construção de um sistema multiprocessador. 
Tanto asestruturas quanto as interfaces são as mesmas que seriam vistas em 
um sistema de processador único. Entretanto, para facilitar a comunicação 
entre processadores e memória, são fornecidos os seguintes recursos.
 � Endereçamento: capacidade de distinguir os módulos no barramento 
para determinar a origem e o destino dos dados.
 � Arbitração: possibilidade de que qualquer módulo de entrada e saída 
atue como mestre para gerenciar requisições concorrentes.
 � Tempo compartilhado: bloqueio dos outros módulos quando um módulo 
utiliza o barramento.
Arquiteturas de computadores10
Entre as vantagens do SMP com barramento único, estão a simplicidade 
desse sistema, que é igual a um sistema de processador único; a facilidade 
para expandir o sistema com mais processadores; e a garantia de que uma 
falha em um componente conectado ao barramento não cause falhas em 
todo o sistema.
Porém, essa configuração sofre de problemas de desempenho, pois vários 
processadores precisam disputar o uso do mesmo barramento, limitando 
ainda mais a velocidade do processador. A fim de mitigar esse problema, 
é necessário que os processadores estejam equipados com memórias cache 
para reduzir o número de acessos à memória principal. Processadores moder-
nos geralmente possuem dois níveis de memória cache: L1 e L2. Alguns têm, 
ainda, um terceiro nível de cache, o L3. A introdução do cache trouxe consigo 
outras complexidades, como a necessidade de garantir a consistência nos 
dados, visto que uma alteração em um dado em cache deveria invalidar as 
cópias desse dado nos caches de outros processadores (STALLINGS, 2010).
Outro tipo mais recente de sistema de memória compartilhada é o NUMA 
— do inglês non-uniform memory access (em português: acesso à memória 
não uniforme) —, no qual o tempo de acesso a diferentes regiões da memória 
pode variar. Esse tipo de sistema se baseia na ideia de que um processador 
em um diretório é capaz de acessar sua memória local com uma latência 
menor se comparada à latência para acessar a memória de outro processador.
Como pode ser visto na Figura 5, arquiteturas NUMA são organizadas 
de modo que cada processador tenha sua própria memória e seu próprio 
barramento locais, além de uma memória compartilhada e mais lenta que 
pode ser acessada por todos os processadores.
Figura 5. Arquitetura NUMA.
Fonte: Adaptada de Fernandez (2015).
Arquiteturas de computadores 11
A implementação desse tipo de arquitetura começou nos anos 1990, por 
empresas como Unisys, Convex Computer, Honeywell, Silicon Graphics, Data 
General e Digital. A sua introdução trouxe algumas vantagens em relação a 
sistemas sem NUMA, principalmente no que diz respeito ao desempenho. 
Isso porque, em uma arquitetura NUMA, os processadores não precisam 
ficar bloqueados à espera de sua vez de acessar a memória compartilhada.
São exemplos modernos de NUMA a implementação do HyperTrans-
port, pela AMD, nos processadores Opteron, em 2003, e da interco-
nexão Quick Path Interconnect (QPI), pela Intel, em 2007.
Ainda, uma arquitetura NUMA pode ser vista como uma forma fortemente 
acoplada de computação em cluster — que, segundo Stallings (2010), é um 
grupo de computadores completos conectados entre si com o objetivo de 
trabalharem juntos, dando a impressão de que são um único computador.
Para Brewer (1997), existem quatro benefícios principais para a compu-
tação em cluster:
 � a escalabilidade absoluta, pois é possível criar clusters grandes 
com capacidades de processamento muito maiores do que a de um 
computador;
 � a escalabilidade incremental, que permite que o cluster seja escalado 
aos poucos, começando com um sistema pequeno que vai crescendo 
de acordo com a necessidade;
 � a alta disponibilidade, pois, uma vez que cada nó do cluster é um com-
putador completo e independente, a falha de um deles não acarreta 
a perda do serviço;
 � o preço mais acessível e o desempenho superior, já que é possível 
montar um cluster como se fossem blocos de construção, com um 
preço muito menor e um desempenho superior ao de computadores 
de alto desempenho.
Arquiteturas de computadores12
Referências
BREWER, E. Clustering: multiply and conquer. [S. l.]: Data Communications, 1997.
FERNANDEZ, M. P. Arquitetura de Computadores. 3. ed. Fortaleza: EdUECE, 2015. Disponível 
em: https://educapes.capes.gov.br/bitstream/capes/177823/2/Livro_Computacao_Ar-
quitetura%20de%20Computadores.PDF. Acesso em: 19 jan. 2021.
STALLINGS, W. Arquitetura e Organização de Computadores. 8. ed. São Paulo: Pearson, 
2010.
Leituras recomendadas
GUPTA, A. et al. Introduction to Parallel Computing: Design and Analysis of Algorithms. 
São Paulo: Pearson, 2003.
PACHECO, P. An Introduction to Parallel Programming. Waltham MA, USA: Morgan 
Kaufmann, 2011.
Os links para sites da web fornecidos neste capítulo foram todos 
testados, e seu funcionamento foi comprovado no momento da 
publicação do material. No entanto, a rede é extremamente dinâmica; suas 
páginas estão constantemente mudando de local e conteúdo. Assim, os editores 
declaram não ter qualquer responsabilidade sobre qualidade, precisão ou 
integralidade das informações referidas em tais links.
Arquiteturas de computadores 13