5

これまでの経験から、マルチコア プロセッサを使用した場合でも、アルゴリズムを並列化しても必ずしも高速になるとは限らないことがわかりました。実際、時々それは物事を遅くすることができます. アルゴリズムを並列化することで大幅に高速化できることを示す良いヒントは何ですか?

(もちろん、時期尚早の最適化と悪との相関関係に関する警告を考慮して)

4

6 に答える 6

5

並列化から最大限の利益を得るには、タスクを独立した (またはほぼ独立した) 同じようなサイズの粗粒度のチャンクに分割し、チャンク間のデータ通信や同期をほとんど必要としないようにする必要があります。

細粒度の並列化は、ほとんどの場合、オーバーヘッドの増加に悩まされ、利用可能な物理コアの数に関係なく、有限のスピードアップになります。

[これに対する警告は、非常に大きな番号を持つアーキテクチャです。「コア」の数 (接続マシン 64,000 コアなど)。これらは、特定のトポロジ (長方形のメッシュなど) に割り当てられた比較的単純なアクションに分割できる計算に適しています。]

于 2009-03-23T03:55:06.953 に答える
3

作業を独立した部分に分割できる場合は、うまく並列化できる可能性があります。

アムダールの法則も覚えておいてください。これは、ほとんどのプログラムにコアを追加することでパフォーマンスが向上するという点で、私たちが期待できることはほとんどないことを冷静に思い出させるものです。

于 2009-03-23T03:56:16.780 に答える
2

以前の計算に依存する計算があるときはいつでも、それは並列の問題ではありません。線形画像処理、ブルートフォース手法、遺伝的アルゴリズムなどはすべて簡単に並列化できます。

良い例えは、たくさんの友達に一度にさまざまな部分を実行させることができるということです。たとえば、さまざまな人がさまざまなセクションで作業できる場合、イケアの家具を組み合わせるとうまく並列化できますが、壁を順番に作成する必要があるため、壁紙をローリングすることはできません。

于 2009-03-23T04:13:31.433 に答える
2

まず、故ジム・グレイによるこの論文をチェックしてください。

分散コンピューティングの経済学

実際、これにより、質問に書いたことに基づいて誤解が解消されます。明らかに、問題セットが離散化に適していないほど、離散化は難しくなります。

于 2009-03-23T03:55:28.670 に答える
1

有限要素モデルを含むシミュレーションなど、大規模な行列計算を行っている場合、これらは多くの場合、単純な方法で小さな断片に分割できます。行列とベクトルの乗算は、非常に大きな行列を扱っていると仮定すると、並列化の恩恵を受けることができます。コードの実行速度を低下させる実際のパフォーマンスのボトルネックがない限り、並列処理に手間をかける必要はおそらくありません。

于 2009-03-23T04:20:42.040 に答える
0

それが機能するために多くのロックが必要な場合、それはおそらくうまく並列化できない難しいアルゴリズムの 1 つです。互いに接触する必要のない別々の部分に分割できるアルゴリズムの部分はありますか?

于 2009-03-23T03:55:17.547 に答える