Algoritmo Paralelo - Guia Rápido

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)

A análise de um algoritmo nos ajuda a determinar se o algoritmo é útil ou não. Geralmente, um algoritmo é analisado com base em seu tempo de execução(Time Complexity) e a quantidade de espaço (Space Complexity) Isso requer.

Como temos sofisticados dispositivos de memória disponíveis a um custo razoável, o espaço de armazenamento não é mais um problema. Conseqüentemente, a complexidade do espaço não recebe tanta importância.

Algoritmos paralelos são projetados para melhorar a velocidade de computação de um computador. Para analisar um algoritmo paralelo, normalmente consideramos os seguintes parâmetros -

• Complexidade de tempo (tempo de execução),
• Número total de processadores usados, e
• Custo total.

Complexidade de tempo

A principal razão por trás do desenvolvimento de algoritmos paralelos foi reduzir o tempo de computação de um algoritmo. Assim, avaliar o tempo de execução de um algoritmo é extremamente importante na análise de sua eficiência.

O tempo de execução é medido com base no tempo gasto pelo algoritmo para resolver um problema. O tempo total de execução é calculado a partir do momento em que o algoritmo começa a ser executado até o momento em que ele para. Se todos os processadores não iniciam ou terminam a execução ao mesmo tempo, então o tempo total de execução do algoritmo é o momento em que o primeiro processador iniciou sua execução até o momento em que o último processador interrompe sua execução.

A complexidade de tempo de um algoritmo pode ser classificada em três categorias−

• Worst-case complexity - Quando a quantidade de tempo necessária por um algoritmo para uma determinada entrada é maximum.

• Average-case complexity - Quando a quantidade de tempo necessária por um algoritmo para uma determinada entrada é average.

• Best-case complexity - Quando a quantidade de tempo necessária por um algoritmo para uma determinada entrada é minimum.

Análise Assintótica

A complexidade ou eficiência de um algoritmo é o número de etapas executadas pelo algoritmo para obter a saída desejada. A análise assintótica é feita para calcular a complexidade de um algoritmo em sua análise teórica. Na análise assintótica, um grande comprimento de entrada é usado para calcular a função de complexidade do algoritmo.

Note - Asymptoticé uma condição em que uma linha tende a encontrar uma curva, mas elas não se cruzam. Aqui, a linha e a curva são assintóticas entre si.

A notação assintótica é a maneira mais fácil de descrever o tempo de execução mais rápido e mais lento possível para um algoritmo usando limites altos e limites baixos de velocidade. Para isso, usamos as seguintes notações -

• Notação Big O
• Notação Omega
• Notação teta

Notação Big O

Em matemática, a notação Big O é usada para representar as características assintóticas das funções. Ele representa o comportamento de uma função para grandes entradas em um método simples e preciso. É um método de representar o limite superior do tempo de execução de um algoritmo. Ele representa o tempo mais longo que o algoritmo pode levar para concluir sua execução. A função -

f (n) = O (g (n))

se existirem constantes positivas c e n₀ de tal modo que f(n) ≤ c * g(n) para todos n Onde n ≥ n₀.

Notação Omega

A notação Omega é um método de representar o limite inferior do tempo de execução de um algoritmo. A função -

f (n) = Ω (g (n))

se existirem constantes positivas c e n₀ de tal modo que f(n) ≥ c * g(n) para todos n Onde n ≥ n₀.

Notação Theta

A notação Theta é um método de representar o limite inferior e o limite superior do tempo de execução de um algoritmo. A função -

f (n) = θ (g (n))

se existirem constantes positivas c₁, c₂, e n₀ de modo que c1 * g (n) ≤ f (n) ≤ c2 * g (n) para todos n Onde n ≥ n₀.

Aceleração de um Algoritmo

O desempenho de um algoritmo paralelo é determinado pelo cálculo de sua speedup. A aceleração é definida como a razão entre o tempo de execução do pior caso do algoritmo sequencial mais rápido conhecido para um problema particular e o tempo de execução do pior caso do algoritmo paralelo.

Número de processadores usados

O número de processadores usados ​​é um fator importante na análise da eficiência de um algoritmo paralelo. Os custos de compra, manutenção e operação dos computadores são calculados. Quanto maior o número de processadores usados ​​por um algoritmo para resolver um problema, mais caro se torna o resultado obtido.

Custo total

O custo total de um algoritmo paralelo é o produto da complexidade do tempo e do número de processadores usados ​​naquele algoritmo específico.

Custo total = complexidade de tempo × número de processadores usados

Portanto, o efficiency de um algoritmo paralelo é -

O modelo de um algoritmo paralelo é desenvolvido considerando uma estratégia de divisão dos dados e método de processamento e aplicando uma estratégia adequada para reduzir as interações. Neste capítulo, discutiremos os seguintes modelos de algoritmos paralelos -

• Modelo paralelo de dados
• Modelo de gráfico de tarefas
• Modelo de piscina de trabalho
• Modelo mestre escravo
• Consumidor produtor ou modelo de pipeline
• Modelo híbrido

Paralelo de Dados

No modelo paralelo de dados, as tarefas são atribuídas a processos e cada tarefa executa tipos semelhantes de operações em dados diferentes. Data parallelism é uma consequência de operações únicas aplicadas a vários itens de dados.

O modelo de dados paralelos pode ser aplicado em espaços de endereços compartilhados e paradigmas de transmissão de mensagens. No modelo de dados paralelos, os overheads de interação podem ser reduzidos selecionando uma decomposição de preservação de localidade, usando rotinas de interação coletiva otimizadas ou por sobreposição de computação e interação.

