612. 행렬 분해 (LU, QR) 전용 병렬 구조

핵심 인사이트 (3줄 요약)

본질: 행렬 분해 전용 병렬 구조는 LU 분해 (Lower-Upper Decomposition)와 QR 분해 (QR Decomposition)를 처리 요소 (Processing Element, PE) 배열의 국소 데이터 흐름으로 바꿔, 선형대수의 단계적 소거 과정을 하드웨어 파이프라인으로 구현한 아키텍처다.

가치: 다중 입출력 (Multiple-Input Multiple-Output, MIMO) 검출, 최소제곱 추정, 레이더 신호 처리처럼 짧은 시간 안에 반복적으로 행렬을 풀어야 하는 시스템에서, 전용 배열은 중앙처리장치나 범용 그래픽 처리장치보다 훨씬 낮은 지연으로 결과를 낸다.

판단 포인트: 행렬 성질과 수치 안정성에 따라 LU, QR, 촐레스키를 구분하고, 고정소수점·부동소수점·혼합정밀도, 피벗 처리, 온칩 메모리 재사용을 함께 설계해야 진짜 병렬화 이득이 나온다.

Ⅰ. 개요 및 필요성

행렬 분해는 복잡한 행렬 문제를 더 다루기 쉬운 삼각 행렬 구조로 바꾸는 핵심 단계다. 역행렬 계산, 최소제곱 해, 선형 시스템 해법 대부분은 직접 문제를 푸는 것보다 먼저 분해를 수행한 뒤 전방/후방 대입을 하는 편이 안정적이고 효율적이다. 그래서 통신, 로봇, 제어, 레이더, 자율주행 센서 융합에서 행렬 분해는 숨은 공용 엔진처럼 반복적으로 호출된다.

문제는 계산량과 지연이다. n × n 행렬 분해는 기본적으로 O(n^3) 연산을 요구하고, 단계마다 앞선 피벗이나 회전 계수가 다음 연산에 영향을 주므로 데이터 의존성이 강하다. 대규모 행렬 하나를 오래 계산하는 과학 계산도 어렵지만, 더 까다로운 경우는 8×8, 16×16, 64×64 같은 중간 크기 행렬을 직교 주파수 분할 다중화 (Orthogonal Frequency Division Multiplexing, OFDM) 심볼이나 센서 프레임마다 연속으로 풀어야 하는 실시간 시스템이다.

이때 범용 프로세서는 메모리 왕복과 제어 오버헤드가 크고, 행렬곱에 특화된 텐서 코어도 삼각화 과정의 순차 의존성을 완전히 제거하지 못한다. 그래서 입력 데이터가 흐르면서 바로 소거·회전·업데이트가 일어나는 전용 병렬 구조가 필요해진다.

📢 섹션 요약 비유: 행렬 분해는 엉킨 실타래를 한 번에 자르는 일이 아니라, 어디를 먼저 잡아당겨야 전체가 풀리는지 순서를 지켜 정리하는 일과 같다. 전용 하드웨어는 그 순서를 몸으로 기억한 숙련공들이다.

Ⅱ. 아키텍처 및 핵심 원리

행렬 분해 하드웨어의 대표 구조는 시스톨릭 어레이 (Systolic Array)다. 데이터가 칩 위를 한 방향으로 흐르고, 각 PE는 자신에게 온 값에 작은 연산만 수행한 뒤 결과와 보조 계수를 이웃 PE로 넘긴다. 핵심은 "중앙 제어기가 모든 값을 다 만지는 구조"가 아니라, "근처 이웃끼리만 전달하는 구조"라는 점이다.

┌────────────────────────────────────────────────────────────────────────────┐
│ A stream -> [PE00] -> [PE01] -> [PE02] -> ...                            │
│              │         │         │                                         │
│              ▼         ▼         ▼                                         │
│            [PE10] -> [PE11] -> [PE12] -> ...                              │
│              │         │         │                                         │
│              ▼         ▼         ▼                                         │
│            [PE20] -> [PE21] -> [PE22] -> ...                              │
│                                                                            │
│ diagonal PE: pivot / rotation factor generation                            │
│ off-diagonal PE: update, eliminate, accumulate                             │
└────────────────────────────────────────────────────────────────────────────┘

LU 분해에서는 대각선 PE가 피벗 값과 역수를 만들고, 아래쪽 PE들이 소거 계수를 이용해 하부 행을 갱신한다. QR 분해에서는 기븐스 회전 (Givens Rotation)이나 하우스홀더 변환을 이용해 비대각 성분을 0으로 만든다. 하드웨어에서는 나눗셈과 제곱근이 비싸므로, QR 구현에서 코드릭 (Coordinate Rotation Digital Computer, CORDIC)을 써서 시프트와 덧셈만으로 회전 계수를 만드는 경우가 많다.

