Algoritmo Paralelo - Estrutura

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 vinculada, 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 consecutivos de memória. 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 unida 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 semelhantes de dados. 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 hipercubo pode incorporar facilmente 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.