The Cilk Runtime System

[MIT OpenCourseWare] The Cilk Runtime System

 

 

https://youtu.be/Z7r4aAZ9Vqo?si=MdOHE_hw456cZ4nE

 

The Cilk Runtime System

P개의 프로세서에서, Tp <= Ts 시간으로 실행 가능.

 

- Cilk 스케줄러는 실행중인 프로그램을 프로세서 코어에 런타임에 동적으로 매핑시켜줌.

- Cilk의 work-stealing 스케줄링 알고리즘은 효율적임이 입증됨.

 

 

핵심

1) scheduling

2) load balancing

 

- Required Functionality

- Performance Considerations

- Implementating a Worker Deque

- Spawning Computation

- Stealing Computation

- Synchronizing Computation

Required Functionality

The computation dag unfolds dynamically. (computation dag : directed acyclic graph - 유향 비순환 그래프를 의미하는듯?)

computation dag는 동적으로 전개됨.

 

Serial Execution의 예시를 보자.

우리가 잘아는 일반적인 피보나치 수열을 재귀 방식으로 호출한다.

 

(1) 고려해야 할 첫번째 :

a single worker must be able to execute the computation on its own similarly to an ordinary serial computation.

싱글 워커는 일반적인 직렬 연산과 마찬가지로 자체적으로 연산을 수행할 수 있어야 함.

 

이제, Parall Execution은 어떨까?

여기서 주목해야할 점은, 다른 프로세서가 맡은 일감이 없어 지루하니 "다른 프로세서가 할 일"을 훔쳐(Steal)오는 것이다.

P2가 fib(4)에 있는 초록색 가닥(green strand) 부분을 들어가서 실행한다고 가정해보자.

여기서 생각해봐야할 것은, P2는 또 다른 프로세서이므로 자체적인 "레지스터"와 "Instruction Pointer"를 갖고있다.

위 슬라이드를 보면, P1은 'x = cil_spawn fib(n-1);'을 타고 base case까지 도달하게 되는 동안, P2, P3는 그 다음 명령어인 'y = fib(n-2)'에 대한 instruction pointer를 강제로 지정하게 하여 P1의 일감을 Steal하게 되는 것이다.

 

Q) How does a processor start executing in the middle of a running function?

지금 하려는 짓이... 이게 가능한걸까?, 실행 중인 함수의 중간을 다른 프로세서가 가로채서 실행하는 것이 가능한건가?

A) 'y = fib(n-2)'는 원래 P1가 실행해야할 Instruction이다. 하지만 P2에게 '적절한 파라미터', 즉 Instruction Pointer, Register 같은 파라미터들을 P1이 실행할 때와 동일하게 세팅하면 Serial Execution인 것처럼 동작하게 될 것임.

 

(2) 여기서 고려해야할 두번째는, 다른 프로세서가 실행 중인 함수의 중간 부분에 대한 Instruction Pointer 등의 상태를 어떻게든 찾아서 실행시키는 방법이다.

P3가 cilk_snyc를 만난 시점에서, 해당 함수는 본래 P1가 실행하던 것이므로 P1가 해당 함수를 끝내도록 '대기'해야 한다. 

(3) 고려해야할 세번째 : cilk_sync는 'nested subcomputaions'에서 어떻게 기다리죠? 이걸 어떻게 구현해야 하죠?

 

1) a single worker must be able to execute the computation on its own similarly to an ordinary serial computation.

- 싱글 워커는 일반적인 직렬 연산처럼 자체적으로 연산을 실행할 수 있어야 함.

2) A thief must be able to jump into the middle of an executing function to steal a continuation.

- 도둑(thief)은 실행 중인 함수의 중간에 뛰어들어 continuation(연결되는 실행 흐름?)을 가로챌 수 있어야 함.

3) A sync must stall a function's execution until child subcomputations complete.

- 동기화(sync)는 하위 연산이 완료될 때까지 함수의 실행을 일시 중단해야 함.

 

Q) Cilk를 구현하는데 필요한 또 다른 기능이 있을까요?

 

A1) cilk_for 를 구현하기 위해 분할 정복(divide_and_conquer) 사용?

Q1) cilk_for는 내부적으로 cilk_spawn, cilk_sync로 구현되어 있는데, 이건 컴파일러가 해야할 일입니다.

 

A2) cache coherence?

Q2) 하드웨어가 갖는 캐시 일관성 프로토콜만으로도 캐시 일관성은 꽤나 잘 유지한다는 것이 밝혀져 있습니다. 따라서 소프트웨어적인 구현은 불필요합니다.

 

