OpenMP 병렬 처리 : 공유변수 문제 (레이스 컨디션)

2020/10/13 - [Computer & Parallel Processing] - OpenMP를 이용한 병렬 처리 (parallel for)

OpenMP를 이용한 병렬처리 (parallel for)

이전 글에서 OpenMP를 이용해서 for loop를 병렬처리 하는 방법에 대하여 설명하였습니다. 이 글의 예제인 소수의 개수를 세는 프로그램에서 패러렐 프로세싱의 결과가 시리얼 프로세싱과 다른 결과를 보였고, 몇 가지 키워드를 이용해 디버그 했죠. 이 글에서는 문제의 발생 이유에 대해서 설명하겠습니다. 일단 예제 코드를 다시 한번 보여드리겠습니다.

 위 코드를 시리얼 프로세싱 했을때를 플로우 차트로 그리면 아래 그림과 같습니다. 그리느라 고생했어요. 

프로그램이 구동되면 OS는 하나의 프로세서(OS가 정책에 따라 프로세서를 변경할수 있기 때문에 프로세스라고 하는 게 더 맞을 수 있습니다.)가 프로그램을 구동 시킵니다. 프로그램은 세 가지 구역으로 구분할 수 있습니다. 첫 번째는 프로그램 전체를 이루는 main함수에 해당하는 초록색 박스입니다. 두 번째 구역은 i를 2부터 1씩 증가시켜 input까지 계산하는 for loop로 갈색 박스로 구분하였습니다. 세 번째 구역은 j를 2부터 1씩 증가시켜 (i / 2)까지 계산하는 for loop로 보라색 박스로 구분하였습니다. 프로그램에 대한 설명은 이전 포스트에서 구동 결과와 같이 했으니 생략하고, 문제가 발생한 부분만 짚어 보겠습니다.

이 프로그램에서 이용되는 변수는 총 다섯 가지입니다. input, flag, res, i, j 입니다. 먼저 관련 분야의 상식으로 프로그램에서 이용되는 모든 변수는 구동되는 동안 CPU 혹은 Memory의 한 영역에 공간을 차지하고, 저장되어 있어야 합니다. 프로그램은 저장되어 있는 변수의 값을 가져오거나, 치환하여 프로그램에 목적에 따라 구동되게 합니다. 다 사용한 뒤에는 공간을 반납하고, 삭제됩니다.

j를 예를 들어 보죠. 처음 j가 공간을 할당 받을때 i는 2입니다. input은 프로그램 구동 시점에 입력받은 값이고, flag는 true, res는 0입니다. 이 상황에서 보라색 for loop가 구동되면서 처음 j는 자신의 공간을 할당받습니다. 그리고 그 안에 2라는 값을 채워주죠. 첫 루프에서 i와 j/2의 비교 결과가 false이기 때문에 보라색 박스 loop는 즉시 종료되고 갈색 박스로 빠져나가죠. 이때 j가 할당받은 공간은 해제됩니다. 이게 지역 변수 ( private )의 특성입니다.

다른 변수인 flag는 어떨까요? flag는 main 함수에서 선언되었습니다. main 함수 안에서는 특별한 조작이 없는 한 "flag"라는 키워드는 이 변수를 상징합니다. 이 프로그램에서는 갈색 박스에서 호출 하든 보라색 박스에서 호출 하든 같은 flag에 값을 확인하고, 또 치환한다는 의미죠. 위 플로우 차트에서 붉은색 점선은 이러한 변수들에 프로그램이 변화를 가하는 경우를 표기합니다. 

시리얼 프로그램에서는 위와 같은 변수의 범위 문제가 치명적인 문제를 발생시키지 않습니다. 하지만 패러렐 프로그램에서는 다릅니다. 동일한 프로그램을 OpenMP를 이용하여 컴파일하고, 이를 두 개의 프로세스를 이용해서 구동했을때 플로우 차트는 아래 그림과 같습니다.

