MQAStar.h File Reference

Header file for the class template MQAStar, MultiQueue A*: the workers share one CLOSED list, as in SPAStar, and an OPEN list that is a relaxed priority queue, the MultiQueue of Rihani, Sanders and Dementiev, in place of a priority queue under one lock. More...

#include <atomic>
#include <cstdint>
#include <memory>
#include <mutex>
#include <optional>
#include <ranges>
#include <type_traits>
#include <vector>
#include "PBeFS/astar/ConcurrentClosed.h"
#include "PBeFS/astar/HDAStar.h"
#include "ADS/concurrent/MultiQueue.h"

Go to the source code of this file.

Classes
class	MQAStar< D, Executor >
	MultiQueue A*: one relaxed OPEN list and one CLOSED list shared by the workers. More...

Namespaces
namespace	PBeFS_di_unipi_it
	namespace for the Parallel Best-First Search library

Detailed Description

Header file for the class template MQAStar, MultiQueue A*: the workers share one CLOSED list, as in SPAStar, and an OPEN list that is a relaxed priority queue, the MultiQueue of Rihani, Sanders and Dementiev, in place of a priority queue under one lock.

The search is that of SPAStar.h, with the notation of the page "Best-first search and A*" of the documentation, but for OPEN and the test of termination: OPEN is the MultiQueue of ADS, whose pop takes the better of the least entries of two queues drawn at random, and therefore not always the least of all, and the counter \( m \) of the entries that are in OPEN or being expanded, which is atomic, takes the place of busy and of the lock \( L \):

 1  procedure MQA*(s₀, p)
 2     CLOSED ← {s₀}, with g(s₀) ← 0;  OPEN ← {(f(s₀), g(s₀), s₀)}
 3     z ← ∞;  m ← 1;  done ← false
 4     in parallel, on each worker i = 0, ..., p − 1 do
 5        while not done do
 6           e ← a pop of OPEN, possibly nothing
 7           if no entry was popped then
 8              if m = 0 then done ← true
 9              else wait a little
10              continue
11           (f, g, u) ← e;  F ← ∅
12           if f < z then expand u as at lines 13 to 25 of SPA*
13           m ← m + |F| − 1;  push the entries of F in OPEN
14     return the path to the goal of cost z, if z < ∞

An entry popped with \( f \ge z \) is dropped, since the entries of OPEN are not ordered across its queues and a better one may still be there. The test at line 8 is exact: at line 13, \( m \) counts the entries of \( F \) and drops the one popped in one atomic step, before the pushes, so that \( m = 0 \) means that OPEN is empty and that no worker is expanding, whatever the order of the pops; then every node generated with \( f < z \) was expanded, which is the condition of the page "Parallel A*" for an optimal \( z \). One atomic step per expansion, rather than one before and one after the pushes, halves the contention on the line of \( m \), which all the workers share. The order of the pops only changes how many nodes are expanded before \( z \) is optimal, and how many are reopened.

Author

Donato Meoli
Dipartimento di Informatica
Università di Pisa

Copyright

© by Donato Meoli