Qiskit / qiskit-addon-sqd-hpc / 36063769083

75%

Build Type

push

github

Committed by web-flow

Commit Message

Parallelize recover_configurations with OpenMP (#60)

The per-bitstring correction in recover_configurations is embarrassingly
parallel apart from the duplicate-removal step, which is a reduction.
When the consumer compiles with OpenMP enabled, correct the bitstrings in
parallel and then remove duplicates on a single thread, in input order.
The library stays header-only and depends only on the C++ standard
library; the parallel path is guarded by _OPENMP and the previous serial
behavior is used otherwise.

Randomness is the other shared point.  Rather than drawing from the single
generator sequentially (which cannot be parallelized), each work item is
given its own stream, selected by the caller's generator type:

  * A counter-based engine (one with set_counter, such as the C++26
    std::philox_engine) is keyed by bitstring index via set_counter, so the
    result -- including the order of the returned vectors -- is identical
    for any number of threads.
  * Any other engine must be seedable; each thread uses an independently
    seeded copy, giving valid but thread-count-dependent results.
  * A generator that is neither is rejected at compile time under OpenMP
    (a static_assert), and remains usable in a serial build.

Duplicate removal now emits each distinct bitstring once in first-seen
(input) order, so the output is deterministic and identical between the
serial and parallel paths without an O(n log n) sort.  It continues to use
the flat hash map from internal/dense_map.hpp.  This changes the returned
ordering (and, under parallelism, the specific bitstrings selected for a
given seed) relative to previous releases; the returned distribution
remains a valid refinement.

The reusable RNG-keying helpers live in a new internal header,
internal/parallel-rng.hpp, so future distributed (MPI) work can share
them.  Add a CMake option SQD_ENABLE_OPENMP to build the tests and
benchmarks with OpenMP, a development-version CI job that runs the suite
at... (continued)

Coverage Stats

820 of 1226 branches covered (66.88%)

Branch coverage included in aggregate %.

16 of 16 new or added lines in 1 file covered. (100.0%)

12 existing lines in 1 file now uncovered.

757 of 883 relevant lines covered (85.73%)

276670.11 hits per line