Core#

Resources and backends (sequential, OpenMP and CUDA), streams (stream_ref), memory resources (host, pinned host, and the stream-ordered CUDA device resource) and buffers, copies between memory spaces (to_vector, copy, to_space), array views, errors, logging, the profiler (with device times on CUDA), statistics and the umbrella header <dyng/dyng.hpp>.

enum class dyng::backend : std::uint8_t#

An execution backend, chosen at run time through dyng::resources.

sequential is the mandatory reference backend of every algorithm.

Values:

enumerator sequential#

one host thread; the reference implementation

enumerator openmp#

host threads through OpenMP

enumerator cuda#

an NVIDIA GPU

enum class dyng::log_level : std::uint8_t#

Severity of a log message; a message is emitted if its level <= the current level.

Values:

enumerator off#

nothing is logged

enumerator error#

failures reported as exceptions that are also worth a log line (e.g. in destructors)

enumerator warn#

the default: suspicious but handled situations

enumerator info#

coarse progress information

enumerator debug#

details such as implicit copies and chosen engines

enumerator trace#

very verbose

enum class dyng::memory_space : std::uint8_t#

Where a block of memory lives.

Values:

enumerator host#

pageable host memory

enumerator pinned_host#

page-locked host memory (device-accessible for DMA)

enumerator device#

device memory of one GPU

enumerator managed#

CUDA managed (unified) memory.

enum class dyng::algorithm_family : std::uint8_t#

The update family of an algorithm (the two templates of the update model).

Values:

enumerator fixed_point#

a value per element, iterated until nothing changes (sssp)

enumerator aggregate_delta#

a global count, updated by one signed recount (cycle_count)

enum class dyng::container_kind : std::uint8_t#

The container an algorithm runs on.

Values:

enumerator graph#

dyng::graph

enumerator hypergraph#

the hypergraph container (0.3)

enum class dyng::maturity_level : std::uint8_t#

How settled an algorithm’s API and behaviour are (experimental, stable, deprecated; docs/glossary.md), or that it is teaching material (tutorial).

Values:

enumerator experimental#

may change in any release; excluded from SemVer guarantees

enumerator stable#

SemVer applies.

enumerator deprecated#

kept for at least one minor release, then removed

enumerator tutorial#

teaching material (docs/tutorials), not a research algorithm; like experimental

enum class dyng::oracle_kind : std::uint8_t#

What “correct” means for an algorithm’s update (the oracle the conformance kit checks it against).

Values:

enumerator compute#

exact: a chain of updates equals compute() on the final graph

enumerator reference#

approximate: update and compute are within a tolerance of a converged reference

enum class dyng::copy_policy : std::uint8_t#

What to do when an input array lives in another memory space than the one the library reads it in.

The library then copies the array once. In this release batches, graph builds and imported trees are read on the host on every backend (the batch is applied on the host, as the original codes do), so the implicit copies are the ones out of device memory: a batch, an edge list or CSR, or a tree for sssp::result::from_arrays() in device memory. The default allow logs the copy at debug level; while a profiler is attached, allow acts as warn, so an unexpected copy inside a timed run is reported.

Values:

enumerator allow#

copy; log at debug level

enumerator warn#

copy; log at warn level (the default inside timed benchmark runs)

enumerator error#

throw invalid_argument_error instead of copying

enum class dyng::engine : std::uint8_t#

Which update engine an algorithm uses: a fused engine (a ported paper kernel) or the composition of the framework’s operators, or automatic (fused where it can run).

Values:

enumerator automatic#

the library chooses (fused when the device supports it)

enumerator fused#

hand-fused paper kernels (e.g. a persistent cooperative kernel)

enumerator operators#

the multi-kernel framework operators

enum class dyng::determinism : std::uint8_t#

What two runs of an algorithm are guaranteed to agree on (the algorithm contract, ADR 0006).

Values:

enumerator bitwise#

identical bits across runs and backends (canonical tie-breaking)

enumerator exact_value#

identical values (e.g. counts); internal order may differ

enumerator tolerance#

equal within a documented tolerance

using dyng::log_sink = std::function<void(log_level, std::string_view)>#

A log sink: receives the level and the formatted message (without trailing newline).

using dyng::cuda_stream_handle = CUstream_st*#

The CUDA stream handle type (identical to cudaStream_t).

template<typename weight_t>
constexpr bool dyng::is_unweighted_v = std::is_same_v<weight_t, unweighted>#

Whether a weight type is the unweighted tag.

Template Parameters:

weight_t – A weight type.

std::string dyng::citation(std::string_view what = "dyng")#

BibTeX entries to cite when using the library or one of its algorithms.

The entries come from docs/references.bib, compiled into the library.

Parameters:

what – [in] “dyng” (the library only), or an algorithm or storage name: “sssp”, “mosp”, “cycle_count”, “triad_count”, “label_propagation”, “hyper_sssp”, “hypergraph”, or any other algorithm of the registry (dyng::algorithms(), cited with its manifest’s keys).

Throws:

invalid_argument_error – if what is not a known name.

Returns:

The BibTeX of the library followed by the entries of the algorithm’s papers.

std::vector<std::string> dyng::citation_keys(std::string_view what = "dyng")#

The citation keys (in docs/references.bib) for a name accepted by citation().

Parameters:

what – [in] As for citation().

Throws:

invalid_argument_error – if what is not a known name.

Returns:

The keys, the library’s key first.

template<typename value_t>
constexpr array_view<value_t> dyng::host_view(value_t *data, std::size_t size) noexcept#

A host view of a pointer range.

Template Parameters:

value_t – Element type.

Parameters:

  • data – [in] Pointer to the first element.

  • size – [in] Number of elements.

Returns:

array_view in memory_space::host.

template<typename value_t, typename alloc_t>
array_view<value_t> dyng::host_view(std::vector<value_t, alloc_t> &v) noexcept#

A mutable host view of a std::vector.

Template Parameters:

  • value_t – Element type.

  • alloc_t – Allocator type.

Parameters:

v – [in] The vector; must outlive the view and not be resized while viewed.

Returns:

array_view over v.data(), v.size().

template<typename value_t, typename alloc_t>
array_view<const value_t> dyng::host_view(const std::vector<value_t, alloc_t> &v) noexcept#

A read-only host view of a std::vector.

Template Parameters:

  • value_t – Element type.

  • alloc_t – Allocator type.

Parameters:

v – [in] The vector; must outlive the view and not be resized while viewed.

Returns:

array_view<const value_t> over v.data(), v.size().

template<typename value_t>
constexpr array_view<value_t> dyng::device_view(value_t *data, std::size_t size, int device = 0) noexcept#

A device view of a pointer range.

Template Parameters:

value_t – Element type.

Parameters:

  • data – [in] Device pointer to the first element.

  • size – [in] Number of elements.

  • device – [in] CUDA device ordinal owning the memory.

Returns:

array_view in memory_space::device.

bool dyng::backend_available(backend b) noexcept#

Whether a backend can be used in this process.

Parameters:

b – [in] The backend.

Returns:

True if b was compiled in and, for cuda, a device is visible.

backend dyng::default_backend() noexcept#

The backend a default-constructed dyng::resources uses.

Returns:

cuda if available, else openmp if available, else sequential.

std::string_view dyng::to_string(backend b) noexcept#

The lower-case name of a backend (“sequential”, “openmp”, “cuda”).

Parameters:

b – [in] The backend.

Returns:

A static string naming b.

template<typename value_t>
std::vector<std::remove_const_t<value_t>> dyng::to_vector(const resources &res, array_view<value_t> src)#

Copy an array (in any memory space) into a new host std::vector.

Synchronization:

Blocks until the work has completed (synchronous). Waits for the stream of res when src is not host-accessible.

Template Parameters:

value_t – Element type (possibly const).

Parameters:

  • res – [in] Resources whose stream orders the copy.

  • src – [in] The array.

