IMPart: 대규모 k-way 하이퍼그래프 분할을 위한 다단계 프레임워크 내 메메틱 연산의 통합

k-way 하이퍼그래프 분할 (k-way hypergraph partitioning) 문제는 VLSI 설계 및 과학 계산을 포함한 다양한 분야에서 중요한 응용 가치를 지닌 근본적인 문제입니다. 최첨단 하이퍼그래프 분할기 (hypergraph partitioners)들은 일반적으로 조립 (coarsening), 초기 분할 (initial partitioning), 언조립 (uncoarsening), 그리고 정제 (refinement) 단계를 포함하는 다단계 프레임워크 (multi-level framework)를 채택합니다. 그러나 기존의 많은 방법들은 많은 수의 분할 (즉, 큰 k)을 요구하는 문제에 대해 확장성 (scale)이 좋지 않습니다. 매우 높은 솔루션 품질을 추구하기 위해, 기존의 메메틱 (memetic) 접근 방식들은 종종 두 가지 핵심 연산인 재조합 (recombination)과 변이 (mutation)를 별개의 독립적인 다단계 분할기를 호출함으로써 실행합니다. 하지만 이러한 설계 방식은 표준 다단계 분할기보다 실행 시간을 상당히 더 많이 소모하게 만듭니다. 이러한 메메틱 접근 방식들을 더욱 실용적으로 만들기 위해, 우리는 새로운 재조합 및 변이 연산자를 도입하고 이를 단일 다단계 프레임워크의 언조립 단계에 직접 통합하는 고급 메메틱 프레임워크인 IMPart를 제안합니다. 이는 전통적인 다단계 프레임워크에서의 서로 다른 입도 (granularities)를 가진 국소 탐색 (local searches)을 정교하고 협력적인 탐색으로 변환합니다. 여러 표준 벤치마크에 대한 실험 결과는 우리의 프레임워크가 국소 최적해 (local optima)를 더 효과적으로 벗어나 더 높은 품질의 솔루션을 위해 전역 솔루션 공간 (global solution space)을 탐색하며, 대규모 k-way 하이퍼그래프 분할에 대해 모든 기존 하이퍼그래프 분할기들을 실질적으로 능가함을 입증합니다. 우리의 프레임워크는 고급 하이퍼그래프 분할기 개발을 위한 새로운 패러다임을 제시합니다.