포크-조인 모형

Fork–join model
프로그램의 세 영역이 다양한 색상의 블록의 병렬 실행을 허용하는 포크-조인 패러다임의 그림.순차 실행은 상단에 표시되며, 이와 동등한 포크-조인 실행은 하단에 표시된다.

병렬 컴퓨팅에서, 포크-조인 모델은 프로그램의 지정된 지점에서 병렬로 분기하여 다음 지점에서 "조인"(merge)하고 순차 실행을 재개하는 것과 같은 병렬 프로그램을 설정하고 실행하는 방법이다.병렬 섹션은 특정 작업 세분화에 도달할 때까지 반복적으로 분기될 수 있다.포크-조인은 병렬 설계 패턴으로 간주될 수 있다.[1]: 209 ff. 그것은 1963년 초에 공식화되었다.[2][3]null

포크-조인 연산을 반복적으로 내포함으로써, 다음과 같은 일반적인 유사성 노드로 표현되는 분할정복 패러다임의 평행 버전을 얻는다.[4]

해결(해결): 문제가 충분히 작은 경우: 직접 문제 해결(해결 알고리즘) 기타: 세분(해결) 포크 하위 작업에서 해결(부품)하기 위해 이전 루프 리턴 조합 결과에서 생성된 모든 하위 작업 참여

CLRS의 단순 병렬 병합 유형은 포크-조인 알고리즘이다.[5]null

mergesort(A, lo, hi) : lo < hi : // 입력 mid : // 적어도 하나 이상의 요소 = +lo + (hi - lo) //  업무 병합(A, mid, hi)과 병행하여 2차 fork mergesort (A, lo, mid, hi) / 주 업무는 두 번째 재귀합처리한다(a, mid, hi).

첫 번째 재귀 호출은 "forced off"로, 실행은 다음 기능 부분과 (별도의 스레드에서) 병렬로 실행될 수 있다는 것을 의미한다.모든 스레드가 동기화되는 결합결합장벽처럼 보일 수도 있지만, 결합 후에는 하나의 실만 계속 이어지는 반면, 실이 장벽 이후에 계속 작동하기 때문에 다르다.[1]: 88

두 번째 반복 호출은 위의 유사 코드에서 포크가 아니다. 이것은 포킹 작업이 비용이 들 수 있기 때문에 의도적인 것이다.두 번의 재귀 호출이 모두 하위 작업으로 설정된 경우, 본 작업은 조인에서 차단되기 전에 수행할 추가 작업이 없을 것이다.[1]null

구현

포크-조인 모델의 구현은 일반적으로 작업, 섬유 또는 경량 나사산을 작동 시스템 수준의 "중량" 나사산이나 프로세스가 아닌 포크하고, 이러한 작업을 실행하기 위해 스레드 풀을 사용한다: 포크 원시 모델은 프로그래머가 잠재적 병렬 처리를 지정할 수 있도록 하며, 그 구현은 실제 병렬 실행에 매핑된다.[1]이 설계의 이유는 새로운 스레드를 만드는 것이 너무 많은 오버헤드를 초래하는 경향이 있기 때문이다.[4]null

포크-조인 프로그래밍에 사용되는 경량 스레드는 일반적으로 기본 스레드 풀에 매핑되는 자체 스케줄러(일반적으로 스레드 풀)가 있다.이 스케줄러는 완전한 기능을 갖춘 선제적 운영 체제 스케줄러보다 훨씬 간단할 수 있다. 범용 스레드 스케줄러잠금 차단을 다루어야 하지만 포크-조인 패러다임에서는 스레드만 결합 지점에서 차단한다.[4]null

포크-조인은 OpenMP 구현이 병렬 섹션의 중첩을 지원할 수도 있고 지원하지 않을 수도 있지만 OpenMP 프레임워크에서 병렬 실행의 주요 모델이다.[6]또한Java 동시성 프레임워크인 [7]Task Parallel Library에서 지원한다.NET [8]및 Intel의 TBB([1]Trading Building Block)킬크 프로그래밍 언어는 포크와 가입에 대한 언어 수준의 지원을, 포크의 형태로 하고 있다.spawn그리고sync키워드 [4]또는cilk_spawn그리고cilk_syncCilk Plus에서.[1]

참고 항목

참조

  1. ^ a b c d e f Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier.
  2. ^ Melvin E. Conway (1963). A multiprocessor system design. Fall Join Computer Conference. pp. 139–146. doi:10.1145/1463822.1463838.
  3. ^ Nyman, Linus; Laakso, Mikael (2016). "Notes on the History of Fork and Join". IEEE Annals of the History of Computing. IEEE Computer Society. 38 (3): 84–87. doi:10.1109/MAHC.2016.34.
  4. ^ a b c d Doug Lea (2000). A Java fork/join framework (PDF). ACM Conference on Java.
  5. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
  6. ^ Blaise Barney (12 June 2013). "OpenMP". Lawrence Livermore National Laboratory. Retrieved 5 April 2014.
  7. ^ "Fork/Join". The Java Tutorials. Retrieved 5 April 2014.
  8. ^ Daan Leijen; Wolfram Schulte; Sebastian Burckhardt (2009). The design of a Task Parallel Library. OOPSLA.

외부 링크