2013-01-24 21 views
6

私はMinkowskiの高速計算が必要なC++ソフトウェアを作成しています。二重に基づく実装で十分です。スレッドセーフな三角形分割ライブラリ

私は、このような

  • CGAL
  • LEDA
  • boost::geometry(ミンコフスキー和の実装を持っているが、それを実装する方法を説明するtutorialはありません)
など、いくつかの幾何学的なライブラリを評価しました

しかし、私は以前のものと比べて非常に速い別のサードパーティのライブラリを使用してしまいました三角形分割のためにFISTライブラリを使用しています。

私のコードは次のように多かれ少なかれ作品:

  • 私はミンコフスキーは私がしたポリゴンを決めるn回
    • について
    • を必要とする合計計算
    • 私のポリゴンを読みます次の計算で使用
    • 私はミンコフスキーの合計に基づいていくつかのものを行います
    • 私はvalを与えますループ内の計算は四捨五入するラウンドから独立しているので、私は最終的な結果として、最高値で

    を結果を取った結果

  • にUE、私はループを並列化し、すべてがうまく働きました。私は使用する多角形を決定私はnumber_of_threadsのための私のポリゴン
  • を読み取る(= N)

      • そしてIは各並列ラウンドでミンコフスキー和計算を移動することを決めました計算の後に

      • 私はこのラウンドで必要なミンコフスキーの合計を計算します
      • 私はミンコフスキーの合計に基づいていくつかのことを行います
      • は私が最終的な結果

        しかし、サードパーティのライブラリがこれ以上働いたとして最高の値で結果を取る結果

    • に値を与えます。

    は私が

    アサーションが失敗したと言ってnumber_of_threads - 1エラーメッセージを取得します。

    アサーションの失敗を引き起こすファイルは、実行時とスレッドからスレッドに変更されますが、すべてがFISTヘッダーと同じ名前のCファイルです(サードパーティ製ライブラリのソースコード

    前述のように、私は並列化されたコードの外に必要なすべてのミンコフスキーの合計を計算し、その中の結果を使用しようとしました。これは大丈夫だった。だから、私はFISTの問題だとほとんど確信しています。

    • あなたはFISTライブラリは、スレッドセーフであれば知っていますか:

      私は2つの質問がありますか?

    • もしそうでなければ、FIST(おそらく同等の性能を持つ)を置き換えるにはスレッドセーフ(Cまたはそれ以上)のC++三角形分割ライブラリをお勧めしますか?

    編集:私は、同時に多くの独立した三角形分割を計算することができtringulationライブラリを必要とする:「スレッドセーフ」は、私がしたい正確に何である場合

    実は、私は知りません。

    私は、ライブラリはグローバル変数を持っていないし、それがstatic変数

    class triangulation 
    { 
        // no static variables 
    
        void execute_triangulation(); 
    } 
    

    せずにクラスを持っていた場合、それは十分でできればと思います。 私はそのクラスの異なるインスタンスを使用し、それらのメソッドを並列に実行できます。

  • +0

    一般に、スレッドセーフであることが明示的に指定されていない場合は、すべてをスレッドセーフではないと考えることができます。 –

    +0

    これはライブラリのスレッドの安全性やコードの誤りによるものかどうかは不明です。スレッドの安全性について心配する必要があるかどうかは不明です。 – Mikhail

    +0

    @Mikhailあなたは正しいです、私は質問を編集します – 888

    答えて

    3

    おそらく2D triangulation package of CGALを使用してFISTを置き換え、それをMinskowski合計を行うサードパーティライブラリの入力として使用できます。 CGAL三角測量は非常に高速で信頼性があります。制約付きのDelaunay三角形分割を使用して、ポリゴンと複雑な図形を三角形分割できます。

    ところで、どのMinkowskyライブラリを使用していますか?

    +0

    私は、CGALの2D三角形分割パッケージは、すべての種類のカーネルを使用できることを知っています(これは私には良いですが、私は "正確な"ものは必要ありません)。しかし、私はおそらくそれを商業ライセンスは非常に高価です。申し訳ありませんが、私の上司は私たちが使用している図書館を秘密に保つことを好みます。 – 888

    1

    それはあなたがこれで何を意味するかに非常に大きく依存:私はあなたが助けを得るためには、より具体的にする必要があり

    をマルチスレッド紹介私のコードは並列化されているので

    。 「あなたはマルチスレッドを導入しました」とはどういう意味ですか?例えば、あなたが言及しているライブラリのどれも、ミンコフスキーの合計(あるいは何か他のもの)の並列計算を持っていません - それをあなた自身で並列化する必要があります。

    Minkowski sumについては、map-reduceアプローチを使用することができます。入力データセットをより小さな部分に分割し、それぞれのMinkowski合計を並列に(マップ)計算し、独立した労働者(削減)。これのための要件は、計算のパラメータへの読み取り専用アクセスを備えた基本的なスレッド安全保証(例えばCGALなど)です。

    +0

    私はちょうど編集しました。私はそれが今より明らかであることを願っています。 – 888

    2

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

    少なくとも、問題を正しく識別したかどうかがわかります。計算が総帯域幅の小さな部分を形成する場合、それは良い解決策になるかもしれません - そうでなければ道路上の一歩です。

    関連する問題