폰 노이만 병목과 시스톨릭 배열

25% 적음

행렬 원소의 논리적 이동 횟수. 격자 6K회, 단일 보드 8K회

295~326배

격자가 단일 보드보다 느렸던 정도

약 417배

이동 한 번에 드는 비용 차이. 3.23 µs 대 1,346.9 µs

1.0%

격자의 처리 시간 중 실제 계산에 쓰인 비율

AI 관련주가 오를 때 에너지 관련주도 같이 오르는 걸 보고, AI와 전력이 무슨 관계인지 찾아봤습니다. LLM에 질문 하나를 보내는 데 드는 전력이 일반 검색 한 번보다 훨씬 크다는 연구가 있었고, AI 서비스가 늘수록 데이터센터 전력 수요도 빠르게 늘고 있었습니다.

딥러닝은 입력과 가중치 행렬의 곱을 반복하며 학습하고 추론합니다. 모델이 커질수록 행렬도 커지고 연산 횟수도 빠르게 늘어납니다. 여기에 대부분의 컴퓨터가 쓰는 폰 노이만 구조는 같은 데이터를 메모리에서 반복해서 읽어 와야 한다는 구조적 비효율을 갖고 있습니다.

시스톨릭 배열은 데이터를 매번 메모리에서 가져오는 대신 처리 소자끼리 직접 주고받으며 재사용하는 구조입니다. 두 방식을 아두이노로 직접 구현해서, 시스톨릭 배열의 이점이 실제로 어떤 조건에서 성립하는지 확인하려고 했습니다.

행렬곱과 MAC 연산

M×K 행렬 A와 K×P 행렬 B를 곱하면 M×P 행렬 C가 나옵니다. 공통 차원 K를 내부 차원이라고 부릅니다. C의 원소 하나는 A의 한 행과 B의 한 열을 원소끼리 곱해 더한 값이고, 이 과정은 곱한 값을 부분합에 계속 더하는 MAC(Multiply-Accumulate) 연산의 반복입니다.

부분합 ← 부분합 + A × B

원소 하나를 구하려면 곱셈 K번과 덧셈 K−1번, 합쳐 2K−1번의 연산이 필요합니다. 전체로는 약 2×M×K×P번이고, 정사각행렬이면 n³에 비례해서 각 차원이 2배가 되면 연산량은 8배가 됩니다.

폰 노이만 병목

폰 노이만 구조는 프로그램과 데이터를 같은 주기억장치에 두고, CPU가 필요한 명령어와 데이터를 메모리에서 차례로 읽어 와 처리합니다. 병목이 생기는 이유는 두 가지입니다.

• 단일 버스: CPU와 메모리가 물리적으로 떨어져 있고 하나의 시스템 버스를 공유합니다. 그래서 명령어와 데이터가 동시에 오갈 수 없습니다.
• 메모리 장벽(Memory Wall): CPU 연산 속도는 빠르게 좋아졌지만 메모리 접근 지연은 훨씬 느리게 개선됐습니다. 그래서 CPU가 데이터를 기다리며 노는 시간이 늘어납니다.

행렬곱에서는 연산마다 원소를 메모리에서 읽어야 하므로 처리 비용도 연산 횟수처럼 K³ 규모로 늘어납니다.

시스톨릭 배열

1978년 카네기멜런 대학의 H. T. Kung과 Charles Leiserson이 제안한 구조입니다. 이름은 심장이 규칙적으로 수축해 혈액을 내보내는 동작(systole)에서 왔습니다. PE(Processing Element)라는 단순한 처리 소자를 격자로 늘어놓고, 각 PE가 클럭에 맞춰 동시에 MAC 연산을 한 뒤 결과를 이웃 PE로 넘깁니다. 각 PE는 부분합이나 입력값을 담아 둘 로컬 메모리를 갖습니다.

