Parallel synchronous double-buffered engine. More...

#include <tpl_ca_parallel_engine.H>

Collaboration diagram for Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >:

Public Types
using	lattice_type = Lattice

using	rule_type = Rule

using	neighborhood_type = Neighborhood

using	order_type = Order

using	state_type = typename Lattice::state_type

using	coord_type = typename Lattice::coord_type

using	extents_type = typename Lattice::extents_type

using	hook_type = std::function< void(std::size_t, const Lattice &)>
	Hook signature: `(step_index, frame)`.

Public Member Functions
	Parallel_Synchronous_Engine (Lattice initial, Rule r, Neighborhood n, Parallel_Engine_Config cfg={})
	Build an engine on top of an existing initial lattice.

	Parallel_Synchronous_Engine (Lattice initial, Rule r, Parallel_Engine_Config cfg={})
	Build an engine with a default-constructed neighbourhood.

const Lattice &	frame () const noexcept
	Return the current frame.

std::size_t	steps_run () const noexcept
	Return the number of completed steps.

const extents_type &	extents () const noexcept

const Parallel_Engine_Config &	config () const noexcept

void	set_config (Parallel_Engine_Config cfg) noexcept
	Replace the configuration. Takes effect on the next `step()`.

template<typename F >
void	on_pre_step (F &&f)
	Register a hook fired before every `step()`.

template<typename F >
void	on_post_step (F &&f)
	Register a hook fired after every `step()`.

void	step ()
	Apply the rule to every cell once and swap buffers.

void	run (const std::size_t steps)
	Run several synchronous steps.

Static Public Attributes
static constexpr std::size_t	rank = Lattice::rank
	Lattice dimension.

static constexpr std::size_t	neighbour_count = Neighborhood::size_v
	Number of neighbours.

Private Member Functions
void	compute_cell (const coord_type &c) const =delete

void	update_cell (const coord_type &c, std::span< state_type > nbuf)
	Update a single cell `c`: gather its neighbours, evaluate the rule and write the result into `nxt_buf_`.

void	update_slab_1d (const ca_size_t r_begin, const ca_size_t r_end)

void	update_slab_2d_row_major (const ca_size_t r_begin, const ca_size_t r_end)

template<std::size_t TileW, std::size_t TileH>
void	update_slab_2d_tile (const ca_size_t r_begin, const ca_size_t r_end)

void	update_slab_3d_row_major (const ca_size_t r_begin, const ca_size_t r_end)

void	process_slab (const ca_size_t r_begin, const ca_size_t r_end)
	Drive the iteration over a single row slab according to `Order`.

std::size_t	effective_partitions (ThreadPool *pool) const noexcept
	Resolve the effective number of partitions for the next `step()`.

Private Attributes
Lattice	cur_buf_

Lattice	nxt_buf_

Rule	rule_

Neighborhood	nh_

hook_type	pre_hook_

hook_type	post_hook_

std::size_t	step_count_ = 0

Parallel_Engine_Config	cfg_ {}

Detailed Description

template<typename Lattice, typename Rule, typename Neighborhood, typename Order = RowMajor>
class Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >

Parallel synchronous double-buffered engine.

Same template parameters as Synchronous_Engine. The only user-visible additions are the configuration knobs and the fact that step() schedules work on a thread pool when the lattice is large enough.

Template Parameters

Lattice	lattice type satisfying `LatticeLike`.
Rule	rule type satisfying `RuleLike<Rule, Lattice>`.
Neighborhood	neighbourhood type satisfying `NeighborhoodLike`.
Order	iteration order tag (`RowMajor` or `Tile<W, H>`).

Complexity: step() is O((N * S) / P) wall-clock with P workers, where N is the cell count and S is the neighbour count.

Thread-safety: The engine is not concurrent: only one driving thread should call step() / run() at a time. Worker threads inside the pool cooperate without synchronisation by reading the previous frame (read-only) and writing into disjoint slices of the next frame. Bit-packed Bit_Cell_Storage writes are safely parallelized because the underlying bits use atomic operations to avoid data races.

Definition at line 186 of file tpl_ca_parallel_engine.H.

Member Typedef Documentation

◆ coord_type

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

using Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::coord_type = typename Lattice::coord_type

Definition at line 201 of file tpl_ca_parallel_engine.H.

◆ extents_type

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

using Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::extents_type = typename Lattice::extents_type

