ComPart: 고품질 하이퍼그래프 분할을 위한 커뮤니티 가이드 기반 사후 조밀화 (Post-Coarsening)

하이퍼그래프 분할 (Hypergraph partitioning)은 복잡한 임베디드 시스템 설계에서 매우 중요한 단계로, 이기종 MPSoC (Multi-Processor Systems-on-Chip) 상의 태스크 매핑을 최적화하고 멀티-FPGA 프로토타이핑을 가능하게 하는 데 필수적입니다. 기존의 많은 방법론은 내부 연결은 밀집되어 있고 외부 연결은 희소한 모듈을 식별하기 위해 커뮤니티 탐지 (community detection)에 의존하며, 일반적으로 이를 조밀화 (coarsening) 단계의 제약 조건으로 활용하는 방식을 채택하고 있습니다. 본 연구에서는 사후 조밀화 (post-coarsening) 단계(즉, 초기 분할 및 언코어스닝 (uncoarsening)) 전반에 걸쳐 고품질의 클러스터링 (clustering)을 찾아내기 위해 다양한 커뮤니티 탐지 방법을 통합하는 일반화된 프레임워크인 ComPart를 제안합니다. 이렇게 발견된 클러스터링은 독특한 구조적 가이드 역할을 하여, 정제 (refinement) 과정이 더 우수한 분할 솔루션을 식별할 수 있도록 합니다. 우리의 프레임워크는 두 가지 핵심적인 장점을 제공합니다: (1) 언코어스닝 중에 탐지된 커뮤니티 구조를 활용하여 지역 최적해 (local optima)를 벗어나고 전역적으로 의미 있는 솔루션 부분 공간 (solution subspaces)을 탐색하는 새로운 패러다임을 구축함으로써, 표준적인 지역 정제 (local refinements)의 한계를 초월합니다; (2) 기존 및 향후의 커뮤니티 탐지 방법들을 유연하게 수용할 수 있습니다. 나아가, 우리는 원래 그래프 (graphs)에서 유래한 국소 밀집 분해 (locally-dense decomposition)를 하이퍼그래프 (hypergraph) 영역으로 이론적으로 일반화합니다. 우리는 이 기술을 하이퍼그래프에 적용하기 위한 공식적인 확장과 필요한 증명들을 제공하며, 이는 하이퍼그래프 분할에서의 첫 번째 적용 사례가 됩니다. 구체적으로, 우리는 엄격하게 도출된 이 분해법을 활용하여 초기 분할 단계를 더 우수한 시작점으로 유도합니다. 표준 벤치마크에 대한 실험 결과는 우리의 방법이 솔루션 품질 면에서 최신 기술 (state-of-the-art) 방법들을 지속적으로 능가함을 입증합니다.