astar/HDAStarMPI.h

Header of the layer astar, in the group Searches; the same header on the site of Doxygen, its source on GitHub.

Classes

Class	Description
HDAStarMPI	Hash Distributed A* with one MPI process per worker.

Description of the header

Header file for the class template HDAStarMPI, Hash Distributed A* on a distributed-memory machine, with one MPI process per worker.

The search is HDA* [see HDAStar.h] on the process \( i \) of \( p \), with the notation of the page “Best-first search and A*” of the documentation; a node records the state of its parent instead of a pointer, since the parent may be stored by another process, and \( z \) is the incumbent known to the process:

 1  procedure HDA*-MPI(s₀) on the process i
 2     z ← ∞;  if owner(s₀) = i then INSERT(s₀, 0, nil)
 3     loop
 4        for each message m received do
 5           if m is a batch of nodes then INSERT each of them
 6           else if m is an incumbent z' then z ← min(z, z')
 7           else if m is a stop then stop expanding
 8        if OPEN_i has a node of f < z then
 9           expand it as at lines 7 to 15 of HDA*, a goal that lowers z
                sending z to all the other processes
10        else send all the outboxes
11        if OPEN_i has no node of f < z and the mailbox detects the end
12           then break
13     the sends in progress complete
14     the process of the least goal broadcasts it, and the path is rebuilt
          from it, each state broadcast with its parent by its owner

The nodes and the incumbents travel through the mailbox of the processes of ADS, packed in batches of batch messages and sent with non-blocking sends, and the end is detected by the four-counter method of Mattern, which by line 11 a process joins only when it has no node of \( f < z \) and nothing to send. A process that reaches the node limit stops the mailbox of all the processes (line 7), after which they only wait for the end. The path is rebuilt by asking the owner of each state for its parent (line 14), which is why the distribution has to be deterministic.

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright

© by Donato Meoli