サンプルソート

サンプルソートは、並列処理システムでよく用いられる分割統治法の一種であるソートアルゴリズムです。 [ 1 ]従来の分割統治法ソートアルゴリズムは、配列をサブ区間またはバケットに分割します。各バケットは個別にソートされ、連結されます。しかし、配列が不均一に分散されている場合、これらのソートアルゴリズムのパフォーマンスは著しく低下する可能性があります。サンプルソートは、n要素のシーケンスからサイズsのサンプルを選択し、サンプルをソートして結果からp −1 < s個の要素を選択することでバケットの範囲を決定することで、この問題に対処します。これらの要素（スプリッタと呼ばれる）は、配列をp個のほぼ等しいサイズのバケットに分割します。[ 2 ]サンプルソートは、WD FrazerとAC McKellarによる1970年の論文「Samplesort: A Sampling Approach to Minimal Storage Tree Sorting」で説明されています。[ 3 ]

アルゴリズム

サンプルソートはクイックソートの一般化です。クイックソートはピボットと呼ばれる単一の値に基づいて、各ステップで入力を2つの部分に分割しますが、サンプルソートは入力からより大きなサンプルを取得し、それに応じてデータをバケットに分割します。クイックソートと同様に、サンプルソートはバケットを再帰的にソートします。

サンプルソートの実装を考案するには、バケットの数pを決定する必要があります。これが完了すると、実際のアルゴリズムは3つのフェーズで動作します。[ 4 ]

  1. 入力（スプリッタ）からp −1個の要素をサンプリングします。これらをソートします。隣接するスプリッタの各ペアはバケットを定義します。
  2. データをループ処理し、各要素を適切なバケットに配置します。（マルチプロセッサシステムの場合は、データをプロセッサに送信することを意味します。）
  3. 各バケットを分類します。

完全にソートされた出力はバケットの連結です。

一般的な戦略としては、pを利用可能なプロセッサの数に設定することが挙げられます。その後、データはプロセッサ間に分散され、各プロセッサは別のシーケンシャルソートアルゴリズムを用いてバケットのソートを実行します。

擬似コード

以下のリストは、上記の3段階アルゴリズムを疑似コードとして示し、アルゴリズムが原理的にどのように動作するかを示しています。[ 5 ]以下、Aはソートされていないデータ、kは後述するオーバーサンプリング係数、pはスプリッターの数です。 

関数sampleSort(A[1..n], k , p ) // 平均バケットサイズがしきい値を下回っている場合は、クイックソートなどに切り替える n / k < 閾値の場合、 smallSort(A) /* ステップ1 */S = [ S 1 , ..., S ( p −1) k ] をランダムに 選択する// サンプルを選択する ソートS // ソートサンプル [ s 0 , s 1 , ..., s p −1 , s p ] <- [-∞, S k , S 2 k , ..., S ( p −1) k , ∞] // スプリッターを選択 /* ステップ2 */ Aの各aについて、 s j −1 < a <= s jとなるjを 探し、 aをバケットb jに 入れる。 /* ステップ3と連結 */ 連結(sampleSort( b 1 ), ..., sampleSort( b k )) を返す

この擬似コードは、FrazerとMcKellarのオリジナルのアルゴリズムとは異なります。[ 3 ]この擬似コードでは、samplesortが再帰的に呼び出されます。FrazerとMcKellarはsamplesortを一度だけ呼び出し、その後のすべての反復処理ではクイックソートを使用しました。

複雑

プロセッサ による並列実装の複雑度は、Big O 表記で次のように表されます。p{\displaystyle p}

スプリッターを探します。

お（np+ログ⁡（p））{\displaystyle O\left({\frac {n}{p}}+\log(p)\right)}

バケットに送信します。

お（p）{\displaystyle O(p)}すべてのノードを読み取る
お（ログ⁡（p））{\displaystyle O(\log(p))}放送用
お（npログ⁡（p））{\displaystyle O\left({\frac {n}{p}}\log(p)\right)}すべてのキーの二分探索
お（np）{\displaystyle O\left({\frac {n}{p}}\right)}バケットにキーを送信する

