6.157 실시간 로봇 제어를 위한 연산 최적화

1. 실시간 제약 조건의 정의

실시간 시스템(real-time system)이란 정해진 시간 기한(deadline) 내에 연산을 완료하여야 하는 시스템을 말한다. 로봇 제어에서 실시간 제약은 제어 루프의 주기(control loop period)로 정의되며, 일반적으로 다음과 같은 범위를 가진다.

제어 주기 T 내에 모든 연산(센서 읽기, 상태 추정, 제어 법칙 계산, 액추에이터 명령 출력)을 완료하여야 하며, 이 중 행렬 연산이 차지하는 시간을 T_{\text{mat}}라 하면 T_{\text{mat}} \ll T를 만족하여야 한다.

2. 연산량 절감 전략

2.1 대칭성과 희소성의 활용

로봇 동역학에서 나타나는 행렬은 특별한 구조를 가지며, 이를 활용하면 연산량을 크게 줄일 수 있다.

관성 행렬의 대칭성: 관성 행렬 \mathbf{M}(\mathbf{q}) \in \mathbb{R}^{n \times n}은 대칭 양의 정부호이므로, 저장 시 상삼각(또는 하삼각) 부분만 필요하다. n(n+1)/2개의 원소만 계산하고 저장하면 된다. Cholesky 분해의 계산량도 LU 분해의 절반인 n^3/3 FLOP이다.

자코비안의 구조: 6자유도 로봇의 자코비안 \mathbf{J} \in \mathbb{R}^{6 \times n}에서, 회전 관절의 경우 각 열은 다음과 같은 구조를 가진다.

\mathbf{J}_i = \begin{bmatrix} \mathbf{z}_{i-1} \times (\mathbf{p}_e - \mathbf{p}_{i-1}) \\ \mathbf{z}_{i-1} \end{bmatrix}

여기서 \mathbf{z}_{i-1}은 관절 축 방향, \mathbf{p}_e는 말단 위치, \mathbf{p}_{i-1}은 관절 위치이다. 이 구조를 이용하면 순방향 기구학 계산 과정에서 자코비안을 동시에 구성할 수 있어 별도의 연산이 불필요하다.

재귀적 알고리즘의 활용

대규모 행렬을 명시적으로 형성하고 분해하는 대신, 재귀적 알고리즘을 사용하면 연산량을 극적으로 줄일 수 있다.

RNEA(Recursive Newton-Euler Algorithm)는 기저에서 말단으로의 전방 재귀(forward recursion)와 말단에서 기저로의 후방 재귀(backward recursion)로 구성되며, 각 링크에서 일정한 수의 연산만 수행하므로 \mathcal{O}(n) 복잡도를 달성한다.

행렬-벡터 곱의 회피

실시간 제어에서 가능한 한 행렬-벡터 곱 자체를 회피하는 것이 가장 효과적인 최적화이다. 예를 들어, 역동역학에서 \boldsymbol{\tau} = \mathbf{M}(\mathbf{q})\ddot{\mathbf{q}} + \mathbf{C}(\mathbf{q}, \dot{\mathbf{q}})\dot{\mathbf{q}} + \mathbf{g}(\mathbf{q})를 계산할 때, 각 항을 개별 행렬로 형성한 후 곱하는 대신 RNEA를 사용하면 단일 재귀 순회로 \boldsymbol{\tau}를 직접 얻을 수 있다. 이는 행렬 형성의 \mathcal{O}(n^2)와 곱셈의 \mathcal{O}(n^2)를 모두 \mathcal{O}(n)으로 줄인다.

수치 정밀도와 연산 효율의 균형

단정밀도와 배정밀도

IEEE 754 부동소수점 표준에서 단정밀도(single precision, FP32)는 32비트, 배정밀도(double precision, FP64)는 64비트를 사용한다.

단정밀도를 사용하면 메모리 사용량과 대역폭이 절반으로 줄어들고, 많은 프로세서에서 FP32 연산이 FP64보다 2배 이상 빠르다. 로봇 제어에서 관절 각도 분해능이 10^{-4} rad 수준이라면, FP32의 7자리 유효 숫자로도 충분한 경우가 많다.

