A Parallel CPU-GPU Framework for Cost-Bounded DFS with Applications to IDA* and BTS
Ehsan Futuhi, Nathan R. Sturtevant · 2025
Read A Parallel CPU-GPU Framework for Cost-Bounded DFS with Applications to IDA* and BTS by Ehsan Futuhi, Nathan R. Sturtevant (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-11916.txt.
Introduction
Futuhi and Sturtevant put graphics processors to work inside depth-first search. Batched best-first search already farms out batches of heuristic scores to a GPU, but depth-first methods like IDA* stall at every step waiting for a single score. Their framework splits the work: the tree search runs in parallel on the CPU while heuristic evaluations are batched onto the GPU.
The scheme, called cost-bounded depth-first search, adapts to both IDA* and budgeted tree search. On the 3x3 Rubik's Cube and the 4x4 sliding tile puzzle, with classifier and regression heuristics alike, the parallel version runs much faster than its serial form. The authors argue depth-first search need not be left out of the GPU era.
Catalog record
| CREATOR | Ehsan Futuhi, Nathan R. Sturtevant |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-11916
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Parallel CPU-GPU Framework for Cost-Bounded DFS with Applications to IDA* and BTS Ehsan Futuhi, Nathan R. Sturtevant Abstract The rapid advancement of GPU technology has unlocked powerful parallel processing capabilities, creating new opportunities to enhance classic search algorithms. A recent successful application of GPUs is in compressing large pattern database (PDB) heuristics using neural networks while preserving heuristic admissibility. However, very few algorithms have been designed to exploit GPUs during search. Several variants of A* exist that batch GPU computations. In this paper we introduce a method for batching GPU computations in depth first search. In particular, we describe a new cost-bounded depth-first search (CB-DFS) method that leverages the combined parallelism of modern CPUs and GPUs. This is used to create algorithms like Batch IDA* , an extension of the Iterative Deepening A* (IDA*) algorithm, or Batch BTS, an extensions of Budgeted Tree Search. Our approach builds on the general approach used by Asynchronous Parallel IDA* (AIDA*), while maintaining optimality guarantees. We evaluate the approach on the 3x3 Rubik’s Cube and 4x4 sliding tile puzzle (STP), showing that GPU operations can be efficiently batched in DFS. Additionally, we conduct extensive experiments to analyze the effects of hyperparameters, neural network heuristic size, and hardware resources on performance. Introduction In recent years, there has been exponential growth in computational resources, particularly in GPUs ( Dally, Keckler, and Kirk 2021 ; Rotem et al. 2022 ) . Modern CPUs also continue to evolve with enhanced parallel processing capabilities, enabling faster execution of complex algorithms. Simultaneously, GPUs have become indispensable for computation-intensive tasks due to their massive parallelism, capable of performing millions of operations simultaneously. This rapid advancement in both CPU and GPU technologies has been well exploited in many fields of Artificial Intelligence, especially deep learning ( Schrittwieser et al. 2020 ; Yao et al. 2024 ) . How can classic search algorithms such as Iterative Deepening A* (IDA*) ( Korf 1985 ) and more modern algorithms like Budgeted Tree Search (BTS) ( Helmert et al. 2019 ; Sturtevant and Helmert 2020 ) benefit from this growth in technology? Several approaches ( Li et al. 2022 ; Zhou and Zeng 2015 ; Agostinelli et al. 2019 ; Agostinelli et al. 2024 ) have been developed to enhance search algorithms using the parallel processing capabilities of modern GPUs. Li et al. 2022 introduced the first admissible neural network heuristic that compresses a large pattern database (PDB) heuristic with less information loss than standard compression techniques ( Felner et al. 2007 ; Helmert, Sturtevant, and Felner 2017 ) . Batch A* ( Li et al. 2022 ) was then designed to use the admissible heuristic to find optimal solutions. Batch A* is a variant of the A* algorithm ( Hart, Nilsson, and Raphael 1968 ) , collecting states into batches to evaluate their heuristics through a single neural network lookup. This technique, called batch heuristic evaluations , utilizes GPU parallelism and significantly improves performance over performing individual neural network lookups for each state. However, Batch A* remains slower than the plain A* algorithm that uses PDB heuristics. Agostinelli et al. 2019 introduced the Batch Weighted A* (BWAS) algorithm, which combines weighted A* search ( Pohl 1970 ; Ebendt and Drechsler 2009 ) with batch heuristic evaluations. Because algorithms like BTS and IDA* are both designed around cost-bounded depth-first search (CB-DFS), the aim of this paper is to design a parallel CPU/GPU implementation of CB-DFS to efficiently use neural network heuristics during search. We demonstrate CB-DFS inside Batch IDA* has two distinct phases working together: search and heuristic evaluation . The search phase is modified from the AIDA* algorithm ( Reinefeld and Schnecke 1994 ) , utilizing CPU parallelism to asynchronously generate and explore different subtrees in CB-DFS. Meanwhile, the heuristic evaluation phase continuously collects nodes generated by all subtrees into batches, which are then processed by the heuristic model on the GPU. We then prove that using CB-DFS inside Batch IDA* still guarantees the discovery of optimal solutions. In our experimental setting, IDA* and BTS behave identically, so we only formulate and evaluate Batch IDA*. We show that Batch IDA* outperforms Batch A* and performs comparably to AIDA* in the Rubik’s Cube domain. In addition, we show that scaling the number of GPUs accelerates Batch IDA* by enabling simultaneous evaluations. Related Work In recent years, several parallel versions of the IDA* algorithm have been introduced. AIDA* ( Reinefeld and Schnecke 1994 ) , a highly parallel iterative-deepening search algorithm, was designed for large-scale asynchronous Multiple Instruction, Multiple Data (MIMD) systems. The algorithm partitions the search space and processes it asynchronously across multiple CPU processors. Taking a different approach, Horie and Fukunaga 2017 investigate the parallelization of IDA* on GPUs using a block-based approach. The proposed Block-Parallel IDA* (BPIDA*) assigns subtrees to blocks of threads that execute on the same streaming multiprocessors (SMs) . BPIDA* takes advantage of local shared memory of within a SM to reduce warp divergence and improve load balancing. GPU parallelism has also been effectively utilized in other search algorithms. Zhou and Zeng 2015 introduced the first parallel variant of the A* search algorithm called GA* that leverages the computational power of GPUs. GA* uses multiple parallel priority queues to manage the Open list, enabling the simultaneous extraction and expansion of nodes across GPU threads. The heuristic computations are also parallelized across the GPU cores to optimize performance further. GA* is up to 45x faster than a traditional CPU-based A* implementations in large and complex search spaces. Q* search ( Agostinelli et al. 2024 ) employs deep Q-networks to calculate combined transition costs and heuristic values for child nodes in a single forward pass, thereby eliminating the need to explicitly generate them. Edelkamp and Sulewski 2009 investigate bitvector-based search algorithms, where the GPU’s parallel processing capabilities allow for the efficient handling of state expansion and duplicate detection. The GPU is also employed for ranking and unranking permutations, computing hash functions, and managing the search frontier, all of which are parallelized to exploit the GPU’s architecture. Meanwhile, other approaches have formulated A* and weighted A* algorithms as differentiable and end-to-end trainable neural network planners ( Yonetani et al. 2021 ; Archetti, Cannici, and Matteucci 2021 ) . These data-driven approaches, rather than learning the heuristic function, take a raw image as an input and convert it to a guidance map by an encoder. GPUs have also been instrumental in learning heuristics. For example, Li et al. 2022 developed an admissible heuristic for the sliding tile puzzle (STP) and TopSpin using an ensemble of neural networks and classifier quantiles. Other approaches ( Agostinelli et al. 2021 ; Arfaee, Zilles, and Holte 2011 ; Thayer, Dionne, and Ruml 2011 ; Pándy et al. 2022 ) have also focused on heuristic learning, though without guaranteeing admissibility. Background In heuristic search , the task is to find a path in a graph \{G=\{V,E\},s,g,c,h\} from a start state s\in V to a goal state g\in V , where c:E\rightarrow\mathbb{R}^{+} is a cost function associated with the edges between states. The heuristic function h(v) provides an estimate of the distance from a state v to the goal g . The heuristic is considered admissible if, for all states