私は現在、何百ものユーザー定義式を含むことができるアプリケーションを持っています。現在、逆ポーランド記法を使用して計算を実行しています (値と変数をスタックにプッシュし、スタックからポップして評価します)。このプロセスの並列化を開始する最良の方法は何ですか? 関数型言語を検討する必要がありますか?
計算は数値の配列に対して実行されるため、たとえば、単純な A+B は実際には数百の加算を意味する可能性があります。私は現在 Delphi を使用していますが、これは今後の要件ではありません。その仕事に最も適したツールを使用します。数式は相互に依存する場合もあるため、たとえば、1 つの数式 C=A+B と 2 つ目の数式 D=C+A がある場合があります。
式 (方程式) が循環的ではないと仮定しましょう。そうでなければ、それらを「ただ」評価することはできません。A、B、C が配列である A = B + C のようなベクトル化された方程式がある場合、それらを構成要素の方程式に概念的に分割して、配列サイズが 5 の場合、この方程式が次のように分割されるようにします。
a1 = b1 + c1
a2 = b2 + c2
...
a5 = b5 + c5
これを仮定すると、単純な量 (整数、有理数、またはその他のもの) に関する大量の方程式が得られます。
E と F の 2 つの方程式がある場合、たとえば、F の右辺が E の左辺に言及している場合、F は E に依存しているとします。
E: a = b + c
F: q = 2*a + y
これを計算する方法に進むために、次のアルゴリズムに従って、常にランダム化された反復を使用してこれを解決できます (これは説明の中間ステップにすぎません)。
1 while (there is at least one equation which has not been computed yet)
2 select one such pending equation E so that:
3 for every equation D such that E depends_on D:
4 D has been already computed
5 calculate the left-hand side of E
このプロセスは、// 2 でどのように選択したかに関係なく、正しい答えで終了します。ここで優れているのは、簡単に並列化できることです。任意の数のスレッドで実行できます! 必要なのは、前提条件 (方程式が依存するもの) が計算されているが、それ自体はまだ計算されていない方程式を保持する同時実行セーフ キューです。すべてのスレッドは、このキューから一度に 1 つの方程式を (スレッド セーフに) ポップアウトし、答えを計算してから、すべての前提条件が計算されるように新しい方程式があるかどうかを確認し、それらの方程式を (スレッド セーフに) 追加します。作業キューに。終わり。
詳しくはわかりませんが、可能であれば SIMD スタイルのアプローチを採用することをお勧めします。つまり、スレッドを作成して、単一のデータ セットのすべての数式を計算します。数式の計算を分割して並列化しようとしても、スレッド化に適した個別のユニットに計算を分割できるようにするために必要なロジックを書くのが難しく、正しくするのが難しく、オーバーヘッドが相殺されるため、速度はあまり向上しません。速度の向上をすべてアウトします。また、収益の減少にもすぐに悩まされます。
ここで、多くのデータ セットに適用される数式のセットがある場合、並列化が容易になり、スケーリングが向上します。各スレッドは、1 セットのデータに対してすべての計算を行います。CPU コアごとに 1 つのスレッドを作成し、そのアフィニティを各コアに設定します。各スレッドは、数式評価コードの 1 つのインスタンスをインスタンス化します。単一のデータ セットをロードし、それをアイドル スレッドに渡すスーパーバイザを作成します。アイドル状態のスレッドがない場合は、最初のスレッドがそのデータの処理を完了するまで待ちます。すべてのデータ セットが処理され、すべてのスレッドが終了したら、終了します。この方法を使用すると、スレッドの切り替えが遅くなり、全体の速度に悪影響を及ぼすため、CPU のコアよりも多くのスレッドを使用しても利点はありません。
データセットが 1 つしかない場合、それは簡単な作業ではありません。他のブランチに依存しないブランチの評価ツリーを解析し、それらのブランチをファーミングして、各コアで実行されているスレッドを分離し、結果を待つ必要があります。次に、データの同期とデータの一貫性の確保で問題が発生します。