平方根を見つけるための二分法アルゴリズムを考えてみましょう。すべてのステップは前のものに依存するため、私の意見では、それを並列化することはできません。私が間違っている？
二分探索のような同様のアルゴリズムも検討してください。
編集
私の問題は二等分ではありませんが、非常に似ています。私は単調関数を持っておりf(mu)、mu where を見つける必要がありf(mu)<alphaます。1 つのコアの計算f(mu)には 2 分かかり、非常に高い精度が必要です。約 100 コアのファームがあります。私の最初の試みは、コアを 1 つだけ使用してからf、 にどれだけ近づいたかに応じて、動的ステップで のすべての値をスキャンすることでしたalpha。今、私はファーム全体を使用したいのですが、私の唯一のアイデアは、f等間隔の点で 100 の値を計算することです。
それは、 parallelizeの意味と、どの粒度であるかによって異なります。たとえば、命令レベルの並列処理 (SIMD など) を使用して、一連の入力値の平方根を見つけることができます。
二分探索は、反復回数と同様に制御フローがデータに依存するため、よりトリッキーですが、最大反復回数 (log2 N) を許可する限り、いくつかの二分探索を並行して実行することも考えられます。
これらのアルゴリズムを並列化できたとしても (実際に並列化できるかどうかはわかりませんが)、そうすることにはほとんど意味がありません。
一般的に言えば、すでにサブリニアな時間境界 (つまり、T < O(n)) を持つアルゴリズムを並列化しようとしても、ほとんど意味がありません。これらのアルゴリズムはすでに非常に高速であるため、追加のハードウェアによる影響はほとんどありません。
さらに、データの依存関係を持つすべてのアルゴリズムを並列化できないというのは (一般的には) 正しくありません。場合によっては、たとえば、異なる機能ユニットが並行して動作し、それらの間でデータを順次供給するパイプラインをセットアップすることが可能です。特に、画像処理アルゴリズムは、しばしばそのような構成に適している。
このようなデータの依存関係がない (したがって、プロセッサ間で通信する必要がない) 問題は、「非常に並列」と呼ばれます。これらの問題は、並列化できるすべての問題のスペースの小さなサブセットを表しています。
多くのアルゴリズムには, 各ステップが前のステップに依存するいくつかのステップがあります.一部のアルゴリズムはステップを変更して並列に実行できます. いくつかは並列に不可能です. BinarySearch は第二のタイプだと思います. あなたは間違っていません.