Shared counting

1. 개념

 

Shared counting이란, 여러 쓰레드가 getAndInc를 한다고 생각하면 된다. 만약 진짜로 그렇게 한다면, bottleneck이 걸릴 것이므로, 이 챕터에서는 적은 contention으로 하게 해주는 structure를 소개할 것이다.

2. Software combining tree

 이건 좀 어려운 개념이다. 쓰레드(프로세서) 개수 / 2만큼 리프노드를 만들고, 쭉쭉 위로 둘씩 이어서 바이너리 트리를 만들어야 한다. 그리고 노드에서 contention하여 combining하는 것인데, combining하게되면, (왼쪽 노드가 combining 했을때) 오른쪽 노드 값을 합해서 부모노드로 들고 올라가는 것이다. 이후 distribute에서 왼쪽노드에 더해지기 전 값을 주고, 오른쪽노드에 왼쪽노드의 값을 더한 값을 주는 것이다. 편의를 위해 왼쪽, 오른쪽을 강제했다.

 이해를 돕기위해 다른 경우를 생각해보자. getAndInc에서는 먼저 접근한 놈은 상대적으로 나중에 접근한 놈보다 적은 값을 받는다. 나중에 접근한 놈은 먼저 접근한 놈부터 나중에 접근한 놈까지 더해진 값을 다 더해서 받기 때문이다. 이걸 combining tree와 같이 생각해보면 먼저 간 놈(combining 한 노드)이 적은 값을 받을 것이므로 나중에 간 combining 하지 못한 노드에게 큰 값을 주는 것이다. 코드를 보면 더 쉽게 이해될 것이다.

 장점으로는, contention을 한 노드에서 두 쓰레드만 하게 되므로 contention의 수가 대폭 줄어 효과적으로 contention을 해결할 수 있다. 그러나 단점으로는, 최악의 경우 n번의 counting을 할 때, O(nlogn)만큼 걸려서 오히려 비효율적이다. 따라서 많은 쓰레드가 contention하면서 counting할 때 사용하여야 좋은 structure이다.

3. counting network

 counting network는 balancer들을 여러개 사용해서 만드는 것이다. balancer란, 2개의 인풋에 2개의 아웃풋으로 만들어지는데, 한 토큰이 어느 인풋으로 들어오든 아웃풋이 매번 교차하면서 토큰을 내보내는 것이다. 따라서 어느 인풋으로 토큰을 주던지 두 아웃풋의 차이는 최대 1이다. 이걸 여러개 사용하면, 4개 인풋 4개 아웃풋인 모듈을 만들어 토큰이 차례대로 쌓이도록 할 수 있다. 이것을 network라고 한다.

 

 counting network를 쉽게 구성하는 방법에는 bitonic counting network, periodic counting network가 있다. 이는 검색하면 나오므로, 생략한다. 둘다 공통적으로, 재귀적인 구성을 통해 2^n의 인풋, 아웃풋을 가진 network를 만들 수 있다.

 어떻게 그게 가능한지 증명해보자. merger[k]를 k개 인풋 아웃풋인 network라고 하면, merger[k] 두개를 뒀을 때, 둘은 한 줄에서 약간 어긋나지만 잘 카운팅 될 것이다. 이를 merger[2k]인 두 개를 두고 인풋에 넣는다고 쳐도, 아웃풋은 비슷하게 어긋나지만 잘 카운팅 될 것이다. 어긋난다는 말은 한 줄씩 채워지지만, 마지막 줄의 빈 곳이 둘로 나눠질 수 있다는 것이다.

 여기서, 마지막에 merger 각자 아웃풋 1번째를 연결하는 밸런서 , 2번째를 연결하는 밸런서, ... 를 배치하면, 토큰은 올바르게 카운팅 된다. 이해가 안된다면 책을 보자.

4. diffracting tree

 이젠 인풋이 하나인 밸런서를 써보자. 그럼 당연히 contention이 일어날 것이다. 이 때, concurrent stack에서 사용한 EliminationArray를 사용해보자. 두 쓰레드가 만나 서로의 아이디를 교환한 뒤, 수가 작은 놈은 위로 보내고, 큰 놈은 아래로 보낸다. 이게 다다. 근데 성능이 좋다. 중요한 점은 linearizability가 보장되지 않아서, pipelining 하듯이 보내면 concurrency가 생긴다고 한다. 책에서 그 말밖에 안했는데, 아마 depth가 같은 놈끼리 토큰을 동시에 보내면 그게 되지 않을까 싶다.

 이외에 structure 몇 개가 더 있는 것 같은데 강의하지 않았다.