그러나 조건수가 큰 시스템(예: 특이 자세 근처의 자코비안, 강성 시뮬레이션)에서는 FP32의 정밀도가 부족할 수 있으므로, 혼합 정밀도(mixed precision) 전략이 유용하다. 핵심 풀이(Cholesky 분해, 삼각 풀이)는 FP64로 수행하고, 잔차 계산이나 행렬-벡터 곱은 FP32로 수행하는 반복적 정밀도 향상(iterative refinement) 기법이 대표적이다.

\mathbf{x}_0 = \text{solve}_{FP32}(\mathbf{A}, \mathbf{b}), \quad \mathbf{r} = \mathbf{b} - \mathbf{A}\mathbf{x}_0 \; (FP64), \quad \mathbf{d} = \text{solve}_{FP32}(\mathbf{A}, \mathbf{r}), \quad \mathbf{x}_1 = \mathbf{x}_0 + \mathbf{d}

2.2 고정소수점 연산

임베디드 제어기에서 부동소수점 유닛(FPU)이 없거나 느린 경우, 고정소수점(fixed-point) 연산을 사용할 수 있다. Q_{m.f} 표기법에서 m비트의 정수부와 f비트의 소수부를 가지는 고정소수점 수는 다음과 같이 실수를 근사한다.

x_{\text{fixed}} = \text{round}(x \cdot 2^f)

고정소수점 행렬 곱셈에서 각 원소의 곱은 정수 곱셈과 비트 시프트로 수행된다.

c_{ij} = \sum_k \frac{a_{ik} \cdot b_{kj}}{2^f}

이 방식은 정수 연산만을 사용하므로 FPU가 없는 마이크로컨트롤러에서도 효율적으로 수행할 수 있으나, 동적 범위와 정밀도가 제한되므로 스케일링 설계에 주의가 필요하다.

3. 룩업 테이블과 사전 계산

3.1 삼각 함수의 룩업 테이블

순방향 기구학에서 DH(Denavit-Hartenberg) 변환 행렬은 \sin\theta_i와 \cos\theta_i를 포함한다. 삼각 함수의 소프트웨어 계산은 수십~수백 클럭 사이클이 소요될 수 있으므로, 사전에 구축한 룩업 테이블(lookup table)을 사용하면 상수 시간에 근사값을 얻을 수 있다.

관절 각도의 범위 [0, 2\pi)를 N개의 구간으로 등분하고 각 구간의 삼각 함수값을 저장하면, 테이블 크기는 2N (sin과 cos)이고 최대 근사 오차는 다음과 같다.

\vert \epsilon \vert \leq \frac{\pi^2}{2N^2}

N = 4096이면 최대 오차는 약 3 \times 10^{-7} rad 수준으로, 대부분의 제어 응용에 충분하다. 선형 보간을 추가하면 같은 테이블 크기에서 오차를 더욱 줄일 수 있다.

구성 의존 행렬의 사전 계산

로봇의 관성 행렬 \mathbf{M}(\mathbf{q})는 관절 변수 \mathbf{q}에 대한 연속 함수이다. 작업 공간의 특정 영역에서 자주 동작하는 로봇의 경우, 해당 영역의 격자점에서 \mathbf{M}과 그 Cholesky 분해를 사전에 계산하여 저장한 후, 실시간에서는 보간(interpolation)으로 근사하는 방법이 있다.

n자유도 로봇에서 각 관절을 N_g개의 격자점으로 이산화하면 총 N_g^n개의 격자점이 필요하며, 각 점에서 n(n+1)/2개의 행렬 원소를 저장해야 한다. 자유도가 높으면 차원의 저주(curse of dimensionality)로 인해 이 방법이 비실용적이 되므로, 3자유도 이하의 서브시스템에 국한하여 적용하는 것이 현실적이다.

연산 스케줄링과 파이프라이닝

제어 루프의 시간 분배

실시간 제어 루프의 한 주기 내에서 연산을 효율적으로 배치하는 것이 중요하다. 전형적인 위치 제어 루프의 시간 분배는 다음과 같다.

T = T_{\text{sensor}} + T_{\text{state}} + T_{\text{control}} + T_{\text{output}} + T_{\text{margin}}

여기서 각 항의 의미는 다음과 같다.

