Algoritmo Paralelo - Classificação
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