Q) 힌트는 지난 강의에서 배운 것에 전부 포함되어 있습니다.

Cilk는 C의 포인터 규칙을 지원하는데, 다음과 같다.

스택 영역을 가리키는 포인터는 부모(Caller)→자식(Callee) 전달은 가능하지만, 반대로 자식(Callee)→부모(Caller) 전달은 불가능. 다시 말해서, children은 parent frame에 대한 포인터를 볼 수 있지만, 반대로 parent는 child frame에 대한 포인터를 볼 수 없음.

 

위 이미지에서, 5개의 프로세서(워커)들은 함수 A(즉, Instantiation A)의 스택에 대해 동일한 뷰를 공유한다. 그리고, P3~P5는 Instantiation C의 스택에 대해 동일한 뷰를 공유한다.

(4) 고려해야 할 네번째 : Cilk는 여러 개의 워커가 스택에 대한 동일한 뷰를 갖도록, 즉 일관성을 갖게 하는 Cactus Stack을 구현해야 한다!

each worker maintains a work deque of ready strands, and it manipulates the bottom of the deque like a stack.

각각의 워커는 ready stands로 구성된 work deque을 유지하며, deque을 스택처럼 조작함.

 

Each deque contains a mixture of spawned frames and called frames.

각각의 deque에는 spawn된 프레임과 호출된 프레임이 혼합되어 있음.

When a worker runs out of work, it steals from the top of a random victim's deque.

한 worker의 일감이 다 떨어져 놀고 있으면, 랜덤으로 선택된 victim's deque의 top에서 일감을 훔쳐감.

 

Q) 의문 + 다섯번째 고려해야 할 사항 : thief는 (called + spawned) deque을 어떻게 다뤄야 하는지?

- What is involved in stealing frames?

프레임을 훔치는데에는 어떤 과정이 포함되는지?

- What synchronization is needed?

동기화가 필요한지?

- What happens to the stack?

스택에는 어떤 일이 발생하는지?

→ 스택을 빼앗긴 victim은 여전히 해당 스택 데이터에 접근할 수 있어야 함.

- How efficient can this be?

이러한 방법이 얼마나 효율적일지?

1) A single worker must be able to execute the computation on its own similarly to an ordinary serial computation.

- 싱글 워커는 일반적인 직렬 연산처럼 자체적으로 연산을 수행할 수 있어야 함.

2) A thief must be able to jump into the middle of an executing function to steal a continuation.

- Thief는 실행 중인 함수의 중간에 뛰어들어 continuation을 가로챌 수 있어야 함.

3) A sync must stall a function’s execution until child subcomputations complete.

- Sync는 자식 하위 연산이 완료될 때까지 함수의 실행을 정지시켜야 함.

4) The runtime must implement a cactus stack for its parallel workers.

cilck runtime은 parallel workers를 위해 Cactus Stack을 구현해야 함.

5) Thieves must be able to handle mixtures of called spawned functions.

- Thieves는 훔칠 때, 호출된 함수와 생성된 함수가 혼합된 상황을 처리할 수 있어야 함.

Performance Considerations

Cilk의 work-stealing scheduler의 실행 시간 Tp는, 다음과 같음

 

P개의 워커들이 일감을 잘 나누어 갖고, stealing하는데 걸리는 시간에 많이 영향받음을 알 수 있음.

 

이상적으로, Serial running Time이 Ts라면 P개의 워커들이 나눠서 일했을 때 Tp = Ts / P에 근접해야 한다.

Ample parallelism : T1 / T∞ >> P

→ 아직 이해가 잘 안감. (Parallel Storage Allocation에서 한 번 언급했었다고함)

 

Cilk Runtime System은 뛰어난 병렬성을 기반한 최적화로 작업 효율을 갖추기 위해 다음과 같은 1원칙을 준수함.

Optimize for the ordinary serial execution, at the expense of some additional computation in steals.
일반적인 직렬 실행을 최적화하되, steal 과정에서 약간의 추가 계산 비용을 감수한다.

 

 

1원칙은 Cilk runtime system을 컴파일러와 런타임 라이브러리에 작업을 분할하도록 안내함.

 

Compiler

- 소량의 작은 자료구조 사용, e.g : workers, stack frames

- steal이 발생하지 않을 때 함수 실행을 위한 최적화된 빠른 경로(fast path)를 구현

 

Runtime Library

- 더 큰 자료 구조 사용

- steal이 발생할 때 함수 실행을 위한 느린 경로(slow path) 운용.

Implementing a Worker Deque

Fib 예제보다 더 간단한 예제.

이후에 다시 볼 예정.

