애초에 전제조건을 잘못 잡은거 같아. 내 원래 생각은 정렬 알고리즘을 무리하게 n분의 1하는건 오히려 성능에 안좋다고 했었는데 코드 돌려보니까 무리하게만 안하면 2스레드가 훨씬 빠르긴 하네. 대충 퀵소트 한번 싱글 스레드로 돌려서 2분의 1로 만들고 각각의 분할된 조각을 그대로 스레드에 넣고 돌려버리니 데이터량에 따라 차이가 있긴 하지만 아무리 적어도 대충 5%에서 많으면 두배 가까이 차이나는거 같음.


퀵 정렬에서 한번 분할된 조각은 둘이 연관성을 가지지 않으므로 데이터 의존성이 없고 데이터량 대비 시간복잡도가 로그 함수의 특징을 가진다는 사실을 간과해서 저 사단이 난거 같아요. 이제 멀티스레드 글은 그만 쓰겠습니다. 그리고 더 공부하고 와야겠네요.


코드


#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>

#include <pthread.h>


#include "sort.h"


struct thread_arg {

sort_data_t * parray;

size_t left, right;

} thread_arg_s, thread_arg_d;


pthread_t thread_s, thread_d;

pthread_mutex_t thread_mtx;

pthread_cond_t thread_cond;




void * thread_entry(void * args);


int mpsort_init() {

pthread_cond_init(&thread_cond, NULL);

if (pthread_mutex_init(&thread_mtx, NULL)) {

perror("pthread_mutex_init");

return 1;

}

pthread_mutex_lock(&thread_mtx);


if (pthread_create(&thread_s, NULL, thread_entry, &thread_arg_s) || pthread_create(&thread_d, NULL, thread_entry, &thread_arg_d)) {

perror("pthread_create");

abort();

}

pthread_mutex_unlock(&thread_mtx);


return 0;

}


void mpsort(sort_data_t * parr, size_t count) {

thread_arg_s.parray = thread_arg_d.parray = parr;


ssize_t i = 0, j = count;

sort_data_t pivot = parr[(i+j)/2];


do {

while (parr[i] < pivot)

i++;

while (pivot < parr[j])

j--;

if (i <= j) {

sort_data_t temp = parr[i];

parr[i++] = parr[j];

parr[j--] = temp;

}

} while (i <= j);


if (0 < j) {

thread_arg_s.left = 0;

thread_arg_s.right = j;

}

if (i < count) {

thread_arg_d.left = i;

thread_arg_d.right = count;

}

pthread_cond_broadcast(&thread_cond);


pthread_join(thread_s, NULL);

pthread_join(thread_d, NULL);

return;

}


static void mpquicksort(sort_data_t * parr, ssize_t left, ssize_t right) {

ssize_t i = left, j = right;

sort_data_t pivot = parr[(i+j)/2];


do {

while (parr[i] < pivot)

i++;

while (pivot < parr[j])

j--;

if (i <= j) {

sort_data_t temp = parr[i];

parr[i++] = parr[j];

parr[j--] = temp;

}

} while (i <= j);


if (left < j)

mpquicksort(parr, left, j);

if (i < right)

mpquicksort(parr, i, right);


return;

}

void * thread_entry(void * args) {

struct thread_arg * argp = (struct thread_arg *)args;

pthread_mutex_lock(&thread_mtx);


pthread_cond_wait(&thread_cond, &thread_mtx);


mpquicksort(argp->parray, argp->left, argp->right);

pthread_mutex_unlock(&thread_mtx);

pthread_exit(NULL);

}


int compare_int(const void * a, const void * b) {

return *(int*)a - *(int*)b;

}


int main(void) {

if (mpsort_init()) {

return -1;

}

srand(time(NULL));


int i, max, range;

clock_t beg, end;

float mptime, sptime;

sort_data_t * parr;


printf("Input size : ");

scanf("%d", &max);

printf("Input range : ");

scanf("%d", &range);


parr = malloc(sizeof(sort_data_t) * max);

if (!parr) {

perror("malloc");

return -1;

}


for (i = 0; i < max; i++) {

parr[i] = rand()%range;

}

beg = clock();

mpsort(parr, max);

end = clock();

mptime = ((float)end - beg)/CLOCKS_PER_SEC;

for (i = 0; i < max; i++) {

parr[i] = rand()%range;

}


beg = clock();

qsort(parr, max, sizeof(sort_data_t), compare_int);

end = clock();

printf("Time(Single) : %.3f\nTime(Multi) : %.3f\n", ((float)end - beg)/CLOCKS_PER_SEC, mptime);

free(parr);


return 0;

}