Throws:
Returns:

A host vector with the elements of src.

template<typename value_t>
void dyng::copy(const resources &res, detail::non_deduced<array_view<const value_t>> src, array_view<value_t> dst)#

Copy the elements of one array into another of the same size.

The element type is deduced from dst alone, so a mutable source view converts: copy(res, host_view(a), host_view(b)) works for two std::vector<T>.

Synchronization:

Stream-ordered; returns before the work completes (asynchronous). Ordered on the stream of res when a device space is involved (host-to-host copies complete before the call returns).

Template Parameters:

value_t – Element type (deduced from dst).

Parameters:

  • res – [in] Resources whose stream orders the copy.

  • src – [in] Source array (a view of value_t or const value_t).

  • dst – [out] Destination array (same size as src).

Throws:
template<typename value_t>
buffer<std::remove_const_t<value_t>> dyng::to_space(const resources &res, array_view<value_t> src, memory_space space)#

Copy an array into a new buffer in the memory space space.

The memory resource follows the space: res.memory() when it allocates in space; otherwise default_host_memory_resource() for memory_space::host, default_pinned_host_memory_resource() for memory_space::pinned_host (the host staging resource of a CUDA handle), and default_device_memory_resource(res.device()) for memory_space::device on a CUDA handle. Managed memory needs a handle whose memory resource is managed.

Synchronization:

Stream-ordered; returns before the work completes (asynchronous). Allocation and copy are ordered on the stream of res (host-to-host copies complete before the call returns).

Template Parameters:

value_t – Element type (possibly const).

Parameters:

  • res – [in] Resources providing the stream (and the memory resource, see above).

  • src – [in] The array.

  • space – [in] The memory space of the new buffer.

Throws:
Returns:

A buffer holding a copy of src.

void dyng::set_log_level(log_level level) noexcept#

Set the process-wide log level.

Parameters:

level – [in] The new level.

log_level dyng::get_log_level() noexcept#

The process-wide log level.

Initially the value of the environment variable DYNG_LOG_LEVEL (off, error, warn, info, debug, trace; read once), or warn if it is unset or invalid.

Returns:

The current level.

void dyng::set_log_sink(log_sink sink)#

Replace the log sink. The sink is called without any library lock held, so it may itself log or call other dynG functions, and it may be called concurrently from several threads (it must be thread-safe, or serialize itself). A call that is running when the sink is replaced finishes with the old sink.

Parameters:

sink – [in] The new sink; an empty function restores the default stderr sink (which writes whole lines under its own lock).

bool dyng::log_enabled(log_level level) noexcept#

Whether a message of level would be emitted.

Parameters:

level – [in] The message level.

Returns:

True if level != off and level <= get_log_level().

void dyng::log_message(log_level level, std::string_view message)#

Emit a message if its level is enabled.

Named log_message (not log) so that unqualified calls of the math function log() inside namespace dyng keep working.

Parameters:

  • level – [in] The message level (must not be log_level::off).

  • message – [in] The message.

log_level dyng::parse_log_level(std::string_view name)#

Parse a level name.

Parameters:

name – [in] One of “off”, “error”, “warn”, “info”, “debug”, “trace” (case-insensitive).

Throws:

invalid_argument_error – if name is not a level name.

Returns:

The level.

std::string_view dyng::to_string(log_level level) noexcept#

The lower-case name of a level.

Parameters:

level – [in] The level.

Returns:

A static string (“off”, “error”, “warn”, “info”, “debug” or “trace”).

std::string_view dyng::to_string(memory_space space) noexcept#

The lower-case name of a memory space (“host”, “pinned_host”, “device”, “managed”).

Parameters:

space – [in] The memory space.

Returns:

A static string naming space (the enumerator’s name).

constexpr bool dyng::is_host_accessible(memory_space space) noexcept#

Whether host code may dereference memory of a space.

Parameters:

space – [in] The memory space.

Returns:

True for host, pinned_host and managed.

host_memory_resource &dyng::default_host_memory_resource() noexcept#

The process-wide stateless host resource used by host backends by default.

Returns:

A reference to a static host_memory_resource.

cuda_async_memory_resource &dyng::default_device_memory_resource(int device)#

The default memory resource of the CUDA backend on a device: a process-wide cuda_async_memory_resource, created on first use.

It is never destroyed (its memory returns to the driver when the process exits), so buffers and workspaces may outlive every resources handle that used it.

Parameters:

device – [in] CUDA device ordinal.

Throws:
Returns:

The device’s default resource.

pinned_host_memory_resource &dyng::default_pinned_host_memory_resource() noexcept#

The process-wide pinned host resource (host staging of the CUDA backend).

Returns:

A reference to a static pinned_host_memory_resource.

std::string_view dyng::to_string(algorithm_family family) noexcept#

The name of an update family, as in the manifests (“fixed_point”, “aggregate_delta”).

Parameters:

family – [in] The family.

Returns:

A static string naming family.

std::string_view dyng::to_string(container_kind container) noexcept#

The name of a container kind, as in the manifests (“graph”, “hypergraph”).

Parameters:

container – [in] The container kind.

Returns:

A static string naming container.

std::string_view dyng::to_string(maturity_level maturity) noexcept#

The name of a maturity level, as in the manifests (“experimental”, “stable”, “deprecated”, “tutorial”).

Parameters:

maturity – [in] The maturity level.

Returns:

A static string naming maturity.

std::string_view dyng::to_string(oracle_kind oracle) noexcept#

The name of an oracle kind, as in the manifests (“compute”, “reference”).

Parameters:

oracle – [in] The oracle kind.

Returns:

A static string naming oracle.

const std::vector<algorithm_info> &dyng::algorithms()#

The algorithms compiled into this library, in the order of the manifests.

A build that selects a subset (the CMake option DYNG_ALGORITHMS) lists only that subset.

Throws:

out_of_memory_error – on the first call if the table cannot be allocated.

Returns:

The registry (built on first use; valid for the life of the program).

const algorithm_info *dyng::find_algorithm(std::string_view name)#

Look up a compiled algorithm by name.

Parameters:

name – [in] The algorithm’s name (e.g. “cycle_count”).

Throws:

out_of_memory_error – as algorithms().

Returns:

Its entry, or nullptr if this library does not contain it.

std::string_view dyng::to_string(copy_policy policy) noexcept#

The lower-case name of a copy policy (“allow”, “warn”, “error”).

Parameters:

policy – [in] The policy.

Returns:

A static string naming policy (the enumerator’s name).

template<typename id_t>
constexpr id_t dyng::invalid_id() noexcept#

The “no id” sentinel of a signed id type (vertex, edge, hyperedge or parent).

Template Parameters:

id_t – A signed integer type.

Returns:

-1 converted to id_t.

template<typename distance_t>
constexpr distance_t dyng::infinite_distance() noexcept#

The “unreachable” distance of an integer distance type.

Equals std::numeric_limits<distance_t>::max() / 4, so that adding any valid edge weight to it cannot overflow. Writers print values >= infinite_distance<distance_t>() / 2 as INF.

Template Parameters:

distance_t – A signed integer distance type (std::int64_t in the public API).

Returns:

max() / 4 of distance_t.

std::string_view dyng::to_string(engine e) noexcept#

The lower-case name of an engine (“automatic”, “fused”, “operators”).

Parameters:

e – [in] The engine.

Returns:

A static string naming e (the enumerator’s name).

std::string_view dyng::to_string(determinism d) noexcept#

The lower-case name of a determinism level (“bitwise”, “exact_value”, “tolerance”).

Parameters:

d – [in] The level.

Returns:

A static string naming d (the enumerator’s name, as in the manifests).

template<typename container_t, typename batch_view_t, typename ...results_t>
std::tuple<typename detail::stats_of<results_t>::type...> dyng::update(const resources &res, container_t &g, const batch_view_t &batch, results_t&... results)#

Apply Batches to g once and bring every result up to date.

