並列アルゴリズム-ソート

並べ替えは、グループ内の要素を特定の順序、つまり昇順、降順、アルファベット順などに配置するプロセスです。ここでは、次のことについて説明します。

• 列挙型ソート
• 奇数偶数転置ソート
• 並列マージソート
• ハイパークイックソート

要素のリストの並べ替えは、非常に一般的な操作です。大量のデータを並べ替える必要がある場合、順次並べ替えアルゴリズムは十分に効率的ではない可能性があります。したがって、ソートには並列アルゴリズムが使用されます。

列挙型ソート

列挙型ソートは、ソートされたリスト内の各要素の最終的な位置を見つけることによって、リスト内のすべての要素を配置する方法です。これは、各要素を他のすべての要素と比較し、値が小さい要素の数を見つけることによって行われます。

したがって、任意の2つの要素、_aiと_jについて、次のいずれかの場合が真でなければなりません。

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

アルゴリズム

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

奇数偶数転置ソート

奇数偶数転置ソートは、バブルソート手法に基づいています。隣接する2つの番号を比較し、最初の番号が2番目の番号より大きい場合はそれらを切り替えて、昇順リストを取得します。逆の場合は、降順の系列に適用されます。奇数-偶数転置ソートは2つのフェーズで動作します-odd phase そして even phase。両方のフェーズで、プロセスは右側の隣接する番号と番号を交換します。

アルゴリズム

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

並列マージソート

マージソートは、最初にソートされていないリストを可能な限り最小のサブリストに分割し、隣接リストと比較して、ソートされた順序でマージします。分割統治アルゴリズムに従うことにより、並列処理を非常にうまく実装します。

アルゴリズム

procedureparallelmergesort(id, n, data, newdata)

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

ハイパークイックソート

ハイパークイックソートは、ハイパーキューブでのクイックソートの実装です。その手順は次のとおりです-

• ソートされていないリストを各ノードに分割します。
• 各ノードをローカルで並べ替えます。
• ノード0から、中央値をブロードキャストします。
• 各リストをローカルで分割してから、最も高い次元で半分を交換します。
• 寸法が0に達するまで、手順3と4を並行して繰り返します。

アルゴリズム

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