Definindo melhor alguns conceitos
Concorrência
termo mais geral, um programa pode ser constituído por mais de um
thread/processo concorrendo por recursos
Paralelismo
uma aplicação é executada por um conjunto de processadores em um
ambiente único (dedicado)
Computação distribuída
aplicações sendo executadas em plataformas distribuídas
Definindo melhor alguns conceitos
Qualquer que seja o conceito, o que queremos?
estabelecer a solução do problema
lidar com recursos independentes
aumentar desempenho e capacidade de memória
fazer com que usuários e computadores trabalhem em
espírito de colaboração
O que paralelizar?
• Pode estar em diferentes níveis de sistemas
computacionais atuais
– Hardware
– Sistema Operacional
– Aplicação
• As principais questões que são focadas são
– Desempenho
– Corretude
– Possibilidade de explorar o paralelismo
Por que paralelizar?
Aplicação Paralela
– várias tarefas
– vários processadores
• redução no tempo total de execução
Modelos de Programação Paralela
• Criação e gerenciamento de processos
– estático ou dinâmico
• Comunicação
– memória compartilhada: visão de um único espaço de
endereçamento global
– memória distribuída: troca explícita de mensagens
Modelos de Programação Paralela
• Expressão de Paralelismo: Paradigmas
– SPMD ( Single Program Multiple Data )
– MPMD (Multiple Program Multiple Data )
• Metas
– aumento no desempenho
– maior eficiência
Modelo de Programação Paralela
As arquiteturas paralelas e distribuídas possuem muitos detalhes
Como especificar uma solução paralela pensando em todos esses detalhes?
O que queremos?
Executar a solução paralela o mais rápido possível?
Todos os detalhes influem no desempenho eficiente da solução?
Então
Um modelo de programação paralela deve especificar a metodologia de
execução e detalhes que influenciam na execução da aplicação naquela
arquitetura
Um modelo não deve especificar detalhes de um sistema/máquina específico
Abstraindo para Programar
Maior facilidade de programação: o esforço intelectual é
reduzido quando nos concentrarmos em "uma coisa de cada
vez”
duas dimensões:
– dimensão espacial
– dimensão temporal
Dimensão Espacial
A cada momento, conjuntos de tarefas independentes são
implementadas
– cada tarefa ou processador não sabe o que acontecerá
"a seguir"
detalhamento de informações globais levam a uma
programação difícil
Dimensão Temporal
programas são composições de ações seqüenciais
que preenchem o sistema computacional como um
todo:
pode-se definir com maior conhecimento o que vai
acontecer a seguir
Níveis de Paralelismo
Dependendo do nível considerado, a exploração do paralelismo é
diferente
nível de aplicações ou fases de aplicações
a nível de tarefas
a nível de instruções - a execução da instrução necessita da
busca, análise e execução propriamente dita
dentro dos circuitos aritméticos
Algoritmos
Quando queremos resolver um problema computacionalmente,
temos que analisar a complexidade deste. No domínio seqüencial,
se procura definir um algoritmo que resolva o problema em tempo
mínimo.
Mas quando se tratando de algoritmos paralelos, mais um
parâmetro
– número de processadores
– operações independentes devem ser executadas em paralelo.
qual o tamanho dos processos? noção de granulosidade
(granularity)
– a razão entre o tempo de computação necessário para
executar uma tarefa e a sobrecarga de comunicação durante
essa computação.
Modelos de Computação
Modelo de Computação Seqüencial: von Neumann
plataforma base para que usuários e projetistas
– complexidade de tempo do pior caso: tempo máximo
que o algoritmo pode levar para executar qualquer
entrada com n elementos
– complexidade de tempo esperado: complexidade média
– critério de custo uniforme: qualquer instrução RAM leva
uma unidade de tempo para ser executada e também o
acesso a registradores
Modelos de Computação
Modelo de Computação Paralela
O desempenho do programa paralelo depende de certos
fatores dependentes da máquina:
– grau de concorrência;
– escalonamento e alocação de processadores;
– comunicação e sincronização.
Modelos de Computação Paralela
Memória Compartilhada
• Com ou sem uso de threads
Memória Distribuída
• Troca de mensagens
Modelos de Computação Paralela
Memória Compartilhada sem uso de threads
• Processos podem compartilhar espaço de memória
• Através de semáforos para não ocorrer deadlock
Modelos de Computação Paralela
Memória Compartilhada sem uso de threads
• Uma vantagem deste modelo:
• todos os processos podem acessar igualmente os dados
compartilhados.
• Não há necessidade de explicitar a troca de dados entre
processos
• como em memória distribuída
Modelos de Computação Paralela
Memória Compartilhada sem uso de threads
• Uma desvantagem desse modelo:
• o gerenciamento da localidade de dados: ou seja, trazer
dados para a cache para economizar acesso a memória
principal
Modelos de Computação Paralela
Threads
• Utilização de múltiplos "light weight”
• Por exemplo, podemos pensar que
dependendo do problema, uma sub-
rotina possa ser definida como uma
thread
• Comunicação entre threads realizada
por memória compartilhada
• Sincronização entre as threads
necessárias se duas ou mais threads
estão atualizando o mesmo endereço
de memória
Modelos de Computação Paralela
Memória Distribuída (troca de mensagens)
• Cada tarefa tem sua memória local
• Pode haver uma ou mais tarefas por processador e
em vários processadores
• A troca de informações é realizada através de
mensagens
• Para tal, geralmente é utilizada uma biblioteca de
troca de mensagens
• Exemplo: Message Passing Interface (MPI) library
• Se tornou padrão entre aplicações industriais e
acadêmicas de fato
• MPI-1 em 1994
• MPI-2 em 1996
• MPI-3 in 2012
Modelos de Computação Paralela
Modelo de Paralelismo de Dados
Paralelismo é realizado em uma estrutura global comum
Um conjunto de tarefas trabalha em conjunto nesta estrutura
A mesma operação sobre elementos diferentes
Pode ser implementado em memória compartilhada ou memória
distribuída
Compartilhada – estrutura na memória global
Distribuída – estrutura dividida entre as diferentes memórias.
Modelo PRAM
Mas como pensar em paralelo?
Abstrair de formas de como implementar....
O que tínhamos com computação sequencial?
Memória
CPU
Modelo PRAM
Mas como pensar em paralelo?
Abstrair de formas de como implementar....
Como podemos pensar em paralelo?
Memória
CPU
Memória
CPU CPU CPU
Modelo PRAM – modelo ideal
conjunto de p processadores operando
sincronamente sob o controle de um único relógio,
compartilhando um espaço global de memória
algoritmos desenvolvidos para este modelo
geralmente são do tipo SIMD
– todos os processadores executam o mesmo
conjunto de instruções, e ainda a cada unidade de
tempo, todos os processadores estão executando a
mesma instrução mas usando dados diferentes.
Modelo PRAM – modelo ideal
propriedades chaves:
– execução síncrona sem nenhum custo adicional para a
sincronização
– comunicação realizada em uma unidade de tempo,
qualquer que seja a célula de memória acessada
– comunicação é feita usando a memória global
Passo do algoritmo PRAM
fase de leitura: os processadores acessam
simultaneamente locais de memória para leitura. Cada
processador acessa no máximo uma posição de memória
e armazena o dado lido em sua memória local
fase de computação: os processadores executam
operações aritméticas básicas com seus dados locais
fase de gravação: os processadores acessam
simultaneamente locais de memória global para escrita.
Cada processador acessa no máximo uma posição de
memória e grava um certo dado que está armazenado
localmente
Modelo PRAM
análise e estudo de algoritmos paralelos
definição de pa