Q) How de we implement a worker's deque?

 

- The worker should operate its own deque like a stack.

- A steal needs to transfer ownership of several consecutive frames to a thief.

- A thief needs to be able to resume a continuation.

가장 핵심에 해당되는 슬라이드.

Worker에선 Deque의 head / tail에 대한 포인터를 들고 있고,

Deque에서는 각각의 element안에 frame을 steal하기 위한 필수 정보들을 저장하고 있음.

 

Woker → Deque → stolen frame 

Intel Cilk Plus runtime system은 아이디어를 다음과 같이 정교화했음.

- every spawned subcomputation은 자체적인 spawn-helper 함수내에서 실행됨.

- runtime system은 워커가 작업을 실행하는 동안, 3개의 기본 자료구조를 가짐.

-- a worker structure for every worker used to execute the program.

-- a cilk stack-frame structure for each instantiation of a spawning function.

-- a spawn-helper stack frame for each instantiaion of a cilk_spawn.

→ 이전 슬라이드의 그림 구조와 유사하다고 생각하면 된다.

 

 

Cilk Compiller가 Cilk stack-frame 구조체를 local variable 형태로 생성함.

 

Cilk Stack Frame에는 어떤게 있을까?

1) Context Buffer, ctx

cilk_spawn, cilk_sync 호출 이후에 함수를 재개하기 위한 정보들을 포함.

→ 다시 말해서, 강의 초반부에 다른 Worker가 일감을 Steal해서 대신 실행시킬려면, register / instruction pointer같은 정보도 가져와야 한다고 했으므로 여기에 해당된다고 생각해보자.

 

2) Cilk stack frame의 상태를 요약하는 integer, flags

 

3) parent stack frame에 대한 포인터

- 이후에 다시 알아볼 예정

Cilk worker는 Deque의 head, tail에 대한 포인터 뿐만 아니라, current_sf(현재 스택프레임 - Cilk RTS stack frame)에 대한 포인터도 유지.

→ 보통 스택의 바닥 근처 쯤에 있음?

Spawning Computation

Code for a "Spawning Function"

 

1) Create and intialize a Cilk stack-frame structure.

2) Prepare to spawn.

3) Invoke the spawn helper.

4) Clean up the Cilk stack-frame structure.

5) Clean up the deque.

Code for a "Spawn Helper"

- spawn_bar() 내부 구조

 

1) Create and initialize a Cilk stack-frame structure.

2) Update the deque to allow the parent to be stolen.

- deque에 대한 업데이트

3) Invoke the spawned subroutine.

4) Clean up the Cilk stack-frame structure.

5) Clean up the deque and attempt to return.

 

Cilk worker가 해야할 일은 current_sf을 foo_sf으로 가리키는 것이 전부이다. ↓

 

setjmp 함수는 함수를 재개할 수 있도록 sf.ctx에 필요한 정보를 저장.

 

Q) 어떤 정보가 저장되어야 할까?

A) Instruction Pointer, Stack Pointer

 

Q) 또 다른 정보는?

A) Register?

 

Q) 모든 Register가 저장되어야 할까?

A) Callee-saved registers.

이것을 저장해야 하는 것은 'foo' 함수의 책임에 해당.

→ 여기의 Q&A 내용이 이후 "longjmp" 슬라이드에서 재언급되므로 기억해두자.

 

Spawning a Function

좌측 : 함수가 호출될 때

우측 : Cilk worker의 각 포인터가 어디를 가리키는지, Call Stack 상태는 어떤지 잘 보자

1) spawn_bar(&x, n);

 

2) __cilkrts_enter_frame_fast(&sf);

스택에 새로운 Cilk RTS stack frame을 갖게 되면, 어떤 것이 변화되는 걸까?

1) 현재 stack frame이 spawn_bar's stack frame을 가리킴. (serial system에서 기본적으로 해당)

2) 부모 스택프레임에 대한 포인터 (spawn_bar_sf → foo_sf)

3) woker's current_sf이 spawn_bar_sf를 가리키도록 설정.

 

Q) __cilkrts_enter_frame_fast(&sf)는 부모 스택프레임이 무엇인지 어떻게 알 수 있나요?

A) Enter frame은 worker를 알고 있음, 또는 Cilk worker structure가 접근할 수 있도록 call? 가능.

 

★ : 위 이미지에서, 빨간색 화살표가 Before, 검정색 화살표가 After에 해당.

3) __cilkrts_detach();

__cilkrts_detach()는 일부 계산 작업이 도난당할 수 있도록 허용하는 함수.

