Arquitetura de Processamento Paralelo

Prévia do material em texto

Arquitetura de Processamento Paralelo
Componentes:
Laís Urano
Letícia Souza 
Luiz Neto
Maria Eugênia
Matheus Martins
Sumário:
Conceito, definição e aplicações;
SISD;
MISD;
SIMD;
MIMD;
Referências.
2
Conceito,definição e aplicações
1
3
O paralelismo possui níveis com ou sem a utilização de linguagens de programação paralela, são eles:
Nível de Instrução;
 Pipeline, arquitetura superescalares.
Nível de Threads;
 Arquitetura SMT
Nível de Processos;
 Multiprocessadores e Multicomputadores.
4
Uma arquitetura paralela fornece uma estrutura explícita e de alto nível para o desenvolvimento de soluções utilizando o processamento paralelo, através da existência de múltiplos processadores que cooperam para resolver problemas através de execução concorrente.(DUNCAN,1990)
5
“
Conceito:
A arquitetura paralela ou computação paralela é um tipo de organização de sistema computacional, a qual permite a execução de tarefas em menos tempo e de forma simultânea.
Esse tipo de arquitetura possui uma classificação chamada Taxonomia de Flynn, criada por Michael Flynn em a qual se baseia na execução de uma instrução de dados em vez do fluxo de instruções ou de dados.
6
I. Onde é possível encontrar a arquitetura paralela? 
-Big Data:
Hadoop MapReduce;
Hadoop Distributed File System (HDFS);
Hadoop Yarn;
Hadoop Common (Hadoop Core);
-Simulação da Circulação de Oceanos;
-Simulação da Evolução das Galáxias;
7
Taxonomia de Flynn:
8
9
SISD
Single Instruction, Single Data
2
10
Nesta classe, um único fluxo de instruções opera sobre um único fluxo de dados. Isso corresponde ao processamento sequencial característico da máquina de Von Neumann e que compreende os computadores pessoais e estações de trabalho. Apesar dos programas estarem organizados por meio de instruções sequenciais, elas podem ser executadas de forma sobreposta em diferentes estágios (pipelining).
Arquiteturas SISD caracterizam-se por possuírem uma única unidade de controle, podendo possuir mais de uma unidade funcional.
11
Relembrando pipeline:
A segmentação de instruções (pipeline) é uma técnica hardware que permite que a CPU realize a busca de uma ou mais instruções além da próxima a ser executada. Estas instruções são colocadas em uma fila de memória dentro do processador (CPU) onde aguardam o momento de serem executadas: assim que uma instrução termina o primeiro estágio e parte para o segundo, a próxima instrução já ocupa o primeiro estágio.
Em resumo, é o processo pelo qual uma instrução de processamento é subdividido em etapas, uma vez que cada uma destas etapas é executada por uma porção especializada da CPU, podendo colocar mais de uma instrução em execução simultânea. Isto traz um uso mais racional da capacidade computacional com ganho substancial de velocidade
12
Fluxo da SISD:
13
14
II. Marque V ou F nas alternativas abaixo:
 ( ) SISD é a representação do esquema de Duncan do clássico computador de Von Neumann.
 ( ) SISD é conhecido por possuir apenas um fluxo de instrução e de dados.
 ( ) Se considerarmos a maquina de Von Neumann nela a próxima instrução a ser executada é apontada pelo registrador PC, logo a instrução é única.
 ( ) SISD é a classe que representa os computadores convencionais. As instruções podem ser sobrepostas (pipeline) enquanto os estágios são executados serialmente.
MISD
Multiple Instruction, Single Data
3
15
Na arquitetura MISD um conjunto de dados é colocado concorrente em múltiplas unidades de processamento. Cada UP opera de maneira independente via conjuntos independentes de instruções, que opera em um mesmo conjunto de dados.
16
Isso é realizado para um dado string S = s1s2...sn, e um dado padrão 
P = p1p2...pn, checando-se a validade do padrão H(S,P). Essa função tem como retorno [0,1], isto é, o padrão foi encontrado ou não.
Porém, nessa arquitetura, a função H(S,P) é quebrada em diversos subproblemas paralelizáveis na forma:
 H(S,P)= H1(S,p1)^H2(Si+1,p2)^H3(Si+2,p3)...^Hn(Si+n,pn)
17
 Após isso, cada pequena unidade, das 127 possíveis, assume a busca de um padrão na substring e após a execução paralela são combinados os resultados de todos os casamentos dos subpadrões.
 A descoberta desses padrões podem ser utilizados, por exemplo, expressões regulares, operações em strings, processamento de linguagem natural e sequenciamento de DNA e RNA.
 O processador é implementado em uma arquitetura VLSI, permitindo até 127 linhas de processamento para descoberta de padrões paralelamente, a um clock de 100MHz, realizando