All before-apply work of every result runs on G_t first, then the batch is applied once, then every result is updated on G_{t+1}. Every result must match g.version(), and no result may be passed twice. The postcondition of each algorithm’s own update() holds for each result (for sssp: equal to sssp::compute() on the new graph).

Thread safety: the call changes g and every result, so it must not overlap any other call on g or on one of the results (graph, “Thread safety”); updates of distinct graphs may run concurrently.

Synchronization:

Blocks until the work has completed (synchronous).

Exception safety:

Strong for every error found before the batch is applied (the before-apply work of every result runs on G_t before the commit): the graph and every result are unchanged. Basic for an error after the commit: the graph holds the new version, the result whose update threw is poisoned (every later use throws stale_result_error), the other results are still brought up to date, and the first exception is rethrown.

Template Parameters:
Parameters:

  • res – [in] Execution resources.

  • g – [inout] The container; its version increases by one.

  • batch – [in] The batch (any memory space; read on the host in this release, so arrays in device memory are copied once under res.get_copy_policy()).

  • results – [inout] The results to update.

Throws:
Returns:

One stats object per result, in order.

template<typename container_t, typename batch_view_t, typename result_t>
std::vector<typename detail::stats_of<result_t>::type> dyng::update_each(const resources &res, container_t &g, const batch_view_t &batch, array_view<result_t*const> results)#

Apply Batches to g once and bring a run-time list of results of one type up to date (for example the K objectives of a multi-objective graph).

The same contract as update(res, g, batch, results…), for a list whose length is known only at run time. The list must not be empty (the variadic update() rejects zero results at compile time; here it is invalid_argument_error, checked before anything changes).

Synchronization:

Blocks until the work has completed (synchronous).

Exception safety:

Strong for every error found before the batch is applied (the before-apply work of every result runs on G_t before the commit): the graph and every result are unchanged. Basic for an error after the commit: the graph holds the new version, the result whose update threw is poisoned (every later use throws stale_result_error), the other results are still brought up to date, and the first exception is rethrown.

Template Parameters:
Parameters:

  • res – [in] Execution resources.

  • g – [inout] The container; its version increases by one.

  • batch – [in] The batch (any memory space; read on the host in this release, so arrays in device memory are copied once under res.get_copy_policy()).

  • results – [inout] Pointers to the results to update (host memory, at least one, none null).

Throws:

  • stale_result_error – if a result does not match g (its version, or the graph state it was computed on).

  • invalid_argument_error – if the list is empty or not in host memory, a pointer is null or a result is listed twice, the batch is invalid, or a batch array must be copied to the host and the copy policy is copy_policy::error.

  • not_supported_error – if the backend of res cannot apply the batch or update a result (vertex operations before 0.4), or a batch array is in device memory and CUDA is not built.

  • out_of_memory_error – if host or device memory cannot be allocated.

  • error – any other exception of an algorithm’s own update() (for example cycle_count’s internal_error or capacity_error, a cuda_error); the first one is rethrown.

Returns:

One stats object per result, in order.

template<typename container_t, typename batch_view_t, typename result_t>
std::vector<typename detail::stats_of<result_t>::type> dyng::update_each(const resources &res, container_t &g, const batch_view_t &batch, array_view<result_t*> results)#

update_each() for a view of mutable pointers, as host_view(std::vector<result_t*>&) gives (the same call; the element type does not deduce through the conversion).

Synchronization:

Blocks until the work has completed (synchronous).

Exception safety:

As update_each().

Template Parameters:
Parameters:

  • res – [in] Execution resources.

  • g – [inout] The container; its version increases by one.

  • batch – [in] The batch (any memory space, as for update_each()).

  • results – [inout] Pointers to the results to update (host memory, none null).

Throws:
Returns:

One stats object per result, in order.

constexpr version_info dyng::header_version() noexcept#

The version of the headers in use.

Returns:

The compile-time version of the dynG headers.

version_info dyng::library_version() noexcept#

The version of the compiled library that is linked in.

Differs from header_version() only if a program was compiled against one release and linked against another.

Returns:

The version the library binary was built with.

DYNG_EXPECTS(cond, ...)#

Check a precondition; throw dyng::invalid_argument_error if it does not hold.

Usage: DYNG_EXPECTS(source < n, "source ", source, " is out of range [0, ", n, ")"); At least one message argument is required. The message receives the condition text and the source file and line.

DYNG_FAIL(...)#

Report a broken internal invariant: throws dyng::internal_error.

Usage: DYNG_FAIL("unexpected row layout ", static_cast<int>(layout)); At least one message argument is required.

DYNG_HAS_OPENMP#

1 if the OpenMP backends were compiled in, else 0.

DYNG_HAS_CUDA#

1 if the CUDA backends were compiled in, else 0.

DYNG_VERSION_MAJOR#

Major version of dynG.

DYNG_VERSION_MINOR#

Minor version of dynG.

DYNG_VERSION_PATCH#

Patch version of dynG.

DYNG_VERSION_STRING#

Full version string as written in the VERSION file (PEP 440, e.g. “0.1.0.dev0”).

DYNG_VERSION#

Single integer for comparisons: MAJOR * 10000 + MINOR * 100 + PATCH.

template<typename value_t>
class array_view#
#include <dyng/core/array_view.hpp>

A non-owning, trivially copyable description of an array: {data, size, space, device}.

One type describes host and device arrays, which keeps public signatures (and the Python bindings, through DLPack) free of memory-space templates. Element access through operator[], begin() and end() is only valid for host-accessible spaces (see is_host_accessible()).

Template Parameters:

value_t – Element type; const value_t for read-only views.

Public Types

using value_type = std::remove_cv_t<value_t>#

the element type without const

using element_type = value_t#

the element type as viewed

using size_type = std::size_t#

the size type

using pointer = value_t*#

pointer to an element

using reference = value_t&#

reference to an element (host spaces only)

using iterator = value_t*#

host iterator

Public Functions

constexpr array_view() noexcept = default#

An empty host view.

inline constexpr array_view(pointer data, size_type size, memory_space space = memory_space::host, int device = -1) noexcept#

View size elements at data.

Parameters:

  • data – [in] Pointer to the first element (may be null if size is 0).

  • size – [in] Number of elements.

  • space – [in] Memory space of the elements.

  • device – [in] CUDA device ordinal for device / managed memory; -1 for host memory.

template<typename other_t, typename = std::enable_if_t<std::is_const_v<value_t> && std::is_same_v<const other_t, value_t>>>
inline constexpr array_view(const array_view<other_t> &other) noexcept#

Implicit conversion from a mutable view to a read-only view.

Template Parameters:

other_t – The element type of the source view (value_type).

Parameters:

other – [in] The mutable view.

inline constexpr pointer data() const noexcept#

Pointer to the first element.

Returns:

The data pointer (may be a device pointer).

inline constexpr size_type size() const noexcept#

Number of elements.

Returns:

The element count.

inline constexpr size_type size_bytes() const noexcept#

Size of the viewed memory in bytes.

Returns:

size() * sizeof(value_t).

inline constexpr bool empty() const noexcept#

Whether the view has no elements.

Returns:

True if size() == 0.

inline constexpr memory_space space() const noexcept#

The memory space of the elements.

Returns:

The space given at construction.

inline constexpr int device() const noexcept#

The CUDA device of the elements.

Returns:

The device ordinal, or -1 for host memory.

inline constexpr reference operator[](size_type i) const noexcept#

Unchecked element access (host-accessible spaces only).

Parameters:

i – [in] Index in [0, size()).

Returns:

Reference to element i.

inline reference at(size_type i) const#

Checked element access (host-accessible spaces only).

Parameters:

i – [in] Index.

Throws:

invalid_argument_error – if i >= size() or the space is not host-accessible.

Returns:

Reference to element i.

inline constexpr iterator begin() const noexcept#

Host iterator to the first element.

Returns:

data().