해당 함수 실행이 완료되면, thief는 다가와서 cilk_spawn의 continuation을 훔칠 수 있게 됨.

 

Q) 그럼, __cilkrts_detach()가 본질적으로 하는 일이 뭘까요?

A) parent - foo's stack frame을 Deque's tail에  push.

따라서, tail pointer를 한 칸 전진.

4) *x = bar(n);

여기엔 serial execution과 동일.

여기선 stack frame으로부터 bar 제거가 끝.

 

5) __cilkrts_pop_frame(&sf);

__cilkrts_pop_frame(*sf)는 stack frame structure를 정리하는 동작.

 

Q) 이후에 어떤 작업을 추가로 진행할까?

A) 현재 stack frame을 parent stack frame으로 이동.

+ parent stack frame을 가리키던 것은 더 이상 필요없으므로 제거.

FYI) 추가적으로 메모리를 garbage로 만듦? (#)

6) __cilkrts_leave_frame(&sf);

May or may not return, depending on what's in the worker's deque.

- worker's deque에 뭐가 들어있냐에 따라 리턴 유무가 갈림.

Q) May or may not return?

GUESS) 강의 초반에, Fibonacchi 예제를 들면서 훔친 일감을 대신 실행했을 때, 마지막 리턴되기전에 일감의 원래 주인의 실행이 끝날 때까지 대기해야한다는 언급이 있었다. 아마 그 부분을 말하는 것이 아닐까?

 

A) There's nothing else for the worker to do, so it'll sit there spinning until there's work you can steal?

→ If there's nothing on the Deque, then it has nowhere to return do.

Deque이 비어있으므로, 즉 Worker가 할 일이 없으므로 리턴할 곳이 없어 대기해야 함.

__cilkrts_leave_frame에서, worker는 Deque's tail로부터 stack frame을 pop하려고 시도하는데 다음과 같은 2가지 경우가 존재함.

1) pop이 성공하면, 평소와 같이 계속 진행.

2) pop이 실패하면, worker는 할 일이 떨어진 상황. 그러므로 thief가 되어 random victim's deque의 top으로부터 일감을 훔쳐오는 것을 시도.

 

Q) 위 2가지 케이스 중 어떤 경우가 최적화 중요도가 더 높을까요?

A) Case 1.

 

we assume that in the common case, workers are doing useful work, they're not just spending their time stealing from each other. And therefore, ideally, we want to assume that the worker will do what's normal, just an ordinary serial execution. In a normal serial execution, there is something on the deque, the pop succeeds, that's case one. So what we'll see is that the runtime system, in fact, does a little bit of optimization on case one.

일반적인 경우 worker는 유용한 작업을 수행하고 서로의 작업을 훔치면서 시간을 낭비하지 않는다고 가정합니다. 따라서 이상적으로는 worker가 ordinary serial execution을 수행할 것이라고 가정하고 싶습니다. normal serial execution에서는 Deque에 무언가가 있고, Pop이 성공합니다. 이것이 첫 번째 경우입니다. 따라서 런타임 시스템은 실제로 첫 번째 경우에 대해 약간의 최적화를 수행합니다.

 

이전 슬라이드 질문

Q) 6) __cilkrts_leave_frame(&sf); 쯤에서요, 결과를 return 한다는 건 어디에 return 한다는 건가요?

A) so the original Cilk code, we had X equals Cilk spawn_bar. That's the same X. All that Cilk does is pass a pointer to the memory allocated for that variable down to the spawn helper. And now the spawn helper, when it calls bar and that returns, it gets stored into that storage in the parent stack frame. Good catch. Good observation

원래 Cilk 코드에서는 x = Cilk_spawn bar(n)라고 되어 있었죠. 그 x는 동일한겁니다. Cilk는 그 변수에 할당된 메모리 영역에 대한 포인터를 spawn 헬퍼 함수로 전달할 뿐입니다. 그리고 spawn 헬퍼 함수가 bar를 호출하고 그 결과가 반환되면, 그 값은 부모 스택 프레임의 해당 메모리 영역에 저장됩니다. 잘 찾아내셨네요. 좋은 관찰입니다.

→ spawn_bar 함수내에서 *x = bar(n); 같이 argument로 전달된 포인터 x에 메모리를 할당한 주소를 넘기는 부분이 있다. 이건 원래의 Cilk_spawn 헬퍼 함수에서 리턴했을 때 x에 주소를 저장하는 해당 코드와 매치되는 것이다.

 

→ 우리가 여태 계속 봐온 setjmp라던가, spawn_bar()는 Clik_spawn 같은 헬퍼 함수가 c언어레벨에서 어떻게 구현되어있는지 내부 구현을 이해하기 위한 것이었음 !

