0

C++ で openMP を使用しているときに、もう一度スタックします。今回は並列ハノイタワーを実装してみます。

サブハノイ（n、D、A、I）
    n =1の場合
    それから
        ディスクDをAに移動
    そうしないと              
        ハノイ(n-1,D,I,A)
        ディスクDをAに移動
        ハノイ(n-1,I,A,D)
    終わり
エンドサブ

OpenMp の命令を使用してこのアルゴリズムを並列化する方法は?

4

2 に答える 2

3

私は、このアルゴリズムが OpenMPed であるとは思わないし、ハノイ ソリューション アルゴリズムのどの塔にも多くの並列性があることに疑問を持っています。このソリューションは再帰的ですが、（たとえば）クイックソートとは異なり、タスクベースの分解には適していません。独立して実行できる 2 つのブランチはありません。そして、アルゴリズムを別の方法で書くことは、それほど重要ではないと思います。任意の時点で、1 つのディスクをあるパイルから別のパイルに (たとえば、1 から 2 に) 移動したいとします。これが発生している間、パイル 2 のディスクを移動することはできません。また、一番上のディスクが移動されるまで、パイル 1 の下にあるディスクを移動することはできません。これにより、システム内のもう 1 つの一番上のディスク (パイル 3 のディスク) だけが残り、それをパイル 3 からパイル 3 に移動することは何も行われないため、ここで可能な並列処理があるとは思えません。

たぶん、3 つ以上のパイルを使って何らかの一般化された問題を解いていたのなら、できることはあるでしょうが、それでも簡単ではないと思います。

于 2012-04-02T12:46:08.207 に答える
2

tasksv3.0で仕様に追加されたOpenMPを使用します。再び問題が発生した場合は、コードを投稿してください。

于 2012-04-02T09:30:39.313 に答える