이번엔 OS가 두개의 프로세서를 편성했습니다. processor1은 위 시리얼 프로그램과 같이 구동되고, processor2가 병렬 처리가 필요한 부분에 투입되어 연산속도를 향상합니다. 이전 플로우 차트와 달라진 부분은 붉은색으로 표기하였습니다. 두 프로그램의 첫 for loop (병렬 처리한 부분)의 초기화 부분을 보면 Processor 1은 i를 2로 시작하지만, Processor 2는 3으로 시작합니다. 또한 두 processor 모두 i의 증가량을 2로 변경했죠. 이런 방식으로 각 Processor가 task을 분배하여 속도를 가속화합니다.

이전 글에서 언급한 것처럼 이 프로그램에서 문제가 되는 변수는 flag와 res입니다. 이유는 이 변수들이 두 Processor에 공유되어 있으며, 서로의 상태를 확인하지 않고 참조 및 치환하고 있는 상태입니다.

flag의 문제점.

flag의 경우를 확인하죠. flag는 총 3번 이용됩니다. 첫 번째는 첫 for loop에서 flag를 true로 변경한 후, 두 번째 for loop에서 조건부로 false로 변경합니다. 마지막으로 두번째 for loop가 종료되면 flag의 값을 비교합니다. 이 프로세스가 시리얼 프로세싱 환경으로 구동되면 아무 문제없으나 병렬 처리가 되면 문제가 되죠. 이유는 각 processor가 다른 processor의 상태에 관계없이 flag의 값을 참조하거나 치환하기 때문입니다.

문제가 발생하는 과정은 아래와 같습니다.

1. processor 1이 i와 j의 나머지 값이 0인지 비교합니다. i가 4, j가 2 임으로 참입니다.

2. processor 1이 flag를 false로 변경합니다.

3. processor 2가 flag를 true로 변경합니다.

4. processor 1이 flag의 값이 true 인지 확인합니다. 

5. processor 1이 flag의 값이 true 임으로 res를 증가시킵니다.

processor 1의 두 번째 for loop 결과로 flag가 false가 되기 때문에 processor 1은 res의 증가 없이 i를 증가 시키고 loop를 재개해야 합니다. 하지만 3번째 과정에서 processor 2가 flag를 true로 변경하여, 5번째 과정과 같이 오류가 발생합니다. 코드 상으로는 1번과정이 진행 된뒤, break 명령으로 두번째 for문이 종료된 뒤, 곧바로 flag의 값을 비교합니다. 코드상으로 이렇게 짧은 순간에도 병렬 처리 상황에서는 문제가 될 수 있습니다. 

res의 문제점.

res에서도 문제의 발생 원인은 같습니다. processor 1과 processor 2가 동시에 res에 접근하는 것이죠. res의 경우는 flag와 달리 코드 상으로는 한 줄의 코드입니다. processor 1이 접근하던 processor 2가 접근하던 "res++"라는 짧은 구문으로 실행되며, 아래 스냅샷과 같이  어셈블리어로도 addl 단 한 줄로 구현되는 짧은 코드입니다.

그러므로 문제가 발생하기엔 너무 짧은 구간이라고 할 수도 있죠. 만약 구동 PC가 다른 프로그램의 구동 없이(부팅 이후 OS조차 구동하지 않고) 이 프로그램만 구동하고 있다면, 이 부분에서 문제가 발생하지 않을 수도 있습니다. 하지만 현실에서 이용되는 대부분의 PC는 시분할 시스템을 채용하고, OS의 관리 하에 구동됩니다. 이 조건에서는 어떤 process도 컴퓨팅 자원을 독점하지 않고, 다른 process와 공유하며 사용하기 때문에 동일 코드라도 구동 시간 등은 달라질 수 있습니다. 실제 분석을 위해 코드를 아래 스냅숏과 같이 변경합니다.