Stealing a Frame 상황을 Thief, Victim 관점에서 자세하게 살펴보자.Before : 빨간색 화살표 → After : 검정색 화살표 

 

Victim's Deque으로부터 head를 dequeue한 뒤, 얻은 포인터를 Thief's current sf가 가리키도록 변경. 따라서 Deque의 Top element에 있던 포인터 삭제.

 

★ Victim, Thief는 현재 다른 프로세서에 있음. 따라서, Deque의 head에서 발생하는 일들에 대해서 "concurrent"하게 다뤄야 함.→ Synchronization을 보장해야한다는 것인데, 일반적으로 이 비용은 비싸고, 머리 아픈일임.

Dequeue Access에 대한 concurrent handling은 THE protocol을 사용함.

 

여기서는 THE protocol에 대한 high-level view만 설명.1) The thief always grabs a lock before operating on the deque.- Thief는 deque에 대한 모든 접근은 항상 deque에 대해 Lock을 잡는 것이 선행되어야 함.

 

2) The worker pops the deque optimistically.Worker는 thief보다 좀 더 최적화되어 있는데, 우선 낙관적으로 pop 성공할 것이라 가정하고 pop operation을 수행한다. 이후 실패 유무를 확인하여 실패한 경우 더 복잡한 작업을 수행함.→ 복잡한 작업이라 함은, lock을 잡고 한 번 더 시도한 뒤 '진짜 성공했는지' 다시 확인하는 것이다. 만약 또 실패하면 pop이 불가능하니 다른 worker의 일감을 훔쳐올 수도 있는 것 같다(강의에선 "see if it really succeeds or fails, and possibly turn to a life of crime" 이라고 축약하여 표현한 것을 필자가 임의로 해석함).

 

3) The worker only grabs a lock if the deque appears to be empty.

(2)에서 이어지는 내용인데, 강의에선 high-level view만 설명했으나 위 worker protocol을 전부 해석하려면 부가 설명이 필요하다.

 

부가 설명

우선 전제조건으로 알아야할 것이 있다.- tail은 worker(victim)만 접근하고, head는 thief만 접근하므로 해당 연산에 대한 동기화가 필요없다. 즉, 동기화없이 조건부 lock-free다.조건부라는 것은 어떤 의미일까? pop() 함수내에서, if (head > tail) 이 성립하는 경우는 2가지가 존재한다.1) deque이 비어있는 경우- head, tail이 교차하게 되므로 실패를 반환해야 한다.2) element가 1개인 경우, victim과 thief가 동시에 해당 element를 가져가려고 하는 경우 (충돌)

 

RECALL : Popping the Deque 슬라이드의 Case 1.

Worker protocol이 더 길어보이는 것은 worker는 일반화된 경우에 대해 최적화된 special case를 구현하기 때문.

→ 이전에 보았던 __cilkrts_leave_frame에서, 'Case 1 - pop form the deque succeeding' 에 대해 최적화 된 것.

★ : 이전에, setjmp() 함수를 통해서 foo's stackframe(foo_sf.ctx)에 일부 상태를 저장했었음(instruction pointer, stack pointer, callee-saved register).

thief는 저장했던 것을 꺼내서 현재의 register, instruction pointer등으로 설정하고 해당 일감을 실행해야 함. 즉, "resume a stolen continuation".

 

thief needs to resume a continuation. And this is that whole process about jumping into the middle of an executing function. It already has a frame, it already has a bunch of state going on, and all that was established by a different processor. So somehow that thief has to magically come up with the right state and start executing that function. How does that happen? Well, this has to do with a routine that's the complement of the set jump routine we saw before. The complement of set jump is what's called long jump.
So Cilk uses, in particular Cilk thieves, use the long jump function in order to resume a stolen continuation. Previously, in our spawning function foo, we had this set jump call. And that set jump saved some state to a local buffer, in particular the buffer in the stack frame of foo. 

Now the thief has just created this Cilk worker structure, where the current stack frame is pointing at the stack frame of foo. And so what the thief will do is it'll execute a call, it'll execute the statement, it will execute the long jump function, passing that particular stack frame's buffer and an additional argument, and that long jump will take the registered state stored in the buffer, put that registered state into the worker, and then let the worker proceed.

This is kind of a wacky routine because, if you remember, one of the registers stored in that buffer is an instruction pointer. And so it's going to read the instruction pointer out of the buffer. It's also going to read a bunch of callee-saved registers and stack pointers out of the buffer. And it is going to say, that's my register state now, that's what the thief says. It just stole that register state. And it's going to set its RAP to be the RAP it just read.

 