inline constexpr iterator end() const noexcept#

Host iterator past the last element.

Returns:

data() + size().

inline array_view subview(size_type offset, size_type count) const#

A view of a contiguous sub-range.

Parameters:

  • offset – [in] First element of the sub-range.

  • count – [in] Number of elements.

Throws:

invalid_argument_error – if the range exceeds the view.

Returns:

The view of [offset, offset + count), in the same space and device.

template<typename value_t>
class buffer#
#include <dyng/core/buffer.hpp>

An owning, move-only, UNINITIALIZED array allocated from a memory_resource_ref.

Semantics follow rmm::device_uvector: the elements are not constructed or zeroed, so value_t must be trivially copyable. Allocation and release are ordered on the buffer’s stream. The memory resource must outlive the buffer. With the per-thread default stream (cudaStreamPerThread) that means the stream of the thread that allocates or releases: a buffer released on another thread than the one whose work last used it must be ordered after that work by the caller (or moved to an explicit stream with set_stream()).

Template Parameters:

value_t – Trivially copyable element type.

Public Types

using value_type = value_t#

element type

using size_type = std::size_t#

size type

using pointer = value_t*#

pointer to an element

using const_pointer = const value_t*#

pointer to a const element

Public Functions

inline buffer() noexcept#

An empty host buffer that owns no memory.

inline buffer(size_type size, stream_ref stream, memory_resource_ref mr, int device = -1)#

Allocate size uninitialized elements.

Synchronization:

Stream-ordered; returns before the work completes (asynchronous). The allocation is ordered on stream (host memory resources allocate before returning).

Parameters:

  • size – [in] Number of elements.

  • stream – [in] Stream the allocation is ordered on.

  • mr – [in] Memory resource; must outlive the buffer.

  • device – [in] CUDA device of the memory for device / managed spaces, else -1.

Throws:
inline buffer(const resources &res, size_type size)#

Allocate size uninitialized elements with the memory resource and stream of res.

Synchronization:

Stream-ordered; returns before the work completes (asynchronous). The allocation is ordered on the stream of res (host memory resources allocate before returning).

Parameters:

  • res – [in] Resources providing the memory resource, stream and device.

  • size – [in] Number of elements.

Throws:
inline buffer(buffer &&other) noexcept#

Take over the memory of another buffer.

Parameters:

other – [inout] The source; left empty.

inline buffer &operator=(buffer &&other) noexcept#

Release the current memory and take over the memory of another buffer.

Synchronization:

Stream-ordered; returns before the work completes (asynchronous). The current memory is released in the order of its stream.

Parameters:

other – [inout] The source; left empty.

Returns:

*this.

inline ~buffer()#

Release the memory (stream-ordered).

Synchronization:

Stream-ordered; returns before the work completes (asynchronous). The memory is reused only after the work enqueued on the buffer’s stream before the destruction (host memory is freed at once).

inline pointer data() noexcept#

Pointer to the first element.

Returns:

The data pointer (nullptr if empty).

inline const_pointer data() const noexcept#

Pointer to the first element.

Returns:

The data pointer (nullptr if empty).

inline size_type size() const noexcept#

Number of elements.

Returns:

The element count.

inline bool empty() const noexcept#

Whether the buffer holds no elements.

Returns:

True if size() == 0.

inline memory_space space() const noexcept#

The memory space of the elements.

Returns:

The space of the memory resource.

inline int device() const noexcept#

The CUDA device of the elements.

Returns:

The device ordinal, or -1 for host memory.

inline stream_ref stream() const noexcept#

The stream allocation and release are ordered on.

Returns:

The buffer’s stream.

inline void set_stream(stream_ref stream) noexcept#

Order the buffer’s later release (destruction, move assignment, resize) on another stream.

The caller orders the new stream after the work on the old one that still uses the buffer (rmm::device_uvector::set_stream semantics). The memory itself is not touched.

Synchronization:

Blocks until the work has completed (synchronous). Enqueues no work.

Parameters:

stream – [in] The new stream (of the buffer’s device).

inline memory_resource_ref memory_resource() const noexcept#

The memory resource the buffer allocates from.

Returns:

A reference to the resource.

inline array_view<value_t> view() noexcept#

A mutable view of the elements.

Returns:

array_view over data(), size() in space().

inline array_view<const value_t> view() const noexcept#

A read-only view of the elements.

Returns:

array_view<const value_t> over data(), size() in space().

inline value_t &operator[](size_type i) noexcept#

Unchecked element access (host-accessible spaces only).

Parameters:

i – [in] Index in [0, size()).

Returns:

Reference to element i.

inline const value_t &operator[](size_type i) const noexcept#

Unchecked element access (host-accessible spaces only).

Parameters:

i – [in] Index in [0, size()).

Returns:

Reference to element i.

inline void resize(size_type new_size)#

Change the size; the first min(old, new) elements are kept, new ones are uninitialized.

Synchronization:

Stream-ordered; returns before the work completes (asynchronous). The new allocation, the copy of the kept elements and the release of the old memory are ordered on the buffer’s stream.

Parameters:

new_size – [in] The new element count.

Throws:
class error : public std::runtime_error#
#include <dyng/core/error.hpp>

Base class of every exception thrown by dynG.

Subclassed by dyng::capacity_error, dyng::convergence_error, dyng::cuda_error, dyng::internal_error, dyng::invalid_argument_error, dyng::io_error, dyng::not_supported_error, dyng::out_of_memory_error

class invalid_argument_error : public dyng::error#
#include <dyng/core/error.hpp>

Bad input: ids out of range, wrong layout or backend, violated preconditions.

Subclassed by dyng::stale_result_error

class stale_result_error : public dyng::invalid_argument_error#
#include <dyng/core/error.hpp>

A result was used with a graph whose version no longer matches it.

class io_error : public dyng::error#
#include <dyng/core/error.hpp>

A file could not be read or written, or its content is malformed.

Public Functions

inline explicit io_error(const std::string &message, std::string path = {}, std::int64_t line = 0, std::int64_t column = 0)#

Construct an I/O error with its location.

Parameters:

  • message – [in] Human-readable description.

  • path – [in] The file concerned (may be empty).

  • line – [in] 1-based line number, or 0 if unknown.

  • column – [in] 1-based column number, or 0 if unknown.

inline const std::string &path() const noexcept#

The file concerned.

Returns:

The path given at construction (may be empty).

inline std::int64_t line() const noexcept#

The line of the error.

Returns:

1-based line number, or 0 if unknown.

inline std::int64_t column() const noexcept#

The column of the error.

Returns:

1-based column number, or 0 if unknown.

class capacity_error : public dyng::error#
#include <dyng/core/error.hpp>

A fixed capacity was exceeded (slotted row overflow, 2^31 payload, too many objectives).

class not_supported_error : public dyng::error#
#include <dyng/core/error.hpp>

A backend, type, engine or feature is not built or not implemented.

class convergence_error : public dyng::error#
#include <dyng/core/error.hpp>

An iterative algorithm hit its iteration cap and was asked to fail.

class cuda_error : public dyng::error#
#include <dyng/core/error.hpp>

A CUDA runtime or driver call failed.

Public Functions

inline cuda_error(const std::string &message, int code)#

Construct a CUDA error.

Parameters:

  • message – [in] Description, including the failing call, its source file and line, and the CUDA error string.

  • code – [in] The numeric cudaError_t value.

inline int code() const noexcept#

The CUDA error code.

Returns:

The numeric cudaError_t value.

class out_of_memory_error : public dyng::error#
#include <dyng/core/error.hpp>

A host or device allocation failed.

class internal_error : public dyng::error#
#include <dyng/core/error.hpp>

A broken internal invariant: a library bug. Please report it.

class memory_resource_ref#
#include <dyng/core/memory.hpp>

Non-owning, type-erased reference to a stream-ordered memory resource.

