일손 도둑질

병렬 컴퓨팅에서 워크스틸은 멀티 스레드 컴퓨터 프로그램의 스케줄링 전략입니다.이 솔루션은 동적 멀티스레드 컴퓨팅을 실행하는 문제를 해결합니다.이는 정적 멀티스레드 컴퓨터에서 프로세서(또는 코어) 수를 고정하여 새로운 실행 스레드를 "확산"할 수 있는 것입니다.실행 시간, 메모리 사용률 및 프로세서 간 통신 측면에서 이를 효율적으로 수행할 수 있습니다.

워크스틸 스케줄러에서 컴퓨터 시스템의 각 프로세서는 실행하는 워크 아이템(컴퓨팅 태스크, 스레드)의 큐를 가진다.각 작업 항목은 순차적으로 실행되는 일련의 명령으로 구성되지만, 그 실행 과정에서 작업 항목은 다른 작업과 병행하여 실행 가능한 새로운 작업 항목을 생성할 수도 있다.이러한 새로운 아이템은 처음에 작업 아이템을 실행하는 프로세서의 큐에 배치됩니다.프로세서가 동작하지 않게 되면, 다른 프로세서의 큐를 보고, 그 작업 항목을 「스틸」합니다.실제로 워크스틸은 스케줄링 작업을 아이돌프로세서로 분산시켜 모든 프로세서가 작업을 수행하는 한 스케줄링 오버헤드는 ^[1]발생하지 않습니다.

작업 절도는 동적 멀티스레딩을 위한 또 다른 일반적인 스케줄링 방법인 작업 공유와 대조됩니다.이 방법에서는 각 작업 항목이 생성될 때 프로세서로 스케줄이 설정됩니다.이 접근방식에 비해 모든 프로세서가 작업을 수행해야 ^[2]하는 경우에는 이러한 마이그레이션이 발생하지 않기 때문에 작업 절감을 통해 프로세서 간의 프로세스 이행이 감소합니다.

작업 절도의 개념은 멀티리스프 프로그래밍 언어의 구현으로 거슬러 올라가 1980년대에 ^[2]병렬 기능 프로그래밍 언어에 대해 연구했습니다.이것은 Cilk 프로그래밍 언어,^[3] Java fork/join ^[4]프레임워크의 스케줄러에서 사용됩니다.NET 태스크 병렬 라이브러리 ^[5]및 Rust Tokio 런타임.^[6]^[7]

실행 모델

워크스틸링은 병렬 연산의 "엄격한" 포크-조인 모델을 위해 설계되었으며, 이는 연산이 단일 소스(연산의 시작)와 단일 싱크(연산의 끝)를 가진 지향성 비순환 그래프로 볼 수 있음을 의미한다.이 그래프의 각 노드는 포크 또는 결합을 나타냅니다.포크는 "스레드"^[2] 또는 "스트랜드"^[8]로 다양하게 불리는 여러 논리 병렬 계산을 생성합니다.엣지는 시리얼 ^[9]^{[note 1]}계산을 나타냅니다.

예를 들어 Cilk와 같은 구문의 다음 간단한 포크 결합 프로그램을 생각해 보겠습니다.

함수 f(a, b): c ← fork g(a) d ← h(b) join return c + d 함수 g(a): return a × 2 함수 h(a): b ← fork g(a) c ← a + 1 join return b + c

함수 호출f(1, 2)는 다음과 같은 계산 그래프를 생성합니다.

그래프에서 두 개의 가장자리가 노드를 벗어날 때 가장자리 레이블로 표시되는 계산은 논리적으로 병렬로 수행되거나 순차적으로 수행됩니다.계산은 들어오는 에지로 표현되는 계산이 완료된 경우에만 조인 노드를 통과할 수 있습니다.스케줄러의 작업은 전체 계산을 올바른 순서로(조인 노드에 의해 제약되는 대로) 가능한 한 빨리 완료되도록 프로세서에 연산(에지)을 할당하는 것입니다.

알고리즘.

Blumofe와 Leiserson이 제시한 워크스틸 알고리즘의 랜덤 버전은 여러 스레드의 실행을 유지하고 이를 P $\displaystyle$ P 프로세서로 $P$ $스케줄합니다$ .각 프로세서에는 이중 엔드 큐(디큐)의 스레드가 있습니다.데크의 끝을 "위"와 "아래"라고 부릅니다.