핵심은 데이터 재사용입니다. 폰 노이만 구조에서는 결과 원소 K²개를 계산하는 동안 같은 행과 열을 K번씩 다시 읽습니다. 시스톨릭 배열에서는 한 번 격자에 들어온 원소가 여러 PE를 지나며 계속 연산에 쓰입니다.

데이터 흐름 방식은 여러 가지가 있는데, AI 연산에서 많이 쓰이는 것은 출력 고정형(OS, Output Stationary)과 가중치 고정형(WS, Weight Stationary)입니다. OS에서는 각 PE가 맡은 출력의 부분합을 붙잡고 있고, 입력값이 PE를 지나갑니다. 저장소에는 OS와 WS 코드가 모두 있지만, 이 연구의 측정과 결과는 OS 방식 기준입니다.

이론적 클럭 수와 한계

Raja(2024)는 시스톨릭 배열이 행렬곱을 끝내는 데 필요한 총 클럭 사이클 수를 다음과 같이 제시했습니다. S_R은 격자의 행 수, S_C는 열 수, T는 내부 차원입니다.

N_C = 2·S_R + S_C + T − 2

식에서 T를 뺀 나머지 항은 데이터가 격자를 채우고 빠져나가는 동안 실제 연산이 없는 파이프라인 지연입니다. 행렬이 격자보다 작을수록 이 지연의 비중이 커집니다. 또 행렬이 격자보다 크면 행렬을 격자 크기로 나눠 차례로 밀어 넣는 타일링이 필요합니다. 이 실험의 2×2 격자도 더 큰 행렬을 처리하려고 파이프라인 타일링을 코드에 넣었습니다. 결국 시스톨릭 배열의 우위는 조건에 따라 달라집니다.

같은 행렬곱을 두 가지 구조로 처리하고 처리 시간과 데이터 이동 횟수를 비교했습니다. 두 구조가 처리하는 행렬과 연산량은 완전히 같습니다.

격자의 크기가 2×2로 고정돼 있어서 출력 행렬도 2×2로 두고 내부 차원 K만 바꿨습니다. A는 2×K, B는 K×2 행렬입니다.

Arduino Nano 호환보드(SZH-EK025, ATmega328P) 다섯 대를 썼습니다. 네 대는 2×2 격자의 PE, 한 대는 대조군입니다. 전원은 전원 공급형 USB 허브로 한꺼번에 넣고, 다섯 보드의 GND를 브레드보드 공통 레일에 묶어 신호 기준을 맞췄습니다. 결과와 처리 시간은 PE(1,1)에 연결한 16×2 I2C LCD로 확인합니다.

각 연결은 클럭선과 데이터선 두 가닥을 한 쌍으로 씁니다. D2·D4는 가로 링크, D3·D5는 세로 링크입니다. D6는 PE(0,0)과 PE(1,1)을 직접 잇는 시간 측정용 신호선입니다.

ATmega328P는 명령어 메모리와 데이터 메모리가 물리적으로 나뉜 수정 하버드 구조라서, 칩 수준에서 폰 노이만 병목을 그대로 재현할 수는 없습니다. 그래서 전역 변수 BUS를 두고, 행렬 원소에 대한 모든 접근이 busRead()를 거치게 했습니다. 하나의 통로를 공유하는 폰 노이만 구조의 동작을 소프트웨어로 흉내 내면서, 접근 횟수도 정확히 셀 수 있습니다.

volatile int BUS = 0;          // 공유 버스

inline int busRead(int value) {
  BUS = value;                 // 모든 접근은 이 통로를 거침
  accessCount++;
  return BUS;
}

출력 고정형(OS) 데이터 흐름을 구현했습니다. 각 PE는 맡은 출력 원소의 부분합을 끝까지 들고 있고, A의 원소는 가로로, B의 원소는 세로로 격자를 지나갑니다.