Any object with the members void* allocate(stream_ref, std::size_t bytes, std::size_t alignment), void deallocate(stream_ref, void*, std::size_t bytes, std::size_t alignment) noexcept, void* allocate_sync(std::size_t bytes, std::size_t alignment), void deallocate_sync(void*, std::size_t bytes, std::size_t alignment) noexcept and memory_space space() const noexcept can be referenced. The referenced resource must outlive the reference and every allocation made through it.

Public Functions

template<typename resource_t, typename = std::enable_if_t<!std::is_same_v<std::decay_t<resource_t>, memory_resource_ref>>>
inline memory_resource_ref(resource_t &resource) noexcept#

Refer to a resource.

Template Parameters:

resource_t – A type providing the members listed in the class description.

Parameters:

resource – [in] The resource; not owned.

inline void *allocate(stream_ref stream, std::size_t bytes, std::size_t alignment)#

Allocate stream-ordered memory.

Synchronization:

Stream-ordered; returns before the work completes (asynchronous). Ordered on stream for stream-ordered resources (cuda_async_memory_resource); host resources return memory that is usable at once.

Parameters:

  • stream – [in] The stream the allocation is ordered on.

  • bytes – [in] Size in bytes.

  • alignment – [in] Alignment in bytes (a power of two).

Throws:

out_of_memory_error – if the allocation fails.

Returns:

Pointer to at least bytes bytes.

inline void deallocate(stream_ref stream, void *ptr, std::size_t bytes, std::size_t alignment) noexcept#

Release stream-ordered memory.

Synchronization:

Stream-ordered; returns before the work completes (asynchronous). Ordered on stream for stream-ordered resources; what a resource does is stated on its own deallocate() (pinned host memory waits for the stream).

Parameters:

  • stream – [in] The stream the release is ordered on.

  • ptr – [in] Pointer returned by allocate() of the same resource.

  • bytes – [in] The size passed to allocate().

  • alignment – [in] The alignment passed to allocate().

inline void *allocate_sync(std::size_t bytes, std::size_t alignment)#

Allocate memory that is usable as soon as the call returns.

Synchronization:

Blocks until the work has completed (synchronous). The memory is usable by any stream and the host as soon as the call returns.

Parameters:

  • bytes – [in] Size in bytes.

  • alignment – [in] Alignment in bytes (a power of two).

Throws:
Returns:

Pointer to at least bytes bytes.

inline void deallocate_sync(void *ptr, std::size_t bytes, std::size_t alignment) noexcept#

Release memory obtained from allocate_sync().

Synchronization:

Blocks until the work has completed (synchronous). The memory is released at once: all work using it must have completed.

Parameters:
inline memory_space space() const noexcept#

The memory space of every allocation of the resource.

Returns:

The resource’s memory space.

Friends

inline friend bool operator==(const memory_resource_ref &lhs, const memory_resource_ref &rhs) noexcept#

Whether two references refer to the same resource object.

Parameters:

  • lhs – [in] First reference.

  • rhs – [in] Second reference.

Returns:

True if both refer to the same object.

inline friend bool operator!=(const memory_resource_ref &lhs, const memory_resource_ref &rhs) noexcept#

Whether two references refer to different resource objects.

Parameters:

  • lhs – [in] First reference.

  • rhs – [in] Second reference.

Returns:

True if the objects differ.

class host_memory_resource#
#include <dyng/core/memory.hpp>

Pageable host memory from the global aligned operator new.

Stateless: every instance is interchangeable. The stream arguments are ignored (host allocations are immediately usable).

Public Functions

void *allocate(stream_ref stream, std::size_t bytes, std::size_t alignment)#

Allocate host memory.

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

  • stream – [in] Ignored.

  • bytes – [in] Size in bytes.

  • alignment – [in] Alignment in bytes (a power of two).

Throws:
Returns:

Pointer to at least bytes bytes (non-null, also for 0 bytes).

void deallocate(stream_ref stream, void *ptr, std::size_t bytes, std::size_t alignment) noexcept#

Release host memory.

Synchronization:

Blocks until the work has completed (synchronous). The memory is freed at once: the caller must not release memory that enqueued work still uses.

Parameters:

  • stream – [in] Ignored.

  • ptr – [in] Pointer returned by allocate() or allocate_sync().

  • bytes – [in] The size passed at allocation.

  • alignment – [in] The alignment passed at allocation.

void *allocate_sync(std::size_t bytes, std::size_t alignment)#

Allocate host memory.

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

  • bytes – [in] Size in bytes.

  • alignment – [in] Alignment in bytes (a power of two).

Throws:
Returns:

Pointer to at least bytes bytes.

void deallocate_sync(void *ptr, std::size_t bytes, std::size_t alignment) noexcept#

Release host memory.

Synchronization:

Blocks until the work has completed (synchronous). The memory is freed at once.

Parameters:

  • ptr – [in] Pointer returned by allocate() or allocate_sync().

  • bytes – [in] The size passed at allocation.

  • alignment – [in] The alignment passed at allocation.

inline memory_space space() const noexcept#

The memory space of the allocations.

Returns:

memory_space::host.

Friends

inline friend bool operator==(const host_memory_resource&, const host_memory_resource&) noexcept#

Host resources are interchangeable (stateless).

Returns:

True.

inline friend bool operator!=(const host_memory_resource&, const host_memory_resource&) noexcept#

Host resources are interchangeable (stateless).

Returns:

False.

class cuda_async_memory_resource#
#include <dyng/core/memory.hpp>

Device memory from a stream-ordered memory pool (cudaMallocFromPoolAsync); the default resource of the CUDA backend.

Each object owns its own pool on one device (it never changes the device’s default pool, which belongs to the application). Freed memory stays in the pool (release threshold: unlimited), so once a workload has reached its peak, further allocations and releases do not call into the driver and do not synchronize (invariant I9). Allocations are aligned to 256 bytes.

The resource is neither copyable nor movable: memory_resource_ref and buffer refer to it by address. Destroying it returns the pool’s memory to the device once every allocation made from it has been released.

Public Functions

explicit cuda_async_memory_resource(int device = 0)#

Create a pool on a device.

Parameters:

device – [in] CUDA device ordinal.

Throws:
cuda_async_memory_resource(const cuda_async_memory_resource&) = delete#

not copyable

cuda_async_memory_resource &operator=(const cuda_async_memory_resource&) = delete#

no copy

cuda_async_memory_resource(cuda_async_memory_resource&&) = delete#

not movable

cuda_async_memory_resource &operator=(cuda_async_memory_resource&&) = delete#

not movable

~cuda_async_memory_resource()#

Destroy the pool (deferred by the driver until every allocation is released).

void *allocate(stream_ref stream, std::size_t bytes, std::size_t alignment)#

Allocate device memory, ordered on a stream.

The memory may be used by work enqueued on stream after this call; other streams must be ordered after it (events or synchronization).

Synchronization:

Stream-ordered; returns before the work completes (asynchronous).

Parameters:

  • stream – [in] The stream (of this resource’s device).

  • bytes – [in] Size in bytes (0 gives nullptr).

  • alignment – [in] Alignment in bytes: a power of two, at most 256.

Throws:
Returns:

Device pointer.

void deallocate(stream_ref stream, void *ptr, std::size_t bytes, std::size_t alignment) noexcept#

Release memory, ordered on a stream: it is reused only after the work enqueued on stream before this call has completed.

Synchronization:

Stream-ordered; returns before the work completes (asynchronous).

Parameters:

  • stream – [in] The stream.

  • ptr – [in] Pointer returned by this resource (nullptr is ignored).

  • bytes – [in] The size passed at allocation.

  • alignment – [in] The alignment passed at allocation.

void *allocate_sync(std::size_t bytes, std::size_t alignment)#

Allocate device memory that every stream may use as soon as the call returns.

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

  • bytes – [in] Size in bytes.

  • alignment – [in] Alignment in bytes: a power of two, at most 256.

Throws:
Returns:

Device pointer.

void deallocate_sync(void *ptr, std::size_t bytes, std::size_t alignment) noexcept#

Release memory obtained from allocate_sync(); all work using it must have completed.

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

  • ptr – [in] Pointer returned by this resource (nullptr is ignored).

  • bytes – [in] The size passed at allocation.

  • alignment – [in] The alignment passed at allocation.

inline memory_space space() const noexcept#

The memory space of the allocations.

Returns:

memory_space::device.

inline int device() const noexcept#

The device of the pool.

Returns:

The device ordinal.

std::size_t used_bytes() const#

Bytes currently allocated from the pool and not yet released.

Throws:

cuda_error – if the runtime reports an error.

Returns:

The pool’s used memory.

std::size_t reserved_bytes() const#

Bytes the pool holds from the device (used plus cached for reuse).

Throws:

cuda_error – if the runtime reports an error.

Returns:

The pool’s reserved memory.

Friends

inline friend bool operator==(const cuda_async_memory_resource &lhs, const cuda_async_memory_resource &rhs) noexcept#

Whether two references denote the same pool.

Parameters:

  • lhs – [in] First resource.

  • rhs – [in] Second resource.

Returns:

True if they are the same object.

inline friend bool operator!=(const cuda_async_memory_resource &lhs, const cuda_async_memory_resource &rhs) noexcept#

Whether two references denote different pools.

Parameters:

  • lhs – [in] First resource.

  • rhs – [in] Second resource.

Returns:

True if they are different objects.

class pinned_host_memory_resource#
#include <dyng/core/memory.hpp>

Page-locked (pinned) host memory, usable by asynchronous copies from and to every device.

Stateless: every instance is interchangeable. Allocation is synchronous and costly (it maps the pages for DMA), so the library allocates staging buffers once per workspace and reuses them.

Public Functions

void *allocate(stream_ref stream, std::size_t bytes, std::size_t alignment)#

Allocate pinned host memory.

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

  • stream – [in] Ignored: the memory is usable when the call returns.

  • bytes – [in] Size in bytes (0 gives nullptr).

  • alignment – [in] Alignment in bytes: a power of two, at most 256.

Throws:
Returns:

Host pointer, also valid in device code through unified addressing.

void deallocate(stream_ref stream, void *ptr, std::size_t bytes, std::size_t alignment) noexcept#

Release pinned host memory after the work enqueued on stream has completed (the call waits for the stream).

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

  • stream – [in] The stream the memory was last used on.

  • ptr – [in] Pointer returned by this resource (nullptr is ignored).

  • bytes – [in] The size passed at allocation.

  • alignment – [in] The alignment passed at allocation.

void *allocate_sync(std::size_t bytes, std::size_t alignment)#

Allocate pinned host memory.

Synchronization:

Blocks until the work has completed (synchronous). cudaHostAlloc: the memory is usable as soon as the call returns.

Parameters:

  • bytes – [in] Size in bytes (0 gives nullptr).

  • alignment – [in] Alignment in bytes: a power of two, at most 256.

Throws:
Returns:

Host pointer.

void deallocate_sync(void *ptr, std::size_t bytes, std::size_t alignment) noexcept#

Release pinned host memory; all work using it must have completed.

Synchronization:

Blocks until the work has completed (synchronous). cudaFreeHost, at once (errors are logged).

Parameters:

  • ptr – [in] Pointer returned by this resource (nullptr is ignored).

  • bytes – [in] The size passed at allocation.

  • alignment – [in] The alignment passed at allocation.

inline memory_space space() const noexcept#

The memory space of the allocations.

Returns:

memory_space::pinned_host.

Friends

inline friend bool operator==(const pinned_host_memory_resource&, const pinned_host_memory_resource&) noexcept#

Pinned resources are interchangeable (stateless).

Returns:

True.

inline friend bool operator!=(const pinned_host_memory_resource&, const pinned_host_memory_resource&) noexcept#

Pinned resources are interchangeable (stateless).

Returns:

False.

struct profiler_options#
#include <dyng/core/profiler.hpp>

Profiler settings.

Public Members

bool sync_stages = false#

Synchronize the resources’ stream at stage boundaries, so stage times are paper-comparable breakdowns (adds synchronization; host backends are unaffected).

bool nvtx = false#

Emit an NVTX range per stage (push at its start, pop at its end), for Nsight Systems and other NVTX tools. Needs a build with DYNG_WITH_NVTX (ON in CUDA builds whose toolkit ships NVTX 3); ignored otherwise.

bool cuda_events = false#

Time stages with CUDA events on the device (CUDA backend only; ignored otherwise).

struct stage_record#
#include <dyng/core/profiler.hpp>

Aggregate of all calls of one stage.

Public Members

std::string name#

<algo>.<hook>[.<sub>]

int depth = 0#

nesting depth at the first call (0 = outermost)

std::int64_t calls = 0#

number of completed calls

double host_ms = 0.0#

total host wall time in milliseconds

double device_ms = 0.0#

total device time in milliseconds (0 without CUDA events)

struct stage_sample#
#include <dyng/core/profiler.hpp>

One completed call of a stage.

Public Members

std::string name#

<algo>.<hook>[.<sub>]

int depth = 0#

nesting depth of this call

double host_ms = 0.0#

host wall time in milliseconds

double device_ms = 0.0#

device time in milliseconds (0 without CUDA events)

struct counter_record#
#include <dyng/core/profiler.hpp>

A named counter (summed over all additions).

Public Members

std::string name#

<algo>.<name>[.<sub>]

std::int64_t value = 0#

the sum of all added values

class profiler#
#include <dyng/core/profiler.hpp>

Records stage times and counters of library calls.

Thread safety: recording is safe from several threads at once. Library calls that run concurrently through copies of one resources handle (which share its profiler) record into the same profiler; the stages of each calling thread nest separately (a stage’s depth is its depth on its own thread), and the aggregated records combine every thread’s calls. Reading the records (stages(), samples(), counters(), write_csv(), write_json()) and reset() must not overlap a call that records: read them after the calls returned (the references stay valid until the next recording or reset()).

Public Functions

explicit profiler(profiler_options options = {})#

Create a profiler.

Parameters:

options – [in] Settings.

inline const profiler_options &options() const noexcept#

The settings.

Returns:

The options given at construction.

void begin_stage(std::string_view name)#

Start a stage (prefer scoped_stage).

Parameters:

name – [in] Stage name <algo>.<hook>[.<sub>] in dotted lower case.

Throws:

invalid_argument_error – if name does not follow the naming scheme.

void end_stage(double device_ms = 0.0)#

End the innermost open stage.

Parameters:

device_ms – [in] Device time of the stage in milliseconds, if measured (else 0).

Throws:

invalid_argument_error – if no stage is open.

void add_counter(std::string_view name, std::int64_t value)#

Add to a counter (created with value 0 on first use).

Parameters:

  • name – [in] Counter name <algo>.<name>[.<sub>] in dotted lower case.

  • value – [in] The amount to add.

Throws:

invalid_argument_error – if name does not follow the naming scheme.

inline const std::vector<stage_record> &stages() const noexcept#

Aggregated stages in order of first call.

Returns:

One record per stage name.

inline const std::vector<stage_sample> &samples() const noexcept#

Every completed stage call in completion order.

Returns:

The samples.

inline const std::vector<counter_record> &counters() const noexcept#

Counters in order of first use.

Returns:

One record per counter name.

double total_host_ms(std::string_view name) const noexcept#

Total host time of a stage.

Parameters:

name – [in] Stage name.

Returns:

The summed host milliseconds, or 0 if the stage was never recorded.

std::int64_t counter(std::string_view name) const noexcept#

Value of a counter.

Parameters:

name – [in] Counter name.

Returns:

The counter value, or 0 if the counter was never used.

void reset()#

Drop all records, samples and counters.

Throws:

invalid_argument_error – if a stage is still open.

