Hvilke drivere og barrierer påvirker prosessen?

O tipo de processamento paralelo utilizado neste trabalho pode ser definido como o uso simultâneo de múltiplos processadores para reduzir o tempo de execução de um programa. Outras formas de paralelismo, como no nível de bits, isto é, na implementação de uma instrução, ou no nível de instrução - múltiplas instruções de máquina sendo executadas simultaneamente - não são relevantes ao problema em estudo.

Essa forma de processamento paralelo requer máquinas com múltiplos processadores e/ou um cluster, sistemas operacionais capazes de suportar e de gerenciar esses processadores e aplicações que explorem essa forma de paralelismo. Existem três tipos de arquiteturas de hardware para esta forma de processamento paralelo [19]:

Arquiteturas de Memória Compartilhada (SMP): máquinas de memória

compartilhada possuem uma memória global acessível a todos os processadores. Cada processador possui alguma memória local e o mesmo sistema operacional controla todos os processadores. Os processadores operam de maneira independente, porém apenas um processador por vez pode escrever em um endereço da memória compartilhada. A principal característica de sistemas de memória compartilhada é que o tempo de acesso à memória é independente do processador, embora isto não elimine a disputa por acessos a memória, mesmo para operações de leitura. A vantagem desta arquitetura é a facilidade no uso e a rapidez na transferência de dados entre processadores. Entretanto o número de processadores é limitado pela complexidade do sistema de acesso simultâneo à memória, resultando em baixa escalabilidade, que é a principal limitação dessa arquitetura.

Arquiteturas de Memória Distribuída (Cluster): máquinas de memória distribuída

não compartilham memória, cada processador possui sua própria memória, invisível a todos os outros processadores. Os processos de uma aplicação paralela utilizam troca de mensagens para obter ou alterar os dados nas memórias dos outros processos. A vantagem dessa arquitetura é sua escalabilidade, maior que em máquinas com memória compartilhada, exatamente por não possuir acesso

simultâneo à memória. Além disso, cada processador acessa sem interferência sua memória local. A principal desvantagem é o elevado custo computacional de comunicação entre os processadores.

Arquiteturas Híbridas (SMP Cluster): trata-se de um conjunto de nós de

processamento, onde cada nó é uma máquina com memória compartilhada. Os processadores do nó compartilham uma memória local comum e cada nó da rede pode compartilhar dados de memória com outro nó da rede através de troca de mensagens, [20].

Atualmente duas ferramentas se tornaram o padrão “de fato” para a implementação de aplicações paralelas nestas arquiteturas:

Message Passing Interface (MPI): é o padrão da indústria para programação em

sistemas de memória distribuída, é baseado no modelo de troca de mensagens, com controle explícito do paralelismo. Os processos só são capazes de ler e escrever em sua respectiva memória local. Os dados são copiados para a memória local usando chamadas de sub-rotinas. A norma de interface de programação de aplicativos – Application Programming Interface (API) - do modelo MPI define um conjunto de funções e procedimentos que implementam o modelo de passagem de mensagens[14].

Características do padrão MPI:

 Códigos MPI podem ser executados tanto em arquitetura de memória distribuída como de memória compartilhada.

 Implementações genéricas de MPI têm sido portadas para quase todos os sistemas.

 Particularmente adaptáveis para paralelismo em cluster.  Existe um grande número de bibliotecas MPI otimizadas.  Cada processo tem sua própria memória local.

 Os dados são copiados através de mensagens entre memórias locais e são enviados e recebidos via chamadas explícita de sub-rotinas.

Open Specifications for Multi-Processing (OpenMP): é um padrão da indústria

combinação de diretivas de compilação, biblioteca de rotinas e variáveis de ambiente, que é utilizada para especificar o paralelismo em máquinas de memória compartilhada. As diretivas são adicionadas ao código para especificar ao compilador a presença de uma região a ser executada em paralelo, juntamente com algumas instruções sobre o modo como a região deve ser paralelizada [95].

Características do padrão OpenMP:

 Códigos OpenMP executam em máquinas de memória compartilhada.  Bastante portátil.

 Utiliza diretrizes que ajudam o compilador a paralelizar o código.

 Cada processo vê a mesma memória global, mas tem a sua própria memória local.

 Trocas implícitas de mensagens.

 Alto nível de abstração (superiores ao MPI).

A eficácia do paralelismo depende de como a computação sequencial é dividida entre os processos que compõe o programa paralelo. Esta divisão é conhecida como partição do problema. As principais formas de distribuir a solução de um problema são: a partição de tarefas e a partição de domínio. Nesta última, os dados do problema são divididos entre os processos.

Na partição de tarefas, as tarefas que compõe a solução do problema são divididas entre os processos. Ou seja, na partição de domínio cada processo executa a mesma computação em parte do conjunto de dados, enquanto na partição de tarefas cada processo executa uma tarefa sobre todos os dados. Um fator importante para a eficácia da paralelização, independente do modo de partição do problemas, é garantir que a carga de trabalho seja bem distribuída entre os processadores. Este fator é denominado balanceamento de carga

Em teoria, um modelo de memória compartilhada, como OpenMP, deveria oferecer uma estratégia mais eficiente de paralelização. Assim, uma combinação dos paradigmas de memória compartilhada e paralelização por passagem de mensagem dentro da mesma aplicação (modo híbrido de programação) pode prestar um serviço mais eficiente do que a estratégia de paralelização apenas por troca de mensagens

[96], [86]. Diversos trabalhos têm sido realizados para avaliar uma utilização destes dois paradigmas, individualmente e em conjunto [97], [96], [98].