1

並列コンピューティングの概念のいくつかの概念を確認するために、この質問をしています。

簡単な例を挙げましょう: 数値のセットがあります。n少なくともn/3並列コンピューターがある場合、そこからアイテムを検索するのに最適な実行時間はどれくらいですか?

これはまだ続くと思いますがO(n)、私が正しいかどうかはわかりません。大王表情の固定部分が消せるから？

ありがとうございました

4

2 に答える 2

3

O（1）またはO（ln n）の場合があります。

n /3台のコンピューターのそれぞれにn/（n / 3）個の番号が与えられます。それらはすべて本質的に3つの値を取得します。一定のサイズのセットを検索して結果を返すには、個別に一定の時間がかかります（ "0-> not found"、配列のk番目の位置で見つかった場合はk、それぞれにK *（n / 3）が与えられている場合開始する配列のインデックス）。したがって、値は時間O（1）で見つかります。

問題は答えを報告することです。n / 3マシンからの応答の中から、独自の結果を選択するために何かが選択されました。通常、これにはマシンのサブセットの中から「繰り返し」選択する必要があります。これはO（n）時間で実行できますが、並列システムでは「削減」演算子（SUM、MAXなど）を使用して実行されることがよくあります。このような削減演算子は、対数である削減ツリーを使用して実装できます（通常は実装されます） 。

一部の並列ハードウェアには非常に高速なリダクションハードウェアがありますが、それでも対数です。奇妙なことに、CPUがn / 1000の場合でも、O（1）の検索時間（大きな定数）とO（ln n）の削減時間（非常に小さな定数）が得られます。O表記を無視すると、定数時間のように「見えます」。

于 2012-05-15T10:40:20.020 に答える
0

これは、基礎となる並列モデルに厳密に依存します。実際、すべてのプロセッサがフラグFound xを定義し、すべてのプロセッサが並行して削減を実行する最終的な削減ステップは、複雑さが異なる場合があります。特に、COMMON CRCW PRAM のケースを参照してください。

メッセージパッシング設定の場合:

  • T(n) = O(n/p + log p) for p < n
  • T(n) = O(log n) for p = O(n)

共有メモリ設定の場合:

a) EREW PRAM

  • T(n) = O(n/p + log p) for p < n
  • T(n) = O(log n) for p = O(n)

b) 乗員用乳母車

同時読み取りは役に立ちません: 最終削減ステップにはまだ O(log p) 時間がかかります

  • T(n) = O(n/p + log p) for p < n
  • T(n) = O(log n) for p = O(n)

c) 一般的な CRCW PRAM

同時書き込みは非常に役立ちます。最終削減ステップには O(1) 時間かかります。フラグFound xが設定されたプロセッサは、共有場所に同じ値を同時に書き込むことができます。

  • T(n) = O(n/p) for p < n
  • T(n) = O(1) for p = O(n)
于 2012-05-17T07:58:20.187 に答える