포인터 점프

Pointer jumping

포인터 점프 또는 경로 더블링은 연결된 목록 및 방향 그래프와 같은 포인터 구조에서 작동하는 병렬 알고리즘의 설계 기법입니다.포인터 점프를 사용하면 알고리즘이 가장 긴 경로의 길이에 대해 로그가 되는 시간 복잡도를 가진 경로를 따라갈 수 있습니다.네이버가 계산한 경로의 끝에 '점프'함으로써 이를 실현합니다.

포인터 점핑의 기본 조작은 포인터 구조의 각 네이버를 네이버의 네이버로 대체하는 것입니다.알고리즘의 각 단계에서 이 치환은 데이터 구조 내의 모든 노드에 대해 수행되며, 병렬로 독립적으로 수행될 수 있습니다.네이버 네이버를 추종하는 다음 단계에서는 이전 스텝에서 이미 추종하고 있는 네이버 경로가 노드의 추종 경로에 단일 스텝으로 추가됩니다.따라서 각 단계는 탐색된 경로가 통과하는 거리를 효과적으로 두 배로 늘립니다.

포인터 점프는 리스트 랭킹과 루트 찾기 같은 간단한 예시를 통해 가장 잘 이해할 수 있습니다.

리스트 랭킹

포인터 점프 알고리즘으로 해결할 수 있는 가장 간단한 작업 중 하나는 리스트 랭킹 문제입니다.이 문제는 다음과 같이 정의됩니다.N개의 노드의 링크목록을 지정하면 각 노드의 목록 끝까지 거리(노드 수로 측정)를 구합니다.거리next라고 하는 포인터로 후계자를 가리키는 노드n의 경우 d(n)는 다음과 같이 정의됩니다.

  • n.next가 0일 경우 d(n) = 0입니다.
  • 다른 노드의 경우 d(n) = d(n.next) + 1입니다.

이 문제는 시퀀셜머신에서는 리니어 타임으로 쉽게 해결할 수 있지만 병렬 알고리즘이 더 효과적입니다.n개의 프로세서를 지정하면 다음 포인터 점핑 [1]: 693 알고리즘에 의해 로그 타임 O(log N)로 해결할 수 있습니다.

  • N개의 정수 배열을 할당합니다.
  • 초기화: 각 프로세서/리스트 노드 n에 대해 병렬로:
    • n.next = 0이면 d[n] ← 0으로 설정합니다.
    • 그렇지 않으면 d[n] ← 1로 설정합니다.
  • 노드 n은 n.next가 0인 경우:
    • 각 프로세서/리스트 노드 n에 대해 병렬로:
      • n.next가 0인 경우:
        • d[n] ← d[n] + d[n.next]를 설정합니다.
        • n.next ← n.next.next를 설정합니다.

포인터 점핑은 알고리즘의 마지막 줄에서 발생합니다.각 노드의 다음 포인터는 노드의 직접 후계자를 건너뛰도록 리셋됩니다.계산의 PRAM 모델에서 공통되는 것처럼 메모리 액세스는 잠금 스텝으로 실행되므로 각 n.next.next.memory fetch는 각 n.next 메모리 스토어 전에 실행됩니다.그렇지 않으면 프로세서가 서로의 데이터를 클로빙하여 불일치를 일으킬 [1]: 694 수 있습니다.

다음 그림은 병렬 리스트 랭킹 알고리즘이 11개의 요소가 포함된 링크 리스트에 포인터 점프를 사용하는 방법을 보여줍니다.알고리즘에 기술되어 있듯이 첫 번째 반복은 null 포인터가 다음인 경우를 제외하고 모든 순위가 1로 설정된 상태에서 초기화됩니다.첫 번째 반복에서는 인접 라우터를 조사합니다.이후의 각 반복은 앞의 두 배만큼 멀리 점프합니다.

An example of performing the parallel pointer jumping technique to compute list ranking.

알고리즘을 분석하면 로그 실행 시간이 생성됩니다.N개의 프로세서가 모두 병렬로 일정한 양의 작업을 수행하기 때문에 초기화 루프에는 일정한 시간이 걸립니다.메인 루프의 내부 루프도 루프 종료 체크와 마찬가지로 일정한 시간이 소요되므로 실행 시간은 이 내부 루프가 실행되는 빈도에 따라 결정됩니다.각 반복에서의 포인터 점핑은 리스트를 홀수 요소와 짝수 요소로 이루어진 두 부분으로 분할하기 때문에 각 프로세서의 n이 가리키는 목록의 길이는 각 반복에서 절반으로 줄어들며, 각 목록의 길이가 최대 [1]: 694–695 1이 되기 전까지 최대 O(log N) 시간 동안 수행될 수 있다.

루트 파인딩