Definition at line 202 of file tpl_ca_parallel_engine.H.

◆ hook_type

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

using Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::hook_type = std::function<void(std::size_t, const Lattice &)>

Hook signature: (step_index, frame).

Definition at line 210 of file tpl_ca_parallel_engine.H.

◆ lattice_type

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

using Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::lattice_type = Lattice

Definition at line 195 of file tpl_ca_parallel_engine.H.

◆ neighborhood_type

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

using Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::neighborhood_type = Neighborhood

Definition at line 197 of file tpl_ca_parallel_engine.H.

◆ order_type

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

using Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::order_type = Order

Definition at line 198 of file tpl_ca_parallel_engine.H.

◆ rule_type

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

using Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::rule_type = Rule

Definition at line 196 of file tpl_ca_parallel_engine.H.

◆ state_type

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

using Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::state_type = typename Lattice::state_type

Definition at line 200 of file tpl_ca_parallel_engine.H.

Constructor & Destructor Documentation

◆ Parallel_Synchronous_Engine() [1/2]

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::Parallel_Synchronous_Engine	(	Lattice	initial,
		Rule	r,
		Neighborhood	n,
		Parallel_Engine_Config	cfg = `{}`
	)

inline

Build an engine on top of an existing initial lattice.

Parameters

[in]	initial	initial lattice (consumed by move).
[in]	r	rule instance.
[in]	n	neighbourhood instance.
[in]	cfg	parallel-engine configuration.

Exceptions

std::bad_alloc on next-buffer allocation.

Complexity: O(N) for allocating the next buffer.

Definition at line 377 of file tpl_ca_parallel_engine.H.

◆ Parallel_Synchronous_Engine() [2/2]

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::Parallel_Synchronous_Engine	(	Lattice	initial,
		Rule	r,
		Parallel_Engine_Config	cfg = `{}`
	)

inline

Build an engine with a default-constructed neighbourhood.

Parameters

[in]	initial	initial lattice (consumed by move).
[in]	r	rule instance.
[in]	cfg	parallel-engine configuration.

Exceptions

std::bad_alloc on next-buffer allocation.

Definition at line 390 of file tpl_ca_parallel_engine.H.

Member Function Documentation

◆ compute_cell()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::compute_cell ( const coord_type & c ) const

privatedelete

◆ config()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

const Parallel_Engine_Config & Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::config ( ) const

inlinenoexcept

Returns: the active configuration.

Definition at line 418 of file tpl_ca_parallel_engine.H.

References Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::cfg_.

◆ effective_partitions()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

std::size_t Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::effective_partitions ( ThreadPool * pool ) const

inlineprivatenoexcept

Resolve the effective number of partitions for the next step().

Falls back to 1 when the pool is unavailable or the lattice is too small to amortise the scheduling overhead.

Definition at line 344 of file tpl_ca_parallel_engine.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::cfg_, Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::cur_buf_, Aleph::CA::Parallel_Engine_Config::min_parallel_cells, Aleph::CA::Parallel_Engine_Config::num_partitions, Aleph::CA::should_run_sequential(), and Aleph::CA::Lattice< Storage, Boundary >::size().

Referenced by Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::step().

◆ extents()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

const extents_type & Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::extents ( ) const

inlinenoexcept

Returns: the current frame extents.

Definition at line 412 of file tpl_ca_parallel_engine.H.

References Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::cur_buf_, and Aleph::CA::Lattice< Storage, Boundary >::extents().

◆ frame()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

const Lattice & Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::frame ( ) const

inlinenoexcept

Return the current frame.

Returns: read-only view of the current lattice buffer.

Definition at line 398 of file tpl_ca_parallel_engine.H.

References Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::cur_buf_.

Referenced by expect_engine_equivalence().

◆ on_post_step()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

template<typename F >

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::on_post_step ( F && f )

inline

Register a hook fired after every step().

Definition at line 439 of file tpl_ca_parallel_engine.H.

References Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::post_hook_.

◆ on_pre_step()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

template<typename F >

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::on_pre_step ( F && f )

inline

Register a hook fired before every step().

Hooks run on the driving thread, never inside a worker.

Definition at line 432 of file tpl_ca_parallel_engine.H.

References Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::pre_hook_.

Referenced by TEST().

◆ process_slab()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::process_slab	(	const ca_size_t	r_begin,
		const ca_size_t	r_end
	)