시간 단계 k마다 PE(0,0)은 자기 MAC 연산을 한 뒤 A[0][k]와 B[k][1]을 오른쪽으로 보내고, 스큐 시간만큼 기다린 다음 B[k][0]과 A[1][k]를 아래로 보냅니다. 스큐는 4,000 µs로 정했습니다. PE(0,1)이 데이터를 받아 PE(1,1)로 넘기기에 충분한 시간이라서, PE(1,1)은 폴링 없이 정해진 순서대로 두 방향의 신호를 받을 수 있습니다.

행렬 크기를 바꿀 때는 PE(0,0)의 코드만 바꿨습니다. 나머지 세 PE는 종료 신호가 올 때까지 반복하는 구조라서 K와 상관없이 동작합니다.

처리 시간

두 구조 모두 첫 MAC 연산이 시작될 때부터 마지막 MAC 연산이 끝날 때까지를 쟀습니다.

• 대조군: 3중 반복문 진입 직전과 종료 직후에 micros()로 시각을 기록합니다.
• 실험군: PE(0,0)이 첫 MAC 직전에 D6를 HIGH로 올리고, PE(1,1)이 그 신호를 감지한 순간을 시작 시각으로 기록합니다. 종료 시각은 PE(1,1)이 MAC을 끝낼 때마다 갱신해서 마지막 MAC이 끝난 시점이 남게 했습니다. 종료 신호가 격자 전체로 퍼지는 시간은 측정에서 빠집니다.

데이터 이동 횟수

두 구조에서 이동의 물리적 실체가 달라서, 행렬 원소 하나가 한 지점에서 다른 지점으로 옮겨지는 논리적 이동을 공통 기준으로 삼았습니다.

• 대조군: 반복마다 A와 B의 원소를 BUS로 한 번씩 읽으므로 2×2×K×2 = 8K회입니다.
• 실험군: 시간 단계마다 PE(0,0)에서 오른쪽으로 2개(A[0][k], B[k][1]), 아래로 2개(B[k][0], A[1][k]), PE(0,1)에서 PE(1,1)로 1개(B[k][1]), PE(1,0)에서 PE(1,1)로 1개(A[1][k])가 이동합니다. 단계당 6개라서 6K회입니다.

절차

조건마다 PE(0,0)의 리셋 버튼으로 실험을 시작하고, LCD와 시리얼 모니터로 결과 행렬과 처리 시간을 기록했습니다. 모든 조건을 5회 이상 반복해 평균과 표준편차를 냈습니다.

최소제곱 직선으로 근사하면 다음과 같습니다.

• 단일 보드: y = 25.8K + 4.0 (R² = 0.9968)
• 2×2 격자: y = 8,081.1K + 775.6 (R² = 0.99999)

기울기 비는 8,081.1 ÷ 25.8 = 313.2이고 절편도 격자 쪽이 큽니다. 그래서 두 직선은 K가 아무리 커져도 만나지 않습니다. 이 실험 환경에서는 시스톨릭 배열이 단일 보드를 앞지르는 지점이 없습니다.

이론값과도 비교했습니다. 2×2 격자에 Raja(2024)의 식을 넣으면 N_C = K + 4이므로 K = 2, 4, 6, 8에서 각각 6, 8, 10, 12사이클입니다. 실측 시간을 16 MHz 클럭 수로 바꾸면 271,558~1,047,424사이클로, 네다섯 자릿수 이상 큽니다. 이론은 PE 간 전달을 1클럭으로 보는데, 이 구현에서는 전달이 마이크로초 단위의 외부 GPIO 통신이기 때문입니다.

처리 시간과 반대로, 이동 횟수는 격자가 모든 구간에서 25% 적었습니다. 단일 보드는 원소 하나를 계산할 때마다 필요한 값을 새로 읽어 8K회가 필요합니다. 격자에서는 한 번 들어온 원소가 여러 PE를 지나며 계속 쓰여서 6K회면 충분합니다.

예를 들어 PE(0,0)이 아래로 보낸 A[1][k]는 PE(1,0)에서 한 번 쓰이고, 다시 PE(1,1)로 넘어가 한 번 더 쓰입니다. 시스톨릭 배열의 데이터 재사용이 실제로 일어났다는 뜻입니다.