A principal característica dos problemas de modelo de paralelismo de dados é que a intensidade do paralelismo de dados aumenta com o tamanho do problema, o que, por sua vez, torna possível usar mais processos para resolver problemas maiores.

Example - Multiplicação de matrizes densas.

Modelo de Gráfico de Tarefa

No modelo de gráfico de tarefas, o paralelismo é expresso por um task graph. Um gráfico de tarefa pode ser trivial ou não trivial. Neste modelo, a correlação entre as tarefas é utilizada para promover a localidade ou para minimizar os custos de interação. Este modelo é aplicado para resolver problemas em que a quantidade de dados associados às tarefas é grande em comparação com o número de cálculos associados a eles. As tarefas são atribuídas para ajudar a melhorar o custo da movimentação de dados entre as tarefas.

Examples - Classificação rápida paralela, fatoração de matriz esparsa e algoritmos paralelos derivados por meio da abordagem de dividir e conquistar.

Aqui, os problemas são divididos em tarefas atômicas e implementados como um gráfico. Cada tarefa é uma unidade independente de trabalho que possui dependências em uma ou mais tarefas antecedentes. Após a conclusão de uma tarefa, a saída de uma tarefa antecedente é passada para a tarefa dependente. Uma tarefa com tarefa antecedente inicia a execução apenas quando toda a tarefa antecedente é concluída. A saída final do gráfico é recebida quando a última tarefa dependente é concluída (Tarefa 6 na figura acima).

Modelo de piscina de trabalho

No modelo de pool de trabalho, as tarefas são atribuídas dinamicamente aos processos para balancear a carga. Portanto, qualquer processo pode potencialmente executar qualquer tarefa. Este modelo é usado quando a quantidade de dados associados às tarefas é comparativamente menor do que o cálculo associado às tarefas.

Não existe uma pré-atribuição desejada de tarefas aos processos. A atribuição de tarefas é centralizada ou descentralizada. Os ponteiros para as tarefas são salvos em uma lista fisicamente compartilhada, em uma fila de prioridade ou em uma tabela ou árvore hash, ou podem ser salvos em uma estrutura de dados fisicamente distribuída.

A tarefa pode estar disponível no início, ou pode ser gerada dinamicamente. Se a tarefa for gerada dinamicamente e uma atribuição descentralizada de tarefa for feita, um algoritmo de detecção de término será necessário para que todos os processos possam realmente detectar a conclusão de todo o programa e parar de procurar mais tarefas.

Example - Pesquisa de árvore paralela

Modelo Master-Slave

No modelo mestre-escravo, um ou mais processos mestre geram tarefas e as alocam aos processos escravos. As tarefas podem ser alocadas de antemão se -

• o mestre pode estimar o volume das tarefas, ou
• uma atribuição aleatória pode fazer um trabalho satisfatório de balanceamento de carga, ou
• escravos recebem tarefas menores em momentos diferentes.

Este modelo é geralmente igualmente adequado para shared-address-space ou message-passing paradigms, uma vez que a interação é naturalmente de duas maneiras.

Em alguns casos, uma tarefa pode precisar ser concluída em fases, e a tarefa em cada fase deve ser concluída antes que a tarefa nas fases seguintes possa ser gerada. O modelo mestre-escravo pode ser generalizado parahierarchical ou multi-level master-slave model em que o mestre de nível superior alimenta a grande parte das tarefas para o mestre de segundo nível, que subdivide as tarefas entre seus próprios escravos e pode realizar uma parte da tarefa por si mesmo.

Precauções no uso do modelo mestre-escravo

Deve-se ter cuidado para garantir que o mestre não se torne um ponto de congestionamento. Isso pode acontecer se as tarefas forem muito pequenas ou os trabalhadores forem comparativamente rápidos.

As tarefas devem ser selecionadas de forma que o custo de execução de uma tarefa domine o custo de comunicação e o custo de sincronização.

A interação assíncrona pode ajudar a sobrepor a interação e o cálculo associado à geração de trabalho pelo mestre.

Modelo de Pipeline

Também é conhecido como producer-consumer model. Aqui, um conjunto de dados é transmitido por meio de uma série de processos, cada um dos quais executa alguma tarefa nele. Aqui, a chegada de novos dados gera a execução de uma nova tarefa por um processo na fila. Os processos podem formar uma fila na forma de matrizes lineares ou multidimensionais, árvores ou gráficos gerais com ou sem ciclos.

Este modelo é uma cadeia de produtores e consumidores. Cada processo na fila pode ser considerado como consumidor de uma sequência de itens de dados para o processo anterior na fila e como produtor de dados para o processo seguinte na fila. A fila não precisa ser uma cadeia linear; pode ser um gráfico direcionado. A técnica de minimização de interação mais comum aplicável a este modelo é a interação sobreposta com computação.

Example - Algoritmo de fatoração de LU paralela.

Modelos Híbridos

Um modelo de algoritmo híbrido é necessário quando mais de um modelo pode ser necessário para resolver um problema.

Um modelo híbrido pode ser composto de vários modelos aplicados hierarquicamente ou vários modelos aplicados sequencialmente a diferentes fases de um algoritmo paralelo.

Example - Classificação rápida paralela

Parallel Random Access Machines (PRAM)é um modelo, que é considerado para a maioria dos algoritmos paralelos. Aqui, vários processadores são anexados a um único bloco de memória. Um modelo PRAM contém -

• Um conjunto de processadores semelhantes.

• Todos os processadores compartilham uma unidade de memória comum. Os processadores podem se comunicar entre si apenas por meio da memória compartilhada.

• Uma unidade de acesso à memória (MAU) conecta os processadores com a única memória compartilhada.

Aqui, n número de processadores podem realizar operações independentes em nnúmero de dados em uma determinada unidade de tempo. Isso pode resultar no acesso simultâneo do mesmo local de memória por diferentes processadores.