실행할 현재 스레드가 있는 각 프로세서는 다음 4가지 ^[2]^{: 10}"특수한" 동작의 원인이 되는 명령을 발견할 때까지 스레드 내의 명령을 하나씩 실행합니다.

생성 명령은 새 스레드를 만듭니다.현재 스레드는 deque 하단에 배치되며 프로세서가 새 스레드의 실행을 시작합니다.
정지 명령은 스레드의 실행을 일시적으로 중단하는 명령입니다.프로세서가 디큐 바닥에서 스레드를 꺼내고 해당 스레드의 실행을 시작합니다.디큐가 비어 있는 경우 아래 설명에 따라 훔치기 작업을 시작합니다.
명령으로 인해 나사산이 끊어질 수 있습니다.이 경우의 동작은 정지하는 명령과 동일합니다.
명령은 다른 스레드를 활성화할 수 있습니다.다른 스레드는 디큐 바닥에 푸시되지만 프로세서는 현재 스레드의 실행을 계속합니다.

처음에 계산은 단일 스레드로 구성되며 일부 프로세서에 할당되며 다른 프로세서는 유휴 상태로 시작합니다.프로세서가 아이돌 상태가 되면 실제 작업 도둑질이 시작됩니다.즉, 다음과 같습니다.

랜덤으로 균일하게 다른 프로세서를 선택한다.
다른 프로세서의 디큐가 비어 있지 않은 경우 디큐에서 최상위 스레드를 제거하고 실행을 시작합니다.
그렇지 않으면 반복합니다.

아동 절도 vs. 계속 절도

