Sqaod overview for developers
Sqoad comprises python modules and c++-based libraries. You can run solvers from both python and C++.
Below is a diagram for python modules. All python modules are included in sqaod package.
Packages of sqaod.py, sqaod.cpu and sqaod.cuda include solvers. Each package include 4 solvers as shown below. The 2 algorithm have been implemented :
- Simulated quantum annealing (path-intergral monte-carlo)
- Brute force search And each algorithm has 2 solvers for 2 graph types as shown below.
- Dense graph
- Bipartite graph So we have 4 solvers in each packages.
Every package also have Formulas module, which does energy calculations for both QUBO and Ising model, and does QUBO-to-Hamiltonian conversions as well.
For CPU- and GPU-based solvers, C-extensions are provided to invoke native libraries. You can find the source code of these extensions under directories of sqaodc/pyglue, sqaodpy/sqaod/cpu/src and sqaodpy/sqaod/cuda/src.
- Including all python modules.
- Pure python implementation of solvers are included.
This implementation is to show algorithm of each solvers.
- CPU-based implementation of solvers are included.
The implementation is parallelized and accelerated by OpenMP.
- CUDA-based implementation of solvers are included.
The implementation is parallelized and accelerated by CUDA.
- utility functions
Below is a simplified diagram of libsqaodc/libsqaodc_cuda, native libraries of sqaod.
public interface <sqaodc/sqaodc.h>
Public interface of sqaod native library, declaring types, solver classes and factory functions. This header (and included headers from <sqaodc/sqaodc.h>) only include system headers, thus it's portable. Public interface headers are packaged as libsqaodc-devel.(deb|rpm).
Following solver classes are provided:
| solver class | algorithm | graph | device |
|---|---|---|---|
| CPU-based solvers (thread-parallel) | |||
| sqaod::cpu::DenseGraphAnnealer | Simulated quantum annealing | Dense graph | CPU |
| sqaod::cpu::BipartiteGraphAnnealer | Simulated quantum annealing | Bipartite graph | CPU |
| sqaod::cpu::DenseGraphBFSearcher | Brute force searcher | Dense graph | CPU |
| sqaod::cpu::BipartiteGraphBFSearcher | Brute force searcher | Bipartite graph | CPU |
| CUDA-based solvers (utilizing CUDA) | |||
| sqaod::cuda::DenseGraphAnnealer | Simulated quantum annealing | Dense graph | CUDA |
| sqaod::cuda::BipartiteGraphAnnealer | Simulated quantum annealing | Bipartite graph | CUDA |
| sqaod::cuda::DenseGraphBFSearcher | Brute force searcher | Dense graph | CUDA |
| sqaod::cuda::BipartiteGraphBFSearcher | Brute force searcher | Bipartite graph | CUDA |
As described for python modules, public interface provides CPU- and CUDA-based Formulas classes.
All above classes are using MatrixType<>, VectorType<> and c++ scalars as parameters.
Solver interfaces are defined as pure-virtual classes in sqaodc/common/Solver.h.
Solver interfaces, Matrix and Vector types are defined by using C++ templates, and float and double versions are implemented.
Native interface for sqaod. It includes 3rd party libraries of eigen and CUB which are placed in sqaod source tree. By using this interface, developers are able to use functions not included in public interface.
This directory includes typedefs, basic classes and utility functions.
Public data types of MatrixType<>, VectorType<> are declared in common/Matrix.h. These classes are implemented as C++ templates since sqaod provides fp64 and fp32 versions of solvers.
Internally, Eigen is used for calculations of matrices and vectors.
This directory includes native implementation of CPU-based solvers. All classes are under the namespace of sqaod_cpu. It's parallelized by using OpenMP. Eigen is used for calculations of matrices and vectors, and Dot_SIMD.cpp is implemented to provide accelerated dot calculations for SSE2 and AVX2. All public solver classes are prefixed with "CPU".
This directory includes native implementation of CUDA-based solvers. All classes are under the namespace of sqaod_cuda. It's parallelized by using CUDA. The cuBLAS and cuRAND are used for linear algebra and pseudo random number generation respectively. CUB is also used for collective primitives for brute force searchers. All public solver classes are prefixed with "CUDA", and back-end classes utilizing CUDA are prefixed with "Device".