Loading article…
ポインタ ジャンピングまたはパス ダブリングは、リンク リストや有向グラフなどのポインタ構造で動作する並列アルゴリズムの設計手法です。ポインタ ジャンピングにより、アルゴリズムは最長パスの長さに対して対数的な時間複雑度でパスをたどることができます。これは、近傍によって計算されたパスの末尾に「ジャンプ」することで実現されます。
ポインタ ジャンプの基本的な操作は、ポインタ構造内の各隣接ノードをその隣接ノードの隣接ノードに置き換えることです。アルゴリズムの各ステップでは、データ構造内のすべてのノードに対してこの置き換えが行われ、独立して並列に実行できます。隣接ノードの隣接ノードをたどる次のステップでは、前のステップですでにたどった隣接ノードのパスが、1 つのステップでノードのたどったパスに追加されます。したがって、各ステップでは、探索されたパスがたどる距離が実質的に 2 倍になります。
ポインター ジャンプは、リストのランク付けやルートの検索などの簡単な例を見るとよく理解できます。
リストランキング
ポインタ ジャンピング アルゴリズムで解決できる比較的単純なタスクの 1 つは、リスト ランキング問題です。この問題は次のように定義されます。N個のノードのリンク リストが与えられた場合、各ノードからリストの末尾までの距離 (ノード数で測定) を求めます。nextと呼ばれるポインタによって後続ノードを指すノードnの距離d(n)は次のように定義されます。
- n.nextがnilの場合、d(n) = 0となります。
- その他のノードの場合、d(n) = d(n.next) + 1です。
この問題は逐次処理マシンでは線形時間で簡単に解くことができますが、並列アルゴリズムではもっとうまくいきます。n個のプロセッサがあれば、次のポインタジャンプアルゴリズムによって対数時間O(log N)で解くことができます。[ 1 ] : 693
- N 個の整数の配列を割り当てます。
- 初期化: 各プロセッサ/リストノードnに対して並列に:
- n.next = nilの場合、d[n] ← 0を設定します。
- それ以外の場合はd[n] ← 1とする。
- どのノードnもn.next≠nilである:
- 各プロセッサ/リストノードnに対して、並列に次の処理を実行します。
- n.next ≠ nil の場合:
- d[n] ← d[n] + d[n.next]と設定します。
- n.next ← n.next.nextを設定します。
- n.next ≠ nil の場合:
- 各プロセッサ/リストノードnに対して、並列に次の処理を実行します。
ポインタジャンプはアルゴリズムの最後の行で発生し、各ノードの次のポインタがリセットされて、そのノードの直接の後続ノードをスキップします。PRAM計算モデルで一般的に行われているように、メモリアクセスはロックステップで実行されると想定されており、各n.next.nextメモリフェッチは各n.nextメモリストアの前に実行されます。そうしないと、プロセッサが互いのデータを上書きし、不整合が生じる可能性があります。[1] : 694
次の図は、並列リスト ランキング アルゴリズムが 11 個の要素を持つリンク リストに対してポインタ ジャンプを使用する方法を示しています。アルゴリズムで説明されているように、最初の反復は、nextの null ポインタを持つものを除き、すべてのランクが 1 に設定された状態で初期化されます。最初の反復では、すぐ隣の要素が調べられます。後続の各反復では、前の反復の 2 倍の距離をジャンプします。
アルゴリズムを分析すると、対数的な実行時間が得られる。初期化ループは、N 個のプロセッサのそれぞれが一定量の作業をすべて並列に実行するので、一定時間かかる。メイン ループの内部ループも一定時間かかる。ループの終了チェックも (仮定により) 一定時間かかるため、実行時間はこの内部ループの実行頻度によって決まる。各反復でのポインタ ジャンプによってリストが 2 つの部分に分割され、1 つは「奇数」要素で構成され、もう 1 つは「偶数」要素で構成されるため、各プロセッサのnが指すリストの長さは各反復で半分になり、これは最大でO (log N )時間で実行され 、各リストの長さは最大で 1 になる。[1] : 694–695
ルートの発見
グラフ内のパスをたどることは本質的にシリアルな操作ですが、ポインタ ジャンピングはすべてのパスを同時にたどり、依存する操作間で結果を共有することで、全体の作業量を削減します。ポインタ ジャンピングは反復され、毎回後続頂点(ツリーのルートに近い頂点) を見つけます。他の頂点に対して計算された後続頂点をたどることで、各パスのトラバースを反復ごとに 2 倍にすることができます。つまり、ツリーのルートを対数時間で見つけることができます。
successorポインター ダブリングは、グラフ内のすべての頂点のエントリを持つ配列に対して動作します。各頂点は、その頂点がルートでない場合は頂点の親インデックスで初期化され、その頂点がルートの場合はそれ自身で初期化されます。各反復で、各後続頂点はその後続頂点の後続頂点に更新されます。後続頂点の後続頂点がそれ自身を指している場合、ルートが見つかります。
successor[i]ii
次の疑似コードはアルゴリズムを示しています。
アルゴリズム
入力:木の森を表す配列の親。parent[i]は頂点iの親、またはルートの場合はそれ自身。
出力:すべての頂点のルート祖先を含む配列。
i ← 1からlength(parent)まで並列で実行
successor[ i ] ← parent[ i ]
がtrue
の場合、i ← 1からlength(successor)まで並列で実行
successor_next[ i ] ← successor[successor[ i ]]
の 場合successor_next = successor の場合
壊す
i ← 1からlength(successor)まで並列に実行
successor[ i ] ← successor_next[ i ]
を返すsuccessor
次の画像は、小さなフォレストでポインタ ジャンプを使用する例を示しています。各反復で、後続頂点は 1 つ後の後続頂点を指します。2 回の反復の後、すべての頂点はルート ノードを指します。
歴史と例
ポインタジャンピングという名前は後からつけられたが、JáJá [2] : 88 は 、この手法が初期の並列 グラフアルゴリズム[3] [4] : 43 とリストランキング[5]で初めて使用されたとしている。この手法はショートカット[6] [7]など他の名前でも説明されてきたが、1990 年代までには並列アルゴリズムの教科書では一貫してポインタジャンピングという用語が使われていた。[2] : 52–56 [1] : 692–701 [8] : 34–35 今日では、ポインタジャンピングは再帰データ型を並列に操作するためのソフトウェア設計パターンと考えられている。[9] : 99
リンクされたパスをたどる手法として、グラフアルゴリズムはポインタジャンピングに自然に適合します。その結果、ポインタジャンピングを利用した並列 グラフアルゴリズムがいくつか設計されました。これらには、根付き木の森の根を見つけるアルゴリズム、[2] : 52–53 [6]連結成分、[2] : 213–221 最小全域木[2] : 222–227 [10]および双連結成分[2] : 227–239 [7]が含まれます。ただし、ポインタジャンピングは、コンピュータービジョン、[11]画像圧縮、[12]ベイズ推論[13]など、他のさまざまな問題にも有用であることが示されています。
参考文献
- ^ abcd コーメン、トーマス H. ;レイソン、チャールズ E. ;リベスト、ロナルド L. ;スタイン、クリフォード(2001) [1990]。アルゴリズム入門（第 2 版）。MIT プレスおよびマグロウヒル。ISBN 0-262-03293-7。
- ^ abcdef ジャジャ、ジョセフ (1992).並列アルゴリズムの概要。アディソン・ウェスリー。ISBN 0-201-54856-9。
- ^ Hirschberg, DS (1976). 「推移閉包と連結成分問題のための並列アルゴリズム」。第 8 回 ACM コンピューティング理論シンポジウム議事録 - STOC '76。pp. 55–57。doi : 10.1145/800113.803631。S2CID 306043。
- ^ Savage, Carla Diane (1977). グラフ理論問題のための並列アルゴリズム（論文）. イリノイ大学アーバナシャンペーン校. 2022年6月1日時点のオリジナルよりアーカイブ。
- ^ Wylie, James C. (1979). 「第 4 章: 計算構造」.並列計算の複雑さ(論文)。コーネル大学。
- ^ ab Shiloach, Yossi; Vishkin, Uzi (1982). 「O(log n )並列接続アルゴリズム」. Journal of Algorithms . 3 (1): 57–67. doi :10.1016/0196-6774(82)90008-6.
- ^ ab Tarjan, Robert E; Vishkin, Uzi (1984). 「双連結成分の検出と対数並列時間でのツリー関数の計算」。第 25 回コンピュータサイエンスの基礎に関する年次シンポジウム、1984 年。pp. 12–20。doi : 10.1109 / SFCS.1984.715896。ISBN 0-8186-0591-X。
- ^ クイン、マイケル J. (1994)。並列コンピューティング: 理論と実践(第 2 版)。マグロウヒル。ISBN 0-07-051294-9。
- ^ Mattson, Timothy G.; Sanders, Beverly A.; Massingill, Berna L. (2005).並列プログラミングのパターン. Addison-Wesley. ISBN 0-321-22811-1。
- ^ Chung, Sun; Condon, Anne (1996). 「Bouvka の最小全域木アルゴリズムの並列実装」。国際並列処理会議の議事録。pp . 302–308。doi :10.1109/ IPPS.1996.508073。ISBN 0-8186-7255-2. S2CID 12710022。
- ^ Little, James J.; Blelloch, Guy E.; Cass, Todd A. (1989). 「細粒度並列マシンでのコンピュータビジョンのためのアルゴリズム手法」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 11 (3): 244–257. doi :10.1109/34.21793.
- ^ Cook, Gregory W.; Delp, Edward J. (1994). 「並列処理による JPEG 画像およびビデオ圧縮の調査」. ICASSP '94 議事録. IEEE 国際音響、音声、信号処理会議. pp. 437–440. doi :10.1109/ICASSP.1994.389394. ISBN 0-7803-1775-0. S2CID 8879246。
- ^ Namasivayam, Vasanth Krishna; Prasanna, Viktor K. (2006).ベイジアンネットワークにおける ExactInference のスケーラブルな並列実装。第 12 回並列分散システムに関する国際会議 - (ICPADS'06)。pp. 8 pp. doi : 10.1109/ICPADS.2006.96。ISBN 0-7695-2612-8. S2CID 15728730。