그래프에서 경로를 따르는 것은 본질적으로 직렬 작업이지만 포인터 점핑은 모든 경로를 동시에 추적하고 종속 작업 간에 결과를 공유함으로써 총 작업량을 줄입니다.포인터 점핑은 매번 반복하여 트리 루트에 가까운 정점인 후계자를 찾습니다.다른 정점에 대해 계산된 후계자를 따라가면 각 경로의 횡단은 반복마다 두 배로 증가할 수 있습니다. 이는 트리 루트를 로그 시간으로 찾을 수 있음을 의미합니다.

포인터 더블링은 어레이 상에서 동작합니다.successor그래프의 모든 정점에 대한 엔트리가 표시됩니다.각각successor[i]정점의 상위 지수로 초기화됨i그 정점이 뿌리 또는 에 해당하지 않는 경우i그 정점이 루트일 경우 그 자체입니다.반복할 때마다 각 후계자는 후계자의 후계자로 갱신됩니다.루트는 후계자가 자신을 가리킬 때 검색됩니다.

다음 의사 코드는 알고리즘을 나타냅니다. 

알고리즘 입력: 트리 포레스트를 나타내는 어레이 부모.parent[i]는 루트 출력에 대한 정점 i 또는 그 자체의 부모입니다.i ← 1 to length(부모)에 대한 모든 정점에 대한 뿌리 조상이 포함된 배열[i] ← parallel successor[i]에 대해 true인 반면, i ← 1 to length(부모)는 parallel successor_next[i] ← successer에 대해 successer에 대한 루트 조상이 포함된 배열. i ← successer_next = successure_successer에 대해 brequisher에 대해 breaker에 대해 breakescuser를(7) 병행승계[i] ← successor_next[i] return successor로 한다.

다음 이미지는 작은 포레스트에서 포인터 점프를 사용하는 예를 보여 줍니다.각 반복에서 후계자는 하나 이상의 후계자 뒤에 오는 정점을 가리킵니다.두 번 반복하면 모든 정점은 루트 노드를 가리킵니다.

Pointer jumping: example execution

이력 및 예시

포인터 점핑이라는 이름은 나중에 나오지만, JaJaha는[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. ^ a b c d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.
  2. ^ a b c d e f JáJá, Joseph (1992). An Introduction to Parallel Algorithms. Addison Wesley. ISBN 0-201-54856-9.
  3. ^ Hirschberg, D. S. (1976). "Parallel algorithms for the transitive closure and the connected component problems". STOC '76: Proceedings of the Eighth Annual ACM Symposium on Theory of Computing: 55–57. doi:10.1145/800113.803631. S2CID 306043.
  4. ^ Savage, Carla Diane (1977). Parallel Algorithms for Graph Theoretic Problems (Thesis). University of Illinois at Urbana-Champaign. Archived from the original on June 1, 2022.
  5. ^ Wylie, James C. (1979). "Chapter 4: Computational Structures". The Complexity of Parallel Computations (Thesis). Cornell University.
  6. ^ a b Shiloach, Yossi; Vishkin, Uzi (1982). "An O(log n) Parallel Connectivity Algorithm". Journal of Algorithms. 3 (1): 57–67. doi:10.1016/0196-6774(82)90008-6.
  7. ^ a b Tarjan, Robert E; Vishkin, Uzi (1984). "Finding Biconnected Components And Computing Tree Functions In Logarithmic Parallel Time". SFCS '84: Proceedings of the 25th Annual Symposium on Foundations of Computer Science: 12–20. doi:10.1109/SFCS.1984.715896. ISBN 0-8186-0591-X.
  8. ^ Quinn, Michael J. (1994). Parallel Computing: Theory and Practice (2 ed.). McGraw-Hill. ISBN 0-07-051294-9.
  9. ^ Mattson, Timothy G.; Sanders, Beverly A.; Massingill, Berna L. (2005). Patterns for Parallel Programming. Addison-Wesley. ISBN 0-321-22811-1.
  10. ^ Chung, Sun; Condon, Anne (1996). "Parallel Implementation of Bouvka's Minimum Spanning Tree Algorithm". Proceedings of International Conference on Parallel Processing: 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). "Algorithmic Techniques for Computer Vision on a Fine-Grained Parallel Machine". 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). "An investigation of JPEG image and video compression using parallel processing". Proceedings of ICASSP '94. IEEE International Conference on Acoustics, Speech and Signal Processing: 437–440. doi:10.1109/ICASSP.1994.389394. ISBN 0-7803-1775-0. S2CID 8879246.
  13. ^ Namasivayam, Vasanth Krishna; Prasanna, Viktor K. (2006). Scalable Parallel Implementation of ExactInference in Bayesian Networks. 12th International Conference on Parallel and Distributed Systems - (ICPADS'06). pp. 8 pp. doi:10.1109/ICPADS.2006.96. ISBN 0-7695-2612-8. S2CID 15728730.