행렬 곱셈에 대한 병렬 표현방법

정방행렬 $A,B\in\mathbb{R}^{N\times N}$를 곱하는것을 쿠다로 구현하기 이전에 병렬로 연산하는 방법에 대해서 정리를 하면 다음과 같음. 먼저 각 행렬을 $p\times p$개의 사이즈를 가지는 부분행렬로 나눈 다음에 각각 구간의 곱을 구한다음에 합을 구하는게 병렬처리에 유리함

1. 블록 분할 형태

• 전체 $A$는 $p\times p$개의 블록으로 구성
• 각 블록 $A_{ij}$는 $m\times m$ 크기의 부분 정방행렬

예시: $p=2$, $m=2$인 경우

동일 한 형식으로 B도 표현하면 아래와같이 표현됨

2. 블록 행렬곱(Block Matrix Multiplication)

두 정방행렬 $A,B\in\mathbb{R}^{(pm)\times(pm)}$를 같은 방식으로 분할하면
곱 $C = A B$의 각 블록도 다음과 같이 표현할 수 있음

$C_{ij} = \sum_{k=1}^{p} A_{\,i k}\;B_{\,k j}, \quad i,j = 1, \dots, p$

즉,

• $C_{11} = A_{11}B_{11} + A_{12}B_{21} + \cdots + A_{1p}B_{p1}$
• $C_{12} = A_{11}B_{12} + A_{12}B_{22} + \cdots + A_{1p}B_{p2}$
• $\dots$
• $C_{pp} = A_{p1}B_{1p} + A_{p2}B_{2p} + \cdots + A_{pp}B_{pp}$

위 수식은 전체 행렬곱을 부분 정방행렬 간 곱과 덧셈으로 표현이 가능함. 좀더 일반적인 형태로 표현 하면 다음과같이 나타낼수 있음

3. CUDA 병렬연산과의 관계성

1. 그리드(Grid) 분할

   • 전체 행렬을 $p\times p$ 그리드로 나누면 ,각 그리드 셀은 크기 $m\times m$인 부분정방행렬(블록)으로 표현 가능
     $N = p \times m,\quad A = \begin{bmatrix} A_{11} & \cdots & A_{1p}\\ \vdots & \ddots & \vdots\\ A_{p1} & \cdots & A_{pp} \end{bmatrix},\quad A_{ij}\in\mathbb{R}^{m\times m}$

2. 블록 단위 연산

   • 각 블록 $(i,j)$에 대해 독립적으로 다음 수식을 계산
     $C_{ij} \;=\; \sum_{k=1}^{p} A_{ik}\,\;B_{kj}$
   • 이 연산은 GPU의 각 스레드 블록이 “부분행렬 $\,A_{ik}$·$B_{kj}$ 내적 → 합산”을 담당하도록 매핑됩니다.

3. 병렬 처리

   • $p\times p$ 블록 모두를 병렬로 실행하여 전체 $C=AB$를 완성
   • 타일링(shared memory) 기법을 써서 각 블록 내에서 메모리 접근을 최적화하고, 글로벌 메모리 트래픽을 연산속도를 빠르게 구현가능