E-그래프는 논리 합성 및 형식 검증과 같은 여러 분야에서 관심을 끌고 있다. E-그래프 추출은 NP-완전 조합 최적화 문제로, 기하급수적으로 많은 동등한 표현 중에서 최적 항을 식별하는 것이 필요하며, 이는 E-그래프 기반 최적화 작업의 주요 성능 병목 현상으로 작용한다. 그러나 전통적인 추출 방법은 중요한 트레이드오프에 직면해 있다: 휴리스틱 접근 방식은 속도는 빠르지만 최적성을 희생하고, 정확한 방법은 최적의 솔루션을 제공하지만 실용적인 문제에서 과도한 계산 비용에 직면한다. 우리는 이 격차를 세 가지 주요 혁신을 통해 연결하는 새로운 프레임워크 e-boost를 제시한다: (1) 약한 데이터 의존성을 활용하여 DAG 비용을 동시 계산하는 병렬화된 휴리스틱 추출로, 추출 품질을 희생하지 않고 효율적인 다중 스레드 성능을 가능하게 한다; (2) 매개변수화된 임계값 메커니즘을 사용하는 적응형 탐색 공간 가지치기로, 유망한 후보만을 유지하여 솔루션 공간을 극적으로 줄이면서 근사 최적 솔루션을 보존한다; (3) warm-start 기능이 있는 정수 선형 프로그램으로 축소된 문제를 공식화하는 초기화된 정확한 솔루션으로, 솔버가 고품질 솔루션으로 더 빠르게 수렴하도록 유도한다. 형식 검증 및 논리 합성 분야의 다양한 벤치마크에서, e-boost는 전통적인 정확한 접근 방식(ILP)에 비해 558배의 실행 속도 향상과 최신 추출 프레임워크(SmoothE)에 비해 19.04%의 성능 향상을 보여준다. 현실적인 논리 합성 작업에서 e-boost는 두 가지 다른 기술 매핑 라이브러리에 대해 기존 합성 도구에 비해 각각 7.6% 및 8.1%의 면적 향상을 이룬다. e-boost는 https://github.com/Yu-Maryland/e-boost에서 사용할 수 있다.
Yin et al. (Mon,)은 이 질문을 연구하였다.