Para resolver este problema, as seguintes restrições foram aplicadas no modelo PRAM -

• Exclusive Read Exclusive Write (EREW) - Aqui, dois processadores não têm permissão para ler ou gravar no mesmo local de memória ao mesmo tempo.

• Exclusive Read Concurrent Write (ERCW) - Aqui, dois processadores não têm permissão para ler no mesmo local da memória ao mesmo tempo, mas podem gravar no mesmo local da memória ao mesmo tempo.

• Concurrent Read Exclusive Write (CREW) - Aqui, todos os processadores podem ler no mesmo local de memória ao mesmo tempo, mas não podem gravar no mesmo local de memória ao mesmo tempo.

• Concurrent Read Concurrent Write (CRCW) - Todos os processadores têm permissão para ler ou gravar no mesmo local de memória ao mesmo tempo.

Existem muitos métodos para implementar o modelo PRAM, mas os mais proeminentes são -

• Modelo de memória compartilhada
• Modelo de passagem de mensagem
• Modelo paralelo de dados

Modelo de Memória Compartilhada

A memória compartilhada enfatiza control parallelism do que em data parallelism. No modelo de memória compartilhada, vários processos são executados em diferentes processadores de forma independente, mas eles compartilham um espaço de memória comum. Devido a qualquer atividade do processador, se houver alguma alteração em qualquer local da memória, ela será visível para o restante dos processadores.

Como vários processadores acessam o mesmo local de memória, pode acontecer que, em qualquer ponto específico do tempo, mais de um processador esteja acessando o mesmo local de memória. Suponha que um esteja lendo aquele local e o outro esteja escrevendo naquele local. Isso pode criar confusão. Para evitar isso, algum mecanismo de controle, comolock / semaphore, é implementado para garantir a exclusão mútua.

A programação de memória compartilhada foi implementada no seguinte -

• Thread libraries- A biblioteca de threads permite vários threads de controle que são executados simultaneamente no mesmo local de memória. A biblioteca de threads fornece uma interface que suporta multithreading por meio de uma biblioteca de sub-rotinas. Ele contém sub-rotinas para

  • Criação e destruição de threads
  • Agendamento de execução de thread
  • passando dados e mensagens entre conversas
  • salvar e restaurar contextos de discussão

Exemplos de bibliotecas de thread incluem - threads SolarisTM para Solaris, threads POSIX conforme implementado no Linux, threads Win32 disponíveis no Windows NT e Windows 2000 e threads JavaTM como parte do JavaTM Development Kit (JDK) padrão.

• Distributed Shared Memory (DSM) Systems- Os sistemas DSM criam uma abstração de memória compartilhada em arquitetura fracamente acoplada para implementar a programação de memória compartilhada sem suporte de hardware. Eles implementam bibliotecas padrão e usam os recursos avançados de gerenciamento de memória no nível do usuário, presentes nos sistemas operacionais modernos. Os exemplos incluem Tread Marks System, Munin, IVY, Shasta, Brazos e Cashmere.

• Program Annotation Packages- Isso é implementado nas arquiteturas com características uniformes de acesso à memória. O exemplo mais notável de pacotes de anotação de programa é o OpenMP. OpenMP implementa paralelismo funcional. Ele se concentra principalmente na paralelização de loops.

O conceito de memória compartilhada fornece um controle de baixo nível do sistema de memória compartilhada, mas tende a ser tedioso e errôneo. É mais aplicável à programação do sistema do que à programação do aplicativo.

Méritos da Programação de Memória Compartilhada

• O espaço de endereço global oferece uma abordagem de programação amigável para a memória.

• Devido à proximidade da memória com a CPU, o compartilhamento de dados entre os processos é rápido e uniforme.

• Não há necessidade de especificar distintamente a comunicação de dados entre os processos.

• A sobrecarga de comunicação do processo é insignificante.

• É muito fácil aprender.

Deméritos da programação de memória compartilhada

• Não é portátil.
• Gerenciar a localidade dos dados é muito difícil.

Modelo de passagem de mensagem

A passagem de mensagens é a abordagem de programação paralela mais comumente usada em sistemas de memória distribuída. Aqui, o programador deve determinar o paralelismo. Neste modelo, todos os processadores possuem sua própria unidade de memória local e trocam dados por meio de uma rede de comunicação.

Os processadores usam bibliotecas de passagem de mensagens para comunicação entre si. Junto com os dados sendo enviados, a mensagem contém os seguintes componentes -

• O endereço do processador do qual a mensagem está sendo enviada;

• Endereço inicial da localização da memória dos dados no processador de envio;

• Tipo de dados do envio de dados;

• Tamanho dos dados de envio;

• O endereço do processador para o qual a mensagem está sendo enviada;

• Endereço inicial da localização da memória para os dados no processador receptor.

Os processadores podem se comunicar uns com os outros por qualquer um dos seguintes métodos -

• Comunicação Ponto a Ponto
• Comunicação Coletiva
• Interface de passagem de mensagens

Comunicação Ponto a Ponto

A comunicação ponto a ponto é a forma mais simples de transmissão de mensagens. Aqui, uma mensagem pode ser enviada do processador de envio para um processador de recebimento por qualquer um dos seguintes modos de transferência -

• Synchronous mode - A próxima mensagem é enviada somente após o recebimento de uma confirmação de que sua mensagem anterior foi entregue, para manter a seqüência da mensagem.

• Asynchronous mode - Para enviar a próxima mensagem, não é necessário o recebimento da confirmação de entrega da mensagem anterior.

Comunicação Coletiva