inlineprivate

Drive the iteration over a single row slab according to Order.

Picked at compile time so workers run a tight, branch-free loop.

Definition at line 318 of file tpl_ca_parallel_engine.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::rank, Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_1d(), Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_2d_row_major(), and Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_3d_row_major().

Referenced by Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::step().

◆ run()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::run ( const std::size_t steps )

inline

Run several synchronous steps.

Parameters

[in] steps number of consecutive step() calls to perform.

Exceptions

Any	exception propagated by `step()`.

Complexity: O(steps * N * K / P).

Definition at line 521 of file tpl_ca_parallel_engine.H.

References Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::step(), and steps.

Referenced by expect_engine_equivalence(), main(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ set_config()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::set_config ( Parallel_Engine_Config cfg )

inlinenoexcept

Replace the configuration. Takes effect on the next step().

Definition at line 424 of file tpl_ca_parallel_engine.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::cfg_.

◆ step()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::step ( )

inline

Apply the rule to every cell once and swap buffers.

Refreshes the halo (when applicable), fires the pre-step hook, schedules the per-partition work onto the configured thread pool (or runs sequentially when the workload is below the threshold), swaps the buffers in O(1), and fires the post-step hook.

Exceptions

Any	exception propagated by the rule, lattice or hooks.
std::runtime_error	if a worker encountered an exception during the parallel section.

Complexity: O((N * K) / P) wall-clock, where N is the cell count, K the neighbourhood size and P the effective worker count.

Definition at line 459 of file tpl_ca_parallel_engine.H.

Referenced by Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::run().

◆ steps_run()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

std::size_t Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::steps_run ( ) const

inlinenoexcept

Return the number of completed steps.

Returns: the number of step() invocations performed so far.

Definition at line 406 of file tpl_ca_parallel_engine.H.

References Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::step_count_.

Referenced by expect_engine_equivalence().

◆ update_cell()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_cell	(	const coord_type &	c,
		std::span< state_type >	nbuf
	)

inlineprivate

Update a single cell c: gather its neighbours, evaluate the rule and write the result into nxt_buf_.

The neighbour buffer is on the caller's stack to avoid any heap activity per cell. The Cell_Context is derived from the engine's step counter and the cell coordinate, so contextual rules (e.g. Phase 8 stochastic rules) see the same (step, coord) pair regardless of which worker visits the cell.

Definition at line 236 of file tpl_ca_parallel_engine.H.

References Aleph::CA::apply_rule(), Aleph::CA::Lattice< Storage, Boundary >::at(), Aleph::blossom_maximum_cardinality_matching(), Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::cur_buf_, Aleph::CA::gather_neighbors(), Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::nh_, Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::nxt_buf_, Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::rule_, Aleph::CA::Lattice< Storage, Boundary >::set(), and Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::step_count_.

Referenced by Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_1d(), Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_2d_row_major(), Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_2d_tile(), and Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_3d_row_major().

◆ update_slab_1d()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_1d	(	const ca_size_t	r_begin,
		const ca_size_t	r_end
	)

inlineprivate

Definition at line 251 of file tpl_ca_parallel_engine.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_cell().

Referenced by Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::process_slab().

◆ update_slab_2d_row_major()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_2d_row_major	(	const ca_size_t	r_begin,
		const ca_size_t	r_end
	)

inlineprivate

Definition at line 262 of file tpl_ca_parallel_engine.H.

References Aleph::blossom_maximum_cardinality_matching(), cols, Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::cur_buf_, Aleph::CA::Lattice< Storage, Boundary >::size(), and Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_cell().

Referenced by Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::process_slab().

◆ update_slab_2d_tile()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

template<std::size_t TileW, std::size_t TileH>

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_2d_tile	(	const ca_size_t	r_begin,
		const ca_size_t	r_end
	)

inlineprivate

Definition at line 277 of file tpl_ca_parallel_engine.H.

References Aleph::blossom_maximum_cardinality_matching(), cols, Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::cur_buf_, Aleph::CA::Lattice< Storage, Boundary >::size(), and Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_cell().

◆ update_slab_3d_row_major()

template<typename Lattice , typename Rule , typename Neighborhood , typename Order = RowMajor>

void Aleph::CA::Parallel_Synchronous_Engine< Lattice, Rule, Neighborhood, Order >::update_slab_3d_row_major	(	const ca_size_t	r_begin,
		const ca_size_t	r_end
	)