구성 블록	역할	설계 포인트
대각선 PE	피벗/회전 파라미터 생성	지연이 길면 전체 배열이 막힌다
내부 PE	행/열 업데이트	연산 지연 균형과 로컬 버퍼가 중요하다
온칩 스크래치패드	행렬 블록 재사용	외부 메모리 왕복을 줄여야 병렬 이득이 산다
파이프라인 레지스터	주파수 확보	지나치게 깊으면 제어와 초기 지연이 늘어난다

좋은 구조는 계산만 빠른 것이 아니라 데이터 이동도 짧다. 행렬 분해는 같은 값을 여러 단계에서 반복 참조하므로, 피벗·회전 계수·부분 행렬을 온칩에 머물게 해야 한다. 결국 성능은 산술기 수보다도 "PE 간 국소 통신과 온칩 재사용을 얼마나 잘 설계했는가"에서 크게 갈린다.

📢 섹션 요약 비유: 시스톨릭 어레이는 긴 작업대를 따라 부품이 흘러가고, 각 작업자가 자기 자리에서 필요한 동작만 정확히 수행하는 조립 라인과 같다. 멀리 뛰어다니지 않아야 진짜 빠르다.

Ⅲ. 비교 및 연결

행렬 분해 하드웨어는 어떤 알고리즘을 택하느냐에 따라 구조와 안정성이 달라진다. 연산 수만 보고 LU를 택하면 불안정한 행렬에서 피벗 문제가 생길 수 있고, 무조건 QR만 고르면 연산량과 면적이 늘어난다. 그래서 알고리즘 비교가 곧 아키텍처 비교다.

항목	LU 분해	QR 분해	촐레스키 분해
적용 행렬	일반 행렬	일반 행렬	대칭 양의 정부호 (Symmetric Positive Definite, SPD)
수치 안정성	피벗 처리 품질에 크게 좌우	높음	높음
하드웨어 부담	나눗셈/피벗 관리가 부담	CORDIC 기반 회전 구현 가능	연산량이 가장 적지만 적용 범위 제한
대표 용도	선형 시스템 해법, 역행렬	MIMO 검출, 최소제곱, 레이더	공분산, 최적화, 추정

GPU와의 관계도 중요하다. 범용 그래픽 처리장치 (Graphics Processing Unit, GPU)는 큰 행렬곱에는 강하지만, 작은 행렬을 빠르게 연속 처리하는 실시간 분해에서는 커널 런치와 메모리 이동 오버헤드가 커질 수 있다. 그래서 실제 시스템은 행렬곱은 GPU/텐서 코어가, 행렬 분해와 삼각 해법은 FPGA나 전용 가속기가 맡는 이기종 구조를 자주 택한다.

또한 하우스홀더는 블록 알고리즘과 기본 선형대수 서브프로그램 (Basic Linear Algebra Subprograms, BLAS) 기반 병렬화에 잘 맞고, 기븐스는 국소 회전이라 스트리밍 하드웨어에 잘 맞는다. 즉 QR 하나만 봐도 소프트웨어 친화적 변형과 하드웨어 친화적 변형이 다를 수 있다.

📢 섹션 요약 비유: LU, QR, 촐레스키는 같은 산을 오르는 서로 다른 길과 같다. 가장 짧은 길이 항상 안전한 길은 아니고, 바위가 많은 날씨에서는 조금 돌아가도 튼튼한 길이 더 낫다.

Ⅳ. 실무 적용 및 기술사 판단

실무 의사결정의 첫 질문은 "행렬이 어떤 성질을 갖는가"이다. 행렬이 SPD라면 촐레스키가 연산량이 가장 적고 구조도 단순하다. 일반 행렬인데 조건수가 나쁘거나 피벗 변동이 심하면, LU보다 QR이 안정적이다. 반대로 행렬 성질이 양호하고 지연·면적이 최우선이면 LU가 더 경제적일 수 있다.

두 번째 질문은 정밀도다. 무선 기지국이나 레이더 전처리처럼 입력 스케일이 관리되는 환경은 12~16비트 고정소수점이나 블록 부동소수점으로도 충분한 경우가 많다. 하지만 항법, 과학 계산, 고조건수 문제는 32비트 부동소수점 또는 혼합 정밀도에 반복 보정(iterative refinement)을 붙여야 한다. 즉 산술 포맷 선택은 면적이 아니라 수치 안정성 계약이다.

적용 체크리스트

