[C++] odd-Even Transposition Sort

odd -even transposition Sort란?

홀 수인덱스 차례에는 홀수 인덱스와 홀수 인덱스 +1이 짝수 인덱스 차례에는 짝수 인덱스와 짝수 인덱스 + 1이 같은 실행 타임에 정렬한 후 합치는 과정이다. 그림으로 나타내면 다음과 같다. 

GPU를 이용해 병렬 처리가 가능한 경우 여러 개의 task를 나누어 그 나눈 task들을 한 번에 처리함으로써 sorting을 더 빠르게 처리할 수 있다. 하지만 cpu는 한 번에 하나의 task밖에 처리하지 못하니 병렬 처리를 하기 위해서는 GPU를 사용해야하는데 cpu에서도 병렬 처리처럼 보이게 프로그래밍을 할 수 있다.

바로 thread 개념을 이용해서이다. 

Thread란?

thread란 하나의 프로세스 안에서 실행되는 여러 흐름의 단위라고 생각하면된다. 프로세스란 cpu와 메모리 상에 올려져있는 프로그램을 말하는 것이므로 하나의 프로그램 안에서 Thread를 나누면 여러 개의 흐름이 동시에 처리될 수 있다는 것을 의미한다. 

C++에서는 thread를 만들어낼 수 있는 기능을 제공하는 header 파일인 pthread.c를 제공하기 때문에 이 헤더파일에 있는 메소드들을 이용하면 쉽게 한 프로세스 안에서 여러 개의 Thread를 만들어낼 수 있다. 

// CPP Program for Odd-Even Transposition sort
//쓰레드를 이용할 것이다.  
  
#include <bits/stdc++.h>
#include <pthread.h>
  
using namespace std;
  
// 배열 크기  
#define n 10
  
// 쓰레드 크기는 데이터 총 수의 /2 + 1 
int max_threads = (n + 1) / 2;
  
int a[n]; 
int tmp;
  

void* compare(void* arg)
{
    int index = tmp; // index를 받는다.  
    tmp = tmp + 2; // 홀수는 홀수끼리 짝수는 짝수끼 리 
  
    if ((a[index] > a[index + 1]) && (index + 1 < n)) {
        swap(a[index], a[index + 1]);// 바꿔준다.  
    }
}
  
void oddEven(pthread_t threads[])
{
    int i, j;
  
    for (i = 1; i <= n; i++) {
        // 홀수  
        if (i % 2 == 1) {
            tmp = 0;
  
            // thread를 만들어 compare함수를 실행해준다.  
            for (j = 0; j < max_threads; j++)
                pthread_create(&threads[j], NULL, compare, NULL);
  
            // 모든 thread가 끝날 때까지 기다렸다가 합쳐준다.  
            for (j = 0; j < max_threads; j++)
                pthread_join(threads[j], NULL);
        }
  
        // 짝수 thread 
        else {
            tmp = 1;
  
            // thread를 만들어 각 thread에 대해 compare함수를 실행해준다.  
            for (j = 0; j < max_threads - 1; j++)
                pthread_create(&threads[j], NULL, compare, NULL);
  
            // 쓰레드가 끝날 때까지 기다렸다가 합쳐준다.  
            for (j = 0; j < max_threads - 1; j++)
                pthread_join(threads[j], NULL);
        }
    }
}
  
// 배열을 출력하는 함수  
void printArray()
{
    int i;
    for (i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}

int main()
{
  
    pthread_t threads[max_threads];
    
    for( int i=0 ; i < n; i ++) {
		cin >> a[i];
	}// a입력 받는다. 	
  
    cout << "Given array is: ";
    printArray();
  
    oddEven(threads);
  
    cout << "\nSorted array is: ";
    printArray();
  
    return 0;
}

다음은 pthread를 이용한 odd even sorting을 구현해 본 모습이다. 

여기서 중요한 점은 여러 개의 쓰레드들이 한 함수를 거쳐갈 때 그 함수의 지역 변수는 하나의 쓰레드 때마다 초기화되지 않고 계속 그 변수 값을 유지하고 있다는 점이다. 

중요한 함수는 

pthread_create(thread_id, NULL, 쓰레드마다 실행할 함수, NULL) -> 쓰레드를 만들어주는 메소드이다. 

pthread_join(thread_id, NULL)-> 쓰레드가 끝날 때까지 기다렸다가 하나의 흐름으로 합쳐주는 메소드이다. 

다음은 결과 화면이다.