개선된 알고리즘과 병렬프로그래밍 필요성

병렬처리 프로그래밍이란

일부 컴파일러, 라이브러리에서는 병렬 처리(Parallel Processing) 코드로 변경을 도와준다. 하지만 매우 낮은 수준의 병렬화만 지원하며 활용 여부 또한 불투명하다. 심한경우 성능이 저하되는 경우도 빈번하다. 따라서 병렬 컴퓨티 장치를 제어하는 가장 효과적인 방법은 병렬 처리 프로그래밍을 배우는 것이다.

예제

N개의 값을 계산하고 그 값을 모두 더하는 코드. ComputeNextValue 함수를 사용한다는 가정 하에 for문을 N번 돌면서 값 x를 계산하고 그 값을 sum에 합산해주면 된다.

이 코드를 직렬코드로 작성하면 아래와 같다.

// 직렬코드의 예시
int sum = 0;
for (int i = 0; i < N; i++)         // 단일 프로세스가 반복해 계산
{
	int x = ComputeNextValue();    //계산
	sum += x;
}

이걸 병렬처리 하려면?

1. 전체 N개의 작업을 N/P개 씩 P개 작업 그룹으로 분산한다.
2. 각 스레드([[Thread(Cuda)]])또는 코어는 작업 그룹을 하나씩 할당받는다.
3. 각 스레드는 할당받은 영역을 계산한다.
4. 모든 스레드가 작업을 마칠 때 까지 대기.
5. 모든 코어가 계산한 합을 대표 스레드가 취합한 후 그 값을 하나로 더한다.

// 간단한 병렬코드 예시
int ComputeMySum(int tid)    //tid: Thread's ID
{
	int my_sum[tid] = 0;
	
	// 각 코어(스레드) 담당 구역 할당
	for(int i = my_first; i < my_end; i++)
	{
		int my_x = ComputeNextValue();
		my_sum[tid] += my_x;
	}
}

void main(void)
{
	// 배정받은 구역 처리(연산)
	ComputeMySum(tid);

	// 대표스레드의 작업
	if(master_thread)
	{
		// sum 결과 취합
		sum = my_x;
		for (int i = 1; i < p; i++)
		{
			sum += receive(i);
		}
	}
	
	// 작업스레드는
	else
	{
		// 계산 후 대표스레드에게 작업물 전달
		sendMysum();
	}
}

차이점

위 두 코드의 결과 시간 차이가 날까? 실제 데이터를 활용한 것이 아니니 간이 계산을 해보자.

(데이터)N= 24, (프로세스)P = 8, 모든 연산시간 = 1초 라고 가정하자.

• 직렬 : N * P(1직렬) = 24 * 1 = 24

• 병렬: 스레드 분배(N / P) + 계산(P-1) = (24 / 8) + 7 = 10

즉 병렬처리를 통해 직렬처리보다 2.4배 빠른 연산속도를 보인다. 프로세스는 8배 늘어났는데, 결과는 2.4배 빠른건 아쉽다. 그리고 무작정 프로세스를 늘린다고 연산이 무한히 빨라지지 않는다.

표의 내용처럼 코어의 갯수가 64개 이상부터 성능이 급격히 떨어지는 것으로 보인다. 그럼 더 좋은 방법은 없을까?

개선된 알고리즘

왜 코어가 늘어날수록 작업 시간이 늘어날까? 그 이유는 작업 코어는 늘어나는데, 대표 코어는 언제나 하나만 존재하기 때문이다. 최종 취합을 다른 코어들이 도우면 연산 시간이 빨라지지 않을까? 알고리즘을 바꿔보자.

1. 전체 N개의 작업을 N/P개 씩 P개 작업 그룹으로 분산한다.
2. 각 스레드([[Thread(Cuda)]])또는 코어는 작업 그룹을 하나씩 할당받는다.
3. 각 스레드는 할당받은 영역을 계산한다.
4. 모든 스레드가 작업을 마칠 때 까지 대기.

5. 모든 코어가 계산한 합을 대표 스레드가 취합한 후 그 값을 하나로 더한다. $(i+2^{k-1})$ 번 코어는 작업을 종료한다. 단, 최소의 k == 1

6. i번 스레드는 이전 번호의 코어 결과 값을 가져와서 더한다.
7. k를 1 증가시킨다.
8. 작업에 참여하는 스레드가 더 이상 없을 때까지 5~7을 반복한다.

첫번째 단계에서는 P/2개의 스레드가, 두 번째 단계에선 P/4 개의 스레드가 참여하게되며 P가 8일땐 위의 그림과 같다.

즉 개선된 알고리즘을 수식으로 표현하면 아래와 같다. \({N \over P} + \log_{2}N\)

또한 개선된 알고리즘을 사용한 코어 변화테이블은 아래와 같이 코어가 늘어날 수록 개선되는 모습을 보인다.

참고

서적) CUDA 기반 GPU 병렬 처리 프로그래밍