並列外部メモリ

PEMモデル^{[ 1 ]}は、EMモデルとPRAMモデルを組み合わせたものです。PEMモデルは、以下の要素で構成される計算モデルです。${\displaystyle P}$プロセッサと2レベルのメモリ階層。このメモリ階層は、サイズの大きな外部メモリ（メインメモリ）で構成されています。${\displaystyle N}$そして${\displaystyle P}$小さな内部メモリ（キャッシュ）。プロセッサはメインメモリを共有します。各キャッシュは単一のプロセッサ専用です。プロセッサは他のプロセッサのキャッシュにアクセスできません。キャッシュのサイズは${\displaystyle M}$これは、サイズのブロックに分割されます${\displaystyle B}$プロセッサはキャッシュ内のデータに対してのみ演算を実行できます。データはメインメモリとキャッシュ間でブロック単位で転送できます。${\displaystyle B}$。

PEMモデルの複雑度尺度はI /O複雑度^{[ 1 ]}であり、これはメインメモリとキャッシュ間の並列ブロック転送数を決定します。並列ブロック転送中、各プロセッサはブロックを転送できます。したがって、${\displaystyle P}$プロセッサは、サイズ のデータブロックを並列にロードします${\displaystyle B}$メインメモリをキャッシュに形成すると、I/O の複雑さとして考えられます。${\displaystyle O(1)}$ない${\displaystyle O(P)}$PEMモデルにおけるプログラムは、メインメモリとキャッシュ間のデータ転送を最小限に抑え、キャッシュ内のデータに対して可能な限り多くの処理を行うべきである。

PEMモデルでは、Pプロセッサ間に直接的な通信ネットワークはありません。プロセッサはメインメモリを介して間接的に通信する必要があります。複数のプロセッサがメインメモリ内の同じブロックに同時にアクセスしようとすると、読み書きの競合^{[ 1 ]}が発生します。PRAMモデルと同様に、この問題には3つの異なるバリエーションが考えられます。

• 同時読み出し同時書き込み（CRCW）：メインメモリ内の同じブロックを、複数のプロセッサが同時に読み書きできる。
• 同時読み出し排他書き込み（CREW）：メインメモリ内の同じブロックを複数のプロセッサが同時に読み取ることができます。ただし、1つのブロックに書き込めるのは一度に1つのプロセッサのみです。
• 排他的読み出し排他的書き込み（EREW）：メインメモリ内の同じブロックを複数のプロセッサが同時に読み書きすることはできません。一度に1つのプロセッサのみがブロックにアクセスできます。

以下の2つのアルゴリズム^{[ 1 ]}は、CREWとEREWの問題を解決します。${\displaystyle P\leq B}$プロセッサは同時に同じブロックに書き込みます。最初のアプローチは、書き込み操作を直列化することです。1 つのプロセッサが順番にブロックに書き込みます。これにより、合計で${\displaystyle P}$並列ブロック転送。2番目のアプローチでは${\displaystyle O(\log(P))}$並列ブロック転送と各プロセッサに追加のブロックが1つずつあります。主なアイデアは、書き込み操作をバイナリツリー方式でスケジュールし、データを徐々に1つのブロックに結合することです。最初のラウンドでは${\displaystyle P}$プロセッサはブロックを組み合わせて${\displaystyle P/2}$ブロック。それから${\displaystyle P/2}$プロセッサは${\displaystyle P/2}$ブロックへ${\displaystyle P/4}$この手順は、すべてのデータが1つのブロックに結合されるまで続けられます。