thief는 실행 중인 함수의 중간으로 점프해야 합니다. 이미 프레임이 있고, 여러 상태가 저장되어 있으며, 이 모든 것은 다른 프로세서에 의해 설정된 것입니다. 따라서 thief는 어떻게든 올바른 상태를 찾아내고 함수 실행을 시작해야 합니다. 어떻게 가능할까요? 이는 이전에 살펴본 set jump 루틴의 complement routine과 관련이 있습니다. set jump의 complement routine이 바로 long jump입니다.

따라서 Cilk thief는 훔친 실행을 재개하기 위해 long jump 함수를 사용합니다. 앞서 생성 함수 foo에서 set jump 호출을 했습니다. 이 set jump는 일부 상태를 로컬 버퍼, 특히 foo의 스택 프레임에 있는 버퍼에 저장했습니다.

이제 thief는 현재 스택 프레임이 foo의 스택 프레임을 가리키도록 하는 Cilk worker structure를 생성했습니다. 그래서 thief는 함수 호출을 실행하고, 명령문을 실행하고, 특정 스택 프레임의 버퍼와 추가 argument를 전달하는 long jump 함수를 실행합니다. 이 long jump 함수는 버퍼에 저장된 레지스터 상태를 가져와 worker에 전달한 다음 worker가 계속 진행하도록 합니다.

 

이 루틴은 좀 특이한데, 기억하시겠지만 버퍼에 저장된 레지스터 중 하나가 instruction pointer이기 때문입니다. 그래서 버퍼에서 instruction pointer를 읽어옵니다. 또한 호출된 함수가 저장한 여러 레지스터와 stack pointer도 읽어옵니다. 그리고 "이게 내 레지스터 상태야"라고 말합니다. thief가 방금 레지스터 상태를 훔쳤다는 뜻이죠. 그리고 방금 읽어온 레지스터 상태를 자신의 RAP에 설정합니다.

 

Q) So what does that mean for where the long jump routine returns?

- 'long jump' 루틴이 반환하는 곳은 어떤 의미가 있을까요?

 

A) 방금 언급했던 longjump 함수 호출시 전달했던 2nd argument 값을 반환하게 됨.

setjump() 당시에는 worker의 state, 즉 instruction pointer, stack pointer, callee-saved register 값을 성공적으로 저장했을 때 0을 리턴하면서 if statement가 통과되고, spawn_bar가 정상적으로 호출되게끔함. longjump() 함수가 정상 호출되면 1을 리턴함으로써 spawn_bar가 호출되지 않고 그 다음 명령어를 실행하도록 if statement를 조절하게 되는 것.

 

Q) Is there any reason you couldn't just add some fixed offset to the instruction pointer to jump over the call?

longjmp()를 호출할 때 instruction pointer에 들어갈 주소 값을 fixed offset, 즉 정적으로 계산해서 바로 넣을 수는 없나요?

 

A) In principle, if you can statically compute the distance you need to jump, then you can just add that to RIP and let the long jump do its thing. Or rather, the thief will just adopt that RIP and end up in the right place. What's done here is basically, this was the protocol that the existing set jump and long jump routines implement. And I imagine it's a bit more flexible of a protocol than what you strictly need for the Cilk runtime. And so, you know, it ends up working out. But if you can statically compute that offset, there's no reason in principle you couldn't adopt a different approach. So, good observation.

원칙적으로, 점프해야 할 거리를 정적으로 계산할 수 있다면, 그 값을 RIP에 추가하고 long jump 루틴이 알아서 처리하도록 하면 됩니다. 다시 말해, thief가 그 RIP를 adopt해서 결국 정확한 위치에 도달하게 되는 거죠. 여기서 사용된 방식은 기본적으로 기존의 setjmp() 및 longjmp() 루틴에서 구현하는 프로토콜과 동일합니다. 그리고 이 프로토콜은 Cilk runtime에 필요한 것보다 조금 더 유연하다고 생각합니다. 그래서 결과적으로는 잘 작동하는 거죠. 하지만 offset을 정적으로 계산할 수 있다면, 원칙적으로 다른 접근 방식을 채택하지 못할 이유는 없습니다. 좋은 관찰입니다.

 

It's fine to be generally confused why their routines, set jump and long jump, with this wacky behavior. Compiler writers have that reaction all the time. These are a nightmare to compile.

setjmp()와 longjmp() 같은 루틴들이 왜 이렇게 이상한 동작을 하는지 이해가 안 가는 건 당연합니다. 컴파일러 개발자들도 늘 그런 반응을 보이니까요. 이런 루틴들은 컴파일하기엔 악몽입니다.

 

