C++ pthread 멀티스레딩으로 대규모 배열의 최댓값 찾기

문제 개요

매우 큰 크기의 정수 배열이 주어졌을 때, 멀티스레딩(multithreading)을 활용하여 배열 내 최댓값을 찾는 것이 이 글의 목표입니다. 데이터가 방대할 경우 단일 스레드보다 여러 스레드로 작업을 분산 처리하는 것이 훨씬 효율적입니다.

예시

입력 배열이 다음과 같다고 가정해 보겠습니다.

{10, 14, -10, 8, 25, 46, 85, 1673, 63, 65, 93, 101, 125, 50, 73, 548}

이 배열에서 가장 큰 요소는 1673입니다.

알고리즘

• 배열의 크기를 total_elements라고 정의합니다.
• N개의 스레드를 생성합니다.
• 각 스레드는 (total_elements / N)개씩 배열 요소를 나누어 담당하며, 자신이 맡은 구간의 최댓값을 계산합니다.
• 마지막으로 각 스레드가 보고한 최댓값들을 비교하여 전체 최댓값을 도출합니다.

구현 예제

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <limits.h>

#define MAX 10
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))

typedef struct struct_max {
    int start;
    int end;
    int thread_num;
} struct_max;

int arr[] = {10, 14, -10, 8, 25, 46, 85, 1673, 63, 65, 93, 101, 125, 50, 73, 548};
int max_values_from_threds[MAX];

void *thread_fun(void *arg) {
    struct_max *s_max = (struct_max*)arg;
    int start = s_max->start;
    int end = s_max->end;
    int thread_num = s_max->thread_num;
    int cur_max_value = INT_MIN;
    for (int i = start; i < end; ++i) {
        if (arr[i] > cur_max_value) {
            cur_max_value = arr[i];
        }
    }
    max_values_from_threds[thread_num] = cur_max_value;
    return NULL;
}

int main() {
    int total_elements = SIZE(arr);
    int n_threads = 4;
    struct_max thread_arr[4];
    for (int i = 0; i < 4; ++i) {
        thread_arr[i].thread_num = i + 1;
        thread_arr[i].start = i * 4;
        thread_arr[i].end = thread_arr[i].start + 4;
    }
    pthread_t threads[4];
    for (int i = 0; i < 4; ++i) {
        pthread_create(&threads[i], NULL, thread_fun, &thread_arr[i]);
    }
    for (int i = 0; i < 4; ++i) {
        pthread_join(threads[i], NULL);
    }
    int final_max_val = max_values_from_threds[0];
    for (int i = 0; i < n_threads; ++i) {
        if (max_values_from_threds[i] > final_max_val) {
            final_max_val = max_values_from_threds[i];
        }
    }
    printf("Maximum value = %d\n", final_max_val);
    return 0;
}

컴파일 방법

pthread 라이브러리를 사용하므로 컴파일 시 반드시 -lpthread 옵션으로 링크해야 합니다.

gcc program.c -o program -lpthread

코드 설명

이 프로그램은 16개의 요소를 가진 배열을 4개의 스레드로 나누어 처리합니다. 각 스레드는 4개의 요소를 담당하며, 자신의 구간에서 최댓값을 계산한 뒤 max_values_from_threds 배열에 저장합니다. 초기값을 INT_MIN으로 설정하기 때문에 음수 요소가 포함된 배열에서도 올바르게 동작합니다.

모든 스레드의 작업이 완료될 때까지 pthread_join()으로 대기한 후, 메인 스레드는 각 스레드가 계산한 최댓값들을 서로 비교하여 최종 최댓값을 도출합니다. 이러한 분할 정복(divide and conquer) 방식은 배열의 크기가 클수록 성능상 이점이 커집니다.

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Maximum value = 1673