Algoritmo paralelo: clasificación
La clasificación es un proceso de organizar elementos en un grupo en un orden particular, es decir, orden ascendente, orden descendente, orden alfabético, etc. Aquí discutiremos lo siguiente:
- Orden de enumeración
- Orden de transposición pares-impares
- Orden de fusión en paralelo
- Clasificación hiperrápida
Ordenar una lista de elementos es una operación muy común. Un algoritmo de clasificación secuencial puede no ser lo suficientemente eficiente cuando tenemos que clasificar un gran volumen de datos. Por lo tanto, se utilizan algoritmos paralelos en la clasificación.
Orden de enumeración
La ordenación por enumeración es un método para organizar todos los elementos de una lista al encontrar la posición final de cada elemento en una lista ordenada. Se hace comparando cada elemento con todos los demás elementos y encontrando el número de elementos que tienen un valor menor.
Por lo tanto, para dos elementos cualesquiera, a i y a j cualquiera de los siguientes casos debe ser verdadero:
- a i <a j
- a i > a j
- a yo = 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
Orden de transposición pares-impares
La clasificación por transposición de pares pares e impares se basa en la técnica de clasificación de burbujas. Compara dos números adyacentes y los cambia, si el primer número es mayor que el segundo número para obtener una lista en orden ascendente. El caso contrario se aplica a una serie de orden descendente. La ordenación por transposición pares-impares opera en dos fases:odd phase y even phase. En ambas fases, los procesos intercambian números con su número adyacente a la derecha.
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
Orden de fusión en paralelo
Merge sort primero divide la lista sin clasificar en sublistas más pequeñas posibles, la compara con la lista adyacente y la fusiona en un orden ordenado. Implementa el paralelismo muy bien siguiendo el algoritmo de divide y vencerás.
Algoritmo
procedureparallelmergesort(id, n, data, newdata)
begin
data = sequentialmergesort(data)
for dim = 1 to n
data = parallelmerge(id, dim, data)
endfor
newdata = data
end
Clasificación hiperrápida
La ordenación hiperrápida es una implementación de la ordenación rápida en hipercubo. Sus pasos son los siguientes:
- Divida la lista sin clasificar entre cada nodo.
- Ordene cada nodo localmente.
- Desde el nodo 0, difunda el valor mediano.
- Divida cada lista localmente, luego intercambie las mitades en la dimensión más alta.
- Repita los pasos 3 y 4 en paralelo hasta que la dimensión llegue a 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