res를 증가시키는 코드 바로 앞과 뒤에 clock() 함수를 이용하여 구간의 구동 시간을 확인합니다. clock 함수는 CPU clock 단위로 구동 시간을 확인하는 함수입니다. 이를 이용해 res를 증가시킬 때마다 구동 시간을 출력합니다. 이 프로그램을 시리얼 프로그램으로 구동하여 확인한 결과가 아래 스냅샷 입니다.

같은 코드 임에서 구동 시간은 0~3으로 천차만별입니다. ( 왜 clock이 0일 수 있는지 잘 모르겠습니다. 멀티 코어의 특성이 아닐까 조심스럽게 예상하지만, 아시는 분은 조언 부탁드립니다. ) 실제 데이터를 분석해 보면 수치는 최대 54까지 입력되었으며, 경향은 아래 그래프와 같습니다. 데이터의 대부분이 0~2 사이 이기 때문에 가로축을 log 스케일로 표기하여 가독성을 향상했습니다. 99.56% 의 확률로 계산 시간은 0~2 clock 이였으나, 15 clock 이상 소요되는 경우도 0.27% 발생합니다. 이렇게 단순한 코드여도, 컴퓨팅 자원의 상태와 OS의 운정 정책에 따라 소요시간이 달라질 수 있습니다. 그럼에도 불구하고 공유된 변수를 다른 Process의 상태에 관계없이 참조, 치환하면, 문제가 발생하게 되는 것입니다.

예제 프로그램에서는 두 개의 processor 중 하나가 res++를 처리하기 위해 데이터를 획득하던 중 다른 processor가 res++를 실행하고 마쳤다면 res의 값이 제대로 적용되지 않는 문제가 발생하게 되는 것입니다. 실제로 문제가 발생하는 과정을 풀어 보죠.

1. processor 1이 "res++"를 실행하기 위해 res의 값을 받아 온다. 값은 15였다.

2. processor 2가 "res++"를 실행하기 위해 res의 값을 받아 온다. 값은 15였다.

3. processor 1 혹은 2가 "res++"의 실행을 마쳐 res 값을 치환한다. res의 값은 16이 된다.

4. 남은 processor가 "res++"의 실행을 마쳐 res 값을 치환한다. res의 값은 16이 된다. 

여기서 갑자기 제가 배웠던 예전 설명을 따라 보겠습니다. -----------변수의 값을 변경할 때 명령어의 처리 순서는 1. 변수의 값을 cpu에서 직접 접근할 수 있는 저장소(상위 레지스터)로 가져온다. 2. 값을 변경한다. 3. 변수를 원래 저장소에 저장한다. 이 과정이 이루어지는 중간에 다른 processor가 이 일을 동일하게 진행해 버리면 문제가 됩니다. -------------- 실제로 2020년 10월 제가 구글로 찾아보니 많은 블로거 분들이 위 설명을 따르셨더군요. 개념적으로는 위 설명이 맞습니다만, 제가 쓰고 싶지는 않습니다. 왜냐면 어셈블리어로 변환된 c++ 코드를 분석하면 위 설명을 따른다고 이야기하기 어렵거든요. 아무튼 중요한 점은 이런 식으로 공유된 변수를 processor들이 아무런 감시 없이 이용하면 문제가 됩니다. 될 수 있습니다. ( 치환이 아닌 참조라면 문제가 안되기도 합니다. ex> input 변수 )

이 글도 너무 길어진 것 같으니, OpenMP에서 이 문제를 해결하는 내용은 다음 글로 넘기도록 하겠습니다. 그 글도 아마 flag의 해결과 res의 해결 두 가지로 쓰게 될 것 같네요. 감사합니다.

 

다음 포스팅

2021.03.12 - [Computer & Parallel Processing] - OpenMP 병렬 처리 : 공유변수 문제 (레이스 컨디션) 해결

OpenMP 병렬 처리 : 공유변수 문제 (레이스 컨디션) 해결