Tracks the cumulative usage of the execution trace across a series of circuits. More...

#include <execution_trace_usage_tracker.hpp>

Public Types
using	Range = std::pair< size_t, size_t >

using	Builder = MegaCircuitBuilder

using	MegaTraceFixedBlockSizes = MegaExecutionTraceBlocks

Public Member Functions
	ExecutionTraceUsageTracker (const TraceSettings &trace_settings=TraceSettings{})

void	update (const Builder &circuit)

void	print ()

void	print_active_ranges ()

void	print_previous_active_ranges ()

void	print_thread_ranges ()

void	construct_thread_ranges (const size_t num_threads, const size_t full_domain_size, bool use_prev_accumulator=false)
	Construct ranges of execution trace rows that evenly distribute the active content of the trace across a given number of threads.

Static Public Member Functions
static std::vector< Range >	construct_union_of_ranges (std::vector< Range > &ranges)
	Construct sorted disjoint ranges representing the union of an arbitrary set of ranges.

static std::vector< std::vector< Range > >	construct_ranges_for_equal_content_distribution (const std::vector< Range > &union_ranges, const size_t num_threads)
	Given a set of ranges indicating "active" regions of an ambient space, define a given number of new ranges on the ambient space which evenly divide the content.

Public Attributes
TraceStructure	max_sizes

MegaTraceFixedBlockSizes	fixed_sizes

std::vector< Range >	active_ranges

std::vector< Range >	previous_active_ranges

std::vector< std::vector< Range > >	thread_ranges

size_t	max_databus_size = 0

size_t	max_tables_size = 0

size_t	max_gates_size = 0

TraceSettings	trace_settings

Static Public Attributes
static constexpr std::array< std::string_view, 14 >	block_labels

Detailed Description

Tracks the cumulative usage of the execution trace across a series of circuits.

Primary uses are (1) determining the minimum required structured trace block sizes for a series of circuits in an IVC, and (2) determining the optimal distribution of rows across threads to evenly distribute work based on the fact that unused rows often do not require any computation.

Definition at line 22 of file execution_trace_usage_tracker.hpp.

Member Typedef Documentation

◆ Builder

using bb::ExecutionTraceUsageTracker::Builder = MegaCircuitBuilder

Definition at line 24 of file execution_trace_usage_tracker.hpp.

◆ MegaTraceFixedBlockSizes

using bb::ExecutionTraceUsageTracker::MegaTraceFixedBlockSizes = MegaExecutionTraceBlocks

Definition at line 25 of file execution_trace_usage_tracker.hpp.

◆ Range

using bb::ExecutionTraceUsageTracker::Range = std::pair<size_t, size_t>

Definition at line 23 of file execution_trace_usage_tracker.hpp.

Constructor & Destructor Documentation

◆ ExecutionTraceUsageTracker()

bb::ExecutionTraceUsageTracker::ExecutionTraceUsageTracker ( const TraceSettings & trace_settings = TraceSettings{} )

inline

Definition at line 62 of file execution_trace_usage_tracker.hpp.

Member Function Documentation

◆ construct_ranges_for_equal_content_distribution()

static std::vector< std::vector< Range > > bb::ExecutionTraceUsageTracker::construct_ranges_for_equal_content_distribution	(	const std::vector< Range > &	union_ranges,
		const size_t	num_threads
	)

inlinestatic

Given a set of ranges indicating "active" regions of an ambient space, define a given number of new ranges on the ambient space which evenly divide the content.

In practive this is used to determine even distribution of execution trace rows across threads according to ranges describing the active rows of an IVC accumulator. Even if two ranges contain the same number of rows, their workloads can differ depending on row complexity. To balance this, we distribute rows from each range as evenly as possible across the available threads. If the total number of rows is not perfectly divisible by the thread count, some threads will be assigned one additional row to ensure complete coverage.

Parameters

union_ranges	A set of sorted, disjoint ranges
num_threads

Returns: std::vector<std::vector<Range>>

Definition at line 233 of file execution_trace_usage_tracker.hpp.

◆ construct_thread_ranges()

void bb::ExecutionTraceUsageTracker::construct_thread_ranges	(	const size_t	num_threads,
		const size_t	full_domain_size,
		bool	use_prev_accumulator = `false`
	)

inline

Construct ranges of execution trace rows that evenly distribute the active content of the trace across a given number of threads.

Parameters

num_threads	Num ranges over which to distribute the data
full_domain_size	Size of full domain; needed only for unstructured case
use_prev_accumulator	Base ranges on previous or current accumulator

Definition at line 171 of file execution_trace_usage_tracker.hpp.

◆ construct_union_of_ranges()

static std::vector< Range > bb::ExecutionTraceUsageTracker::construct_union_of_ranges ( std::vector< Range > & ranges )

inlinestatic

Construct sorted disjoint ranges representing the union of an arbitrary set of ranges.

Used to convert the more complex set of active ranges for the gate types into a set of well formed ranges that can be more easily analyzed.

Parameters

ranges Arbitrary set of input ranges (in practice, active ranges of gate types)

Returns: std::vector<Range>

Definition at line 197 of file execution_trace_usage_tracker.hpp.

◆ print()

void bb::ExecutionTraceUsageTracker::print ( )

inline

Definition at line 116 of file execution_trace_usage_tracker.hpp.

◆ print_active_ranges()

void bb::ExecutionTraceUsageTracker::print_active_ranges ( )

inline

Definition at line 130 of file execution_trace_usage_tracker.hpp.

◆ print_previous_active_ranges()

void bb::ExecutionTraceUsageTracker::print_previous_active_ranges ( )

inline

Definition at line 140 of file execution_trace_usage_tracker.hpp.

◆ print_thread_ranges()

void bb::ExecutionTraceUsageTracker::print_thread_ranges ( )

inline

Definition at line 150 of file execution_trace_usage_tracker.hpp.

◆ update()

void bb::ExecutionTraceUsageTracker::update ( const Builder & circuit )

inline

Definition at line 77 of file execution_trace_usage_tracker.hpp.

Member Data Documentation

◆ active_ranges

std::vector<Range> bb::ExecutionTraceUsageTracker::active_ranges

Definition at line 32 of file execution_trace_usage_tracker.hpp.

◆ block_labels

constexpr std::array<std::string_view, 14> bb::ExecutionTraceUsageTracker::block_labels

staticconstexpr

Initial value:

{ "ecc_op",
                                                                    "busread",
                                                                    "lookup",
                                                                    "pub_inputs",
                                                                    "arithmetic",
                                                                    "delta_range",
                                                                    "elliptic",
                                                                    "memory",
                                                                    "nnf",
                                                                    "poseidon2_external",
                                                                    "poseidon2_internal",
                                                                    "overflow",
                                                                    "databus_table_data",
                                                                    "lookup_table_data" }