ポインタジャンプ

ポインタジャンピングまたはパスダブリングは、リンクリストや有向グラフなどのポインタ構造を操作する並列アルゴリズムの設計手法です。ポインタジャンピングにより、アルゴリズムは最長パスの長さに対して対数的な時間計算量でパスをたどることができます。これは、近傍によって計算されたパスの終点に「ジャンプ」することで実現されます

ポインタジャンプの基本的な操作は、ポインタ構造内の各隣接ノードをその隣接ノードの隣接ノードに置き換えることです。アルゴリズムの各ステップでは、この置き換えがデータ構造内のすべてのノードに対して行われ、独立して並列に実行できます。次のステップで隣接ノードの隣接ノードをたどる際には、前のステップで既にたどった隣接ノードのパスが、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を設定します。

ポインタジャンプはアルゴリズムの最終行で行われ、各ノードの次のポインタがリセットされ、そのノードの直接の後続ポインタをスキップします。PRAM計算モデルで一般的に行われているように、メモリアクセスはロックステップ方式で実行されると想定されており、 n.next.nextメモリフェッチはn.nextメモリストアの前に実行されます。そうでない場合、プロセッサは互いのデータを上書きし、不整合が発生する可能性があります。^{[1] : 694}

次の図は、11個の要素を持つリンクリストに対して、並列リストランキングアルゴリズムがポインタジャンプを使用する様子を示しています。アルゴリズムが示すように、最初の反復処理は、nextにヌルポインタを持つものを除き、すべてのランクが1に設定された状態で初期化されます。最初の反復処理では、すぐ隣の要素を参照します。後続の各反復処理では、前の反復処理の2倍の距離をジャンプします。

アルゴリズムを解析すると、対数的な実行時間が得られる。初期化ループは定数時間かかる。これは、N個のプロセッサそれぞれが一定量の作業を並列に実行するからである。メインループの内部ループも定数時間かかる。ループの終了チェックも（仮定により）定数時間かかるため、実行時間はこの内部ループの実行頻度によって決まる。各反復におけるポインタジャンプによってリストは2つの部分に分割され、一方は「奇数」要素、もう一方は「偶数」要素で構成されるため、各プロセッサのnが指すリストの長さは各反復で半分になる。これは最大でO (log N )回で実行され、 各リストの長さは最大で1になる。^{[1] : 694–695}

ルートの発見

グラフ内のパスを辿ることは本質的に逐次的な操作ですが、ポインタジャンプはすべてのパスを同時に辿り、依存する操作間で結果を共有することで、全体の作業量を削減します。ポインタジャンプは反復処理を行い、そのたびに後継頂点（ツリーのルートに近い頂点）を見つけます。他の頂点に対して計算された後継頂点を辿ることで、各パスの探索は反復ごとに倍増します。つまり、ツリーのルートを対数時間で見つけることができます。

ポインタ倍増は、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]など、他のさまざまな問題にも有効であることが示されています。

参考文献

1. コーメン、トーマス・H. ;レイサーソン、チャールズ・E. ;リベスト、ロナルド・L. ;スタイン、クリフォード(2001) [1990].アルゴリズム入門（第2版）. MITプレスおよびマグロウヒル. ISBN 0-262-03293-7。
2. JáJá, Joseph (1992).並列アルゴリズム入門. Addison Wesley. ISBN 0-201-54856-9。
3. Hirschberg, DS (1976). 「推移閉包と連結成分問題のための並列アルゴリズム」.第8回ACMコンピューティング理論シンポジウム議事録 - STOC '76 . pp.  55– 57. doi :10.1145/800113.803631. S2CID  306043
4. Savage, Carla Diane (1977). グラフ理論的問題のための並列アルゴリズム（論文）. イリノイ大学アーバナ・シャンペーン校. 2022年6月1日時点のオリジナルよりアーカイブ。
5. Wylie, James C. (1979). 「第4章 計算構造」.並列計算の複雑性（論文）. コーネル大学.
6. Shiloach, Yossi; Vishkin, Uzi (1982). 「O(log n )並列接続アルゴリズム」. Journal of Algorithms . 3 (1): 57– 67. doi :10.1016/0196-6774(82)90008-6.
7. Tarjan, Robert E; Vishkin, Uzi (1984). 「双連結成分の探索と木関数の対数並列時間計算」第25回計算機科学基礎シンポジウム, 1984年. pp.  12– 20. doi :10.1109/SFCS.1984.715896. ISBN 0-8186-0591-X。
8. クイン、マイケル・J. (1994).並列コンピューティング：理論と実践（第2版）. マグロウヒル. ISBN 0-07-051294-9。
9. マットソン、ティモシー・G.、サンダース、ビバリー・A.、マッシンギル、ベルナ・L. (2005).並列プログラミングのためのパターン. アディソン・ウェズリー. ISBN 0-321-22811-1。
10. Chung, Sun; Condon, Anne (1996). 「Bouvkaの最小全域木アルゴリズムの並列実装」. Proceedings of International Conference on Parallel Processing . pp.  302– 308. doi :10.1109/IPPS.1996.508073. ISBN 0-8186-7255-2 . S2CID  12710022.
11. 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
12. 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.
13. 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