sjo200 - CS 대학원 수업 정리 블로그

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

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를 보장할 수 있다고 하는데... 책에서 보고 다시 찾으려니까 잘 안보인다

-----------더 볼거리--------------

1. balancer의 구현

- synchronization

public class Balancer {

  Boolean toggle =TRUE;

  public synchronized int traverse(t) {

    if(toggle)

      toggle = FALSE; return 0;

    toggle = TRUE; return 1;  

  }   

}

- CAS

while(true) {

    boolean prior = toggle.get();

    if(toggle.compareAndSet(prior, !prior)) {

        return (prior? 0 : 1);

    }

}

1. 개념

 array-based PQ, Tree-based PQ, Heap-based PQ, Skip-list-based PQ가 있다. removeMin, add를 할 수 있는 structure를 만들 것이다.

2. array-based PQ

 그냥 array에 priority 값을 index로 사용하고, removeMin을 하면 0부터 차례대로 읽어나가는 것이다. 예상 가능한 문제점들이 있다. 쉬우니까 생략한다.

3. tree-based PQ

 priority 값을 index로 사용하는데, 그 위로 모든 노드 값이 0인 binary tree가 있다고 생각하자. add를 하면 root까지 올라가야 하는데, 올라갈때 오른쪽으로 올라간다면 그 부모노드에게 ++, 왼쪽으로 가면 그대로 둔다. removeMin을 하면 root에서 1 이상이면 -- 후 왼쪽으로 이동, 아니면 오른쪽으로 이동한다. 각 operation별의 concurrency는 있겠지만, 둘이 동시에 실행하면 add가 채 끝나기 전에 removeMin에게 overtaken 될 수 있다. 무슨 말이냐면, 다른 노드에 의해 자신까지 올 수 있는 길이 생길 수 있다는 것인데, 총 8개의 노드(1~8)가 있을 때, 3, 4에 add 하고, 3을 담당한 쓰레드가 heap 상의 인덱스 1에서 멈추고, 4를 담당한 쓰레드는 완료했다고 치자. 그리고 removeMin 하면 3이 overtaken 된다.

4. Heap-based PQ

 이건 add, removeMin 둘다 자식노드와 부모노드를 lock하는데, 부모노드부터 lock한다. removeMin은 예상할 수 있듯이, 셋을 lock하여 어디로 내려갈지 정하는 것이고, add는 둘을 lock 하여 올라간다. add할때는 node의 상태를 busy로 바꿔서 parent가 busy면 아닐때까지 lock을 잠그려고 시도하고 풀고 반복하면서 spin lock하고, parent는 lock을 잡은 채로 큰 자식노드와 부모노드를 바꾸고 그곳으로 내려간다. 즉 removeMin은 add에 상관없이 쭉쭉 내려가고, add는 서로 순서가 바뀌지 않게 조심해서 올라간다. add가 보던게 removeMin에 의해서 올라갈 수 있기 때문에, 자신의 id가 node에 없다면 그냥 올라간다. 따라서 concurrency가 있으므로 linearizable 하다.

5. skip-list-based PQ (lazy skip-list)

 linearizable 하지 않지만, 앞에서 배웠듯이 quiescent consistency를 만들어낼 수 있다. 그리고 heap-based PQ를 성능에서 압도한다. 그냥 removeMin은 skip-list에서 첫 번째 원소를 빼는 것이고, add는 추가하는 것이다. 물론, lazy skip-list에서 발생한 문제는 또 일어날 것이고, 그렇기 때문에 말했듯이 constraint로 quiescent consistency를 만들어내야 한다.