정수 선형 계획법 (Integer Linear Programming, ILP)은 네트워크 라우팅, 지도 라우팅, 교통 스케줄링을 포함한 실세계 최적화 문제를 해결하는 데 널리 사용됩니다. 그러나 ILP 알고리즘은 희소성 (sparsity)이 높고 분기 (branch)가 집중되어 있어, 기존의 CPU 및 GPU에서는 비효율적입니다. 이전 연구에 따르면 대규모 ILP 문제는 대규모 병렬 시스템에서도 수십 시간의 실행 시간이 소요될 수 있으며, 이는 시간 민감도가 높은 의사 결정 워크로드에 대한 적용을 제한합니다. Gurobi와 같은 기존 ILP 솔버는 CPU에서 희소성을 처리하기 위해 소프트웨어 수준의 최적화를 사용하지만, 여전히 처리량 (throughput) 제한에 직면해 있습니다. GPU 기반 ILP 솔버 또한 GPU가 희소하고 분기가 많은 워크로드에 적합하지 않아 스레드 발산 (thread divergence), 스트리밍 멀티프로세서 (streaming multiprocessors)의 활용도 저하, 빈번한 호스트-디바이스 (host-device) 상호 작용을 초래하기 때문에 제약이 있습니다.

본 논문은 희소성 인식 (sparsity-aware), 재사용 인식 (reuse-aware), 에너지 효율적이며 재구성 가능한 근접 캐시 (near-cache) ILP 가속기인 SPARK를 제시합니다. SPARK는 CPU 면적의 약 1.4%라는 최소한의 하드웨어 오버헤드로 근접 캐시 가속을 제공하기 위해 CPU의 기존 L1 캐시를 재목적화합니다. 이 아키텍처는 근접 캐시 희소성 탐지 (near-cache sparsity detection) 및 희소성 인식 연산 (sparsity-aware computation)을 수행하여 불필요한 연산과 데이터 이동 에너지를 줄입니다. 또한 SPARK는 ILP 알고리즘의 연산 재사용 패턴을 활용하여 병렬성과 효율성을 향상시킵니다. 제안된 설계는 희소(sparse) 및 밀집(dense) ILP뿐만 아니라 선형 계획법 (Linear Programs, LPs)도 지원합니다.

MIPLIB 2017의 실세계 워크로드에 대한 평가 결과, SPARK는 희소 ILP에 대해 AMD Zen3 CPU 및 NVIDIA Tesla V100 GPU와 비교하여 각각 최대 15배 및 20배의 성능 향상과 최대 152배 및 740배의 에너지 절감을 달성했습니다. 희소 LP의 경우, SPARK는 CPU 및 GPU 베이스라인 대비 7-17배의 성능 향상과 103-250배의 에너지 절감을 달성하여 제안된 아키텍처의 폭넓은 적용 가능성을 입증했습니다.