なぜ再帰アルゴリズムを効率的に並列化できないのですか？

-4

再帰を含むシーケンシャルコードを、openmp、CUDAまたはMPIで書かれた同等のパラレルコードに変換することは非常に困難です。なぜそうですか？なぜ再帰アルゴリズムを効率的に並列化できないのですか？

2017-11-08 Abhishek Shridhar

あなたの質問にはまだ計算されていないぶら下がった依存関係が含まれています：どのコード、厳密に厳しいもの、そして誰がどこから引用したり正確に引用していますか？ – StarShine

-1

コードが再帰アルゴリズムとして記述されている場合、再帰の各レベルで実行される計算は、次の結果に依存する可能性があります。これは、異なる再帰的ステップからの計算を並行して行うことが難しいことを意味する。

このことについての別の考え方は、反復を反復処理にフラット化することです（たとえばCan every recursion be converted into iteration?を参照）。再帰アルゴリズムは、各反復が他の反復の結果に依存する平坦化バージョンを生成する可能性が高く、反復を並行して実行することは困難です。

出典

2017-11-08 16:14:09

これは部分的にのみ正確です。あなたが望むなら、それぞれの非終端に4つの枝があり、同じ深さに渡って木があります。 4つのプロセスがある場合、ツリー内の要素の検索を並列化する簡単なオプションは、各プロセッサにルートからの分岐の1つを与えることです。反復に変換せずに簡単に並列化できる再帰アルゴリズムがあります。 –

私はさらに進んで、明らかに間違っていないと誤解を招く可能性が非常に高いと言います。 1）タスクや同様のパラダイムを使って再帰的コードをフラット化することなく、再帰的コードを並列化することは完全に可能です。 2）平坦化された再帰的アルゴリズムでは、反復は以前の反復に必ずしも依存しない。この答えが適切な唯一のケースは、常に単一の再帰呼び出しがある場合です。 – Zulan

@HighPerformanceMarkこれは、異なる再帰的なステップを並行して行うのではなく、ステップ内で並列化する方が好きです。しかし、私はあなたの要点を取っています - 再帰を組み込んだアルゴリズムは、すべての形式を取ることができますし、並行して行うのが簡単な部分があるかもしれません。私は、私の推論がもっと例になるように言い換えようとします。 –

なぜ再帰アルゴリズムを効率的に並列化できないのですか？

答えて

関連する問題