1

C++ マルチスレッドでネットワーク フローの問題を解決しようとしています。

与えられたネットワーク (すべてのノードがアークで接続され、各アークは 2 つだけの終了ノードに接続され、1 つは入力ノードで、もう 1 つは出力ノードであり、各ノードは複数の入力アークと出力アークを持つことができます)、各ノードは次のことを行う必要があります。いくつかの計算を行い、計算結果データを接続された入力ノードと出力ノードに交換します。

複数のノードを 1 つのスレッドで実行される 1 つのタスクにグループ化できます。このようにして、ネットワーク コンピューティングのワークロード全体を複数のタスクに分割できます。これらのタスクはすべてブースト スレッド プールにプッシュされ、すべてのスレッドが同時にタスクを実行できるようになります。

ただし、ノード (スレッド タスク内) が別のノード (別のスレッド タスク内) とデータ交換を行う必要がある場合、同期の問題があります。データ受信者は、データ送信者のデータ バッファーでデータが使用可能になるまで待機する必要があります。

私のプログラムは、各スレッドのタスク ワークロードができるだけ均等に割り当てられるように、ネットワークを分割する必要があります。すべてのスレッドがワンラージ データ バッファー構造を共有する場合、クリティカル セクションが大きすぎるため、プログラムの並列処理は適切ではありません。一部のスレッドは、データ構造の一部 (スレッドにとって有用) が読み取りまたは書き込みに使用可能になったとしても、1 つの大きなデータ バッファー構造がロック解除されるのを待機する必要があります。

たとえば、ワンラージ データ バッファー構造には、 cell1 、 cell2 、 cell3 、 cell4 のバッファー セルがあります。

スレッド 1 がセル 1 に書き込もうとするとき、スレッド 2 がセル 2 を読み書きできないように、データ バッファ構造全体をロックする必要があります。

そのため、1 つの大きなデータ バッファー構造を、スレッド番号に応じて複数の異なるデータ セルに分割し、各セルが 1 つのスレッド タスクにのみ必要なデータを保持するようにします。

たとえば、2 つのスレッドがある場合、4 つのスレッドが必要とするデータを別々に保持する 2 つのデータ セルを作成します。4 つのスレッドがある場合、4 つのスレッドが必要とするデータを個別に保持する 4 つのデータ セルを作成します。等々。

私の質問は次のとおりです。

(1) データセルの設計方法は? そのサイズはスレッド数に基づいていることがわかります。

(2) 同期のオーバーヘッドを減らすには? クリティカル セクションは小さいですが、ノード間のデータ交換頻度が高い場合、mutex の取得と解放のオーバーヘッドが非常に高くなる可能性があります。

(3) ノードの計算が完了し、データがそのセルに書き込まれるとき、受信ノードの計算タスクを実行する待機中のスレッドによってのみ通知メッセージが受信されるように、データ受信ノードに通知する方法。他のすべての無関係なノードとスレッドは影響を受けません。

このプログラムは非常に時間に敏感であり、メッセージ交換の待ち時間は非常に厳しく制御され、可能な限り短縮される必要があります。

どんな助けでも本当に感謝しています。

ありがとう

4

1 に答える 1

0

これに対処する通常の方法は、スレッド間でメッセージを渡すインフラストラクチャをセットアップすることだと思います。

各スレッドにはメッセージ キューがあります。あなたの例では、ノード N1 がスレッド 1 に割り当てられ、ノード N2 がスレッド 2 に割り当てられ、N1 と N2 の間にエッジがあるとします。次に、スレッド 1 が N1 計算を終了すると、スレッド 2 にメッセージを送信します。

「入力をノード N2 に送信」

メッセージをスレッドに送信するには、そのスレッドのメッセージ キューをロックし、メッセージを追加するだけです。制限付きキューを実装するには、1 つのミューテックスと 2 つの条件変数 (queue_not_empty_condition と queue_not_full_condition) を使用します。スレッドが新しい作業を待ちたいときは、メッセージ キューでスリープ状態になります。

同期のオーバーヘッドを減らすために、mutex を 1 回だけロックしながら、複数のメッセージをキューに入れる (「バッチ送信」) 方法が必要になる場合があります。次に、1 つのスレッド内でループすると、次のようになります。

if (I can do work without communicating with other threads)
    do that work
else
    send all pending messages (in batches to each destination thread)
    wait on my input queue and pop the messages off in a batch

ただし、メッセージの「バッチ処理」は、限定されたキューと複雑な方法で相互作用する可能性があります。フリーランチなし。

于 2011-09-25T05:03:49.787 に答える