병렬 알고리즘 (Parallel Algorithm)

병렬 알고리즘 (Parallel Algorithm)

여러 프로세서가 동시에 연산하여 문제를 해결하는 알고리즘

특징: 동시 실행, 작업 분할, 동기화, 통신 비용

병렬 모델: PRAM(EREW/CREW/CRCW, 이론적 공유메모리), BSP(슈퍼스텝), MapReduce(Map→Shuffle→Reduce)

성능 지표

• •Speedup: S(p)=T(1)/T(p), Efficiency: E(p)=S(p)/p
• •암달의 법칙: S=1/(f+(1-f)/p), 순차 비율 f가 병목 (f=10%→최대 10배)
• •구스타프슨 법칙: S=p-f·(p-1), 문제 크기 확장 관점

패턴: 분할 정복 / 파이프라인 / 마스터-워커 / 데이터 병렬(SIMD) / 태스크 병렬

동기화: 배리어, 뮤텍스, 세마포어, 원자적 연산

기술요소: MPI(분산 메시지), OpenMP(공유 메모리), CUDA(GPU), MapReduce(분산 처리)

비교: 데이터 병렬(같은 연산) vs 태스크 병렬(다른 연산) vs 파이프라인(단계별)

연관: 분산 컴퓨팅, GPU, MapReduce, 암달의 법칙, HPC