A comunicação coletiva envolve mais de dois processadores para a passagem de mensagens. Os seguintes modos permitem comunicações coletivas -

• Barrier - O modo de barreira é possível se todos os processadores incluídos nas comunicações executam um bock particular (conhecido como barrier block) para passagem de mensagens.

• Broadcast - A transmissão é de dois tipos -

  • One-to-all - Aqui, um processador com uma única operação envia a mesma mensagem para todos os outros processadores.

  • All-to-all - Aqui, todos os processadores enviam mensagens para todos os outros processadores.

As mensagens transmitidas podem ser de três tipos -

• Personalized - Mensagens exclusivas são enviadas a todos os outros processadores de destino.

• Non-personalized - Todos os processadores de destino recebem a mesma mensagem.

• Reduction - Na transmissão de redução, um processador do grupo coleta todas as mensagens de todos os outros processadores do grupo e as combina em uma única mensagem que todos os outros processadores do grupo podem acessar.

Méritos da transmissão de mensagens

• Fornece controle de baixo nível de paralelismo;
• É portátil;
• Menos sujeito a erros;
• Menos sobrecarga na sincronização paralela e distribuição de dados.

Deméritos da passagem de mensagens

• Em comparação com o código de memória compartilhada paralela, o código de passagem de mensagens geralmente precisa de mais sobrecarga de software.

Bibliotecas de passagem de mensagens

Existem muitas bibliotecas de transmissão de mensagens. Aqui, discutiremos duas das bibliotecas de passagem de mensagens mais usadas -

• Interface de passagem de mensagem (MPI)
• Máquina Virtual Paralela (PVM)

Interface de passagem de mensagem (MPI)

É um padrão universal para fornecer comunicação entre todos os processos concorrentes em um sistema de memória distribuída. A maioria das plataformas de computação paralela comumente usadas fornece pelo menos uma implementação de interface de passagem de mensagem. Foi implementado como uma coleção de funções predefinidas chamadaslibrary e pode ser chamado de linguagens como C, C ++, Fortran, etc. MPIs são rápidos e portáteis em comparação com outras bibliotecas de passagem de mensagens.

Merits of Message Passing Interface

• É executado apenas em arquiteturas de memória compartilhada ou arquiteturas de memória distribuída;

• Cada processador tem suas próprias variáveis ​​locais;

• Em comparação com grandes computadores com memória compartilhada, os computadores com memória distribuída são mais baratos.

Demerits of Message Passing Interface

• Mais mudanças de programação são necessárias para o algoritmo paralelo;
• Às vezes é difícil depurar; e
• Não funciona bem na rede de comunicação entre os nós.

Máquina Virtual Paralela (PVM)

PVM é um sistema de passagem de mensagens portátil, projetado para conectar máquinas host heterogêneas separadas para formar uma única máquina virtual. É um único recurso de computação paralela gerenciável. Grandes problemas computacionais, como estudos de supercondutividade, simulações de dinâmica molecular e algoritmos de matriz, podem ser resolvidos de maneira mais econômica usando a memória e o poder agregado de muitos computadores. Ele gerencia todo o roteamento de mensagens, conversão de dados, agendamento de tarefas na rede de arquiteturas de computador incompatíveis.

Features of PVM

• Muito fácil de instalar e configurar;
• Vários usuários podem usar o PVM ao mesmo tempo;
• Um usuário pode executar vários aplicativos;
• É um pacote pequeno;
• Suporta C, C ++, Fortran;
• Para uma determinada execução de um programa PVM, os usuários podem selecionar o grupo de máquinas;
• É um modelo de transmissão de mensagens,
• Computação baseada em processo;
• Suporta arquitetura heterogênea.

Programação paralela de dados

O foco principal do modelo de programação paralela de dados é executar operações em um conjunto de dados simultaneamente. O conjunto de dados é organizado em alguma estrutura como uma matriz, hipercubo, etc. Os processadores executam operações coletivamente na mesma estrutura de dados. Cada tarefa é executada em uma partição diferente da mesma estrutura de dados.

É restritivo, pois nem todos os algoritmos podem ser especificados em termos de paralelismo de dados. Esta é a razão pela qual o paralelismo de dados não é universal.

As linguagens paralelas de dados ajudam a especificar a decomposição de dados e o mapeamento para os processadores. Também inclui instruções de distribuição de dados que permitem ao programador ter controle sobre os dados - por exemplo, quais dados irão para qual processador - para reduzir a quantidade de comunicação dentro dos processadores.

Para aplicar qualquer algoritmo adequadamente, é muito importante que você selecione uma estrutura de dados adequada. É porque uma determinada operação realizada em uma estrutura de dados pode levar mais tempo em comparação com a mesma operação realizada em outra estrutura de dados.

Example- Para acessar o i ^ésimo elemento em um conjunto usando uma matriz, pode levar um tempo constante, mas usando uma lista encadeada, o tempo necessário para realizar a mesma operação pode se tornar um polinômio.

Portanto, a seleção de uma estrutura de dados deve ser feita considerando a arquitetura e o tipo de operações a serem realizadas.

As seguintes estruturas de dados são comumente usadas em programação paralela -

• Lista Ligada
• Arrays
• Rede Hypercube

Lista Ligada

Uma lista encadeada é uma estrutura de dados com zero ou mais nós conectados por ponteiros. Os nós podem ou não ocupar locais de memória consecutivos. Cada nó tem duas ou três partes - umadata part que armazena os dados e os outros dois são link fieldsque armazenam o endereço do nó anterior ou seguinte. O endereço do primeiro nó é armazenado em um ponteiro externo chamadohead. O último nó, conhecido comotail, geralmente não contém nenhum endereço.

Existem três tipos de listas vinculadas -

