GPU 기술 발전으로 인한 병렬 처리 능력 향상은 고전적인 탐색 알고리즘의 성능 개선에 새로운 기회를 제공합니다. 특히, 신경망 기반 휴리스틱을 사용하는 최선 우선 탐색 알고리즘(A*, Weighted A*)은 GPU에서 병렬 평가를 통해 성능 향상을 이뤘습니다. 하지만, IDA* 또는 Budgeted Tree Search (BTS)와 같은 깊이 우선 탐색 알고리즘에서 휴리스틱 계산을 일괄 처리하는 방법은 연구되지 않았습니다. 본 논문에서는 트리 탐색을 CPU에서 병렬 처리하고 휴리스틱 평가는 GPU에서 병렬 처리하는 방식으로 깊이 우선 탐색 알고리즘의 GPU 병렬화를 효과적으로 수행할 수 있음을 보입니다. 또한, IDA*와 BTS에 적용 가능한 병렬 비용 제한 깊이 우선 탐색(CB-DFS) 프레임워크를 개발하여 성능을 크게 향상시켰습니다. 3x3 루빅스 큐브 및 4x4 슬라이딩 타일 퍼즐(STP) 문제에 대해 분류기 기반 및 회귀 기반 휴리스틱을 사용하여 접근 방식의 효과를 입증했습니다.