생성 규칙에서 Blumofe와 Leiserson은 함수 호출을 실행하는 것처럼 "부모" 스레드가 새로운 스레드를 실행하도록 제안합니다(C-like 프로그램 f(x); g(y;에서는 g에 대한 호출이 실행되기 전에 f에 대한 함수 호출이 완료됨).생성된 스레드가 실행되는 동안 함수의 연속성이 도용될 수 있기 때문에 이를 "계속 도용"이라고 합니다.이것은 Cilk ^[8]Plus에서 사용되는 스케줄링 알고리즘입니다.워크스틸링을 구현하는 유일한 방법은 아닙니다. 대체 전략은 "자녀스틸링"이라고 불리며 컴파일러 ^[8]지원 없이 라이브러리로 구현하기가 더 쉽습니다.자녀 도용은 스레딩 빌딩 블록, 마이크로소프트의 태스크 병렬 라이브러리 및 OpenMP에 의해 사용되지만, 후자는 프로그래머가 어떤 전략을 ^[8]사용할지 제어할 수 있습니다.

효율성.

몇 가지 종류의 일감 몰아주기가 제안되었다.Blumofe 및 Leiserson에 의한 랜덤화 바리안트는 P $\displaystyle$ P_ $T_{1}/P+O(T_{\infty })$ 1 $P$ $}/P+O(T_{\infty})$ 프로세서에서 $P$ 되는 $T_{1}/P+O(T_{\infty })$ $O$ {\displaystyle T_{\infty})에 $T_{1}/P+O(T_{\infty })$ 병렬연산을 실행합니다. $T_{1}$ 서 $\$ T_ ${1$ }은 $T_{1}$ 작업시간입니다.ter, $T_{\infty }$ T $T_{\infty }$ {\(\ $displaystyle$ T_ ${\infty$ })는 $T_{\infty }$ 무한 평행 ^{[note 2]}기계에서 필요한 시간인 스팬입니다.즉, 예상대로 소요 시간은 최대 상수 인자에 이론적 ^[2]최소값을 곱한 값입니다.단, 실행시간(특히 실행된 도루의 수)은 최악의 경우 T ^[10] ${\(\$ })로 $T_{\infty }$ 지수화될 수 있습니다.프로세서가 빈 시간에 자신의 작업을 훔치려고 하는 현지화된 변종도 이론적으로나 실제로 ^[11]^[12]분석되었습니다.

공간 사용

Blumofe에 의해 스케줄된 계산–리서슨 버전의 작업 도용은 O $O(S_{1}P)$ ( S $O(S_{1}P)$ P $O(S_{1}P)$ ) ( \ $displaystyle$ O ( $S$ _ { { $P$ ) }스택 공간을 $O(S_{1}P)$ 합니다. $S_{1}$ 1 ( \ $display style$ S _ { { $S_{1}$ } )이 $O(S_{1}P)$ $S_{1}$ 단일 ^[2]프로세서에서 동일한 계산을 스택으로 사용하는 경우, 공간 ^[13]효율성에 대한 저자의 초기 정의에 부합합니다.이 바인드에는 계속적인 도용이 필요합니다.다음 ^[8]예에서 알 수 있듯이 자녀 도용 스케줄러에서는 이 바인드는 유지되지 않습니다.

i = 0 ~ n의 경우: 포크 f(i)

자녀 도용 실장에서는 f에 대한 모든 "포크된" 콜이 작업 큐에 배치되며, 따라서 크기가 n으로 커지며, 임의로 커질 수 있습니다.

멀티프로그래밍 바리안트

앞서 설명한 작업 도용 알고리즘과 그 분석에서는 전용 프로세서 세트로 연산이 스케줄 되어 있는 컴퓨팅 환경을 상정하고 있습니다.멀티프로그래밍(멀티태스킹) 환경에서는 연산 태스크를 워커 스레드 풀로 스케줄 하도록 알고리즘을 변경해야 합니다.워크 스레드 풀은 오퍼레이팅시스템 스케줄러에 의해 실제 프로세서로 스케줄 됩니다.다른 프로세스가 나머지 프로세서를 사용하고 있을 가능성이 있기 때문에 OS 스케줄러는 언제든지 작업 도용 프로세스에 컴퓨터 내의 P $프로세서$ 중 몇 개 P $p A$ P를 할당합니다.이 설정에서는 P 워커 스레드 $풀$ 을 사용하여 작업을 훔치면 절도범으로 동작하는 워커가 라이브록의 원인이 될 수 있습니다.즉, 실제로 유용한 ^[14]^[15]작업을 생성하는 워커의 실행을 차단할 수 있습니다.

이 상황을 위해 예상 시간에 계산을 실행하는 다양한 작업 도둑질이 고안되었습니다.

O\left({\frac {T_{1}}) {P_{\mathrm {avg}}}}+{\frac {T_{\infty}P}{P_{\mathrm {avg}}}}}\right

$여기$ 서_avg P는 계산 실행 ^[16]시간 동안 OS 스케줄러에 의해 계산에 할당된 프로세서의 평균 수입니다.멀티프로그래밍 작업스케줄러는 두 가지 점에서 기존 버전과 다릅니다.

큐는 논블로킹입니다.전용 프로세서에서는 잠금을 사용하여 큐에 대한 액세스를 동기화할 수 있습니다.멀티프로그래밍 환경에서는 operating system이 잠금을 유지하는 워커 스레드를 프리엠프트하여 같은 큐에 액세스하려는 다른 워커의 진행을 차단할 수 있기 때문에 이는 권장되지 않습니다.
워크를 훔치려고 할 때마다 워커 스레드가 "유율" 시스템 호출을 호출하여 OS에 스케줄된 프로세서를 생성합니다.

멀티프로그래밍 작업스틸러를 개선하기 위한 시도는 캐시 인접성^[12] 문제와 큐 데이터 ^[17]구조 개선에 초점을 맞추고 있습니다.

대체 수단

동적 멀티스레드 연산을 위한 몇 가지 스케줄링 알고리즘은 작업 도용과 경쟁합니다.기존의 작업 공유 접근 방식 외에도,^[18] 병렬 깊이 우선(PDF)이라는 스케줄러가 있어 칩 멀티프로세서의 코어가 ^[1]캐시를 공유하는 경우에 더 나은 성능을 제공할 수 있습니다.

메모들

^ 원래 프레젠테이션에서는 직렬 연산이 노드로도 표현되었으며, 유도된 가장자리는 "뒤로" 관계를 나타냅니다.
^ 정의는 병렬 알고리즘 분석을 참조하십시오.

레퍼런스

^ ^a ^b Chen, Shimin; Gibbons, Phillip B.; Kozuch, Michael; Liaskovitis, Vasileios; Ailamaki, Anastassia; Blelloch, Guy E.; Falsafi, Babak; Fix, Limor; Hardavellas, Nikos; Mowry, Todd C.; Wilkerson, Chris (2007). Scheduling threads for constructive cache sharing on CMPs (PDF). Proc. ACM Symp. on Parallel Algorithms and Architectures. pp. 105–115.
^ ^a ^b ^c ^d ^e ^f Blumofe, Robert D.; Leiserson, Charles E. (1999). "Scheduling multithreaded computations by work stealing" (PDF). J ACM. 46 (5): 720–748. doi:10.1145/324133.324234. S2CID 5428476.
^ Blumofe, Robert D.; Joerg, Christopher F.; Kuszmaul, Bradley C.; Leiserson, Charles E.; Randall, Keith H.; Zhou, Yuli (1996). "Cilk: An efficient multithreaded runtime system". Journal of Parallel and Distributed Computing. 37 (1): 55–69. doi:10.1006/jpdc.1996.0107.
^ Doug Lea (2000). A Java fork/join framework (PDF). ACM Conf. on Java.
^ Leijen, Daan; Schulte, Wolfram; Burckhardt, Sebastian (2009). "The Design of a Task Parallel Library". ACM SIGPLAN Notices. 44 (10): 227. CiteSeerX 10.1.1.146.4197. doi:10.1145/1639949.1640106.
^ "What is Tokio? · Tokio". tokio.rs. Retrieved 2020-05-27.
^ Krill, Paul (2021-01-08). "Tokio Rust runtime reaches 1.0 status". InfoWorld. Retrieved 2021-12-26.
^ ^a ^b ^c ^d ^e Robison, Arch (15 January 2014). A Primer on Scheduling Fork–Join Parallelism with Work Stealing (PDF) (Technical report). ISO/IEC JTC 1/SC 22/WG 21—The C++ Standards Committee. N3872.
^ Halpern, Pablo (24 September 2012). Strict Fork–Join Parallelism (PDF) (Technical report). ISO/IEC JTC 1/SC 22/WG 21—The C++ Standards Committee. N3409=12-0099.
^ Leiserson, Charles E.; Schardl, Tao B.; Suksompong, Warut (2016). "Upper Bounds on Number of Steals in Rooted Trees". Theory of Computing Systems. 58 (2): 223–240. arXiv:1706.08219. doi:10.1007/s00224-015-9613-9. S2CID 424692.
^ Suksompong, Warut; Leiserson, Charles E.; Schardl, Tao B. (2016). "On the efficiency of localized work stealing". Information Processing Letters. 116 (2): 100–106. arXiv:1804.04773. doi:10.1016/j.ipl.2015.10.002. S2CID 1180480.
^ ^a ^b Acar, Umut A.; Blelloch, Guy E.; Blumofe, Robert D. (2002). "The Data Locality of Work Stealing" (PDF). Theory of Computing Systems. 35 (3): 321–347. CiteSeerX 10.1.1.19.3459. doi:10.1007/s00224-002-1057-3. S2CID 10235838.
^ Blumofe, Robert D.; Leiserson, Charles E. (1998). "Space-efficient scheduling of multithreaded computations". SIAM J. Comput. 27 (1): 202–229. CiteSeerX 10.1.1.48.9822. doi:10.1137/s0097539793259471.
^ Ding, Xiaoning; Wang, Kaibo; Gibbons, Phillip B.; Zhang, Xiaodong (2012). BWS: Balanced Work Stealing for Time-Sharing Multicores (PDF). EuroSys.
^ Blumofe, Robert D.; Papadopoulos, Dionisios (1998). The Performance of Work Stealing in Multiprogrammed Environments (Technical report). University of Texas at Austin, Department of Computer Sciences. CiteSeerX 10.1.1.48.2247.
^ Arora, Nimar S.; Blumofe, Robert D.; Plaxton, C. Greg (2001). "Thread scheduling for multiprogrammed multiprocessors" (PDF). Theory of Computing Systems. 34 (2): 115–144. doi:10.1007/s002240011004.
^ Chase, David R.; Lev, Yosef (2005). Dynamic Circular Work-Stealing Deque. ACM Symp. on Parallelism in Algorithms and Architectures. CiteSeerX 10.1.1.170.1097.
^ Blelloch, Guy E.; Gibbons, Phillip B.; Matias, Yossi (1999). "Provably efficient scheduling for languages with fine-grained parallelism" (PDF). Journal of the ACM. 46 (2): 281–321. CiteSeerX 10.1.1.48.8238. doi:10.1145/301970.301974. S2CID 47102937.

[10] 원래 프레젠테이션에서는 직렬 연산이 노드로도 표현되었으며, 유도된 가장자리는 "뒤로" 관계를 나타냅니다.

[11] 정의는 병렬 알고리즘 분석을 참조하십시오.

[dfs-1] Chen, Shimin; Gibbons, Phillip B.; Kozuch, Michael; Liaskovitis, Vasileios; Ailamaki, Anastassia; Blelloch, Guy E.; Falsafi, Babak; Fix, Limor; Hardavellas, Nikos; Mowry, Todd C.; Wilkerson, Chris (2007). Scheduling threads for constructive cache sharing on CMPs (PDF). Proc. ACM Symp. on Parallel Algorithms and Architectures. pp. 105–115.

[jacm-2] ^ ^a ^b ^c ^d ^e ^f Blumofe, Robert D.; Leiserson, Charles E. (1999). "Scheduling multithreaded computations by work stealing" (PDF). J ACM. 46 (5): 720–748. doi:10.1145/324133.324234. S2CID 5428476.

[3] Blumofe, Robert D.; Joerg, Christopher F.; Kuszmaul, Bradley C.; Leiserson, Charles E.; Randall, Keith H.; Zhou, Yuli (1996). "Cilk: An efficient multithreaded runtime system". Journal of Parallel and Distributed Computing. 37 (1): 55–69. doi:10.1006/jpdc.1996.0107.

[lea-4] Doug Lea (2000). A Java fork/join framework (PDF). ACM Conf. on Java.

[5] Leijen, Daan; Schulte, Wolfram; Burckhardt, Sebastian (2009). "The Design of a Task Parallel Library". ACM SIGPLAN Notices. 44 (10): 227. CiteSeerX 10.1.1.146.4197. doi:10.1145/1639949.1640106.

[6] "What is Tokio? · Tokio". tokio.rs. Retrieved 2020-05-27.

[7] Krill, Paul (2021-01-08). "Tokio Rust runtime reaches 1.0 status". InfoWorld. Retrieved 2021-12-26.

[primer-8] Robison, Arch (15 January 2014). A Primer on Scheduling Fork–Join Parallelism with Work Stealing (PDF) (Technical report). ISO/IEC JTC 1/SC 22/WG 21—The C++ Standards Committee. N3872.

[9] Halpern, Pablo (24 September 2012). Strict Fork–Join Parallelism (PDF) (Technical report). ISO/IEC JTC 1/SC 22/WG 21—The C++ Standards Committee. N3409=12-0099.

[12] Leiserson, Charles E.; Schardl, Tao B.; Suksompong, Warut (2016). "Upper Bounds on Number of Steals in Rooted Trees". Theory of Computing Systems. 58 (2): 223–240. arXiv:1706.08219. doi:10.1007/s00224-015-9613-9. S2CID 424692.

[13] Suksompong, Warut; Leiserson, Charles E.; Schardl, Tao B. (2016). "On the efficiency of localized work stealing". Information Processing Letters. 116 (2): 100–106. arXiv:1804.04773. doi:10.1016/j.ipl.2015.10.002. S2CID 1180480.

[local-14] Acar, Umut A.; Blelloch, Guy E.; Blumofe, Robert D. (2002). "The Data Locality of Work Stealing" (PDF). Theory of Computing Systems. 35 (3): 321–347. CiteSeerX 10.1.1.19.3459. doi:10.1007/s00224-002-1057-3. S2CID 10235838.

[15] Blumofe, Robert D.; Leiserson, Charles E. (1998). "Space-efficient scheduling of multithreaded computations". SIAM J. Comput. 27 (1): 202–229. CiteSeerX 10.1.1.48.9822. doi:10.1137/s0097539793259471.

[16] Ding, Xiaoning; Wang, Kaibo; Gibbons, Phillip B.; Zhang, Xiaodong (2012). BWS: Balanced Work Stealing for Time-Sharing Multicores (PDF). EuroSys.

[17] Blumofe, Robert D.; Papadopoulos, Dionisios (1998). The Performance of Work Stealing in Multiprogrammed Environments (Technical report). University of Texas at Austin, Department of Computer Sciences. CiteSeerX 10.1.1.48.2247.

[arora-18] Arora, Nimar S.; Blumofe, Robert D.; Plaxton, C. Greg (2001). "Thread scheduling for multiprogrammed multiprocessors" (PDF). Theory of Computing Systems. 34 (2): 115–144. doi:10.1007/s002240011004.

[19] Chase, David R.; Lev, Yosef (2005). Dynamic Circular Work-Stealing Deque. ACM Symp. on Parallelism in Algorithms and Architectures. CiteSeerX 10.1.1.170.1097.

[20] Blelloch, Guy E.; Gibbons, Phillip B.; Matias, Yossi (1999). "Provably efficient scheduling for languages with fine-grained parallelism" (PDF). Journal of the ACM. 46 (2): 281–321. CiteSeerX 10.1.1.48.8238. doi:10.1145/301970.301974. S2CID 47102937.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[note 1]

[note 2]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Search