정리

So we've seen how a thief can take some computation off of a victim's deque, and we've seen how the thief can jump right into the middle of an executing function with the appropriate register state.

지금까지 우리는 thief가 victim의 deque에서 일부 연산을 빼돌리는 방법과 적절한 레지스터 상태를 이용하여 실행 중인 함수의 중간으로 바로 진입하는 방법을 살펴보았음.

 

이전 victim's deque을 조작하는 방법과 register 값을 저장 및 복원하여 다른 프로세서의 함수에 난입하여 실행하는 방법을 알아봤다. 사실 어떤 함수를 실행 중이라는 것을 나타내기 위해서 register 값뿐만 아니라 한 가지가 더 필요한데, 바로 이전에 언급한적이 있었던 cactus stack이 해당된다.

→ Cilk runtime system을 위한 cactus stack abstraction을 구현해야 한다.

 

Q) Cactus Stack이 필요한 이유는 뭘까? thief가 victim's deque을 사용하여 baz 함수를 호출할 때 어떤 문제가 있는걸까?

A)

The victim in this picture, for example, has some other functions on its stack below foo. So if the thief does any function calls and is using the same stack, it's going to scribble all over the state of, in this case spawn bar, and bar, which the victim is trying to use and maintain. So the thief will end up corrupting the victim stack. And if you think about it, it's also possible for the victim to call the thief stack. They can't share a stack, but they do want to share some amount of data on the stack. They do both care about the state of foo, and that needs to be consistent across all the workers. 

But we at least need a separate call stack for the thief. We'd rather not do unnecessary work in order to initialize this call stack, however. We really need this call stack for things that the thief might invoke, local variables the thief might need, or functions that the thief might call or spawn.

예를 들어, 위 그림에서 victim은 foo 아래에 다른 함수들을 스택에 가지고 있습니다. 따라서 도둑이 같은 스택을 사용하여 함수를 호출하면, 피해자가 사용하고 유지하려는 spawn bar와 bar 함수의 상태를 엉망으로 만들어 버리게 됩니다. 결국 도둑은 피해자의 스택을 손상시키게 되는 것입니다. 생각해 보면, 피해자가 도둑의 스택을 호출하는 것도 가능합니다. 스택 자체를 공유할 수는 없지만, 스택에 있는 데이터는 어느 정도 공유해야 합니다. 둘 다 foo 함수의 상태에 관심을 갖고 있으며, 이 상태는 모든 워커에서 일관성을 유지해야 합니다. 따라서 적어도 도둑을 위한 별도의 호출 스택이 필요합니다. 하지만 이 호출 스택을 초기화하는 데 불필요한 작업을 하고 싶지는 않습니다. 이 호출 스택은 도둑이 호출할 수 있는 함수, 도둑이 필요로 하는 지역 변수, 또는 도둑이 호출하거나 생성할 함수들을 위해 필요합니다. 

So how do we implement the cactus stack? We have a victim stack, we have a thief stack, and we have a pretty cute trick, in my opinion. So the thief steals its continuation. It's going to do a little bit of magic with its stack pointers.

그렇다면 cactus stack은 어떻게 구현할까요? victim stack과 thief stack이 있고, 제 생각엔 꽤 기발한 트릭이 하나 있습니다. thief 스택이 victim's continuation을 훔칩니다. 그리고 스택 포인터를 가지고 약간의 마법을 부릴 겁니다.

1)

What it's going to do is it's going to use the RBP it was given, which points out the victim stack, and it's going to set the stack pointer to point at its own stack. So RBP is over there, and RSP for the thief, is pointing to the beginning of the thief's call stack. And that is basically fine. The thief can access all the state in the function foo, as offsets from RBP, but if the thief needs to do any function calls, we have a calling convention that involves saving RBP and updating RSP in order to execute the call.

주어진 RBP를 사용하여 victim의 스택을 가리키도록 하고, 스택 포인터를 자신의 스택을 가리키도록 설정합니다. 따라서 RBP는 저기(foo)에 있고, thief의 RSP는 thief의 호출 스택 시작 부분을 가리키게 됩니다. 기본적으로는 문제가 없습니다. thief는 RBP에서 offset을 통해 함수 foo의 모든 상태에 접근할 수 있지만, 만약 thief가 함수 호출이 필요한 경우에는 RBP를 저장하고 RSP를 업데이트하여 호출을 실행하는 calling convention(호출 규약)이 있습니다.

2)