1024x10^11 operações de comparação por segundo.
18
 Não se tem conhecimento de arquiteturas de máquinas comerciais com múltiplas instruções trabalhando com um único conjunto de dados concorrente. 
 Em 1971, uma máquina denominada como C.mmp computer foi desenvolvida na universidade de Carnegie-Mellon.
19
III.A respeito dos principais sistemas operacionais, das características dos principais processadores do mercado e dos processadores de múltiplos núcleos, julgue o seguinte item:
Por meio da técnica de pipeline, a arquitetura MIMD e MISD podem executar múltiplos threads ao mesmo tempo. Na arquitetura MISD, os threads executados são independentes e manipulam dados diferentes.
20
III.A respeito dos principais sistemas operacionais, das características dos principais processadores do mercado e dos processadores de múltiplos núcleos, julgue o seguinte item:
Por meio da técnica de pipeline, a arquitetura MIMD e MISD podem executar múltiplos threads ao mesmo tempo. Na arquitetura MISD, os threads executados são independentes e manipulam dados diferentes.
FALSO.
21
SIMD
Single Instruction, Multiple Data
4
22
Definição:
SIMD – Esta sigla é o acrônimo para (Single Instruction, Multiple Data), trata-se de uma forma ou método de operações de computadores com várias unidades operacionais em computação paralela.
23
Histórico de uso da SIMD:
As primeiras máquinas foram os supercomputadores, que também são chamadas de processadores de vetor.
Maior implementação em computadores pessoais para jogos de vídeo, e arquivos multimídia como musicas e vídeos.
A primeira implantação ampla de jogos de vídeo foram para as extensões SIMD MMX para a arquitetura x86 da Intel.
24
Arquitetura SIMD:
Trata-se de uma maquina que contem apenas uma unidade de controle que executa uma instrução de cada vez, porém cada instrução executada opera sobre vários dados.
É formada por uma unidade de controle, um conjunto de elementos processadores, memórias associadas a estes e uma rede de interconexão, onde tais elementos são organizados de duas formas.
25
Primeira forma de Organização:
26
Segunda forma de Organização:
27
Vantagens:
Paralelismo de operações.
Maior desempenho e velocidade de processamento.
Desvantagens:
A implementação de um algoritmo com as instruções SIMD geralmente requer trabalho humano, a maioria dos compiladores não geram instruções SIMD de um programa C comum.
Não possui compiladores que funcionem de forma geral.
Necessário fazer varias operações de baixo nível
28
IV. Um dos métodos mais utilizados para se classificar computadores paralelos é a taxonomia de Flynn, que se baseia no fluxo de instruções e no fluxo de dados. Nessa categorização, um sistema computacional é classificado como:
a) SISD, se existem várias sequencias de instruções e dados, como nas arquiteturas de Von Neumann.
b)SIMD, se uma unidade de controle executa instruções distintas simultaneamente para a operação de um único dado.
c)SIMD, se uma unidade de controle executa uma única instrução para a operação de múltiplos dados destinados ao processamento de imagens.
d)MISD, quando várias instruções diferentes operam sobre vários conjuntos de dados.
29
MIMD
Multiple Instruction, Multiple Data
5
30
Arquitetura MIMD:
As máquinas MIMD (Multiple Instruction Multiple Data) são arquiteturas caracterizadas pela execução simultâneade múltiplos fluxos de instruções.
31
Compartilhamento de Mémoria:
Memória compartilhada (shared memory)
Cada processador consegue ter acesso a todo o espaço de memória do sistema;
o espaço de endereçamento é único;
comunicação através de load e store nos endereços de memória.
32
Memória distribuída (distributed memory)
Cada processador é capaz de endereçar apenas a sua memória local;
a memória é composta por vários módulos;
 cada módulo está próximo a um processador.
33
Multiprocessadores:
São as arquiteturas em que todos os processadores tem acesso ao mesmo espaço de endereços na memória.
Os multiprocessadores ainda podem ser classificados quanto a distância dos processadores à memória, e quanto aos esquemas de coerência de cache. 
34
Arquitetura UMA (Uniform Memory Access) :
Arquitetura de um multiprocessador UMA
O tempo para o acesso aos dados na memória é o mesmo para todos os processadores a para todas as posições da memória. 
35
Arquitetura NUMA (Non-Uniform Memory Access):
Arquitetura de um multiprocessador do tipo NUMA
Neste tipo de multiprocessadores, a memória geralmente é distribuída e portanto implementada com múltiplos módulos. 
36
As máquinas NUMA também estão sujeitas aos problemas de coerência de cache, e conforme a solução implementada existem variações deste tipo de arquitetura. 
NCC-NUMA (Non-Cache Coherent NUMA) 
Nesse tipo de máquina, não existe garantia de coerência nos dados da memória cache, ou simplesmente não existe cache. 
CC-NUMA (Cache Coherent NUMA) 
Nesse tipo de máquina, a coerência de cache é garantida pelo hardware. 
SC-NUMA (Software Coherent NUMA) 
Neste caso, a coerência de cache é garantida em software e essa implementação recebe o nome de DSM (Distributed Shared Memory)
COMA (Cache Only Memory Architecture) 
São multiprocessadores baseados em memórias cache de alta capacidade, em que a coerência é conseguida em hardware com a atualização simultânea em múltiplos nós dos dados alterados
37
Multicomputadores:
Essas máquinas caracterizam-se pelo fato de que cada processador enxerga somente a sua própria memória. Para a troca de mensagens e dados é preciso o envio de requisições através da rede de interconexão.
38
Multicomputadores podem ser divididos em duas categorias:
MPP (Massively Parallel Processors)
 São multicomputadores compostos por um grande número de processadores, fortemente acoplados através de uma rede de alta velocidade.
