OpenMP를 이용한 병렬화에서

재귀적인 성격이 있는 알고리즘 하나를 테스트 겸 OpenMP 2.0을 이용하여 병렬화를 하고 있는데요.

각각의 함수 콜이 서로 비의존적으로 동작 가능해서 이를 태스크 형태로 간단한 큐에 집어넣고, 각각의 쓰레드가 큐에서 작업을 가져오는 형태로 구현을 했습니다.

그런데 돌려보니 논리적인 문제는 없습니다만, 아마도 라이브 락이 걸리는건지 CPU 사용률은 100%인데 실제 동작 속도는 다운이 되네요.

일단 오버헤드가 발생할 수 있는 부분을 보니까 동기화 문제 때문에 쓰레드가 큐에서 작업을 넣거나 가져오는 함수 한 개를 통째로 critical section으로 잡은 정도인데요.

단순히 프로세서 하나만 정상적으로 일하는 상황에 추가로 발생하는 시간은 작업을 가져오기 위해 발생하는 오버헤드 때문이라고 보기엔 좀 미심쩍은데요.

쓰레드가 1개인 경우 17초 걸리는데 2개인 경우 32초, 4개인 경우 61초 이런 식으로 프로세서 갯수에 비례해 동작 시간이 선형적으로 증가합니다.

제가 병렬화 프로그래밍 경험이 거의 없어서 이런 문제가 어디에서 발생하는건지 잘 모르겠더군요.

혹시 조언을 해주실 수 있는 분이 계신다면 부탁드립니다.