병렬 알고리즘과 그 복잡성

6.1 병렬 알고리즘.

병렬 알고리즘은 계산 속도를 높이기 위해 다중 프로세서 또는 다중 스레드 시스템에서 실행되도록 설계되었습니다. 이러한 알고리즘은 작업을 독립적인 하위 작업으로 나누어 동시에 실행합니다. 병렬 알고리즘의 복잡성 분석은 시간적 복잡성과 공간적 복잡성뿐만 아니라 가속화, 효율성 및 확장성과 같은 요소를 고려해야 합니다.

병렬 알고리즘의 주요 개념

• 병렬성: 동시에 실행할 수 있는 여러 하위 작업으로 작업을 나누는 것.
• 속도 향상 (Speedup): 순차 알고리즘의 실행 시간과 병렬 알고리즘의 실행 시간의 비율.
• 효율성 (Efficiency): 가속도를 프로세서 수로 나눈 비율.
• 확장성 (Scalability): 병렬 알고리즘이 증가하는 프로세서 수를 효과적으로 사용할 수 있는 능력.

병렬 알고리즘의 장점:

• 실행 속도 향상: 작업을 병렬로 나누어 더 빠르게 수행.
• 자원 효율적 사용: 프로세서와 코어 사용 최적화.
• 대규모 작업 해결: 하나의 프로세서로는 불가능하거나 매우 느린 대량 데이터 및 복잡한 계산 처리 가능.

병렬 알고리즘의 시간 복잡성

병렬 알고리즘의 시간 복잡성은 모든 병렬 하위 작업 수행과 이들 간의 동기화에 소요되는 시간을 고려하여 측정됩니다. 여기에는 다음이 포함됩니다:

• 이론적 시간 복잡성: 무한한 수의 프로세서가 있을 때의 이상적인 실행 시간.
• 실제 시간 복잡성: 프로세서 수의 제한과 동기화 오버헤드를 고려한 실행 시간.

병렬 알고리즘의 공간 복잡성

병렬 알고리즘의 공간 복잡성은 각 병렬 프로세스의 데이터 및 컨텍스트를 저장하는 데 필요한 메모리 양을 고려합니다. 또한 프로세서 간의 통신 오버헤드를 고려하는 것이 중요합니다.

6.2 병렬 알고리즘의 예

병렬 병합 정렬 (Parallel Merge Sort):

배열을 하위 배열로 나누고, 이를 병렬로 정렬한 후 병합합니다.

시간 복잡성: O(n*log(n)/p), 여기서 n은 배열의 크기이고 p는 프로세서의 수입니다.

from multiprocessing import Pool

def merge_sort_parallel(arr, num_processes=None):
    if len(arr) <= 1:
        return arr
    if num_processes is None:
        num_processes = Pool()._processes
    with Pool(processes=num_processes) as pool:
        size = len(arr) // 2
        left, right = arr[:size], arr[size:]
        left, right = pool.map(merge_sort_parallel, [left, right])
        return merge(left, right)
            
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result
            
# 사용 예시
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort_parallel(arr)
print(sorted_arr)
            

하지만 알고리즘 자체보다는 "효율성" 분석이 더 흥미로울 것입니다.

6.3 병렬 알고리즘 분석

주요 개념:

1. 속도 향상 분석 (Speedup):
   • 순차 알고리즘의 실행 시간과 병렬 알고리즘의 실행 시간의 비율.
   • Speedup = T_seq / T_par, 여기서 T_seq는 순차 알고리즘의 실행 시간이고, T_par는 병렬 알고리즘의 실행 시간입니다.
2. 효율성 (Efficiency):
   • 프로세서 사용 효율성 평가.
   • Efficiency = Speedup / P, 여기서 P는 프로세서의 수입니다.
3. 암달의 법칙 (Amdahl's Law):
   • 작업 병렬화 시 최대 가속도를 결정.
   • Speedup_max = 1 / (S + (1 - S) / P), 여기서 S는 작업의 순차 부분의 비율이고, P는 프로세서의 수입니다.
4. 구스타프손의 법칙 (Gustafson's Law):
   • 프로세서 수 증가 시 작업 크기 변화에 따른 속도 향상 결정.
   • Speedup = P - α * (P - 1), 여기서 P는 프로세서의 수이고, α는 작업의 순차 부분의 비율입니다.

6.4 병렬 알고리즘의 예와 복잡성

예 1: 병렬 병합 정렬 (Parallel Merge Sort)

설명: 병렬 병합 정렬은 배열을 하위 배열로 나누고, 각각의 하위 배열을 병렬로 정렬한 후, 정렬된 하위 배열들을 병합합니다.

복잡성 분석:

• 시간 복잡성: O((n log n) / P), 여기서 P는 프로세서의 수입니다.
• 공간 복잡성: O(n)는 중간 데이터를 저장하기 위한 것입니다.

예 2: 병렬 배열 검색 (Parallel Search)

설명: 배열에서 요소를 검색하는 작업을 여러 하위 작업으로 나누고, 각각을 개별 프로세서에서 병렬로 수행합니다.

복잡성 분석:

• 시간 복잡성: O(n / P), 여기서 P는 프로세서의 수입니다.
• 공간 복잡성: O(1), 동일한 배열을 사용할 경우.

예 3: 병렬 행렬 곱셈 (Parallel Matrix Multiplication)

설명: 행렬을 블록으로 나누고, 블록 쌍의 곱셈을 서로 다른 프로세서에서 병렬로 수행합니다.

복잡성 분석:

• 시간 복잡성: O(n^3 / P), 여기서 P는 프로세서의 수입니다.
• 공간 복잡성: O(n^2)는 중간 결과를 저장하기 위한 것입니다.

6.5 병렬 알고리즘 구현

도구 및 라이브러리:

1. OpenMP:
   • C, C++, Fortran을 위한 라이브러리로, 멀티 스레드 애플리케이션 개발을 지원합니다.
2. MPI (Message Passing Interface):
   • 메시지를 통한 프로세스 간 통신을 지원하며, 분산 시스템에서 병렬 프로그래밍을 위한 표준입니다.
3. CUDA:
   • NVIDIA가 제공하는 플랫폼 및 API로, 그래픽 프로세서 (GPU)를 활용한 병렬 프로그래밍을 위한 것입니다.
4. Threading 및 multiprocessing in Python:
   • Python에서 멀티 스레드 및 멀티 프로세스 프로그램을 생성하기 위한 모듈입니다.

병렬 알고리즘은 작업을 여러 프로세서 또는 코어에 분산시켜 계산 속도를 크게 높일 수 있습니다. 병렬 알고리즘의 복잡성 분석은 가속도, 효율성 및 암달의 법칙과 구스타프손의 법칙을 사용하여 병렬화를 통해 달성할 수 있는 최대 가속도를 이해하는 것을 포함합니다.

병렬 알고리즘은 정렬 및 검색에서 복잡한 수학적 계산까지 다양한 분야에 적용되며, 전문 도구 및 라이브러리를 사용하여 구현해야 합니다.

중요! 병렬 알고리즘에 너무 몰두할 필요는 없습니다. 첫째, 암달의 법칙 때문에 기대만큼 효율적이지 않습니다. 둘째, 현재 30개의 프로세서가 있는 서버는 분당 3000개의 요청을 처리하며, 우리는 여전히 하나의 프로세서에 n개의 작업을 처리하고 있습니다.

셋째, 병렬 처리를 통해 속도를 높여야 하는 실제 작업은 GPU(그래픽 카드)로 이동했으며, 이러한 코드는 C와 같은 저수준 언어로 작성됩니다.