COW (Cluster of Workstations) 
Essas máquinas são construídas a partir de computadores comuns (PCs) ligados por redes de interconexão tradicionais.
39
Redes de interconexão:
Critérios de avaliação:
 
Escalabilidade;
Desempenho;
Custo; 
Confiabilidade; e
Funcionalidade.
40
Redes Estáticas:
São as que especificam uma ligação direta dedicada entre dois componentes quaisquer. 
41
Redes Dinâmicas:
Não existem ligações fixas entre os componentes. São as mais utilizadas em multiprocessadores.
As redes dinâmicas podem ser de três tipos: 
Barramento 
Matriz de chaveamento 
Rede multinível
42
V. Qual a diferença entre um SIMD e um MIMD?
Single-Instruction Multiple-Data (SIMD)
Em um computador SIMD, cada processador tem sua própria memória local. Um processador controla a operação de outros processadores. Uma vez que todos, exceto o controlador, executam a mesma instrução, ao mesmo tempo, nenhuma sincronização é necessária no software.
Multiple-Instruction Multiple-Data (MIMD)
Cada processados em um computador MIMD executa seu próprio fluxo de instruções. Eles podem aparecer em duas configurações distintas: sistemas distribuídos e de memória compartilhada. As máquinas MIMD distribuídas, nas quais cada processador tem sua própria memória, podem ser construídas em um único gabinete ou distribuídas por uma grande área. Suas versões de memória compartilhada evidentemente devem oferecer algum meio de sincronização para impedir conflitos de acesso a memória. Os computadores MIMD são mais caros e mais gerais do que os computadores SIMS e logicamente suportam concorrência no nível de unidade.
43
[1]<http://www.cespe.unb.br/concursos/DPF_12_PERITO/arquivos/DPF13PER_003_07.pdf> Acesso em 25/11/2019.
[2]<https://pensandoarquiteturas.wordpress.com/2011/10/15/arquitetura-de-processadores-misd-em-busca-de-padroes/>Acesso em 25/11/2019.
[3]<http://www.inf.ufsc.br/~mario.dantas/tac.pdf> Acesso em 25/11/2019.
[4]<http://wiki.icmc.usp.br/images/0/0c/SSC0510-Aula12.pdf> Acesso em 25/11/2019.
[5]<https://pt.wikipedia.org/wiki/SIMD#:~:targetText=A%20sigla%20SIMD%20(Single%20Instruction,unidades%20operacionais%20em%20computa%C3%A7%C3%A3o%20paralela.>Acesso em 24/11/2019.
[6]<https://www.qconcursos.com/questoes-de-concursos/questoes/cff7f76b-a4>Aceso em 24/11/2019.
Referências:
44
[7]<https://pt.stackoverflow.com/questions/257086/qual-o-significado-das-siglas-sisd-simd-misd-mimd-qual-a-sua-rela%C3%A7%C3%A3o-com-pro>Acesso em 24/11/2019.
[8]<https://www.lume.ufrgs.br/handle/10183/117094>Acesso em 24/11/2019.
[9]<https://www.computer.org/profiles/michael-flynn>Acesso em 22/11/2019.
[10]<https://edisciplinas.usp.br/pluginfile.php/3482095/mod_resource/content/1/18aula%20-%20Arquiteturas%20Paralelas.pdf> Acesso em 23/11/2019.
[11]<http://www.eng.uerj.br/~ldmm/Arquiteturas_de_Alto_Desempenho/Paralelismo.pdf>Acesso em 23/11/2019.
[12]<https://dcc.ufrj.br/~gabriel/sispar/ArqPar0.pdf>Acesso em 25/11/2019.
[13]<http://www.inf.ufes.br/~luciac/fem/MIMD.pdf>Acesso em 25/11/2019.
[14] <https://dcc.ufrj.br/~gabriel/arqcomp2/ArqPar2.pdf>. Acesso em 25/11/2019.
Referências:
45