• Lista vinculada individualmente
• Lista duplamente vinculada
• Lista Circular Ligada

Lista vinculada individualmente

Um nó de uma lista ligada individualmente contém dados e o endereço do próximo nó. Um ponteiro externo chamadohead armazena o endereço do primeiro nó.

Lista duplamente vinculada

Um nó de uma lista duplamente vinculada contém dados e o endereço do nó anterior e do próximo. Um ponteiro externo chamadohead armazena o endereço do primeiro nó e o ponteiro externo chamado tail armazena o endereço do último nó.

Lista Circular Ligada

Uma lista ligada circular é muito semelhante à lista ligada individualmente, exceto pelo fato de que o último nó salvou o endereço do primeiro nó.

Arrays

Um array é uma estrutura de dados onde podemos armazenar tipos de dados semelhantes. Pode ser unidimensional ou multidimensional. Os arrays podem ser criados estaticamente ou dinamicamente.

• Dentro statically declared arrays, a dimensão e o tamanho dos arrays são conhecidos no momento da compilação.

• Dentro dynamically declared arrays, dimensão e tamanho do array são conhecidos em tempo de execução.

Para programação de memória compartilhada, os arrays podem ser usados ​​como uma memória comum e para a programação paralela de dados, eles podem ser usados ​​por particionamento em submatrizes.

Rede Hypercube

A arquitetura do hipercubo é útil para os algoritmos paralelos em que cada tarefa precisa se comunicar com outras tarefas. A topologia de hipercubo pode facilmente incorporar outras topologias, como anel e malha. Também é conhecido como n-cubos, ondené o número de dimensões. Um hipercubo pode ser construído recursivamente.

Selecionar uma técnica de projeto adequada para um algoritmo paralelo é a tarefa mais difícil e importante. A maioria dos problemas de programação paralela pode ter mais de uma solução. Neste capítulo, discutiremos as seguintes técnicas de projeto para algoritmos paralelos -

• Dividir e conquistar
• Método ganancioso
• Programaçao dinamica
• Backtracking
• Branch & Bound
• Programação linear

Método de divisão e conquista

Na abordagem dividir para conquistar, o problema é dividido em vários pequenos subproblemas. Em seguida, os subproblemas são resolvidos recursivamente e combinados para obter a solução do problema original.

A abordagem de dividir para conquistar envolve as seguintes etapas em cada nível -

• Divide - O problema original está dividido em subproblemas.

• Conquer - Os subproblemas são resolvidos recursivamente.

• Combine - As soluções dos subproblemas são combinadas para obter a solução do problema original.

A abordagem de dividir para conquistar é aplicada nos seguintes algoritmos -

• Busca binária
• Ordenação rápida
• Mesclar classificação
• Multiplicação inteira
• Inversão de matriz
• Multiplicação da matriz

Método ganancioso

No algoritmo guloso de otimização da solução, a melhor solução é escolhida a qualquer momento. Um algoritmo ganancioso é muito fácil de aplicar a problemas complexos. Ele decide qual etapa fornecerá a solução mais precisa na próxima etapa.

Este algoritmo é chamado greedyporque quando a solução ótima para a instância menor é fornecida, o algoritmo não considera o programa total como um todo. Uma vez que uma solução é considerada, o algoritmo guloso nunca considera a mesma solução novamente.

Um algoritmo guloso funciona recursivamente criando um grupo de objetos a partir das menores partes componentes possíveis. A recursão é um procedimento para resolver um problema em que a solução de um problema específico depende da solução da instância menor desse problema.

Programaçao dinamica

A programação dinâmica é uma técnica de otimização, que divide o problema em subproblemas menores e depois de resolver cada subproblema, a programação dinâmica combina todas as soluções para obter a solução final. Ao contrário do método de dividir e conquistar, a programação dinâmica reutiliza a solução dos subproblemas muitas vezes.

O algoritmo recursivo para a série Fibonacci é um exemplo de programação dinâmica.

Algoritmo de Backtracking

Backtracking é uma técnica de otimização para resolver problemas combinacionais. É aplicado a problemas programáticos e da vida real. O problema das oito rainhas, o quebra-cabeça do Sudoku e a passagem por um labirinto são exemplos populares de algoritmos de retrocesso.

No retrocesso, começamos com uma solução possível, que satisfaça todas as condições exigidas. Em seguida, passamos para o próximo nível e se esse nível não produzir uma solução satisfatória, retornamos um nível para trás e começamos com uma nova opção.

Branch and Bound

Um algoritmo branch and bound é uma técnica de otimização para obter uma solução ótima para o problema. Busca a melhor solução para um determinado problema em todo o espaço da solução. Os limites da função a ser otimizada são mesclados com o valor da melhor solução mais recente. Ele permite que o algoritmo encontre partes do espaço de solução completamente.

O objetivo de uma pesquisa de ramificação e limite é manter o caminho de menor custo para um destino. Assim que uma solução for encontrada, ele pode continuar melhorando a solução. A pesquisa de ramificação e limite é implementada na pesquisa limitada em profundidade e na pesquisa em profundidade.

Programação linear

A programação linear descreve uma ampla classe de trabalho de otimização em que tanto o critério de otimização quanto as restrições são funções lineares. É uma técnica para obter o melhor resultado, como lucro máximo, caminho mais curto ou custo mais baixo.

Nesta programação, temos um conjunto de variáveis ​​e devemos atribuir-lhes valores absolutos para satisfazer um conjunto de equações lineares e maximizar ou minimizar uma dada função objetivo linear.

