barriers

1. 개념

 멀티코어에서 모든 작업을 다같이 완료했음을 다같이 알기 위해서는 barrier가 필요하다. 이 말은, barrier로 몇 쓰레드가 먼저 실행되지 않도록 막는다는 말이다.

2. Sense-Reversing Barrier

 모두가 볼 수 있는 count를 만들고, size를 넣는다. 그리고 각 쓰레드는 mySense라는 flag를 갖고, sense라는 global flag가 있다. 쓰레드는 완료했을 경우 fetchAndDecrement로 count를 감소시키고, 반환된 값이 1이면 마지막임을 알 수 있다. 마지막이 아니면 while(mySense != sense)로 spin lock을 하고 마지막이라면 count를 size로 다시 set 해준 뒤 sense = mySense를 실행한다. 그럼 동시에 모든 쓰레드가 풀려난다. 가장 쉽게 생각할 수 있는 방법이면서 count에 bottleneck이 발생하여 가장 좋지 않은 방법이다. 각 쓰레드마다 다른 쓰레드를 기다리는 것을 await()라고 하자. 위 로직은 하나의 await() 구현방법이다.

3. Combining Tree Barrier

 combining tree를 만들듯이, Sense-Reversing Barrier의 size를 2로 정하고, 그것을 하나의 노드로 사용한다. 그래서 뒤에 await()가 실행된 쓰레드는 부모의 await()를 재귀 실행하고, 돌아와서 count를 다시 2로 set한뒤 sense = mySense를 실행한다. 앞에 실행된 쓰레드는 while(sense != mySense)로 기다린다.(이건 각 노드마다 공유되는 sense가 하나씩 있다.)

장점은 bottleneck이 없지만, 단점은 local spinning을 하기 때문에 NUMA에 부적합하다.

4. Tournament Tree Barrier

 NUMA에서 사용할 수 있도록, 그리고 RMW operation이 필요없게 tree를 만들어보자. structure를 미리 만드는데, winner와 loser를 미리 정해놓는다. winner에만 부모로 갈 수 있게 포인터를 설정해준다. 만약 loser가 먼저 들어오면, winner의 flag를 바꿔준뒤 자신의 flag에 spinning한다. winner는 자신의 flag가 바뀔때까지 spin하고, 바뀌면 부모의 await()를 재귀로 실행한다. 그리고 재귀 실행이 끝나면 파트너(loser)의 flag를 바꿔줘서 loser가 돌아갈 수 있게 하고 끝낸다.

bottleneck이 없고, fixed location spinning 하기 때문에 NUMA에 사용할 수 있다.

5. Dissemination Barrier

 아름다운 방법으로 Barrier를 구현할 수 있는데, cache coherence가 좋지 않다. 한 round 마다 2^k (k = 0, 1, 2,..) 다음 번째의 쓰레드에게 자신의 상태를 알리고, 2^k가 size를 넘으면 그만둔다. log n 번의 round로 완료할 수 있다.

6. Static Tree Barrier

 가장 이상적인 방법이다. 각 쓰레드 번호에 노드 하나씩 있다고 생각하고, 이진트리를 구성해보자. 그리고 missing child number(아직 자식노드 둘에게서 신호가 안왔을 때 2)를 저장한다. 그럼 leaf node는 그 number가 0이고, 자식이 있는 노드는 자식 개수만큼 있다. 해당 number가 0일때까지 spin 하고, 0이 되면 부모 number를 하나 빼준다. 그리고 global sense flag를 spin한다. root에서 0이 되면 global sense flag를 바꿔준다.

bottleneck 없고, cache coherence도 보장할 수 있다. massage passing architecture에서는 root가 자식에게, 그 노드는 또 자식에게 notify 해주면 된다.