futures, scheduling, and work distribution

1. 개념

 멀티코어 몇 개로 얼마만큼의 성능향상이 있을 수 있는지, 어떻게 일을 분배해야 최적으로 분배하는지, 분배하는건 어떻게 하는지 알아본다.

2. 성능향상에 관한 몇 가지 공식

Define work: total time on one processor

Define critical path length: longest dependency path, 

can't beat that(아무리 많은 코어라도, 이거만큼은 걸린다)

T_1 = time needed on one processor

T_p = time needed on p processor

T_inf = critical path length(time needed on infinite processor)

 

work law:  T_p >= T_1 / p

critical path law: T_p >= T_inf

 - optimal scheduler is greedy

•A node is ready if predecessors are done

•Greedy: schedule as many ready nodes as possible

proof of near-optimality도 한 번 보면 좋다.( T_p <= T_1 / p + T_inf ) 

이 부분은 위 공식만 적당히 이해하고 가면 괜찮았다. 암달의 법칙 보는 느낌

3. work stealing

 일을 분배할 때, 쓰레드마다 Double Ended queue(DEQueue)를 가지고 거기에 Runnable을 넣는다. 쓰레드는 자기 deque에서 하나씩 빼서 일을 실행한다. owner는 popBottom()으로 빼서 일하고, pushBottom()으로 일을 저장한다. 근데 일이 없으면 다른 쓰레드로 랜덤하게 가서 popTop()을 하는데, 다른 백수(thief)랑 contention이 일어날 수 있으니까 CAS를 한다. 이 또한 ABA problem이 발생할 수 있기 때문에, stamp를 사용해서 두 개를 비교하는 CAS를 사용하여 stamp와 일을 확인한 뒤 뺏어온다. isEmpty()의 경우, 여러 쓰레드에서 실행할 수 있으므로 linearizability를 보장하는게 좋을 것이다. 그리고 가능하다. 왜냐하면 top.getReference()로 확인한 뒤, bottom을 확인하고 비교하면 top은 줄어들기만 하므로, linearizability를 보장할 수 있다고 하는데... 책에서 보고 다시 찾으려니까 잘 안보인다