Uma matriz é um conjunto de dados numéricos e não numéricos organizados em um número fixo de linhas e colunas. A multiplicação de matrizes é um projeto de multiplicação importante na computação paralela. Aqui, discutiremos a implementação da multiplicação de matrizes em várias redes de comunicação como malha e hipercubo. Malha e hipercubo têm maior conectividade de rede, portanto, permitem algoritmo mais rápido do que outras redes, como rede em anel.

Malha de rede

Uma topologia em que um conjunto de nós forma uma grade p-dimensional é chamada de topologia de malha. Aqui, todas as arestas são paralelas ao eixo da grade e todos os nós adjacentes podem se comunicar entre si.

Número total de nós = (número de nós na linha) × (número de nós na coluna)

Uma rede mesh pode ser avaliada usando os seguintes fatores -

• Diameter
• Largura da bissecção

Diameter - Em uma rede mesh, o mais longo distanceentre dois nós é o seu diâmetro. Uma rede de malha p-dimensional tendokP nós tem um diâmetro de p(k–1).

Bisection width - A largura da bissecção é o número mínimo de arestas necessárias a serem removidas de uma rede para dividir a rede em duas metades.

Multiplicação de matriz usando rede Mesh

Consideramos um modelo SIMD de rede em malha 2D com conexões envolventes. Projetaremos um algoritmo para multiplicar duas matrizes n × n usando n ² processadores em um determinado período de tempo.

As matrizes A e B têm os elementos a _ij e b _ij respectivamente. O elemento de processamento PE _ij representa a _ij e b _ij . Organize as matrizes A e B de forma que cada processador tenha um par de elementos para multiplicar. Os elementos da matriz A se moverão para a esquerda e os elementos da matriz B se moverão para cima. Essas mudanças na posição dos elementos da matriz A e B apresentam a cada elemento de processamento, PE, um novo par de valores a multiplicar.

Etapas no algoritmo

• Alterne duas matrizes.
• Calcule todos os produtos, a _ik × b _kj
• Calcule as somas quando a etapa 2 estiver concluída.

Algoritmo

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

Rede Hypercube

Um hipercubo é uma construção n-dimensional em que as arestas são perpendiculares entre si e têm o mesmo comprimento. Um hipercubo n-dimensional também é conhecido como cubo n ou cubo n-dimensional.

Características do hipercubo com nó de 2 ^k

• Diâmetro = k
• Largura da bissecção = 2 ^{k – 1}
• Número de arestas = k

Multiplicação de matriz usando rede hipercubo

Especificação geral de redes Hypercube -

• Deixei N = 2^mser o número total de processadores. Sejam os processadores P _0, P ₁ … ..P _N-1 .

• Sejam i e i ^b dois inteiros, 0 <i, i ^b <N-1 e sua representação binária difere apenas na posição b, 0 <b <k – 1.

• Vamos considerar duas matrizes n × n, matriz A e matriz B.

• Step 1- Os elementos da matriz A e da matriz B são atribuídos aos n ³ processadores de forma que o processador na posição i, j, k terá a _ji e b _ik .

• Step 2 - Todo o processador na posição (i, j, k) calcula o produto

  C (i, j, k) = A (i, j, k) × B (i, j, k)

• Step 3 - A soma C (0, j, k) = ΣC (i, j, k) para 0 ≤ i ≤ n-1, onde 0 ≤ j, k <n – 1.

Matriz de Bloco

Matriz de bloco ou matriz particionada é uma matriz em que cada elemento representa uma matriz individual. Essas seções individuais são conhecidas comoblock ou sub-matrix.

Exemplo

Na Figura (a), X é uma matriz de bloco onde A, B, C, D são as próprias matrizes. A Figura (f) mostra a matriz total.

Multiplicação de matriz de bloco

Quando duas matrizes de bloco são matrizes quadradas, elas são multiplicadas da mesma forma que fazemos a multiplicação de matrizes simples. Por exemplo,

A classificação é um processo de organizar os elementos em um grupo em uma ordem particular, ou seja, ordem crescente, ordem decrescente, ordem alfabética, etc. Aqui, discutiremos o seguinte -

• Classificação de enumeração
• Classificação de transposição ímpar-par
• Classificação de fusão paralela
• Classificação Hiper Rápida

Classificar uma lista de elementos é uma operação muito comum. Um algoritmo de classificação sequencial pode não ser eficiente o suficiente quando temos que classificar um grande volume de dados. Portanto, algoritmos paralelos são usados ​​na classificação.

Classificação de enumeração

A classificação por enumeração é um método de organizar todos os elementos em uma lista, encontrando a posição final de cada elemento em uma lista classificada. Isso é feito comparando cada elemento com todos os outros elementos e encontrando o número de elementos com valor menor.

Portanto, para quaisquer dois elementos, a _i e a _j qualquer um dos seguintes casos deve ser verdadeiro -

• a _i <a _j
• a _i > a _j
• a _i = a _j

Algoritmo

procedure ENUM_SORTING (n)

begin
   for each process P1,j do
      C[j] := 0;
		
   for each process Pi, j do
	
      if (A[i] < A[j]) or A[i] = A[j] and i < j) then
         C[j] := 1;
      else
         C[j] := 0;
			
   for each process P1, j do
      A[C[j]] := A[j];
		
end ENUM_SORTING

Classificação de transposição ímpar-par

A classificação por transposição ímpar-par é baseada na técnica de classificação por bolha. Ele compara dois números adjacentes e os troca, se o primeiro número for maior que o segundo, para obter uma lista de ordem crescente. O caso oposto se aplica a uma série de ordem decrescente. A classificação de transposição ímpar-par opera em duas fases -odd phase e even phase. Em ambas as fases, os processos trocam números com seus números adjacentes à direita.

Algoritmo

procedure ODD-EVEN_PAR (n) 