행렬 성질이 일반/대칭/양의 정부호인지 사전에 구분했는가?
LU라면 부분 피벗팅 전략과 그에 따른 데이터 이동 비용을 반영했는가?
QR라면 CORDIC 반복 횟수와 정밀도 손실을 검증했는가?
외부 메모리 대역폭이 아니라 온칩 버퍼 재사용으로 대부분의 데이터를 처리하도록 설계했는가?
잔차 ||A - QR|| 또는 ||PA - LU|| 기준으로 수치 검증을 수행했는가?

피해야 할 안티패턴

모든 PE가 중앙 메모리와 직접 통신하게 만들어 배선을 폭증시키는 구조
피벗과 정밀도 이슈를 무시하고 단순 연산량만 보고 알고리즘을 고르는 판단
작은 행렬 실시간 처리 문제인데도 GPU 대배치 처리 방식만 모방하는 설계
📢 섹션 요약 비유: 행렬 분해 가속기 설계는 공연장 좌석 배치와 같다. 누가 어디에 앉아야 가장 적게 움직이고도 공연이 매끄럽게 보이는지 정해야 하지, 의자 수만 늘린다고 해결되지는 않는다.

Ⅴ. 기대효과 및 결론

행렬 분해 전용 병렬 구조의 가장 큰 효과는 실시간 선형대수의 지연 예측 가능성을 높인다는 점이다. 동일 크기 행렬이 반복되는 시스템에서는 한 번 배열을 잘 짜 두면, 입력이 들어오는 즉시 일정한 흐름으로 소거와 회전이 일어나므로 응답 시간이 매우 안정적이다. 이는 MIMO 검출, 레이더 추적, 칼만 필터 같은 제어·통신 시스템에서 특히 중요하다.

한계도 분명하다. 가변 크기 행렬, 드문 실행, 높은 동적 범위 문제에서는 전용 배열의 활용률이 떨어질 수 있다. 또한 피벗 처리와 혼합 정밀도 제어, 버퍼 관리가 미흡하면 산술 유닛을 많이 깔아도 성능과 정확도가 동시에 무너질 수 있다.

결론적으로 행렬 분해 하드웨어는 "행렬곱을 많이 하는 칩"이 아니라, 삼각화와 의존성 있는 선형대수 과정을 데이터 흐름으로 바꿔 버리는 구조적 사고다. 이 점을 기억하면 LU, QR, 촐레스키와 시스톨릭 어레이, CORDIC, 혼합 정밀도가 왜 한 문맥에서 함께 논의되는지 자연스럽게 이어진다.

📢 섹션 요약 비유: 좋은 행렬 분해 엔진은 복잡한 실타래를 그냥 힘으로 당기지 않는다. 어느 실을 먼저 풀고 어디로 넘길지 알고 있는 숙련된 정리 로봇과 같다.

📌 관련 개념 맵

개념	연결 포인트
시스톨릭 어레이 (Systolic Array)	행렬 분해를 국소 통신 중심의 스트리밍 계산으로 바꾸는 대표 구조다.
CORDIC	QR 분해에서 회전과 벡터 정규화를 곱셈기 없이 처리하게 해 준다.
Pivoting	LU 안정성을 좌우하지만 데이터 이동과 제어 복잡도를 키우는 핵심 요소다.
Cholesky Decomposition	SPD 행렬에서 더 적은 연산으로 분해 가능한 특수 해법이다.
Mixed Precision	처리량과 수치 정확도를 동시에 맞추기 위해 자주 쓰이는 현실적 절충안이다.
On-Chip Scratchpad	외부 메모리 병목 없이 행렬 블록을 재사용하게 하는 실질적 성능 기반이다.

📈 관련 키워드 및 발전 흐름도

가우스 소거 기반 선형대수
        │
        ▼
LU / 촐레스키 전용 배열
        │
        ▼
Givens-QR · CORDIC 기반 구조
        │
        ▼
시스톨릭 어레이 · 온칩 버퍼 최적화
        │
        ▼
혼합 정밀도 · 반복 보정
        │
        ▼
MIMO · 레이더 · 로보틱스 실시간 가속기

이 흐름은 고전 수치해석 알고리즘이 하드웨어 데이터플로 구조로 번역되고, 다시 실시간 도메인 특화 가속기로 발전하는 맥락을 보여 준다.

👶 어린이를 위한 3줄 비유 설명

아주 복잡하게 섞인 숫자 블록을 줄 맞춰 다시 정리하는 로봇 공장이라고 생각하면 돼요.
로봇들은 서로 가까운 친구에게만 블록을 넘기면서 차근차근 정리해요.
그래서 큰 계산도 오래 기다리지 않고 빨리 답을 만들 수 있어요.