させて${\displaystyle M=\{m_{1},...,m_{d-1}\}}$は、昇順にソートされた d-1 個のピボットのベクトルとする。AをN 個の要素からなる順序付けされていない集合とする。Aのd 分割^{[ 1 ]}は、集合である。${\displaystyle \Pi =\{A_{1},...,A_{d}\}}$、 どこ${\displaystyle \cup _{i=1}^{d}A_{i}=A}$そして${\displaystyle A_{i}\cap A_{j}=\emptyset }$のために${\displaystyle 1\leq i<j\leq d}$。${\displaystyle A_{i}}$i 番目のバケットと呼ばれる。${\displaystyle A_{i}}$より大きい${\displaystyle m_{i-1}}$そしてそれよりも小さい${\displaystyle m_{i}^{2}}$以下のアルゴリズム^{[ 1 ]}では、入力はN/Pサイズの連続したセグメントに分割されます。${\displaystyle S_{1},...,S_{P}}$メインメモリ内。プロセッサは主にセグメント上で動作します。${\displaystyle S_{i}}$多分割アルゴリズム（PEM_DIST_SORT^{[ 1 ]}）は、PEMプレフィックス和アルゴリズム^{[ 1 ]}を使用して、最適なプレフィックス和を計算します。${\displaystyle O\left({\frac {N}{PB}}+\log P\right)}$入出力の複雑さ。このアルゴリズムは、最適なPRAMプレフィックスサムアルゴリズムをシミュレートします。

// データセグメントに対してd分割を並列に計算する${\displaystyle S_{i}}$各プロセッサ iに対して並列に、 ピボットのベクトルMをキャッシュに読み込む。 パーティション${\displaystyle S_{i}}$d個のバケットに分割し、ベクトルを${\displaystyle M_{i}=\{j_{1}^{i},...,j_{d}^{i}\}}$各バケット内のアイテム数とする 。 ベクトルの集合に対してPEMプレフィックス和を実行する${\displaystyle \{M_{1},...,M_{P}\}}$同時に。 // プレフィックス和ベクトルを使用して最終パーティションを計算します 各プロセッサ iに対して並列に 要素を書き込む${\displaystyle S_{i}}$適切なオフセットでメモリ位置に${\displaystyle M_{i-1}}$そして${\displaystyle M_{i}}$.end for に保存されているプレフィックス和を使用する${\displaystyle M_{P}}$最後のプロセッサPは、バケットサイズのベクトルBを計算し、それを返します。

ベクトルが${\displaystyle d=O\left({\frac {M}{B}}\right)}$ピボットMと入力セットAが連続メモリに配置されている場合、dウェイ分割問題はPEMモデルで解決できます。${\displaystyle O\left({\frac {N}{PB}}+\left\lceil {\frac {d}{B}}\right\rceil >\log(P)+d\log(B)\right)}$入出力の複雑さ。最終的なバケットの内容は、連続したメモリ領域に配置する必要があります。

選択問題は、サイズNの順不同リストAからk 番目に小さい項目を見つけることです。以下のコード^{[ 1 ]}は、PRAM 最適ソートアルゴリズムであるを使用しています。PRAMSORT${\displaystyle O(\log N)}$、そしてSELECT、これはキャッシュ最適化されたシングルプロセッサ選択アルゴリズムです。

もし${\displaystyle N\leq P}$それから${\displaystyle {\texttt {PRAMSORT}}(A,P)}$戻る${\displaystyle A[k]}$endif //各項目の中央値を求める${\displaystyle S_{i}}$各プロセッサiに対して並列に以下を実行する${\displaystyle m_{i}={\texttt {SELECT}}(S_{i},{\frac {N}{2P}})}$終了 // 中央値でソート ${\displaystyle {\texttt {PRAMSORT}}(\lbrace m_{1},\dots ,m_{2}\rbrace ,P)}$ // 中央値の中央値を中心に分割する ${\displaystyle t={\texttt {PEMPARTITION}}(A,m_{P/2},P)}$もし${\displaystyle k\leq t}$その後戻る${\displaystyle {\texttt {PEMSELECT}}(A[1:t],P,k)}$そうでなければ、${\displaystyle {\texttt {PEMSELECT}}(A[t+1:N],P,k-t)}$endif

入力が連続メモリに格納されているという仮定の下では、PEMSELECT入出力の複雑さは次のようになります。