バケットをソートします。

お（c（np））{\displaystyle O\left(c\left({\frac {n}{p}}\right)\right)}ここで、は基礎となるシーケンシャルソート法の複雑さです。[ 1 ]多くの場合、.c（n）{\displaystyle c(n)}c（n）＝nログ⁡（n）{\displaystyle c(n)=n\log(n)}

このアルゴリズムによって実行される比較回数は、大きな入力シーケンスに対して情報理論的最適値に近づきます。FrazerとMcKellarによる実験では、このアルゴリズムはクイックソートよりも15%少ない比較回数しか必要としませんでした。 ログ2⁡（n!）{\displaystyle \log_{2}(n!)}

データのサンプリング

データは様々な方法でサンプリングされます。例としては以下のようなものがあります。

  1. 均等間隔のサンプルを選択します。
  2. ランダムに選択されたサンプルを選択します。

オーバーサンプリング

オーバーサンプリング比は、スプリッターを決定する前に、サンプルとして抽出するデータ要素の数を決定します。目的は、データの分布を適切に表現することです。データ値が広く分布している場合、つまり重複する値が少ない場合は、小さなサンプリング比で十分です。分布に重複が多い場合は、より大きなオーバーサンプリング比が必要になります。理想的なケースでは、ステップ2の後、各バケットに要素が含まれます。この場合、すべてのバケットのサイズが同じであるため、どのバケットも他のバケットよりもソートに時間がかかることはありません。 n/p{\displaystyle n/p}

必要数よりも多くのサンプルを抽出した後、サンプルはソートされます。その後、サンプルシーケンスの位置にあるサンプルがバケット境界として使用されます（左端のバケットと右端のバケットのそれぞれ左境界と右境界として、 と も使用されます）。これにより、ランダムにスプリッタを選択するよりも、適切なスプリッタを見つけるためのより優れたヒューリスティックが得られます。 け{\displaystyle k}け、2け、3け、…、（p−1）け{\displaystyle k,2k,3k,\dots ,(p-1)k}−∞{\displaystyle -\infty}∞{\displaystyle \infty}p{\displaystyle p}

バケットサイズの見積もり

得られたサンプルサイズを用いて、期待されるバケットサイズ、特にバケットが特定のサイズを超える確率を推定できます。以下では、オーバーサンプリング係数が の場合、どのバケットにも を超える要素が含まれない確率がより大きいことを示します。 S∈Θ（ログ⁡nϵ2）{\displaystyle S\in \Theta \left({\dfrac {\log n}{\epsilon ^{2}}}\right)}（1+ϵ）⋅np{\displaystyle (1+\epsilon )\cdot {\dfrac {n}{p}}}1−1n{\displaystyle 1-{\dfrac {1}{n}}}

