Click here to load reader

Definindo melhor alguns boeres/slides_AP/AlgParalelosI.pdf · PDF file Definindo melhor alguns conceitos Concorrência termo mais geral, um programa pode ser constituído por mais

  • View
    6

  • Download
    0

Embed Size (px)

Text of Definindo melhor alguns boeres/slides_AP/AlgParalelosI.pdf · PDF file Definindo melhor...

  • 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