既に線形時間アルゴリズムを並列化

Question

実際には、すでに線形時間アルゴリズムを並列化する必要がある場合はありますか？私の先生はそれは価値がないと主張しますが、私はそう信じません。

Answer 1

入力が十分大きい場合、はです。常に。

例： 順序付けられていない 'List'の中で最大の数を見つける単純なアルゴリズムは、リストをたどるだけです。これは、レコードを見つけるためにO(n)の注文に時間がかかります。

これは、100レコードまたは1000レコードの場合は問題ありません。

10億件のレコードがある場合はどうなりますか？複数のCPU間でリストを分割し、それぞれが最大値を見つけた場合は、新しい小さいリストを使用します。これをもう一度分割することができます=>並列、より速く。効率的に分割して減らすとO(log(n))だと思います。とはn個のCPUを持っていますです。

要点：入力が十分に大きければ、O(n)はもう十分ではありません。何をする必要があるかに応じて、O（n）はあなたが望むものと比較して、数秒、数分、長すぎるまで成長する可能性があります。

注：上記のO(n)またはO(log(n))と言うとき、私は検索を完了するのにかかる時間を指しています。すなわちではないすべてのCPUによって実行される「合計作業」。通常、アルゴリズムを並列化すると、CPUによって実行される総作業がいくらか増加します。

Answer 2

私はあなたの先生にも同意しません。私の主張は、MapReduceで実行される多くのアルゴリズムが線形時間アルゴリズムであることです。

たとえば、多くのhtmlページ（ウィキペディアのすべてのページなど）を検索して特定の単語を検索すると、入力では線形のアルゴリズムとなります。しかし、あなたは本当にそれを並列性なしで実行することはできません。

Answer 3

あなたの先生は間違っています。単一CPUアルゴリズムの実行時の複雑さ（O（n）、O（log n）など）は、並列化の恩恵を受けるかどうかには関係ありません。

1 CPUを使用するCPUからK CPUを使用するコードを変更すると、ランタイムをKの係数で割ることはできません。薄い空気からCPUを任意に作成することはできないため、Kは事実上定数です。したがって、実行時の複雑さは並列化の影響を受けません。あなたが望むことができるのは、一定の要因改善を得ることだけです。

これは価値がないとは言えません。場合によっては、2倍の改善が非常に有益です。さらに、何千ものCPUからなる超並列システムでは、その定数はかなり大きくなります。

Answer 4

シングルコア、シングルCPU、シングルマシン環境、およびCPUバウンドのタスクを考えると、教師は正しいです。 （しかし、その場合、複数のスレッドを実行していても、パラレルで実行されているだけで、並列に実行されているわけではありません）。

しかし、多くのスマートフォンでもマルチコアに移行しているので、実際には並列化のメリットがあります。タスクが小さいと、スレッド作成コストがメリットより高くなり、コンテキスト・スイッチングもプロセッサ・サイクルにかかるので、私はおそらくそう言います。スマートに行われていない場合、操作を並行させると実際には遅くなる可能性が常にあります。

Answer 5

明確です。グラフィックカードは並列性を提供し、CPUからGPUへの並列計算に切り替えることで多くの時間を節約できます。線形時間アルゴリズムは、並行して実行されるときに、劇的な高速化を有することができる。 GPGPUと「アプリケーション」セクション、または「グラフィックカードの計算」についてはgoogleを参照してください。

あなたは求めていませんでしたが、理論で答えが（プロセッサの多項式番号を与えられた対数時間で解くことができる）はい、複雑性クラスNCは「効果的に並列化」することが可能な問題のためにそこにあるにも明確です、多項式時間で解くことができるが、NCにないと疑われる「P完全」問題を含む。 （P問題とNP完全問題のように、NP完了はPに存在しないと思われる）