5

高速なミンコフスキー合計計算を必要とする C++ ソフトウェアを作成しています。double suffices に基づく実装。

次のようないくつかの幾何学的ライブラリを評価しました

しかし、以前のものと比較して非常に高速で、三角測量にFISTライブラリを使用する別のサードパーティ ライブラリを使用することになりました。

私のコードは、多かれ少なかれ次のように機能します。

  • ポリゴンを読みました
  • 必要なミンコフスキー和を計算します
  • n回
    • 次の計算で使用するポリゴンを決定します
    • ミンコフスキー和に基づいていくつかのことを行います
    • 結果に価値を与える
  • 最終結果として最高の値を持つ結果を取ります

ループ内の計算はラウンドごとに独立しているため、ループを並列化し、すべて正常に機能しました。

次に、各並列ラウンドでミンコフスキー和の計算を移動することにしました。

  • ポリゴンを読みました
  • number_of_threads(=n) 回
    • 次の計算で使用するポリゴンを決定します
    • このラウンドで必要なミンコフスキー和を計算します
    • ミンコフスキー和に基づいていくつかのことを行います
    • 結果に価値を与える
  • 最終結果として最高の値を持つ結果を取ります

しかし、サードパーティのライブラリは機能しなくなりました。

number_of_threads - 1エラーメッセージが表示されます

アサーションに失敗しました。

アサーションの失敗の原因となっているファイルは実行ごと、スレッドごとに変わりますが、それらはすべて FIST ヘッダーと同じ名前の c ファイルです (サードパーティ ライブラリのソース コードは持っていますが、. lib および FIST ライブラリのヘッダー)

前に述べたように、並列化されたコードの外で必要なすべてのミンコフスキー和を計算し、その結果を使用しようとしました。これは大丈夫でした。したがって、問題が FIST に起因することはほぼ確実です。

2 つの質問があります。

  • FISTライブラリがスレッドセーフかどうか知っていますか?

  • そうでない場合は、FIST を置き換える (おそらく同等のパフォーマンスを持つ) スレッドセーフな (C または、より良い) C++ 三角測量ライブラリを提案していただけますか?

編集：

実際、「スレッドセーフ」がまさに私が望んでいるものかどうかはわかりません。必要なのは、多くの独立した三角測量を同時に計算できる三角測量ライブラリだけです。

ライブラリにグローバル変数がなく、static変数のないクラスがあったとします

class triangulation
{
    // no static variables

    void execute_triangulation();
}

それは十分かもしれません。したがって、そのクラスのさまざまなインスタンスを使用して、それらのメソッドを並行して実行できます。

4

3 に答える 3

3

おそらく、CGAL の 2D 三角形分割パッケージを使用して FIST を置き換え、それをミンスコフスキーの合計を行うサードパーティ ライブラリの入力として使用できます。CGAL 三角形分割は非常に高速で信頼性があります。制約付き Delaunay 三角形分割を使用して、多角形と複雑な形状を三角形分割できます。

ところで、どのミンコフスキー ライブラリを使用していますか?

于 2013-01-24T10:53:32.397 に答える
2

考えられるすぐにテスト可能な解決策の1つは、ミンコフスキー計算を呼び出すコードの周りにミューテックスを配置することです。それが面白く聞こえて、その方法がわからない場合は、使用しているプラ​​ットフォームの詳細をコメントに追加してください。私または他の誰かがその方法の概要を説明します。

少なくとも、問題を正しく特定したかどうかがわかります。計算が総帯域幅のごく一部を占める場合、それは良い解決策であることが判明する可能性があります。

于 2013-01-28T15:47:06.507 に答える
1

これは、これが何を意味するかに大きく依存します。

私のコードは並列化可能であるため、マルチスレッドを導入しました

ヘルプを得るには、より具体的にする必要があります。「マルチスレッドを導入した」とはどういう意味ですか？たとえば、言及したライブラリには、ミンコフスキー和（またはその他のもの）の並列計算が組み込まれていません。自分で並列化する必要があります。

ミンコフスキー和に関しては、map-reduceアプローチを使用することができます。入力データセットを小さな部分に分割し、それぞれのミンコフスキー和を並列に計算し（map）、独立したワーカーからの中間結果を結合します（reduce ）。このための要件は、計算のパラメーターへの読み取り専用アクセスを備えた基本的なスレッドセーフ保証（たとえば、CGALが提供する）です。

于 2013-01-26T09:25:04.697 に答える