これを示すために、入力をソートされたシーケンスとします。プロセッサが 個以上の要素を取得するには、長さ 個の入力の部分シーケンスが存在し、そこから最大S個のサンプルが取り出される必要があります。これらのケースが確率 を構成します。これは確率変数として次のように表すことができます。 ⟨e1、…、en⟩{\displaystyle \langle e_{1},\dots ,e_{n}\rangle }（1+ϵ）⋅n/p{\displaystyle (1+\epsilon )\cdot n/p}（1+ϵ）⋅n/p{\displaystyle (1+\epsilon )\cdot n/p}P失敗{\displaystyle P_{\text{失敗}}}X私:={1、もし s私∈⟨ej、…、ej+（1+ϵ）⋅np⟩0、さもないと、X:=∑私＝0S⋅p−1X私{\displaystyle X_{i}:={\begin{cases}1,&{\text{if }}s_{i}\in \left\langle e_{j},\dots ,e_{j}+(1+\epsilon )\cdot {\dfrac {n}{p}}\right\rangle \\0,&{\text{otherwise}}\end{cases}},X:=\sum _{i=0}^{S\cdot p-1}X_{i}}

ホールドの期待値: X私{\displaystyle X_{i}}E（X私）＝P（X私＝1）＝1+ϵp{\displaystyle E(X_{i})=P(X_{i}=1)={\dfrac {1+\epsilon}{p}}}

これは次のことを推定するために使用されます: P失敗{\displaystyle P_{\text{失敗}}}P（X<S）≈P（X<（1−ϵ2）S）＝P（X<（1−ϵ）E（X））{\displaystyle P(X<S)\approx P(X<(1-\epsilon ^{2})S)=P(X<(1-\epsilon )E(X))}

ここで、チェルノフ境界を使用すると、次のようになります。 P失敗＝n⋅P（X<S）≤n⋅経験⁡（−ϵ2⋅S2）≤n⋅1n2 のために S≥4ϵ2ln⁡n{\displaystyle P_{\text{fail}}=n\cdot P(X<S)\leq n\cdot \exp \left({\dfrac {-\epsilon ^{2}\cdot S}{2}}\right)\leq n\cdot {\dfrac {1}{n^{2}}}{\text{ for }}S\geq {\dfrac {4}{\epsilon ^{2}}}\ln n}

多数の同一キー

同一キーが多数存在する場合、シーケンス全体が同一キーで構成されているため、アルゴリズムはシーケンスをソートする再帰レベルを多数回実行します。これは、等価バケットを導入することで回避できます。ピボットに等しい要素は、対応する等価バケットにソートされます。これは、条件分岐を1つ追加するだけで実装できます。等価バケットはそれ以上ソートされません。これは、複数回出現するキーがピボットになる可能性が高いため、有効です。 n/け{\displaystyle n/k}

並列システムでの使用

プロセッサ上での並列サンプルソートとオーバーサンプリング係数の例。p＝3{\displaystyle p=3}け＝3{\displaystyle k=3}

サンプルソートは、バルク同期並列マシンなどの分散システムを含む並列システムでよく使用されます。[ 6 ] [ 4 ] [ 7 ]スプリッタの数が可変であるため（クイックソートではピボットが1つだけであるのに対し）、サンプルソートは並列化とスケーリングに非常に適しており、直感的に操作できます。さらに、サンプルソートは、例えばクイックソートの実装よりもキャッシュ効率に優れています。

並列化は、ソート処理を各プロセッサまたはノードに分割することで実現されます。この場合、バケットの数はプロセッサの数と等しくなります。サンプルソートは、各プロセッサがほぼ同じサイズのバケットを受け取るため、並列システムにおいて効率的です。バケットは同時にソートされるため、各プロセッサはほぼ同時にソート処理を完了し、他のプロセッサを待機させる必要がありません。 p{\displaystyle p}n/p{\displaystyle n/p}

分散システムでは、各プロセッサで要素を取得し、分散ソートアルゴリズムを用いて結果の要素をソートし、-番目ごとに要素を取得して結果をすべてのプロセッサにブロードキャストすることで、スプリッタが選択されます。この処理には、プロセッサ上で要素をソートするコストと、 選択されたスプリッタをプロセッサに配布するコストがかかります。 け{\displaystyle k}けp{\displaystyle kp}け{\displaystyle k}T選別（けp、p）{\displaystyle T_{\text{sort}}(kp,p)}けp{\displaystyle kp}p{\displaystyle p}T全員集まる（p、p）{\displaystyle T_{\text{allgather}}(p,p)}p{\displaystyle p}p{\displaystyle p}

結果として得られるスプリッタを用いて、各プロセッサは自身の入力データをローカルバケットに配置します。これは二分探索でかかります。その後、ローカルバケットはプロセッサに再分配されます。プロセッサは他のすべてのプロセッサのローカルバケットを取得し、ローカルでソートします。分配には かかります。ここで は最大バケットのサイズです。ローカルソートには かかります。 お（n/pログ⁡p）{\displaystyle {\mathcal {O}}(n/p\log p)}私{\displaystyle i}b私{\displaystyle b_{i}}T全員対全員（北、p）{\displaystyle T_{\text{全対全}}(N,p)}北{\displaystyle N}Tローカルソート（北）{\displaystyle T_{\text{localsort}}(N)}

1990年代初頭にコネクションマシンスーパーコンピュータで行われた実験では、サンプルソートはプロセッサ間通信のオーバーヘッドがほとんどないため、これらのマシン上で大規模なデータセットをソートするのに特に適していることが示されました。[ 8 ]最近のGPUでは、このアルゴリズムは他のアルゴリズムよりも効果が低い可能性があります。[ 9 ]

サンプルソートの効率的な実装

スーパースカラーサンプルソートのアニメーション例。各ステップで比較される数値は青でマークされ、それ以外の読み取りまたは書き込みが行われる数値は赤でマークされます。

上述のように、サンプルソートアルゴリズムは選択されたスプリッタに従​​って要素を分割します。効率的な実装戦略は論文「Super Scalar Sample Sort」[ 5 ]で提案されています。この論文で提案されている実装では、効率的な実装のために、2つのサイズの配列（入力データを含む元の配列と一時的な配列）を使用しています。したがって、この実装はインプレースアルゴリズムではありません。 n{\displaystyle n}

各再帰ステップにおいて、データは分割された形で別の配列にコピーされます。最後の再帰ステップでデータが一時配列に保存されていた場合、データは元の配列にコピーされます。

バケットの決定

比較に基づくソートアルゴリズムにおいて、比較演算はパフォーマンスに最も影響を与える部分です。サンプルソートでは、これは各要素のバケットを決定することに相当し、要素ごとに時間がかかります。 ログ⁡け{\displaystyle \log k}

スーパースカラーサンプルソートは、配列tに暗黙的に格納されるバランス探索木を使用します。ルートは 0 に格納され、 の左後続要素はに格納され、右後続要素は に格納されます。探索木tが与えられた場合、アルゴリズムは要素のバケット番号j を次のように計算します（が真であれば 1 、偽であれば 0 と評価されると仮定します）。 t私{\displaystyle t_{i}}t2私{\displaystyle t_{2i}}t2私+1{\displaystyle t_{2i+1}}1つの私{\displaystyle a_{i}}1つの私>tj{\displaystyle a_{i}>t_{j}}

j  := 1 log 2 ( p ) 回 j  := 2 j + ( a > t j ) j  := j − p + 1 を繰り返す

バケット数kはコンパイル時に既知であるため、このループはコンパイラによって展開できます。比較演算は述語付き命令で実装されています。そのため、比較演算の速度を大幅に低下させる 分岐予測ミスは発生しません。

パーティショニング

要素を効率的に分割するには、アルゴリズムはバケットのサイズを事前に知っておく必要があります。シーケンスの要素を分割して配列に格納するには、バケットのサイズを事前に知っておく必要があります。単純なアルゴリズムであれば、各バケットの要素数をカウントできます。そして、それらの要素を別の配列の適切な場所に挿入できます。しかし、この方法では、各要素のバケットを2回（1回はバケット内の要素数をカウントし、もう1回は要素を挿入するため）決定する必要があります。

この比較の重複を避けるため、スーパースカラーサンプルソートでは、要素の各インデックスをバケットに割り当てる追加の配列（オラクルと呼ばれる）を使用します。まず、アルゴリズムは各要素のバケットとバケットサイズを決定することで の内容を特定し、次に によって決定されるバケットに要素を配置します。この配列は記憶領域にもコストがかかりますが、ビットを格納するだけで済むため、入力配列の記憶領域と比較すると、このコストはわずかです。 o{\displaystyle o}o{\displaystyle o}o{\displaystyle o}o{\displaystyle o}n⋅ログ⁡け{\displaystyle n\cdot \log k}

インプレースサンプルソート

上に示した効率的なサンプルソート実装の主な欠点は、インプレース実装ではないため、ソート中に入力シーケンスと同じサイズの2つ目の一時配列が必要になることです。例えば、クイックソートの効率的な実装はインプレース実装であるため、より空間効率に優れています。しかし、サンプルソートもインプレース実装が可能です。[ 10 ]

インプレース アルゴリズムは 4 つのフェーズに分かれています。

  1. 上記の効率的な実装におけるサンプリングと同等のサンプリング。
  2. 各プロセッサ上のローカル分類では、入力をブロックにグループ化し、各ブロック内のすべての要素が同じバケットに属しますが、バケットはメモリ内で必ずしも連続しているとは限りません。
  3. ブロックの順列により、ブロックは全体的に正しい順序になります。
  4. クリーンアップにより、バケットの端にあるいくつかの要素が移動されます。

このアルゴリズムの明らかな欠点は、すべての要素を2回読み書きすることです。1回は分類フェーズ、もう1回はブロック置換フェーズです。しかし、このアルゴリズムは、他の最先端のインプレース型アルゴリズムと比較して最大3倍、他の最先端のシーケンシャル型アルゴリズムと比較して最大1.5倍高速です。サンプリングについては既に上で説明したため、後半の3つの段階については以下で詳しく説明します。

ローカル分類

最初のステップでは、入力配列は各プロセッサに1つずつ、等サイズのブロックのストライプに分割されます。各プロセッサはさらに、各バケットに1つずつ、ブロックに等サイズのバッファを割り当てます。その後、各プロセッサはストライプをスキャンし、要素を対応するバケットのバッファに移動します。バッファがいっぱいの場合、バッファは先頭からプロセッサのストライプに書き込まれます。バッファに書き込む（つまりバッファがいっぱいになる）には、書き戻される要素よりも少なくともバッファサイズ分の要素をスキャンする必要があるため、常に少なくとも1バッファサイズ分の空きメモリが存在します。したがって、すべてのフルブロックには、同じバケットの要素が含まれます。スキャン中は、各バケットのサイズが追跡されます。 p{\displaystyle p}け{\displaystyle k}

ブロック順列

まず、プレフィックス合計演算が実行され、バケットの境界が計算されます。ただし、このフェーズでは完全なブロックのみが移動されるため、境界はブロックサイズの倍数に切り上げられ、オーバーフローバッファが1つ割り当てられます。ブロックの並べ替えを開始する前に、一部の空ブロックをバケットの末尾に移動する必要がある場合があります。その後、各バケットの書き込みポインタがバケットサブ配列の先頭に設定され、読み取りポインタが各バケットのバケットサブ配列内の最後の空でないブロックに設定されます。 わ私{\displaystyle w_{i}}b私{\displaystyle b_{i}}r私{\displaystyle r_{i}}b私{\displaystyle b_{i}}

作業競合を制限するため、各プロセッサには異なるプライマリ バケットと、それぞれがブロックを保持できる 2 つのスワップ バッファが割り当てられます。各ステップで、両方のスワップ バッファが空の場合、プロセッサはプライマリ バケットの読み取りポインタをデクリメントし、 にあるブロックを読み取ってスワップ バッファの 1 つに配置します。ブロックの最初の要素を分類してブロックの宛先バケットを決定した後、プロセッサは書き込みポインタ を増やし、 にあるブロックをもう 1 つのスワップ バッファに読み込み、そのブロックを宛先バケットに書き込みます。 の場合、スワップ バッファは再び空になります。それ以外の場合、スワップ バッファに残っているブロックを宛先バケットに挿入する必要があります。 bpr私メートル{\displaystyle b_{prim}}rpr私メートル{\displaystyle r_{prim}}rpr私メートル−1{\displaystyle r_{prim-1}}bdest{\displaystyle b_{dest}}わdest{\displaystyle w_{dest}}わdest−1{\displaystyle w_{dest-1}}わdest>rdest{\displaystyle w_{dest}>r_{dest}}

プロセッサのプライマリバケットのサブアレイ内のすべてのブロックが正しいバケット内にある場合、次のバケットがプライマリバケットとして選択されます。プロセッサがすべてのバケットをプライマリバケットとして一度選択した場合、そのプロセッサは終了します。

掃除

ブロック置換フェーズではブロック全体のみを移動したため、バケット境界付近に誤って配置された要素が存在する可能性があります。配列には各要素を配置するのに十分なスペースが必要なため、これらの誤って配置された要素は、オーバーフローバッファを考慮して、左から右へと空きスペースに移動できます。

参照

参考文献

  1. ^ a b「標準テンプレート適応型並列ライブラリを使用したサンプルソート」（PDF）（技術レポート）。テキサスA&M大学。
  2. ^ Grama, Ananth; Karypis, George; Kumar, Vipin (2003). 「9.5 バケットソートとサンプルソート」 .並列コンピューティング入門（第2版）. Addison-Wesley. ISBN 0-201-64865-2. 2016年12月13日時点のオリジナルよりアーカイブ。2014年10月28日閲覧。
  3. ^ a b Frazer, WD; McKellar, AC (1970-07-01). 「Samplesort: 最小記憶域ツリーソートへのサンプリングアプローチ」 . Journal of the ACM . 17 (3): 496– 507. doi : 10.1145/321592.321600 . S2CID 16958223 . 
  4. ^ a b Hill, Jonathan MD; McColl, Bill; Stefanescu, Dan C.; Goudreau, Mark W.; Lang, Kevin; Rao, Satish B.; Suel, Torsten; Tsantilas, Thanasis; Bisseling, Rob H. (1998). 「BSPlib: BSPプログラミングライブラリ」. Parallel Computing . 24 (14): 1947– 1980. CiteSeerX 10.1.1.48.1862 . doi : 10.1016/S0167-8191(98)00093-3 . 
  5. ^ a bピーター・サンダース、セバスチャン・ウィンケル (2004年9月14日). 「スーパースカラーサンプルソート」.アルゴリズム – ESA 2004.コンピュータサイエンス講義ノート. 第3221巻. pp.  784– 796. CiteSeerX 10.1.1.68.9881 . doi : 10.1007/978-3-540-30140-0_69 . ISBN  978-3-540-23025-0。
  6. ^ Gerbessiotis, Alexandros V.; Valiant, Leslie G. (1992). 「直接バルク同期並列アルゴリズム」. J. Parallel and Distributed Computing . 22 : 22–251 . CiteSeerX 10.1.1.51.9332 . 
  7. ^ Hightower, William L.; Prins, Jan F.; Reif, John H. (1992).大規模並列マシンにおけるランダムソートの実装(PDF) . ACM Symp. on Parallel Algorithms and Architectures.
  8. ^ Blelloch, Guy E. ; Leiserson, Charles E. ; Maggs, Bruce M. ; Plaxton, C. Gregory ; Smith, Stephen J. ; Zagha, Marco (1991).コネクションマシンCM-2におけるソートアルゴリズムの比較. ACM Symp. on Parallel Algorithms and Architectures. CiteSeerX 10.1.1.131.1835 . 
  9. ^ Satish, Nadathur; Harris, Mark; Garland, Michael.メニーコアGPU向けの効率的なソートアルゴリズムの設計. Proc. IEEE Int'l Parallel and Distributed Processing Symp. CiteSeerX 10.1.1.190.9846 . 
  10. ^ Axtmann, Michael; Witt, Sascha; Ferizovic, Daniel; Sanders, Peter (2017). 「インプレース並列スーパースカラーサンプルソート (IPSSSSo)」 .第25回ヨーロッパアルゴリズムシンポジウム (ESA 2017) . 87 (ライプニッツ国際情報科学会論文集 (LIPIcs)): 9:1–9:14. doi : 10.4230/LIPIcs.ESA.2017.9 .

FrazerとMcKellarのサンプルソートと導関数:

並列コンピュータでの使用に適応:

「 https://en.wikipedia.org/w/index.php?title=Samplesort&oldid=1295632162」から取得