begin 
   id := process's label 
	
   for i := 1 to n do 
   begin 
	
      if i is odd and id is odd then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
      if i is even and id is even then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
   end for
	
end ODD-EVEN_PAR

Classificação de fusão paralela

A classificação por mesclagem divide primeiro a lista não classificada nas menores sub-listas possíveis, compara-a com a lista adjacente e a mescla em uma ordem de classificação. Ele implementa o paralelismo muito bem, seguindo o algoritmo de divisão e conquista.

Algoritmo

procedureparallelmergesort(id, n, data, newdata)

begin
   data = sequentialmergesort(data)
	
      for dim = 1 to n
         data = parallelmerge(id, dim, data)
      endfor
		
   newdata = data
end

Classificação Hiper Rápida

A classificação hiper rápida é uma implementação de classificação rápida no hipercubo. Suas etapas são as seguintes -

• Divida a lista não classificada entre cada nó.
• Classifique cada nó localmente.
• Do nó 0, transmita o valor mediano.
• Divida cada lista localmente e, em seguida, troque as metades na dimensão mais alta.
• Repita as etapas 3 e 4 em paralelo até que a dimensão alcance 0.

Algoritmo

procedure HYPERQUICKSORT (B, n)
begin

   id := process’s label;
	
   for i := 1 to d do
      begin
      x := pivot;
      partition B into B1 and B2 such that B1 ≤ x < B2;
      if ith bit is 0 then
		
      begin
         send B2 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B1 U C;
      endif
      
      else
         send B1 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B2 U C;
         end else
      end for
		
   sort B using sequential quicksort;
	
end HYPERQUICKSORT

Pesquisar é uma das operações fundamentais da ciência da computação. Ele é usado em todos os aplicativos onde precisamos descobrir se um elemento está na lista fornecida ou não. Neste capítulo, discutiremos os seguintes algoritmos de pesquisa -

• Dividir e conquistar
• Pesquisa em profundidade
• Pesquisa em amplitude
• Melhor primeira pesquisa

Dividir e conquistar

Na abordagem de dividir para conquistar, o problema é dividido em vários pequenos subproblemas. Em seguida, os subproblemas são resolvidos recursivamente e combinados para obter a solução do problema original.

A abordagem de dividir para conquistar envolve as seguintes etapas em cada nível -

• Divide - O problema original está dividido em subproblemas.

• Conquer - Os subproblemas são resolvidos recursivamente.

• Combine - As soluções dos subproblemas são combinadas para obter a solução do problema original.

A pesquisa binária é um exemplo de algoritmo de divisão e conquista.

Pseudo-código

Binarysearch(a, b, low, high)

if low < high then
   return NOT FOUND
else
   mid ← (low+high) / 2
   if b = key(mid) then
      return key(mid)
   else if b < key(mid) then
      return BinarySearch(a, b, low, mid−1)
   else
   
      return BinarySearch(a, b, mid+1, high)

Pesquisa em profundidade

Pesquisa em profundidade (ou DFS) é um algoritmo para pesquisar uma árvore ou uma estrutura de dados de gráfico não direcionado. Aqui, o conceito é começar do nó inicial conhecido como oroote atravesse o mais longe possível no mesmo galho. Se obtivermos um nó sem nó sucessor, retornamos e continuamos com o vértice, que ainda não foi visitado.

Etapas da pesquisa em profundidade

• Considere um nó (raiz) que não foi visitado anteriormente e marque-o como visitado.

• Visite o primeiro nó sucessor adjacente e marque-o como visitado.

• Se todos os nós sucessores do nó considerado já foram visitados ou se não houver mais nenhum nó sucessor, retorne ao seu nó pai.

Pseudo-código

Deixei v ser o vértice onde a pesquisa começa no gráfico G.

DFS(G,v)

   Stack S := {};
	
   for each vertex u, set visited[u] := false;
   push S, v;
   while (S is not empty) do
     u := pop S;
	  
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbour w of u
            push S, w;
      end if
		
   end while
   
END DFS()

Pesquisa em amplitude

Pesquisa em amplitude (ou BFS) é um algoritmo para pesquisar uma árvore ou uma estrutura de dados de gráfico não direcionado. Aqui, começamos com um nó e, em seguida, visitamos todos os nós adjacentes no mesmo nível e, em seguida, passamos para o nó sucessor adjacente no próximo nível. Isso também é conhecido comolevel-by-level search.

Etapas da pesquisa abrangente primeiro

• Comece com o nó raiz, marque-o como visitado.
• Como o nó raiz não possui nenhum nó no mesmo nível, vá para o próximo nível.
• Visite todos os nós adjacentes e marque-os como visitados.
• Vá para o próximo nível e visite todos os nós adjacentes não visitados.
• Continue este processo até que todos os nós sejam visitados.

Pseudo-código

Deixei v ser o vértice onde a pesquisa começa no gráfico G.

BFS(G,v)

   Queue Q := {};
	
   for each vertex u, set visited[u] := false;
   insert Q, v;
   while (Q is not empty) do
      u := delete Q;
		
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbor w of u
            insert Q, w;
      end if
		
   end while
   
END BFS()

Melhor primeira pesquisa

Best-First Search é um algoritmo que percorre um gráfico para alcançar um alvo no caminho mais curto possível. Ao contrário do BFS e do DFS, Best-First Search segue uma função de avaliação para determinar qual nó é o mais apropriado para atravessar a seguir.

Etapas da melhor pesquisa

• Comece com o nó raiz, marque-o como visitado.
• Encontre o próximo nó apropriado e marque-o como visitado.
• Vá para o próximo nível, encontre o nó apropriado e marque-o como visitado.
• Continue este processo até que a meta seja alcançada.

Pseudo-código

