＆＃8220;とてつもない並列性の反対は何ですか？＃8221;

StackOverflow https://stackoverflow.com/questions/806569

質問

ウィキペディアによると、「恥ずかしいほど平行」問題は、問題をいくつかの並列タスクに分けるための労力がほとんどまたはまったく必要ない問題です。レイトレーシングは、各光線を原則として並行して処理できるため、例としてよく引用されます。

明らかに、いくつかの問題は並列化がはるかに困難です。不可能なこともあります。これらの困難なケースでは、どの用語が使用され、標準的な例は何なのか疑問に思っています。

「迷惑なシーケンシャル」を提案できますか？可能な名前として？

役に立ちましたか？

解決

本質的にシーケンシャル。

例：女性の数は妊娠期間を短縮しません。

他のヒント

「恥ずかしいほど平行」の反対の言葉が複数あります。問題。

完全にシーケンシャル

1つの反対は、非並列化可能の問題、つまり高速化は、複数のプロセッサを利用することで実現できます。いくつかの提案が既に投稿されていますが、別の名前を提案します：完全に連続した問題です。

例： I / Oバインドの問題、＆quot;計算f 1000000 （x 0 ）＆quot;特定の暗号化ハッシュ関数を計算する問題の種類。

コミュニケーション集中型

もう1つの反対は、並列通信の多くを必要とする並列化可能な問題です（通信集約型の問題）。このような問題の実装は、高帯域幅、低遅延の相互接続を備えたスーパーコンピューターでのみ適切にスケーリングされます。これとは対照的に、相互接続が非常に悪いシステム（例： farms ）。

通信集約型の問題の顕著な例： A x = b を解きます。ここで A は大きくて密な行列です。実際のところ、問題の実装は TOP500 ランキングをコンパイルするために使用されます。これは、個々のCPUの計算能力と相互接続の品質（通信の強度による）の両方を強調するため、優れたベンチマークです。

より実用的な用語では、離散時間ステップを使用して通常のグリッド上の偏微分方程式システムを解く数学モデル（天気予報、 in silico クラッシュテスト）、ドメイン分解。つまり、各CPUはグリッドの一部を処理し、各タイムステップの最後に、CPUは「境界」との領域境界で結果を交換します。 CPU。これらの交換により、この種の問題はコミュニケーション集約型になります。

これを投稿しないのは大変です...議論に何も追加しないことを知っているからです。しかし、すべてのサウスパークファンのために

＆quot;スーパーシリアル！＆quot;

＆quot;頑固にシリアル＆quot;？

恥ずかしいほど平行の反対は、アムダールの法則です。並列であり、完全に並列なタスクに必要な最小時間は、そのタスクの純粋に連続した部分によって決まります。

＆quot;標準例＆quot;順次プロセスの：

  • 赤ちゃんを作る：＆＃8220;クラッシュプログラムは、9人の女性が妊娠している場合、1か月で赤ちゃんを産むことができるという理論に基づいているため、失敗します。 -Werner von Braunによるもの
  • pi、e、sqrt（2）、およびその他の無理数を数百万桁に計算する：ほとんどのアルゴリズムは逐次的
  • ナビゲーション：ポイントAからポイントZに到達するには、まず中間ポイントB、C、Dなどを通過する必要があります。
  • ニュートンの方法：次のより良い近似を計算するには、各近似が必要です
  • チャレンジレスポンス認証
  • 鍵の強化
  • ハッシュチェーン
  • ハッシュキャッシュ

P-complete（ただし、これはまだ確実ではありません）。

「屈辱的にシーケンシャル」を使用します

ポール

＆quot; Gladdengly Sequential＆quot;

すべてはデータの依存関係に関係しています。恥ずかしいほど並列の問題は、解決策が多くの独立した部分で構成されている問題です。この性質の反対の問題は、大規模なデータ依存性を持つものであり、並行して実行できることはほとんどありません。 変性依存？

私がよく耳にする言葉は「密結合」です。つまり、各プロセスは、中間データを共有するために頻繁にやり取りし、通信する必要があります。基本的に、各プロセスは他のプロセスに依存して計算を完了します。

たとえば、行列処理では、多くの場合、各配列パーティションのエッジで境界値を共有する必要があります。

これは、問題の各部分が完全に自己完結型であり、IPCが不要（またはごくわずか）である、恥ずかしいほどに平行（または疎結合）の問題とは対照的です。マスター/ワーカーの並列化を考えてください。

大幅にシーケンシャル。

私は常に、クイックソートのパーティション手順として「悲しいシーケンシャル」を好みました。

自然で、間違いなく連続した問題がどのようなものになるかを推測する必要がある場合は、試してください

至福のシーケンシャル

「恥ずかしいほど平行」に対抗する。

＆quot;完全にシリアル？＆quot;

科学者が、できないことよりもできることについて考えていることは、驚くことではありません。特にこの場合、並列化の代替手段は通常のようにすべてを行うことです。

完全に並列化できませんか？ 極度に並列化可能ですか？

反対は「disconcertingly serial」です。

並列処理とは、同じ時間ステップtで多くのジョブを実行することであることに留意してください。反対は時系列問題である可能性があります

本質的に順次的な問題の例。 これは、CADパッケージおよびある種のエンジニアリング分析で一般的です。

ノード間のデータ依存関係を伴うツリートラバーサル。

グラフを横断してノードの重みを合計することを想像してください。

単に並列化することはできません。

CADソフトウェアはパーツをツリーとして表し、オブジェクトにレンダリングするにはツリーをトラバースする必要があります。 このため、CADワークステーションは多くのコアではなく、使用するコアが少なく高速です。

読んでくれてありがとう。

もちろん、両方の「名前」は問題ではないと思います。 関数型プログラミングの観点からは、「迷惑なシーケンシャル」部分は、アルゴリズムの多かれ少なかれ独立した最小の部分であると言えます。

「恥ずかしいほどに並列」なのに、実際には並列アプローチを採用しないのがコーディングの悪い習慣です。

したがって、これらの事柄に名前を付けても、その時点で並列処理を利用していない場合でも、適切なコーディングの実践が常にソリューションを独立した部分にブレーキアップする場合は意味がありません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top