Algoritmo Paralelo - Introdução

A algorithmé uma sequência de etapas que recebe entradas do usuário e, após alguns cálculos, produz uma saída. UMAparallel algorithm é um algoritmo que pode executar várias instruções simultaneamente em diferentes dispositivos de processamento e então combinar todas as saídas individuais para produzir o resultado final.

Processamento Simultâneo

A fácil disponibilidade de computadores junto com o crescimento da Internet mudou a maneira como armazenamos e processamos dados. Estamos vivendo em uma época em que os dados estão disponíveis em abundância. Todos os dias lidamos com enormes volumes de dados que exigem uma computação complexa e rápida. Às vezes, precisamos buscar dados de eventos semelhantes ou inter-relacionados que ocorrem simultaneamente. É aqui que precisamosconcurrent processing que pode dividir uma tarefa complexa e processá-la em vários sistemas para produzir a saída em tempo rápido.

O processamento simultâneo é essencial quando a tarefa envolve o processamento de uma grande quantidade de dados complexos. Os exemplos incluem - acesso a grandes bancos de dados, testes de aeronaves, cálculos astronômicos, física atômica e nuclear, análise biomédica, planejamento econômico, processamento de imagens, robótica, previsão do tempo, serviços baseados na web, etc.

O que é paralelismo?

Parallelismé o processo de processamento de vários conjuntos de instruções simultaneamente. Reduz o tempo computacional total. O paralelismo pode ser implementado usandoparallel computers,ou seja, um computador com muitos processadores. Computadores paralelos requerem algoritmo paralelo, linguagens de programação, compiladores e sistema operacional que oferecem suporte a multitarefa.

Neste tutorial, discutiremos apenas sobre parallel algorithms. Antes de prosseguirmos, vamos primeiro discutir sobre algoritmos e seus tipos.

O que é um algoritmo?

A algorithmé uma sequência de instruções seguidas para resolver um problema. Ao projetar um algoritmo, devemos considerar a arquitetura do computador em que o algoritmo será executado. De acordo com a arquitetura, existem dois tipos de computadores -

  • Computador Seqüencial
  • Computador Paralelo

Dependendo da arquitetura dos computadores, temos dois tipos de algoritmos -

  • Sequential Algorithm - Um algoritmo no qual algumas etapas consecutivas de instruções são executadas em ordem cronológica para resolver um problema.

  • Parallel Algorithm- O problema é dividido em subproblemas e são executados em paralelo para obter resultados individuais. Mais tarde, essas saídas individuais são combinadas para obter a saída final desejada.

Não é fácil dividir um grande problema em sub-problems. Os subproblemas podem ter dependência de dados entre eles. Portanto, os processadores precisam se comunicar entre si para resolver o problema.

Foi descoberto que o tempo necessário para os processadores se comunicarem entre si é maior do que o tempo real de processamento. Portanto, ao projetar um algoritmo paralelo, a utilização adequada da CPU deve ser considerada para obter um algoritmo eficiente.

Para projetar um algoritmo de forma adequada, devemos ter uma ideia clara do básico model of computation em um computador paralelo.

Modelo de Computação

Os computadores sequenciais e paralelos operam em um conjunto (fluxo) de instruções chamado algoritmos. Este conjunto de instruções (algoritmo) instrui o computador sobre o que ele deve fazer em cada etapa.

Dependendo do fluxo de instrução e fluxo de dados, os computadores podem ser classificados em quatro categorias -

  • Fluxo de instrução único, computadores de fluxo de dados único (SISD)
  • Fluxo de instrução único, computadores com fluxo de dados múltiplos (SIMD)
  • Fluxo de várias instruções, computadores com fluxo de dados único (MISD)
  • Fluxo de instruções múltiplas, computadores de fluxo de dados múltiplos (MIMD)

Computadores SISD

Os computadores SISD contêm one control unit, one processing unit, e one memory unit.

Nesse tipo de computador, o processador recebe um único fluxo de instruções da unidade de controle e opera em um único fluxo de dados da unidade de memória. Durante a computação, em cada etapa, o processador recebe uma instrução da unidade de controle e opera em um único dado recebido da unidade de memória.

Computadores SIMD

Os computadores SIMD contêm one control unit, multiple processing units, e shared memory or interconnection network.

Aqui, uma única unidade de controle envia instruções para todas as unidades de processamento. Durante a computação, em cada etapa, todos os processadores recebem um único conjunto de instruções da unidade de controle e operam em diferentes conjuntos de dados da unidade de memória.

Cada uma das unidades de processamento tem sua própria unidade de memória local para armazenar dados e instruções. Em computadores SIMD, os processadores precisam se comunicar entre si. Isso é feito porshared memory ou por interconnection network.

Enquanto alguns dos processadores executam um conjunto de instruções, os processadores restantes aguardam seu próximo conjunto de instruções. As instruções da unidade de controle decidem qual processador seráactive (executar instruções) ou inactive (aguarde a próxima instrução).

Computadores MISD

Como o nome sugere, os computadores MISD contêm multiple control units, multiple processing units, e one common memory unit.

Aqui, cada processador tem sua própria unidade de controle e compartilham uma unidade de memória comum. Todos os processadores recebem instruções individualmente de sua própria unidade de controle e operam em um único fluxo de dados de acordo com as instruções que receberam de suas respectivas unidades de controle. Este processador opera simultaneamente.

Computadores MIMD

Computadores MIMD têm multiple control units, multiple processing units, e um shared memory ou interconnection network.

Aqui, cada processador tem sua própria unidade de controle, unidade de memória local e unidade aritmética e lógica. Eles recebem diferentes conjuntos de instruções de suas respectivas unidades de controle e operam em diferentes conjuntos de dados.

Nota

  • Um computador MIMD que compartilha uma memória comum é conhecido como multiprocessors, enquanto aqueles que usam uma rede de interconexão são conhecidos como multicomputers.

  • Com base na distância física dos processadores, os multicomputadores são de dois tipos -

    • Multicomputer - Quando todos os processadores estão muito próximos uns dos outros (por exemplo, na mesma sala).

    • Distributed system - Quando todos os processadores estão distantes uns dos outros (por exemplo, nas diferentes cidades)