OpenMP를 활용한 행렬 연산의 점진적 병렬화 및 성능 분석 프로젝트
본 프로젝트는 행렬 곱셈, 전치(Transpose), 컨볼루션(Convolution)과 같은 핵심적인 행렬 연산에 대해 서로 다른 병렬처리 방법의 성능을 하드웨어 한계와 관련지어 분석함. C++와 OpenMP를 사용하여 순차(Sequential) 구현을 토대로, OpenMP를 통한 병렬화, collapse를 이용한 최적화, 그리고 CPU 캐시 효율을 극대화하는 타일링(Tiling/Cache-blocking) 기법까지 점진적으로 구현함.
Python 스크립트를 통해 실험 과정을 자동화하고, 수집된 데이터를 바탕으로 성능 향상률(Speedup)과 병렬 효율성(Efficiency)을 계산하여 matplotlib과 seaborn으로 시각화함. 이를 통해 각 병렬화 기법이 하드웨어(CPU 코어, 캐시)와 상호작용하며 성능에 어떤 영향을 미치는지 정량적으로 분석함.
- Core Logic: C++17, OpenMP
- Build System: CMake
- Automation & Visualization: Python 3, pandas, matplotlib, seaborn
프로젝트는 CMake를 사용하여 빌드됨.
# 1. 빌드 디렉토리 생성 및 이동
mkdir -p build && cd build
# 2. CMake를 사용하여 빌드 파일 생성
cmake ..
# 3. 프로젝트 컴파일
make
# 4. 실험 실행 (run_experiments.py 실행)
# 정의된 파라미터(행렬 크기, 스레드 수 등)에 따라 C++ 프로그램을 반복 실행하고,
# 결과를 'experiment_summary.csv' 파일에 저장함.
make run
# 5. 결과 분석 및 시각화 (visualize_results.py 실행)
# 'experiment_summary.csv'를 읽어 Speedup, Efficiency를 계산하고,
# 'analysis_results' 디렉토리에 성능 분석 그래프를 저장함.
make visualize각 행렬 연산(곱셈, 전치, 컨볼루션)에 대해 아래 4가지 버전을 구현함.
- Sequential: 단일 스레드로 실행되는 기본 순차 코드. 모든 병렬화 성능 측정의 기준으로 사용됨.
- Parallel (Basic): OpenMP의
#pragma omp parallel for를 사용하여 가장 바깥쪽 루프를 병렬화한 가장 기본적인 병렬 모델임. - Parallel Collapsed:
#pragma omp parallel for collapse(2)를 사용하여 2개의 중첩 루프를 병렬화함. 스레드에 분배할 수 있는 작업 단위를 늘려 로드 밸런싱 효과의 향상을 유도함. - Tiled (Cache Blocking): 데이터를 CPU 캐시에 효율적으로 올라갈 수 있는 작은 타일(블록) 단위로 나누어 처리함. 데이터 지역성(Locality)을 극대화하여 캐시 미스(Cache Miss)를 줄이고 메모리 접근 병목 현상을 완화함.
추가로, 행렬 곱셈에 한해 Tiled 기법에 OpenMP의 schedule 절(static, dynamic, guided)을 적용하여 워크로드 스케줄링 정책이 성능에 미치는 영향을 분석함.
GitHub codespace 환경에서 수행됨.
- CPU: AMD EPYC 7763 (VM 환경)
- Cores/Threads: 2 Physical Cores, 4 Logical Cores (2 threads per core)
- L1d Cache: 32 KiB per core
- L2 Cache: 512 KiB per core
- L3 Cache: 32 MiB (shared)
- Matrix Rows (행 크기):
128,256,512,1024 - Matrix Cols (열 크기):
256,512,1024,2048- 다양한 크기와 형태(정사각형, 직사각형)의 행렬에 대한 수행으로 캐시 민감도 및 알고리즘의 확장성을 분석.
- Tile Size (타일 크기):
8,16,24,32,48,64,96- L1/L2 캐시 크기와 관련된 성능 분석.
- Number of Threads:
1,2,4,8,16 - Kernel Size:
5x5(for Convolution) - Iterations (반복 횟수):
2
make visualize를 통해 생성된 그래프는 analysis_results 디렉토리에서 확인가능.
- 성능 향상률 (Speedup):
순차 실행 시간 / 병렬 실행 시간으로 계산됨. 병렬화를 통해 얼마나 빨라졌는지를 나타내는 척도로, 사용한 스레드 개수(N)만큼 성능이 향상되는 것(Speedup = N)이 이상적임. - 병렬 효율성 (Efficiency):
Speedup / 스레드 수로 계산됨. 병렬 처리에 투입된 프로세서(코어) 자원이 얼마나 효율적으로 사용되었는지를 나타냄. 1.0 (100%)에 가까울수록 낭비 없이 자원이 잘 활용되었음을 의미함.
- 스레드 수와 성능의 한계:
- 결과: 대부분의 연산에서 스레드 수가 4개(논리 코어 수)를 초과했을 때 Speedup과 Efficiency가 더 이상 증가하지 않거나 오히려 감소하였음.
- 분석:
- 물리 코어 vs 논리 코어 (하이퍼스레딩): 실험 환경의 CPU는 2개의 물리 코어를 가지며, 각 코어는 2개의 스레드를 동시에 처리할 수 있는 하이퍼스레딩(Hyper-threading) 기술을 지원하여 총 4개의 논리 코어로 동작함. 하이퍼스레딩은 하나의 물리 코어 내 연산 유닛의 유휴 시간을 활용하여 다른 스레드의 명령어를 처리하는 기술로, 완전한 2배의 성능을 보장하지 않음.
- 성능 포화 및 저하: 스레드 수가 2개(물리 코어 수)일 때 약 1.9배의 높은 성능 향상을 보이며, 4개(논리 코어 수)까지는 하이퍼스레딩의 효과로 약 3.5배까지 성능이 개선됨. 하지만 8개, 16개 스레드를 사용했을 때는 실행될 코어가 부족하여 잦은 컨텍스트 스위칭(Context Switching) 오버헤드가 발생함. 이로 인해 성능 향상률이 약 3.2배로 정체되거나 오히려 소폭 하락하는 현상을 관찰함.
그림 1. 1024x1024 행렬 곱셈에서 스레드 수에 따른 성능 변화. 4개 스레드 이후 성능 향상이 둔화되는 것을 볼 수 있음.
- Tiling 기법의 높은 성능:
- 결과: 모든 연산, 특히 행렬 곱셈에서 Tiling 기법이 다른 병렬화 버전에 비해 높은 성능 향상률을 기록함.
- 분석:
- Tiling의 동작 구조: Tiling(Cache Blocking)은 거대한 행렬을 작은 크기의 부분 행렬(타일)로 분할하여 연산하는 기법임. 일반적인 행렬 곱셈은 행 전체와 열 전체를 반복적으로 접근하므로 데이터의 재사용성이 떨어지고 캐시 미스가 빈번하게 발생함. 반면, Tiling은 한 번 캐시에 올린 작은 타일 내에서 모든 계산을 최대한 마침.
- CPU 캐시 계층과의 연관성: 예를 들어,
1024x1024행렬 곱셈을 4개 스레드로 실행했을 때, 기본 병렬화 버전(Parallel Basic)은 약 3.5배의 성능 향상에 그친 반면,TileSize=32로 설정된 Tiled 버전은 약 12배에 달하는 큰 폭의 성능 향상을 보임. 이는 32x32 크기의 부분 행렬과 관련 데이터가 L1/L2 캐시에 효율적으로 적재(fit)되어, 느린 메인 메모리 접근(Cache Miss)을 크게 줄였기 때문으로 분석됨.
그림 2. 행렬 곱셈에서 타일 크기에 따른 성능 변화. 특정 타일 크기(32, 48)에서 최적의 성능을 보이며, 이는 캐시 크기와 밀접한 관련이 있음을 시사함.
- Transpose 연산의 특이점:
- 결과: 특정 스레드 개수(예: 4개 또는 8개)에서 효율이 눈에 띄게 저하되는 현상 확인.
- 분석:
- Memory-bound 특성: Transpose(
result(j, i) = A(i, j))는 복잡한 계산 없이 데이터를 읽고 쓰는 작업이 대부분임. 따라서 CPU의 계산 능력보다 데이터를 얼마나 빨리 메모리에서 가져오는가, 즉 **메모리 버스 대역폭(Memory Bus Bandwidth)**에 의해 성능이 좌우되는 대표적인 Memory-bound 연산임. - 성능 저하 원인:
- 메모리 대역폭 경쟁: 스레드 수가 증가하면 동시에 메모리에 접근하려는 요청이 많아져 한정된 메모리 버스 대역폭을 놓고 경쟁이 발생함.
- False Sharing: 예를 들어, Transpose 연산에서 스레드 2개를 사용할 때 90%에 가깝던 병렬 효율성(Efficiency)이 4개 스레드에서 60% 수준으로 급격히 하락하는 현상이 관찰됨. 이는 서로 다른 코어의 스레드들이 인접한 메모리 주소(같은 캐시 라인에 위치)에 동시 접근하면서, 실제로는 공유하지 않는 데이터임에도 불구하고 캐시 라인 무효화 및 재요청이 반복되는 False Sharing이 발생했기 때문으로 추정됨.
- Memory-bound 특성: Transpose(
그림 3. Transpose 연산의 성능. 다른 연산과 달리 Tiling의 효과가 거의 없으며, 스레드 증가에 따른 성능 향상이 제한적임을 보여줌.
collapse의 효과:- 결과:
Parallel Collapsed버전에서 기본Parallel버전에 비해 약소한 성능 개선을 확인함. - 분석:
collapse의 원리와 한계:collapse(2)는 2개의 중첩 루프를 하나의 큰 루프로 만들어 OpenMP가 스레드에 작업을 분배할 수 있는 전체 작업량(iteration space)을 늘려줌. 이 기법은 바깥쪽 루프의 반복 횟수가 스레드 수보다 적어 기본 병렬화(parallel for) 시 일부 스레드가 작업을 할당받지 못하는 '로드 불균형'이 발생할 때 가장 큰 효과를 발휘함.- 실험 환경과의 연관성: 예를 들어,
128x2048크기의 행렬 연산에서Parallel Basic버전의 성능 향상률이 3.4배일 때,Parallel Collapsed버전은 3.6배로 약 5% 내외의 미미한 성능 개선을 보임. 이는 본 실험의 최소 행 수(MatrixRows)가 128로, 최대 스레드 수 16보다 많아 기본 병렬화만으로도 로드 밸런싱이 충분히 잘 이루어졌기 때문임. 따라서collapse의 주된 장점이 발휘될 여지가 적어 성능 개선 효과가 약소한 수준에 그친 것으로 분석됨.
- 결과:
그림 4. 128x2048 직사각형 행렬에서의 성능 비교. `collapse`가 기본 병렬화보다 근소하게 나은 성능을 보이지만, Tiling에 비하면 개선 효과가 미미함.
본 프로젝트를 통해 성공적인 병렬 프로그래밍은 단순히 스레드 수를 늘리는 것을 넘어, 알고리즘과 하드웨어 구조에 대한 깊은 이해가 필수적임을 확인함. 특히 캐시 지역성을 고려한 Tiling 기법의 병렬 컴퓨팅 성능 최적화에 있어서의 실효성을 확인함.
또한, 자동화된 실험 및 시각화 파이프라인을 구축함으로써 다양한 파라미터가 성능에 미치는 영향을 체계적으로 분석하고 검증함.
본 프로젝트에서 각 병렬 처리 모델에 대한 하드웨어와 결합된 분석이 이루어졌지만, 다음과 같은 한계점을 가짐.
-
가상화 환경의 영향: 모든 실험은 VM 환경에서 수행됨. 하이퍼바이저는 CPU 스케줄링, 메모리 관리 등에 예측 불가능한 오버헤드를 추가할 수 있으며, 이는 미세한 성능 측정에 노이즈를 유발할 수 있음. 즉, Bare-metal 환경에서의 결과와는 차이가 있을 수 있음.
-
제한적인 파라미터 범위: 실험에 사용된 행렬 크기(
256,1024)와 타일 크기(16,32,64)가 제한적임. 실제 최적의 타일 크기는 특정 CPU의 L1/L2 캐시 크기와 밀접한 관련이 있으므로, 더 다양한 크기를 테스트하여 최적점을 찾는 과정이 필요. 또한, 다양한 형태(e.g.,100x10000)의 행렬에 대한 테스트는 이루어지지 않음. -
단순화된 캐시 플러싱: 캐시 효과를 명확히 보기 위해 매 연산 전 더미(dummy) 데이터를 할당하여 캐시를 플러싱하는 방법을 사용함. 이는 L1/L2 캐시에는 효과적일 수 있으나, CPU의 복잡한 다중 레벨 캐시(특히 공유 L3 캐시)와 OS의 동작을 고려할 때 완벽한 캐시 플러싱이 보장되지 않음.
-
데이터 패턴의 단일성: 모든 행렬은 무작위 값으로 채워진 조밀 행렬(Dense Matrix)을 가정함. 실제 시스템에서는 데이터가 특정 패턴을 가지거나 대부분이 0인 희소 행렬(Sparse Matrix)인 경우가 많으며, 이 경우 다른 접근 방식과 최적화 모델이 요구됨.