Loading article…
ポインタジャンプ（またはパス倍増）は、連結リストや有向グラフなどのポインタ構造上で動作する並列アルゴリズムの設計手法です。ポインタジャンプを用いることで、アルゴリズムは最長パスの長さに対して対数的な時間計算量でパスをたどることができます。これは、隣接ノードによって計算されたパスの末尾に「ジャンプ」することで実現されます。
ポインタジャンプの基本的な操作は、ポインタ構造内の各隣接ノードを、その隣接ノードの隣接ノードに置き換えることです。アルゴリズムの各ステップでは、データ構造内のすべてのノードに対してこの置き換えが行われ、これは並列に独立して実行できます。次のステップで隣接ノードの隣接ノードをたどる際、前のステップで既にたどられた隣接ノードのパスが、そのノードのたどられたパスに1ステップで追加されます。したがって、各ステップで探索されたパスがたどった距離が実質的に2倍になります。
ポインタジャンプを理解するには、リストのランキングやルート探索などの簡単な例を見るのが一番です。
ポインタジャンプアルゴリズムで解決できる比較的単純なタスクの1つに、リストランキング問題があります。この問題は次のように定義されます。N個のノードからなる連結リストが与えられたとき、各ノードからリストの末尾までの距離（ノード数で測定）を求めます。ノードnがnextと呼ばれるポインタによって後続ノードを指している場合、距離d(n)は次のように定義されます。
この問題は逐次マシンでは線形時間で簡単に解けますが、並列アルゴリズムの方が優れています。n個のプロセッサがあれば、次のポインタジャンプアルゴリズムによって対数時間O (log N )で解くことができます。 [ 1 ] : 693
ポインタジャンプはアルゴリズムの最後の行で発生し、各ノードの次のポインタがリセットされて、そのノードの直接の後継ノードをスキップします。PRAM計算モデルで一般的に行われているように、メモリアクセスは同期して実行されると想定されています。つまり、各n.next.nextメモリフェッチは、各n.nextメモリストアの前に実行されます。そうでない場合、プロセッサが互いのデータを上書きし、不整合が発生する可能性があります。[ 1 ] : 694
次の図は、並列リストランキングアルゴリズムが11個の要素を持つ連結リストに対してポインタジャンプを使用する方法を示しています。アルゴリズムの説明にあるように、最初の反復では、次の要素へのポインタがヌルである要素を除き、すべてのランクが1に初期化されます。最初の反復では、すぐ隣の要素が調べられます。以降の各反復では、前の反復の2倍の距離までジャンプします。
アルゴリズムを分析すると、実行時間は対数的であることがわかります。初期化ループは定数時間で完了します。これは、N個のプロセッサそれぞれが一定量の処理を並列に実行するためです。メインループの内側ループも定数時間で完了し、ループの終了チェックも（仮定により）定数時間で完了するため、実行時間はこの内側ループの実行頻度によって決まります。各イテレーションでのポインタジャンプによってリストが「奇数」要素と「偶数」要素の2つの部分に分割されるため、各プロセッサのnが指すリストの長さは各イテレーションで半分になります。各リストの長さが最大でも1になるまでには、最大でO (log N )の時間で済みます 。 [ 1 ] : 694–695
グラフ内のパスをたどる操作は本質的に逐次的な処理ですが、ポインタジャンプはすべてのパスを同時にたどり、依存する操作間で結果を共有することで、全体の処理量を削減します。ポインタジャンプは反復処理を繰り返し、毎回、ツリーのルートにより近い後継頂点を見つけます。他の頂点に対して計算された後継頂点をたどることで、各パスの走査を反復ごとに2倍にすることができ、結果としてツリーのルートを対数時間で見つけることができます。
successorポインタ倍増処理は、グラフ内の各頂点に対応するエントリを持つ配列に対して行われます。各エントリは、その頂点がルートでない場合はその頂点の親インデックスで初期化され、ルートの場合は自身で初期化されます。各イテレーションにおいて、各サクセサーはサクセサーのサクセサーに更新されます。サクセサーのサクセサーが自身を指すようになったときに、ルートが見つかります。successor[i]ii
以下の擬似コードは、そのアルゴリズムを示しています。
アルゴリズム入力:木の森を表す配列 parent。parent[i] は頂点 i の親、またはルートの場合は自身です。 出力:すべての頂点のルート祖先を含む配列 i ← 1からlength(parent)まで並列に実行 successor[ i ] ← parent[ i ] を 繰り返すi ← 1からlength(successor)まで並列に実行 successor_next[ i ] ← successor[successor[ i ]] を繰り返すsuccessor_next = successorの場合 壊す for i ← 1 to length(successor) do in parallel successor[ i ] ← successor_next[ i ] return successor
次の図は、小さな森でポインタジャンプを使用する例を示しています。各イテレーションで、後継ノードは次の後継ノードの次の頂点を指します。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 ]など、他のさまざまな問題でも有用であることが示されています。