multithreading - 「恥ずかしいほど平行」の反対語は？

Question

ウィキペディアによると、「非常に並列な」問題とは、問題を多数の並列タスクに分離するのにほとんどまたはまったく労力を必要としない問題です。レイトレーシングは、原則として各光線を並行して処理できるため、よく例として挙げられます。

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

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

score 73 · Accepted Answer

73

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

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

于 2009-04-30T12:17:52.623 に答える

score 27 · Accepted Answer

「恥ずかしいほど並列」の問題の反対は複数あります。

完全にシーケンシャル

反対の 1 つは、並列化できない問題です。つまり、複数のプロセッサを使用しても速度が向上しない問題です。すでにいくつかの提案が投稿されていますが、私はさらに別の名前を提案します:完全に連続した問題です。

例: I/O バウンドの問題、「f ^1000000 (x ₀ ) を計算する」タイプの問題、特定の暗号化ハッシュ関数の計算.

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

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

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

より実際的な言い方をすれば、離散時間ステップを使用して規則的なグリッド上で偏微分方程式系を解く数学モデル (考えてみてください: 天気予報、インシリコ衝突試験) は、ドメイン分割によって並列化できます。つまり、各 CPU はグリッドの一部を処理し、各タイムステップの最後に、CPU は領域境界での結果を「隣接する」CPU と交換します。これらの交換は、このクラスの問題をコミュニケーション集約型にします。

score 13 · Accepted Answer

私はこれを投稿しないのに苦労しています...私はそれが議論に何も追加しないことを知っているので..しかしそこにいるすべてのサウスパークファンのために

「スーパーシリアル！」

score 12 · Accepted Answer

12

「頑固にシリアル」？

于 2009-04-30T12:17:26.293 に答える

score 10 · Accepted Answer

恥ずかしいほど並列の反対は、アムダールの法則です。これは、一部のタスクは並列化できないこと、および完全に並列化されたタスクに必要な最小時間は、そのタスクの純粋に順次的な部分によって決定されることを示しています。

score 9 · Accepted Answer

順次プロセスの「標準的な例」:

赤ちゃんを作る: 「クラッシュプログラムは失敗します。なぜなら、9 人の女性が妊娠している場合、1 か月に赤ちゃんを産むことができるという理論に基づいているからです。」-- ヴェルナー・フォン・ブラウンに帰せられる
pi、e、sqrt(2)、およびその他の無理数を数百万桁まで計算: ほとんどのアルゴリズムは順次
ナビゲーション: 地点 A から地点 Z に到達するには、最初にいくつかの中間地点 B、C、D などを通過する必要があります。
ニュートン法: 次のより良い近似を計算するには、各近似が必要です。
チャレンジレスポンス認証
キー強化
ハッシュチェーン
ハッシュキャッシュ

score 5 · Accepted Answer

5

P-完全 (ただし、それはまだわかっていません)。

于 2009-04-30T13:27:27.230 に答える

score 5 · Accepted Answer

5

「屈辱的シーケンシャル」を使う

ポール

于 2012-06-06T02:57:04.787 に答える

score 2 · Accepted Answer

それはすべてデータの依存関係と関係があります。驚異的並列問題は、ソリューションが多くの独立した部分で構成されている問題です。この性質の反対の問題は、並行して実行できることがほとんどまたはまったくない、大量のデータ依存関係がある問題です。 退化的に依存していますか？

score 2 · Accepted Answer

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

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

これは、問題の各部分が完全に自己完結型であり、IPC がまったく (またはほとんど) 必要とされない、恥ずかしいほど並列 (または疎結合) の問題とは対照的です。マスター/ワーカーの並列処理を考えてください。

score 2 · Accepted Answer

2

自慢のシーケンシャル。

于 2009-06-25T02:46:37.233 に答える

score 2 · Accepted Answer

私は常に、クイックソートのパーティションステップで「悲しいことにシーケンシャル」を好んでいました。

score 2 · Accepted Answer

自然で、手に負えないほど連続的な問題が発生するのはどのようなものかを推測する必要がある場合は、試してみてください。

至福のシーケンシャル

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

score 2 · Accepted Answer

2

「うれしいシーケンシャル」

于 2009-04-30T12:09:12.053 に答える

score 0 · Accepted Answer

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

score 0 · Accepted Answer

「完全シリアル？」

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

score 0 · Accepted Answer

0

反対は「当惑するほどシリアル」です。

于 2009-11-02T10:08:43.860 に答える

score 0 · Accepted Answer

0

完全に非並列化可能ですか? 辛うじて並列化可能ですか?

于 2009-04-30T13:59:45.453 に答える

score -1 · Accepted Answer

本質的にシーケンシャルな問題の例。これは、CAD パッケージやある種のエンジニアリング分析では一般的です。

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

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

あなたはそれを並列化することはできません。

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

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

score -4 · Accepted Answer

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

「驚異的並列」は、実際には並列アプローチを採用していない場合でも、コーディングの慣例としては不適切です。

したがって、たとえその時点で並列処理を利用していなくても、優れたコーディング手法が常にソリューションを独立した部分に分解することである場合、これらに名前を付けることに意味はありません。

multithreading - 「恥ずかしいほど平行」の反対語は？

20 に答える 20

完全にシーケンシャル

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

Related

Reference