algorithm - アルゴリズムはビッグオ表記で評価され、並列処理の影響を受けますか？

Question

行列の乗算のブレークスルーに関する記事を読んだばかりです。O（n ^ 2.373）であるアルゴリズム。しかし、行列の乗算は並列化できるものだと思います。では、1000コアプロセッサの生産を開始した場合、これは無関係になるのでしょうか。物事はどのように変わりますか？

Answer 1

並列実行は、特定のアルゴリズムの複雑さの基本を変更しません。せいぜい、特定のサイズに時間をかけ、コアの数で割るだけです。これにより、特定のサイズの時間が一定の係数で短縮される場合がありますが、アルゴリズムの複雑さには影響しません。

同時に、並列実行によって、特定のタスクに使用するアルゴリズムが変更される場合があります。シリアルコードでうまく機能する一部のアルゴリズムは、並列タスクにうまく分割されません。複雑さが高い他のものは、並列で実行する方が優れているため、実用的なサイズの問題の場合は高速になる可能性があります。

コアの数が非常に多い場合、計算自体の複雑さは、計算を行うためにすべてのコアとの間で必要なデータを取得することの二次的なものになる可能性があります。big-Oのほとんどの計算では、これらの影響をシリアル計算で考慮していませんが、並列計算、特にすべてのノードに均一にアクセスできない並列マシンの一部のモデルでは、非常に重要になる可能性があります。

Answer 2

量子コンピューティングがいつか実用的なものになると、そうです、アルゴリズムの複雑さは変わります。

その間、固定数のプロセッサを使用してアルゴリズムを並列化すると、実行時間が比例的に分割されます（そして、最良の場合、すべてのプロセッサで実行されるタスク間に依存関係がない場合）。つまり、ランタイムを定数で除算するため、複雑さは同じままです。

Answer 3

アムダールの法則によれば、同じサイズの問題の場合、並列化は、コアの数が増えると（理論的には）収穫逓減のポイントになります。実際には、ある程度の並列化から、並列化のオーバーヘッドは実際にプログラムのパフォーマンスを低下させます。

ただし、グスタフソンの法則によれば、コアの数を増やすことは、問題のサイズが大きくなるにつれて実際に役立ちます。それがクラスターコンピューティングの背後にある動機です。より多くの計算能力があるので、並列化の助けを借りて、より大規模またはより良い精度で問題に取り組むことができます。

私たちがそのまま学習するアルゴリズムは、並列化できる場合とできない場合があります。同じタスクを効率的に並行して実行するには、別のアルゴリズムを使用する必要がある場合があります。いずれにせよ、アルゴリズムの時間計算量に対する並列化の影響を考慮に入れるために、並列の場合のBig-O表記を再分析する必要があります。