• T_{\text{sensor}}: 센서 데이터 읽기 및 전처리
• T_{\text{state}}: 상태 추정(필터링, 순방향 기구학)
• T_{\text{control}}: 제어 법칙 계산(역동역학, 자코비안 연산 등)
• T_{\text{output}}: 액추에이터 명령 출력
• T_{\text{margin}}: 안전 여유(전체의 10~20%)

행렬 연산은 주로 T_{\text{state}}와 T_{\text{control}}에 집중되며, 이 두 단계의 최적화가 전체 제어 성능에 결정적이다.

3.2 파이프라이닝

연속적인 제어 주기를 파이프라인(pipeline)으로 구성하면 지연 시간(latency)을 숨길 수 있다. 예를 들어, k번째 주기의 센서 읽기와 (k-1)번째 주기의 제어 계산을 중첩하면, 유효 계산 시간을 늘릴 수 있다. 단, 이 경우 한 주기의 센서-액추에이터 지연이 추가되므로 제어 안정성에 미치는 영향을 분석하여야 한다.

지연 d 샘플을 가지는 이산 시간 시스템의 안정성은 다음 특성 방정식의 근이 단위원 내에 있어야 보장된다.

\det(z^{d+1}\mathbf{I} - z^d \mathbf{\Phi} - \mathbf{\Gamma}\mathbf{K}) = 0

여기서 \mathbf{\Phi}는 시스템 행렬, \mathbf{\Gamma}는 입력 행렬, \mathbf{K}는 제어 이득 행렬이다.

코드 수준 최적화

루프 전개와 SIMD 활용

소규모 고정 크기 행렬 연산에서는 루프 전개(loop unrolling)가 효과적이다. 4 \times 4 동차 변환 행렬의 곱셈을 완전히 전개하면 분기 예측 실패와 루프 오버헤드를 제거할 수 있다.

현대 CPU의 SIMD(Single Instruction, Multiple Data) 명령어(SSE, AVX, NEON)를 활용하면 여러 부동소수점 연산을 동시에 수행할 수 있다. AVX-256은 4개의 배정밀도 연산을 동시에 처리하며, AVX-512는 8개를 동시에 처리한다. 4 \times 4 행렬의 열이나 행을 SIMD 레지스터에 적재하여 벡터 단위로 곱셈과 덧셈을 수행하면, 스칼라 코드 대비 이론적으로 4~8배의 속도 향상이 가능하다.

메모리 레이아웃 최적화

행렬의 메모리 레이아웃이 캐시 성능에 미치는 영향은 크다. C/C++에서 2차원 배열은 행 우선(row-major) 순서로 저장되므로, 행 방향 접근이 열 방향 접근보다 캐시 적중률이 높다. 행렬-벡터 곱에서 행 기반 접근이 자연스러운 반면, 행렬-행렬 곱에서는 \mathbf{B}의 열 접근이 빈번하므로, \mathbf{B}를 전치하여 저장하거나 블록 분할로 캐시 효율을 높이는 기법이 사용된다.

구조체 배열(Array of Structures, AoS)과 배열 구조체(Structure of Arrays, SoA)의 선택도 중요하다. SIMD 활용 시에는 SoA 레이아웃이 연속 메모리 접근을 보장하여 벡터화에 유리하다.

실시간 최적화의 종합 전략

실시간 로봇 제어를 위한 행렬 연산 최적화는 여러 수준에서 동시에 이루어져야 한다.

이러한 최적화를 종합적으로 적용하면, 현대 임베디드 프로세서에서 수십 자유도 로봇의 실시간 제어도 실현 가능하다. 그러나 각 최적화 기법은 복잡도, 정밀도, 유지보수성 간의 트레이드오프를 수반하므로, 응용의 요구 사항에 맞추어 신중하게 선택하여야 한다.

참고문헌

• Featherstone, R. (2008). Rigid Body Dynamics Algorithms. Springer.
• Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.
• Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
• Orin, D. E., Goswami, A., & Lee, S.-H. (2013). “Centroidal dynamics of a humanoid robot.” Autonomous Robots, 35(2–3), 161–176.
• Carpentier, J., & Mansard, N. (2018). “Analytical Derivatives of Rigid Body Dynamics Algorithms.” Robotics: Science and Systems XIV.

v 0.1