분해, 최적화 및 재구성: 대규모 환경에서의 매우 큰 상수 곱셈 (Very Large Constant Multiplication)

자원 제약이 있는 하드웨어 (resource-constrained hardware)를 위한 효율적인 산술 회로 설계는 까다로운 조합 최적화 (combinatorial optimization) 문제를 수반하며, 그중 다중 상수 곱셈 (Multiple Constant Multiplication, MCM)이 대표적인 예입니다. MCM은 비트 시프트 (bit-shifts)와 덧셈/뺄셈을 사용하여 고정된 정수 상수에 의한 곱셈을 구현하는 것을 목표로 하지만, 최적의 방법들은 일반적으로 12비트와 같이 중간 크기의 상수로 제한됩니다. 더 큰 정밀도를 목표로 하는 실제 응용 분야를 위해서는 대신 매우 큰 상수 곱셈 (Very Large Constant Multiplication, VLCM) 문제가 해결되어야 합니다. 기존의 접근 방식들은 일반적으로 큰 상수를 패턴으로 분해하고, 중간 크기의 대상에 MCM 최적화 기술을 적용한 뒤, 최종 결과를 재구성하는 휴리스틱 (heuristic) 흐름을 통해 VLCM을 다룹니다. 본 논문은 이 흐름에 대해 여러 가지 개선 사항을 제안합니다: 패턴 선택과 재구성을 위한 새로운 선언적 최적화 모델 (declarative optimization models) 및 최신 최적 MCM 모델의 적용입니다. 얻어진 개선 사항의 핵심 요소는 (i) 패턴이 중첩되도록 허용하여 MCM 단계에 필요한 고유 대상 상수의 수를 최소화하는 것과, (ii) 재구성 단계를 휴리스틱이 아닌 최적으로 수행하는 것입니다. 또한, 우리는 전역 최적 (globally-optimal) VLCM 접근 방식을 제안하고 그 한계를 규명합니다. 우리는 각 단계를 해결하기 위해 제약 프로그래밍 (constraint programming)과 SAT를 혼합하여 사용합니다. 계수 워드 길이 (coefficient word lengths)가 수십에서 수천 비트에 이르는 합성 및 실제 신호 처리 (signal processing)와 암호학 (cryptographic) 벤치마크에 대한 실험 결과는, 제안된 접근 방식이 매우 큰 정밀도로 확장 가능하며 기존 베이스라인 (baselines)보다 일관되게 우수한 성능을 보임을 입증합니다.