Parallel Best-First Search
PBeFS is a C++20 library for the sequential and parallel best-first search
of two kinds of problems: the A* search [9] of an implicit state-space
graph, i.e., a graph given by an initial state, a goal predicate and a
procedure that generates the successors of a state (cf. [10]), and the
Branch-and-Bound (B&B) of a tree whose nodes have a bound and possibly a
feasible value. In fact, A* is the special case of the general B&B in which
the bound of a node is \(f = g + h\) and a goal gives a feasible solution of
value g (cf. [17]), and the two searches share the parallel schemes and
the runtimes; they differ in that a graph has duplicates, which A* detects
with a closed list, while a tree has none but has an incumbent. The
parallel A* searches follow the taxonomy of the survey of Fukunaga et al.
[1], and the parallel B&B searches that of the survey of Gendron and
Crainic [16]. They run on C++ threads, OpenMP, FastFlow [12] and MPI,
through the executors and the mailboxes of ADS; hence, one can compare the
same algorithm across runtimes, and the same runtime across algorithms.
The headers are in three layers: include/PBeFS/core holds the helpers
and the parameters of the parallel searches, which do not depend on the
kind of search, include/PBeFS/astar the graph searches with their
domains, and include/PBeFS/bnb the tree searches; core.h, astar.h,
bnb.h and PBeFS.h include a layer, or all of them, save the searches
over MPI.
Pattern databases
PatternDatabase.h gives the sliding-tile puzzles the additive pattern
databases of Korf and Felner [22] and of Felner, Korf and Hanan
[23] in place of the Manhattan distance. A table holds, for each
placement of the tiles of a pattern (ranked as a k-permutation of the
cells), its distance from the goal in an abstraction that keeps only the
tiles of the pattern, with the blank either ignored (the table is then
consistent) or minimized over the cells it can reach for free (a stronger
but inconsistent table, as in [22]); it is built by a
breadth-first search by layers on the workers of any runtime. AdditivePDB
sums the tables of a partition of the tiles and takes the maximum with the
reflection about the main diagonal, and SlidingTilePDB is SlidingTile
with that heuristic, so that every search of the library runs on it
unchanged:
#include "PBeFS/PBeFS.h"
using namespace PBeFS_di_unipi_it;
PDBOptions o;
o.blank = BlankRule::minimized;
o.cache = "pdb-cache"; // built once, then loaded
const AdditivePDB< 4 , 4 > pdb( partition_15_7_8() ,
FifteenPuzzle::korf_goal() , o );
const SlidingTilePDB< 4 , 4 > d( FifteenPuzzle::parse( "14 13 15 7 11 12 "
"9 5 6 0 2 1 4 8 10 3" ) , pdb );
const auto s = AStar< SlidingTilePDB< 4 , 4 > >( d ).solve(); // cost 57
The entries are stored in a byte, in 4 bits as the excess over the
Manhattan distance of the tiles of the pattern (the default), modulo 3 in
1.6 bits [25] or in 1 bit [27] (the heuristic of a
successor then follows from that of its parent), by the least excess of
groups of consecutive ranks (the max-compression of [24]), or
by rank and select over the nonzero excesses, all of them in the packed
arrays and in the rank and select of ADS;
the tables are saved to files with a versioned header and a checksum, and a
cache directory keeps them. The theory (the admissibility of the sum and of
the reflection, the consistency, the recovery of the exact value from the
residues) is on the page “Pattern databases” of the documentation. The
nodes expanded by A* on the 100 instances of Korf, summed over the
instances, which do not depend on the machine, are the following
(tools/bench/pdb.sh; all the costs are the optimal ones):
heuristic |
blank |
entries |
memory |
expanded |
ratio |
|---|---|---|---|---|---|
Manhattan |
1557138490 |
1 |
|||
5-5-5, max-compressed by 16 |
ignored |
min |
49 KB |
681766045 |
2.3 |
5-5-5, no reflection |
ignored |
1 bit |
197 KB |
369972440 |
4.2 |
5-5-5 |
ignored |
4 bits |
786 KB |
263234565 |
5.9 |
6-6-3 |
ignored |
4 bits |
5.8 MB |
167667391 |
9.3 |
7-8, no reflection |
ignored |
1 bit |
72 MB |
137386424 |
11.3 |
7-8, max-compressed by 8 |
ignored |
min |
36 MB |
119574805 |
13.0 |
7-8 |
ignored |
4 bits |
288 MB |
43587167 |
35.7 |
5-5-5 |
minimized |
4 bits |
786 KB |
59968561 |
26.0 |
7-8 |
minimized |
4 bits |
288 MB |
2019506 |
771 |
The rule of the blank weighs more than the size of the patterns: with the
blank minimized the partition 7-8 expands about 20000 nodes per instance,
i.e., 21 times fewer than with the blank ignored, at the price of about
6000 reexpansions over the 100 instances, while the encodings in 1 bit and
modulo 3 need the blank ignored and no reflection. The default of
PDBOptions is nevertheless the blank ignored, which every encoding
accepts and which keeps the heuristic consistent, so that the sequential
A* never expands a node twice; the blank minimized is chosen as in the
example above. The tables of the
24-puzzle (6-6-6-6, 255 MB in 4 bits) are built and looked up as well, and
SlidingTile packs the boards of more than 16 cells, 5 bits per cell, into
an integer of 128 bits (Word128), so that SlidingTilePDB< 5 , 5 > with
IDA* is the search of Korf and Felner [22] on that puzzle.
The 50 instances distributed with the code of HDA* of Jinnai and Fukunaga
(data/24-puzzle/instances50.txt) are beyond the reach of a benchmark, as
IDA* solves only one of them within \(10^9\) expansions (cost 82, with
\(6.5 \cdot 10^8\) expansions); tools/bench/pdb.sh therefore solves the 50
instances of PDBBench --walk 150, i.e., the ends of random walks of 150
moves of the blank from the goal (the \(i\)-th seeded by \(i\)), with at most
\(10^{10}\) expansions each. 49 of them are solved, with optimal costs from
50 to 84 and \(4.7 \cdot 10^{10}\) expansions in all (the median being
\(3.5 \cdot 10^7\)), while instance 36 exceeds the limit; grouped by the
optimal cost, the expansions are the following:
optimal cost |
instances |
least expanded |
mean expanded |
most expanded |
|---|---|---|---|---|
50-60 |
3 |
\(3.9 \cdot 10^5\) |
\(7.5 \cdot 10^5\) |
\(1.3 \cdot 10^6\) |
62-66 |
12 |
\(2.6 \cdot 10^5\) |
\(1.3 \cdot 10^7\) |
\(7.2 \cdot 10^7\) |
68-70 |
9 |
\(3.3 \cdot 10^6\) |
\(4.0 \cdot 10^7\) |
\(2.2 \cdot 10^8\) |
72-74 |
11 |
\(2.8 \cdot 10^6\) |
\(4.9 \cdot 10^8\) |
\(2.2 \cdot 10^9\) |
76-78 |
9 |
\(2.1 \cdot 10^8\) |
\(2.9 \cdot 10^9\) |
\(9.5 \cdot 10^9\) |
80-84 |
5 |
\(2.3 \cdot 10^8\) |
\(3.1 \cdot 10^9\) |
\(5.5 \cdot 10^9\) |
The mean grows by about one order of magnitude every 6 moves of the optimal cost up to 78, and within a group of costs the expansions of two instances may differ by up to 3 orders of magnitude.
Scaling with the number of cores
We are concerned here with how each parallel search of the library scales
with the number of cores on one and the same problem, for each problem of
the examples. The runs are those of table F of tools/bench/campaign.sh,
and the tables below are written from its output by tools/bench/tables.py.
Each problem is taken at a size where the sequential search takes about 1
to 10 s on one core. For the 15-puzzle these are the instances 1, 10 and 14
of Korf, and for pathfinding three random grids of \(5000 \times 5000\) cells (25%
of them blocked, the others costing 1 to 5) with 4 and with 8 moves. Also,
the vacuum world has 22 cells and three starting cells, the queens are 28,
29 and 31, the missionaries and the cannibals are 65535 each (with boats of
100 and 200 seats), the jugs are four, of 193 to 211 units, and the
salesperson visits three sets of 32 random cities. However, the 8-puzzle (the instance of
figure 3.28 of the book and one of the hardest) and the road from Arad to
Bucharest cannot grow, and they are solved in microseconds to
milliseconds; hence, on them the tables mostly measure the cost of
starting and stopping the workers. The branch-and-bound is run on three
strongly correlated knapsacks of Pisinger with 90 items, which are usually
the hardest for the bound of Dantzig, and on three traveling salesperson
problems of 24 cities, on the tree of the partial tours bounded by the
minimum spanning tree.
A search is run with the options that its Domain supports. HDA* takes
each work distribution that the Domain gives (Z, AZ, A, P, H and R in the
notation of Jinnai and Fukunaga; the abstractions of AZ and A are given
only by the sliding-tile puzzles, the grids and the vacuum world) on the
threads, OpenMP and FastFlow. SPA* and SafePBNF (the latter where the
Domain has nblocks) run on the threads and on OpenMP, the farm of
FastFlow has a master and one worker less than the cores, and HDA* over MPI
has one process per core, with each distribution but R (which needs a
generator per worker). The branch-and-bound runs each of its schemes on
each runtime, its farm and its search over MPI. PASE pays only when the
expansions are slow (cf. the table of slow expansions); thus, it is run
with HDA, SPA* and the farm on smaller instances whose expansions carry
the artificial work of SlowDomain. Each run that the tables compare is
made twice, in two processes. Furthermore, the cost it finds is checked
against the one of the sequential search, and a difference is written to
F-mismatch.csv and marked in the tables.
The timings were taken on MACHINE (CPU, memory, compiler and flags), on the
cores CORES of the NUMA node NODE, with the memory bound to that node, the
workers pinned one per core (PBEFS_PIN) and no other job on the machine.
The time of a run is the wall-clock time of solve(), i.e., from the
creation of the workers to the solution, the tracing of its path included;
it does not include the start of the process, the reading or the
generation of the instance, the construction of the Domain and of the
tables of the distribution, nor the release of the memory of the search.
In each table, a row is a search (the algorithm, the distribution of HDA*
in brackets and the runtime, i.e., thread, openmp, fastflow or mpi), and a
column is the number of cores given to it. A cell is the median over the
instances of the speedup over the sequential search on 1 core, i.e., A*
with the OPEN list on buckets or the branch-and-bound with the best-first
selection. The time of a run is the median of its two repetitions, and the
smallest and the largest speedup over the instances follow in
parentheses. A cell is empty when some run did
not solve its instance (e.g., HDA*[R] beyond its limit of nodes), and !
marks a cell with a run whose cost differs from the sequential one. The
A/A noise under each table is the median and the largest relative gap
between the two repetitions of a run.
RESULTS: the tables of tables.py (section “Scaling on the problems of
the examples”), one per problem, followed by the comment table by table,
i.e., which search scales best on which problem and by how much (as a
range), where the ranking changes with the number of cores, and the
exceptions.
Citing
If PBeFS is useful in a publication, one can cite it as
@software{PBeFS,
author = {Meoli, Donato},
title = {{PBeFS}: Parallel Best-First Search},
url = {https://github.com/dmeoli/PBeFS},
year = {2026}
}
Code style
The code follows the style of the repository
code-style, i.e., its .clang-format
with what its format.py adds to it (e.g., return( x ); and a space before
each comma), which clang-format has no option for, in its variant spaces,
which .code-format chooses: the indentation and the continuations by spaces
alone, and a space after a cast (( void ) x). On a pull request, the
continuous integration checks the lines that the request changes, and posts
the changes that put them in the style as suggestions on them; with that
repository cloned in ~/code-style,
~/code-style/code-format --since origin/main FILE...
does the same before a commit (clang-format 22 is needed, e.g., pip install clang-format==22.1.5).
License
This software is released under the GNU Lesser General Public License version 3.0 (see the file LICENSE). Its sequential version was first written for the course of Knowledge Engineering of prof. Floriana Esposito at the University of Bari, and the parallel ones for the course of Parallel and Distributed Systems of prof. Marco Danelutto and prof. Massimo Torquati at the University of Pisa.