BFS( m )

   Insert( m.StartNode )
   Until PriorityQueue is empty
      c ← PriorityQueue.DeleteMin
      If c is the goal
      Exit
   Else
   
      Foreach neighbor n of c
         If n "Unvisited"
            Mark n "Visited"
            Insert( n )
      Mark c "Examined"
      
End procedure

Um gráfico é uma notação abstrata usada para representar a conexão entre pares de objetos. Um gráfico consiste em -

• Vertices- Objetos interconectados em um gráfico são chamados de vértices. Vértices também são conhecidos comonodes.

• Edges - Edges são os links que conectam os vértices.

Existem dois tipos de gráficos -

• Directed graph - Em um grafo direcionado, as arestas têm direção, ou seja, as arestas vão de um vértice a outro.

• Undirected graph - Em um gráfico não direcionado, as arestas não têm direção.

Coloração de Gráfico

A coloração do gráfico é um método para atribuir cores aos vértices de um gráfico de forma que dois vértices adjacentes não tenham a mesma cor. Alguns problemas de coloração de gráfico são -

• Vertex coloring - Uma forma de colorir os vértices de um gráfico de forma que não haja dois vértices adjacentes com a mesma cor.

• Edge Coloring - É o método de atribuir uma cor a cada aresta de forma que duas arestas adjacentes não tenham a mesma cor.

• Face coloring - Atribui uma cor a cada face ou região de um gráfico planar de forma que nenhuma face que compartilhe um limite comum tenha a mesma cor.

Número Cromático

O número cromático é o número mínimo de cores necessárias para colorir um gráfico. Por exemplo, o número cromático do gráfico a seguir é 3.

O conceito de coloração de gráfico é aplicado na preparação de horários, atribuição de radiofrequência móvel, Suduku, atribuição de registro e coloração de mapas.

Etapas para colorir gráfico

• Defina o valor inicial de cada processador na matriz n-dimensional como 1.

• Agora, para atribuir uma cor particular a um vértice, determine se essa cor já está atribuída aos vértices adjacentes ou não.

• Se um processador detectar a mesma cor nos vértices adjacentes, ele define seu valor na matriz como 0.

• Depois de fazer n ² comparações, se qualquer elemento da matriz for 1, então é uma coloração válida.

Pseudocódigo para colorir gráfico

begin

   create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n
   status[i0,..in-1] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if aj,k=1 and ij=ikthen
            status[i0,..in-1] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

Árvore de amplitude mínima

Uma árvore geradora cuja soma de peso (ou comprimento) de todas as suas arestas é menor do que todas as outras árvores geradoras possíveis do grafo G é conhecida como um minimal spanning tree ou minimum cost spanningárvore. A figura a seguir mostra um gráfico conectado ponderado.

Algumas árvores abrangentes possíveis do gráfico acima são mostradas abaixo -

Entre todas as árvores de abrangência acima, a figura (d) é a árvore de abrangência mínima. O conceito de árvore geradora de custo mínimo é aplicado no problema do caixeiro-viajante, projeto de circuitos eletrônicos, projeto de redes eficientes e projeto de algoritmos de roteamento eficientes.

Para implementar a árvore de abrangência de custo mínimo, os dois métodos a seguir são usados ​​-

• Algoritmo de Prim
• Algoritmo de Kruskal

Algoritmo de Prim

O algoritmo de Prim é um algoritmo guloso, que nos ajuda a encontrar a árvore de abrangência mínima para um gráfico não direcionado ponderado. Ele seleciona um vértice primeiro e encontra uma aresta com o menor peso incidente naquele vértice.

Etapas do Algoritmo de Prim

• Selecione qualquer vértice, digamos v ₁ do Gráfico G.

• Selecione uma aresta, digamos e ₁ de G tal que e ₁ = v ₁ v ₂ ev ₁ ≠ v ₂ e e ₁ tenha peso mínimo entre as arestas incidentes em v ₁ no gráfico G.

• Agora, seguindo a etapa 2, selecione o incidente mínimo de aresta ponderada em v ₂ .

• Continue até que n – 1 arestas tenham sido escolhidas. Aquin é o número de vértices.

A árvore de abrangência mínima é -

Algoritmo de Kruskal

O algoritmo de Kruskal é um algoritmo guloso, que nos ajuda a encontrar a árvore geradora mínima para um grafo ponderado conectado, adicionando arcos de custo crescentes a cada etapa. É um algoritmo de árvore de abrangência mínima que encontra uma aresta com o menor peso possível que conecta quaisquer duas árvores na floresta.

Etapas do Algoritmo de Kruskal

• Selecione uma aresta de peso mínimo; digamos que e ₁ do gráfico G e e ₁ não seja um loop.

• Selecione a próxima aresta de peso mínimo conectada a e ₁ .

• Continue até que n – 1 arestas tenham sido escolhidas. Aquin é o número de vértices.

A árvore de abrangência mínima do gráfico acima é -

Algoritmo de caminho mais curto

O algoritmo do caminho mais curto é um método para encontrar o caminho de menor custo do nó de origem (S) ao nó de destino (D). Aqui, discutiremos o algoritmo de Moore, também conhecido como algoritmo de primeira pesquisa de amplitude.

Algoritmo de Moore

• Rotule o vértice de origem, S e rotule-o i E definir i=0.

• Encontre todos os vértices não rotulados adjacentes ao vértice rotulado i. Se nenhum vértice estiver conectado ao vértice S, então o vértice D não está conectado a S. Se houver vértices conectados a S, rotule-osi+1.

• Se D estiver rotulado, vá para a etapa 4, caso contrário, vá para a etapa 2 para aumentar i = i + 1.

• Pare depois que o comprimento do caminho mais curto for encontrado.