${\displaystyle O\left({\frac {N}{PB}}+\log(PB)\cdot \log({\frac {N}{P}})\right)}$

分布ソートは、サイズNの入力リストAを、互いに素なd個の同サイズのバケットに分割します。各バケットは再帰的にソートされ、その結果が結合されて完全にソートされたリストが作成されます。

もし${\displaystyle P=1}$このタスクは、キャッシュ最適化されたシングルプロセッサのソートアルゴリズムに委任される。

それ以外の場合は、以下のアルゴリズム^{[ 1 ]}が使用されます。

// サンプル${\displaystyle {\tfrac {4N}{\sqrt {d}}}}$各プロセッサiのA からの要素を並列に実行する場合、${\displaystyle M<|S_{i}|}$それから${\displaystyle d=M/B}$ 負荷${\displaystyle S_{i}}$Mサイズのページ で個別にページをソートする${\displaystyle d=|S_{i}|}$ ロードしてソートする${\displaystyle S_{i}}$単一ページ 終了の場合、 すべて選択してください${\displaystyle {\sqrt {d}}/4}$ソートされた各メモリページから 番目の要素を連続ベクトルに格納する${\displaystyle R^{i}}$サンプルの 終了並列に ベクトルを結合する${\displaystyle R^{1}\dots R^{P}}$単一の連続したベクトルに${\displaystyle {\mathcal {R}}}$ 作る${\displaystyle {\sqrt {d}}}$コピー${\displaystyle {\mathcal {R}}}$:${\displaystyle {\mathcal {R}}_{1}\dots {\mathcal {R}}_{\sqrt {d}}}$end do // 探す${\displaystyle {\sqrt {d}}}$ピボット${\displaystyle {\mathcal {M}}[j]}$のために${\displaystyle j=1}$に${\displaystyle {\sqrt {d}}}$並行して${\displaystyle {\mathcal {M}}[j]={\texttt {PEMSELECT}}({\mathcal {R}}_{i},{\tfrac {P}{\sqrt {d}}},{\tfrac {j\cdot 4N}{d}})}$終了 連続配列でピボットをパックする${\displaystyle {\mathcal {M}}}$ //ピボットを中心にパーティションAをバケットに分割する${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {B}}={\texttt {PEMMULTIPARTITION}}(A[1:N],{\mathcal {M}},{\sqrt {d}},P)}$ // バケットを再帰的にソートする のために${\displaystyle j=1}$に${\displaystyle {\sqrt {d}}+1}$並列に 再帰的に呼び出す${\displaystyle {\texttt {PEMDISTSORT}}}$バケットjのサイズ${\displaystyle {\mathcal {B}}[j]}$ 使用${\displaystyle O\left(\left\lceil {\tfrac {{\mathcal {B}}[j]}{N/P}}\right\rceil \right)}$バケットj内の要素を担当するプロセッサは終了しました

の入出力複雑度は次のPEMDISTSORTとおりです。

${\displaystyle O\left(\left\lceil {\frac {N}{PB}}\right\rceil \left(\log _{d}P+\log _{M/B}{\frac {N}{PB}}\right)+f(N,P,d)\cdot \log _{d}P\right)}$

どこ

${\displaystyle f(N,P,d)=O\left(\log {\frac {PB}{\sqrt {d}}}\log {\frac {N}{P}}+\left\lceil {\frac {\sqrt {d}}{B}}\log P+{\sqrt {d}}\log B\right\rceil \right)}$

プロセッサの数を次のように選択すると${\displaystyle f(N,P,d)=O\left(\left\lceil {\tfrac {N}{PB}}\right\rceil \right)}$そして${\displaystyle M<B^{O(1)}}$入出力の複雑さは次のようになります。

${\displaystyle O\left({\frac {N}{PB}}\log _{M/B}{\frac {N}{B}}\right)}$

どこ${\displaystyle {\textrm {sort}}_{P}(N)}$これは、PEMモデルにおいてP個のプロセッサを使用してN個のアイテムをソートするのにかかる時間です。