이동은 25% 적은데 시간은 300배 넘게 걸린 이유는 이동 한 번의 비용에 있습니다. 회귀식의 기울기를 K당 이동 횟수로 나눠 비교했습니다.

• 단일 보드: 25.8 ÷ 8 = 약 3.23 µs
• 2×2 격자: 8,081.1 ÷ 6 = 약 1,346.9 µs

격자는 이동 횟수를 25% 줄였지만 이동 한 번에 약 417배를 치러서, 전체로는 약 313배 손해입니다.

게다가 스큐 대기는 연산이 전혀 없는 순수한 대기 시간인데 전체의 49.5%를 차지합니다. 통신과 대기를 빼면 실제 계산에 쓰인 시간은 1.0%뿐입니다.

시스톨릭 배열의 성능은 PE 사이의 물리적 거리에 달려 있습니다. 실제 가속기처럼 많은 PE를 한 칩 안에 넣으면 PE 사이 전달은 칩 내부 배선의 매우 짧은 지연으로 끝납니다. 이 실험은 그 전달을 보드 사이의 핀 통신으로 바꾼 셈이고, 그래서 이런 결과가 나왔습니다. PE를 왜 한 칩 안에 모아야 하는지를 거꾸로 보여 주는 결과입니다.

1. ATmega328P는 수정 하버드 구조라서, 대조군은 칩 수준의 폰 노이만 병목이 아니라 공유 통로를 거치는 순차 접근을 소프트웨어로 흉내 낸 것입니다. 대조군의 이동당 비용 3.23 µs에는 반복문 제어 시간도 들어 있어서 실제 메모리 지연과 바로 비교할 수 없습니다.
2. 두 구조에서 이동의 실체가 다릅니다. 대조군은 칩 내부 변수 접근이고 실험군은 외부 통신입니다. 그래서 이동 횟수 비교는 데이터 재사용이라는 구조적 특성을 확인하는 데만 쓰고, 성능 지표로 읽으면 안 됩니다.
3. 실제 시스톨릭 배열처럼 데이터를 한 클럭씩 어긋나게 연속으로 넣기 어려워서, 송신 사이에 고정 대기 시간을 넣어 수신 순서를 보장하는 단순한 방식으로 스큐를 구현했습니다.
4. 격자가 2×2라서 출력 행렬도 2×2로 고정되고, 내부 차원 K만 바꿀 수 있었습니다.

1. 데이터 재사용은 실제로 일어났습니다. 격자의 이동 횟수는 6K회로 단일 보드의 8K회보다 모든 구간에서 25% 적었습니다. 한 번 들어온 원소가 여러 PE에서 쓰여 같은 값을 다시 읽을 필요가 없다는 예측이 맞았습니다.
2. 그래도 처리 시간은 300배 넘게 느렸습니다. 이동 한 번의 비용이 약 417배 비싸서, 이동 횟수 25% 감소로는 메울 수 없었습니다.
3. 시스톨릭 배열의 성능은 집적도에 달려 있습니다. 시스톨릭 배열 자체가 비효율적이라는 뜻이 아닙니다. PE 사이 전달 비용이 메모리 접근 비용보다 충분히 낮을 때만 이점이 생기고, 이 조건이 무너지면 이론적 우위도 사라집니다.

논문: doi.org/10.5281/zenodo.22038219
실험 코드: github.com/regx64/Arduino-repo

1. T. Raja, “Systolic Array Data Flows for Efficient Matrix Multiplication in Deep Neural Networks,” 2024. arXiv:2410.22595
2. A. de Vries, “The Growing Energy Footprint of Artificial Intelligence,” Joule, vol. 7, no. 10, pp. 2191–2194, 2023.
3. Google Cloud, TPU 아키텍처
4. 위키백과, 폰 노이만 구조
5. 위키백과, 하버드 아키텍처