So in particular, the thief calls the function baz, it saves its current value of RBP onto its own stack.

예를 들어, thief가 함수 baz를 호출하면 현재 RBP 값을 thief 자신의 스택에 저장하고,

it advances RSP, it says RBP equals RSP, 

RSP를 증가시키면, RBP가 RSP와 같아집니다. 

3)

it pushes the stack frame for baz onto the stack, and it advances RSP a little bit further. And just like that, the thief is churning away on its own stack. So just with this magic of RBP pointing there and RSP pointing here, we got our cactus stack.

그런 다음 baz 함수의 스택 프레임을 스택에 푸시하고, RSP를 조금 더 증가시킵니다(여기까지 해서 위 이미지와 동일한 상태가 됨). 이렇게 해서 thief는 자신의 스택에서 작업을 자유롭게 처리할 수 있게 됩니다. RBP가 저기를 가리키고 RSP가 여기를 가리키는 이 마법 같은 조합으로 Cactus Stack을 만들 수 있습니다.

 

Q) 컴파일러 최적화가 RBP, RSP를 사용하는 야매를 해칠 수 있지 않나요?

A)  there was a compiler optimization that said, in certain cases you don't need both the base pointer and the stack pointer. You can do all offsets. I think it's actually off the stack pointer, and then the base pointer becomes an additional general purpose register. That optimization clearly does not work if you need the base pointer stack pointer to do this wacky trick. The answer is that the Cilk compiler specifically says, if this function has a continuation that could be stolen, don't do that optimization. It's super illegal, it's very bad, don't do the optimization. So that ends up being the answer. And it costs us a general purpose register for Cilk functions, not the biggest loss in the world,

컴파일러 최적화 기능 중에 특정 경우에는 RBP와 RSP 둘 다 필요하지 않고 offset만으로 사용할 수 있다는 내용이 있었습니다. 스택 포인터만 사용하면 되고, 베이스 포인터는 추가적인 general purpose register(범용 레지스터)가 되는 거죠. 베이스 포인터와 스택 포인터가 모두 필요한 경우에는 이 최적화가 제대로 작동하지 않습니다. Cilk 컴파일러는 함수에 '도난당할 수 있는 continuation'이 있는 경우, 해당 최적화를 수행하지 말라고 명시적으로 지시합니다. 이는 매우 위험하고 나쁜 동작이므로 최적화를 하지 않는 것이 좋다고 지시합니다. 결국 이것이 답입니다. Cilk 함수를 위해 general purpose register 하나를 희생해야 하지만, 하늘이 무너질 만큼 큰 손실은 아닙니다.

Synchronizing Computation

강의 초반에서 언급했듯이, P3가 cilk_sync를 만나게 되어도 P1이 subcomputation을 끝낼 때 까지 기다려야 한다.

cilk_sync은 thief인 P3가 아닌 원래 주인인 P1이 실행함으로써 동기화가 이루어져야 한다.

 

worker는 모든 spwned subcomputations가 완료되기 전에 cilk_sync에 도달했을 때, 놀고 있으면 낭비이기 때문에 thief가 되어야 하지만, worker의 현재 함수 프레임은 사라지지 말아야 한다 !

- 기존 subcomputations은 부모 프레임의 상태에 접근할 수 있음.

- 미래에, 또 다른 worker가 프레임을 재개하고 cilk_sync를 실행해야 함.

- cilk_sync는 프레임의 'nested subcomputations'에만 적용되며, 모든 subcomputations 또는 workers에 적용되는 것은 아님.

 

남색은 현재 실행 중인 프레임

하늘색은 suspended frame

 

thief는 full frame을 훔치고 victim을 위한 새로운 full frame을 생성.

 

 full frame을 훔침으로써, parent full frame에 대한 포인터는 보존됨.

만약 full frame을 생성하지 않았다면, parent full frame에 대한 포인터는 보존되지 않으므로 복잡한 작업을 추가해야 한다고 함, - child측에서 뭔가를 해줘야 한다고 함?

 

child subcomputation이 실행 중이므로 sync할 수 없어 suspended.

 

Q) If the program has ample parallelism, what do we expect will typically happen when the program execution reaches a cilk_sync?

프로그램이 충분한 병렬성을 갖는다면, 프로그램 실행이 cilk_sync에 도달했을 때 일반적으로 발생할 수 있는 일은 뭔가요?

 

A) The executing function contains no outstanding spawned children.

실행 중인 함수에는 아직 처리되지 않은 spawned children이 없을 겁니다.

→ 이론상 병렬성이 뛰어나면 기다려야 하는 subcomputation이 없다는 의미?