void write_csv(std::ostream &out) const#

Write CSV kind,name,value: one stage row per sample (milliseconds, %.6f) followed by one counter row per counter, as the MOSP --timing CSV.

Parameters:

out – [out] The stream.

void write_json(std::ostream &out) const#

Write JSON {"stages": [...], "counters": [...]} with the aggregated records.

Parameters:

out – [out] The stream.

Public Static Functions

static bool is_valid_name(std::string_view name) noexcept#

Whether a name follows <algo>.<hook>[.<sub>]: two or more dot-separated parts, each starting with a lower-case letter followed by lower-case letters, digits or ‘_’.

Parameters:

name – [in] The name.

Returns:

True if the name is valid.

class scoped_stage#
#include <dyng/core/profiler.hpp>

RAII stage: begins a stage on construction and ends it on destruction.

Library code writes scoped_stage stage(res, "sssp.loop");. It does nothing when no profiler is attached. With profiler_options::sync_stages the resources are synchronized at both ends. With profiler_options::cuda_events and resources of the CUDA backend, the stage also records a CUDA event on the stream of the resources at both ends; the end waits for the second event and adds the elapsed device time to the stage’s device_ms.

Public Functions

scoped_stage(const resources &res, std::string_view name)#

Begin a stage on the profiler attached to res (if any).

Synchronization:

Blocks until the work has completed (synchronous). With profiler_options::sync_stages the resources are synchronized first; otherwise only a host timestamp is taken (and, with profiler_options::cuda_events on the CUDA backend, an event is recorded on the stream).

Parameters:

  • res – [in] Resources; must outlive the scoped_stage.

  • name – [in] Stage name <algo>.<hook>[.<sub>].

Throws:
scoped_stage(profiler *p, std::string_view name)#

Begin a stage on p (if not null), without synchronization.

Parameters:

  • p – [in] The profiler, or nullptr.

  • name – [in] Stage name <algo>.<hook>[.<sub>].

Throws:

invalid_argument_error – if p is not null and name is invalid.

~scoped_stage()#

End the stage (if still open).

void stop() noexcept#

End the stage early.

struct algorithm_info#
#include <dyng/core/registry.hpp>

One registered algorithm, as its manifest (cpp/src/algorithms/NAME/manifest.toml) declares it.

Every field is fixed at build time; the strings are static.

Public Members

std::string_view name#

the algorithm’s name: its namespace and header (e.g. “sssp”)

std::string_view title#

a one-line title

algorithm_family family = algorithm_family::fixed_point#

the update family

container_kind container = container_kind::graph#

the container it runs on

maturity_level maturity = maturity_level::experimental#

the maturity level

determinism determinism_level = determinism::bitwise#

the determinism level

oracle_kind oracle = oracle_kind::compute#

the oracle kind

std::vector<backend> backends#

The backends the algorithm implements (sequential first); intersect with backend_available() for the ones this build can run.

std::vector<std::string_view> cite#

keys of docs/references.bib (dyng::citation(name))

class resources#
#include <dyng/core/resources.hpp>

Execution resources: backend, device, stream, memory resource, thread count, profiler.

Cheap to copy: copies share one handle, so set_memory_resource(), set_copy_policy() and attach_profiler() affect every copy. Call them during setup, not while another thread uses the handle; for independent settings create a new resources object. The library never creates streams, sets environment variables, or changes the global OpenMP thread count on its own. A moved-from handle stays valid: moving shares the handle like a copy (the source keeps it), so no accessor ever meets an empty handle.

The default stream is per thread. A CUDA handle created with the default stream_ref uses cudaStreamPerThread, which CUDA defines as a different stream on every host thread. Copies of such a handle share the device, memory resource, profiler and workspaces, but work enqueued through them on two threads runs on two streams: synchronize() and the release of memory wait for (or are ordered on) the calling thread’s stream only, and ordering work across threads is the caller’s job, as with two explicit streams. A handle created with an explicit stream uses that one stream on every thread (ADR 0016 item 10).

Scratch memory. The handle also caches the engines’ workspaces (scratch memory such as the frontier lists of sssp): a compute() or update() leases one from the handle, sizes it once and returns it, so results that run one after another through the same handle (for example the K objectives updated by dyng::update_each()) share one workspace, and a steady-state update allocates no scratch memory (ADR 0015). Calls that run concurrently on copies of one handle get distinct workspaces; a workspace reused on another stream (another thread’s default stream) waits for the device work of its previous use first. The cache lives as long as the last copy of the handle, or until release_workspaces().

Public Functions

resources()#

Resources for default_backend() with its default settings.

Throws:

not_supported_error – if the default backend cannot be initialised.

resources(const resources &other) noexcept#

Share the handle of other (a cheap copy; settings stay shared).

Parameters:

other – [in] The handle to share.

resources(resources &&other) noexcept#

Share the handle of other; other keeps it and stays valid (a move is a copy).

Parameters:

other – [in] The handle to share.

resources &operator=(const resources &other) noexcept#

Share the handle of other (a cheap copy; settings stay shared).

Parameters:

other – [in] The handle to share.

Returns:

*this.

resources &operator=(resources &&other) noexcept#

Share the handle of other; other keeps it and stays valid (a move is a copy).

Parameters:

other – [in] The handle to share.

Returns:

*this.

~resources()#

Release this reference to the shared handle.

backend get_backend() const noexcept#

The backend.

Returns:

The backend chosen at construction.

int device() const noexcept#

The CUDA device.

Returns:

The device ordinal for the CUDA backend, -1 for host backends.

stream_ref stream() const noexcept#

The stream all work is ordered on.

Returns:

The stream (the per-thread default stream unless one was given; that handle means the calling thread’s own stream).

int num_threads() const noexcept#

The number of host threads the backend uses.

Returns:

1 for sequential; the OpenMP team size for openmp; for cuda the OpenMP threads of the host-side work (graph builds and applies, tree imports and checks), fixed when the handle was created.

memory_space default_space() const noexcept#

The memory space results and containers are placed in by default.

Returns:

memory_space::host for host backends, memory_space::device for cuda.

memory_resource_ref memory() const noexcept#

The memory resource used for library allocations.

Returns:

A reference to the current resource (the default host resource for host backends, default_device_memory_resource(device()) for cuda).

void set_memory_resource(memory_resource_ref mr)#

Replace the memory resource (affects every copy of this handle).

The cached workspaces are released first (they were allocated from the previous resource).

Synchronization:

Blocks until the work has completed (synchronous). The idle workspaces are returned to the previous resource after the device work of their last use has completed (it may have run on another thread’s default stream); calls made after this one returns use the new resource.

Parameters:

mr – [in] The new resource; must outlive every allocation made through it.

Throws:

invalid_argument_error – if the resource’s space does not suit the backend (host backends need a host-accessible space, cuda a device or managed space).

copy_policy get_copy_policy() const noexcept#

The policy for implicit host/device copies of inputs.

Returns:

The current policy (default copy_policy::allow).

void set_copy_policy(copy_policy policy) noexcept#

Set the policy for implicit copies of inputs between memory spaces (affects every copy of the handle; see copy_policy for where such copies happen).

Parameters:

policy – [in] The new policy (copy_policy::error makes every implicit copy an invalid_argument_error, raised before anything is changed).

void attach_profiler(profiler *p) noexcept#

Attach a profiler that records the library’s stages and counters.

Every copy of the handle records into it. Library calls that run concurrently through copies may record at the same time (profiler recording is thread-safe); read the records after those calls returned (see profiler). Like the other setters, call it during setup, not while another thread uses the handle.

Parameters:

p – [in] The profiler (not owned; must outlive its attachment); nullptr detaches.

profiler *get_profiler() const noexcept#

The attached profiler.

Returns:

The profiler, or nullptr if none is attached.

void release_workspaces() const noexcept#

Free the cached workspaces that are not in use (affects every copy).

