현재 위치

홈 ›› Forums ›› 재미 ›› 자유 게시판

왜 멀티코어 정렬 제대로 성능이 안나죠?

soc의 이미지
글쓴이: soc / 작성시간: 토, 2011/08/20 - 4:54오전

OpenMP 라이브러리를 gcc에서 for문에 적용한 방식을 그대로 이용할 수 있도록 머지정렬 알고리즘을 for 반복문 하나만으로 다 되게 바꿔서 멀티코어 적용을 해보려 하는데, 성능이 20%밖에 개선되지 않아서 문제입니다. 쓰레드가 코어에 모두 골고루 배분되지 않아서 생기는 문제 같은데. 제 데스크톱이 쿼드코어 cpu를 사용하므로, 쿼드코어 네 개 모두에 쓰레드가 골고루 분배된다면, 성능이 75% 개선되어야 합니다.

5000만 개의 데이터를 쓰레드 하나만 사용해서 정렬했을 때에나, 쓰레드 방식을 적용하지 않고 그냥 처음 작성한 for 반복문만으로 구성된 함수 하나 실행했을 때에는 실행시간이 35초대로 동일합니다.
쓰레드 4개를 적용하면, 실행시간이 8.75초대로 개선되어야 하는데, 그렇지 않고 고작 28초대로 성능이 향상되었습니다. 뭐가 문제일까요? 혹시 제가 빼먹은 것이 있을런지.

#include<stdio.h>
#include<omp.h>
#define MAX 268435456
int n=0,arr[MAX>>1],mem[MAX>>1];
 
void thread(int i,int j){
	int c,p,k,m,l,r;
 
	l=j;
	r=(j+(i<<1)-1);
	if(r>n-1) r=n-1;
	c=p=j;
	k=j+i;
	if(k>n-1) k=n-1, m=n-1;
	else m=k-1;			
 
	while(c<=r) { // 두 구간을 비교하며 크기순서대로 임시배열에 저장한다.
		( (arr[p]>arr[k])?(k>r?true:false):(p>m?false:true) ) ?
				mem[c++]=arr[p++]:
				mem[c++]=arr[k++];
	}
	for(c=l;c<=r;c++) arr[geshifilter-c]=mem[c]; //임시배열에 저장된 내용을 아까 비교했던 구간에 저장한다.&#10;}&#10;&#10;void sort(){&#10;	int i,j;&#10;	&#10;	for(i=1;i&lt;n;i&lt;&lt;=1){ // bottom-up merge sort 실시할 때 비교할 구간의 크기를 1부터 시작해서 무조건 2배한다. (분할과정을 생략하고 그냥 무조건 비율이 2인 등비수열을 적용해도 성능이 그닥 손상되지 않음)&#10;		#pragma omp parallel for&#10;		for(j=0;j&lt;n;j+=(i&lt;&lt;1)) { // 비교할 구간의 크기만큼 띄어가며 정렬한다.&#10;			thread(i,j);&#10;		}&#10;	}&#10;}&#10;&#10;int main(){&#10;	FILE *fp;&#10;	&#10;	fp=fopen(&quot;input.txt&quot;,&quot;r&quot;);&#10;	while(!feof(fp)){&#10;		fscanf(fp,&quot;%d\n&quot;,&amp;arr[n]);&#10;		n++;&#10;	}&#10;	fclose(fp);&#10;	&#10;	omp_set_num_threads(4);&#10;	sort();&#10;	&#10;	fp=fopen(&quot;output.txt&quot;,&quot;w&quot;);&#10;	for(int i=0;i&lt;n;i++) fprintf(fp,&quot;%d\n&quot;,arr[i]);&#10;	fclose(fp);&#10;}&#10;
[/geshifilter-c]
Forums: 
자유 게시판
soc의 이미지

글쓴이: soc / 작성시간: 토, 2011/08/20 - 8:48오전

입출력 구간을 제외하고, 멀티코어 머지정렬 알고리즘이 적용된 구간의 단일쓰레드 실행시간은 10초, 멀티쓰레드 실행시간은 3초로, 70%의 성능향상을 보여 예측했던 성능향상수치의 93%에 이르렀습니다. 단일 쓰레드를 사용했을 때에 비한 성능 향상율은 3.3배로, 가장 이상적인 4배에 대해 82.5%의 효율을 보였습니다.

입력, 출력시간이 각각 12초, 14초 이렇게 총 26초가 되어 실행시간을 모두 잡아먹는 문제가 있음을 파악했습니다.

입력 데이터는 5000만개의 정수를 순서대로 생성한 이후 무작위로 위치를 바꾼 것이며, 입력파일의 크기는 466MB 입니다.

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 일, 2011/08/21 - 12:20오전

조금 애매하긴한데 3.3배 속도 향상이면 쿼드코어에서 잘 나온거 같은데요.
부동소수점 계산이 위주인 경우에 한정된 경험으로만 보면, 대략 코어수의 제곱근 정도로 개선이 되던데요. 그래서 듀얼은 1.4배 정도 빨라지고 쿼드는 2배 빨라지는 경험을 한적이 있스빈다. 그 경험에 비하면 개선정도가 잘 나온 것 같이 보이네요.

fltoll의 이미지

글쓴이: fltoll / 작성시간: 화, 2011/08/23 - 4:08오후

#pragma omp parallel for 지시어가 for 문안에서 반복적으로 실행되면(2중 루프에서 안 쪽)
반복되는 만큼 fork-join을 반복하기 때문에 병렬부하가 발생합니다.
해결 방법은 #pragma omp parallel for 지시어를 가장 바깥의 for 루프에 적용되도록 순서를 바꿔보세요.

둘러보기