The next compute() or update() through the handle sizes a new workspace (allocates). Safe to call while another thread uses the handle: a workspace in use returns to the cache afterwards.

Synchronization:

Blocks until the work has completed (synchronous). Waits until the device work of each idle workspace’s last use has completed (it may have run on another thread’s default stream), then releases its memory on the calling thread’s view of the handle’s stream; host workspaces are freed at once.

std::size_t workspace_bytes() const#

The scratch memory the handle caches (shared by every copy).

Returns:

Bytes held by the cached workspaces that are not in use right now.

void warm_up() const#

Initialise the backend ahead of timed work.

CUDA: creates the device’s context, loads every kernel of the library (under lazy module loading, the CUDA default, each kernel would otherwise be loaded inside its first call), and primes the stream and the memory resource. This replaces setting CUDA_MODULE_LOADING=EAGER in the environment, which a library must not do. A no-op for host backends.

Synchronization:

Blocks until the work has completed (synchronous).

Throws:

cuda_error – if the CUDA runtime reports an error.

void synchronize() const#

Wait for the work enqueued on the handle’s stream.

With an explicit stream: all work enqueued through any copy of the handle. With the default stream (cudaStreamPerThread): the work the CALLING thread enqueued on its own default stream of the handle’s device; work that other threads enqueued through copies of the handle is on their streams and is not waited for. A no-op for host backends, whose calls complete before returning.

Synchronization:

Blocks until the work has completed (synchronous).

Throws:

cuda_error – if the CUDA runtime reports an error.

Public Static Functions

static resources sequential()#

The sequential (reference) backend: one host thread, host memory.

Returns:

New resources for backend::sequential.

static resources openmp(int num_threads = 0)#

The OpenMP backend.

Parameters:

num_threads – [in] Threads used by OpenMP parallel regions of the library; 0 = the OpenMP default at the time of the call (omp_get_max_threads(), which honours OMP_NUM_THREADS).

Throws:
Returns:

New resources for backend::openmp.

static resources cuda(int device = 0, stream_ref stream = {}, int host_threads = 0)#

The CUDA backend on one device and stream.

Records the device’s capabilities once (cooperative launch, multiprocessor count), which the engines read instead of querying the device on every call. Memory comes from the device’s default resource (default_device_memory_resource(): a stream-ordered cudaMallocAsync pool); host staging buffers from default_pinned_host_memory_resource(). The library never creates streams: all work is ordered on stream, which must outlive every copy of the handle and every buffer allocated through it. Every call that enqueues work makes device current for its duration and restores the caller’s current device. The host-side work of a call through the handle (graph builds and batch applies, tree imports and checks, which run on the host next to the device in this release) uses host_threads OpenMP threads, fixed at creation like resources::openmp()’s thread count.

Synchronization:

Blocks until the work has completed (synchronous). Queries the device once; enqueues no work on stream.

Parameters:

  • device – [in] CUDA device ordinal.

  • stream – [in] Stream for all work, created on device; the default is the per-thread default stream (cudaStreamPerThread: the calling thread’s stream, a different one on every thread), never the legacy stream.

  • host_threads – [in] OpenMP threads for the host-side work; 0 = the OpenMP default at the time of the call (omp_get_max_threads(), which honours OMP_NUM_THREADS); 1 without OpenMP.

Throws:
Returns:

New resources for backend::cuda.

struct update_stats#
#include <dyng/core/stats.hpp>

Counters common to every update(); each algorithm’s stats derives from it and appends its own fields.

Each field is documented as deterministic (identical across runs and backends, so tests may assert it), deterministic per backend (identical across runs on one backend, but it may differ between backends because it describes the backend’s engine; tests may compare it between runs of one backend only) or schedule-dependent (it may vary with the thread schedule; log it only). Timing is never a statistic: it goes through the profiler.

Subclassed by dyng::cycle_count::stats, dyng::dynamic_bfs::stats, dyng::mosp::stats, dyng::sssp::stats, dyng::triangle_delta::stats

Public Members

std::int64_t affected = 0#

Deterministic: the number of elements whose value changed (for sssp: vertices whose distance or parent differs after the update). 0 for an update that changes nothing.

std::int64_t iterations = 0#

Schedule-dependent: rounds of the Step 2 loop.

std::int64_t frontier_visits = 0#

Schedule-dependent: elements expanded by the Step 2 loop (frontier visits).

bool fallback_used = false#

Deterministic: true if the update recomputed from scratch instead of updating incrementally (a documented policy such as a budget; never silently).

bool converged = true#

Deterministic: false if an iteration cap was reached (reported under on_limit::report).

engine engine_used = engine::automatic#

Deterministic per backend: the engine that ran (engine::fused for a ported paper engine, engine::operators for a hook-by-hook composition). It differs between backends when they run different engines (for sssp: operators on sequential, fused on openmp, and on cuda fused or operators: options::cuda_engine, with engine::automatic falling back to operators on a device without cooperative launch).

class stream_ref#
#include <dyng/core/stream.hpp>

A non-owning reference to a CUDA stream.

A default stream_ref is the explicit per-thread default stream (cudaStreamPerThread), never the legacy stream (handle 0); pass handle 0 explicitly to use the legacy stream. The per-thread default stream is a different stream on every host thread (and per device): the same stream_ref value used on two threads names two streams. On builds without CUDA, and for host backends, a stream_ref is carried along but no work is enqueued on it.

Public Functions

stream_ref() noexcept#

The per-thread default stream (cudaStreamPerThread).

inline explicit stream_ref(cuda_stream_handle stream) noexcept#

Refer to an existing stream.

Parameters:

stream – [in] The stream handle (a cudaStream_t); not owned.

inline cuda_stream_handle get() const noexcept#

The underlying handle.

Returns:

The cudaStream_t this object refers to.

bool is_per_thread_default() const noexcept#

Whether this is the per-thread default stream.

Returns:

True if the handle is cudaStreamPerThread.

void synchronize() const#

Wait until all work enqueued on the stream has completed.

For the per-thread default stream: the calling thread’s default stream of the CURRENT device (resources::synchronize() makes the handle’s device current first). A no-op in builds without CUDA.

Synchronization:

Blocks until the work has completed (synchronous).

Throws:

cuda_error – if the CUDA runtime reports an error.

Friends

inline friend bool operator==(stream_ref lhs, stream_ref rhs) noexcept#

Compare two stream references.

Parameters:

  • lhs – [in] First stream.

  • rhs – [in] Second stream.

Returns:

True if both refer to the same handle.

inline friend bool operator!=(stream_ref lhs, stream_ref rhs) noexcept#

Compare two stream references.

Parameters:

  • lhs – [in] First stream.

  • rhs – [in] Second stream.

Returns:

True if the handles differ.

struct unweighted#
#include <dyng/core/types.hpp>

Weight tag for graphs without edge weights (e.g. cycle_count).

A graph<V, E, unweighted> has no weight columns (num_weights() == 0), and its batches carry no insertion weights. All values of the tag are equal, so containers of it compare as usual.

Friends

inline friend constexpr bool operator==(unweighted, unweighted) noexcept#

Equality: every value equals every other.

Returns:

true.

inline friend constexpr bool operator!=(unweighted, unweighted) noexcept#

Inequality: no value differs from another.

Returns:

false.

inline friend constexpr bool operator<(unweighted, unweighted) noexcept#

Order: no value is smaller than another.

Returns:

false.

inline friend constexpr bool operator>(unweighted, unweighted) noexcept#

Order: no value is larger than another.

Returns:

false.

struct version_info#
#include <dyng/version.hpp>

Version of the library the program was compiled against (the header version).

Public Members

int major_version#

DYNG_VERSION_MAJOR (not major: glibc may define a macro of that name).

int minor_version#

DYNG_VERSION_MINOR.

int patch_version#

DYNG_VERSION_PATCH.

const char *string#

DYNG_VERSION_STRING.

On this page
Edit on GitHub