execution_trace_usage_tracker.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: not started, auditors: [], date: YYYY-MM-DD }
// external_1:  { status: not started, auditors: [], date: YYYY-MM-DD }
// external_2:  { status: not started, auditors: [], date: YYYY-MM-DD }
// =====================
 
#pragma once
 
#include "barretenberg/honk/execution_trace/mega_execution_trace.hpp"
#include "barretenberg/stdlib_circuit_builders/mega_circuit_builder.hpp"
#include <iostream>
 
namespace bb {
 
struct ExecutionTraceUsageTracker {
    using Range = std::pair<size_t, size_t>;
    using Builder = MegaCircuitBuilder;
    using MegaTraceFixedBlockSizes = MegaExecutionTraceBlocks;
 
    TraceStructure max_sizes;             // max utilization of each block
    MegaTraceFixedBlockSizes fixed_sizes; // fixed size of each block prescribed by structuring
    // Store active ranges based on the most current accumulator and those based on all but the most recently
    // accumulated circuit. The former is needed for the combiner calculation and the latter for the perturbator.
    // The ranges cover all areas in the trace where relations have nontrivial values.
    std::vector<Range> active_ranges;
    std::vector<Range> previous_active_ranges;
 
    std::vector<std::vector<Range>>
        thread_ranges; // ranges within the ambient space over which utilized space is evenly distibuted
 
    // Max sizes of the "tables" for databus and conventional lookups (distinct from the sizes of their gate blocks)
    size_t max_databus_size = 0;
    size_t max_tables_size = 0;
    size_t max_gates_size = 0;
 
    // For printing only. Must match the order of the members in the arithmetization
 
    static constexpr std::array<std::string_view, 14> block_labels{ "ecc_op",
                                                                    "busread",
                                                                    "lookup",
                                                                    "pub_inputs",
                                                                    "arithmetic",
                                                                    "delta_range",
                                                                    "elliptic",
                                                                    "memory",
                                                                    "nnf",
                                                                    "poseidon2_external",
                                                                    "poseidon2_internal",
                                                                    "overflow",
                                                                    "databus_table_data",
                                                                    "lookup_table_data" };
 
    TraceSettings trace_settings;
 
    ExecutionTraceUsageTracker(const TraceSettings& trace_settings = TraceSettings{})
        : trace_settings(trace_settings)
    {
        for (auto& size : max_sizes.get()) {
            size = 0; // init max sizes to zero
        }
 
        if (trace_settings.structure) {
            fixed_sizes.set_fixed_block_sizes(trace_settings);
        }
 
        fixed_sizes.compute_offsets(/*is_structured=*/true);
    }
 
    // Update the max block utilization and active trace ranges based on the data from a provided circuit
    void update(const Builder& circuit)
    {
        // Update the max utilization of each gate block
        for (auto [block, max_size] : zip_view(circuit.blocks.get(), max_sizes.get())) {
            max_size = std::max(static_cast<uint32_t>(block.size()), max_size);
        }
 
        max_gates_size = std::max(max_gates_size, circuit.num_gates);
 
        // update the max sixe of the databus and lookup tables
        max_databus_size = std::max({ max_databus_size,
                                      circuit.get_calldata().size(),
                                      circuit.get_secondary_calldata().size(),
                                      circuit.get_return_data().size() });
        max_tables_size = std::max(max_tables_size, circuit.get_tables_size());
 
        // Update the active ranges of the trace based on max block utilization
        previous_active_ranges = active_ranges; // store active ranges based on all but the present circuit
        active_ranges.clear();
        for (auto [max_size, fixed_block] : zip_view(max_sizes.get(), fixed_sizes.get())) {
            size_t start_idx = fixed_block.trace_offset();
            size_t end_idx = start_idx + max_size;
            active_ranges.push_back(Range{ start_idx, end_idx });
        }
 
        // The active range for lookup-style blocks consists of two components: (1) rows containing the lookup/read
        // gates and (2) rows containing the table data itself. The Mega arithmetization contains two such blocks:
        // conventional lookups (lookup block) and the databus (busread block). Here we add the ranges corresponding
        // to the "table" data for these two blocks. The corresponding gate ranges were added above.
        size_t databus_data_start = 0; // Databus column data starts at idx 0
        size_t databus_data_end = databus_data_start + max_databus_size;
        active_ranges.push_back(Range{ databus_data_start, databus_data_end }); // region where databus contains data
 
        // Note: start of table data is aligned with start of the lookup gates block
        size_t tables_start = fixed_sizes.lookup.trace_offset();
        size_t tables_end = tables_start + max_tables_size;
        active_ranges.emplace_back(Range{ tables_start, tables_end }); // region where table data is stored
    }
 
    void print()
    {
        // NOTE: This is used by downstream tools for parsing the required block sizes. Do not change this
        // without updating (or consulting Grego).
        info("Largest circuit: ", max_gates_size, " gates. Trace details:");
        info("Minimum required block sizes for structured trace: ");
        size_t idx = 0;
        for (auto max_size : max_sizes.get()) {
            std::cerr << std::left << std::setw(20) << block_labels[idx] << ": " << max_size << std::endl;
            idx++;
        }
        info("");
    }
 
    void print_active_ranges()
    {
        info("Active regions of accumulator: ");
        for (auto [label, range] : zip_view(block_labels, active_ranges)) {
            std::cerr << std::left << std::setw(20) << label << ": (" << range.first << ", " << range.second << ")"
                      << std::endl;
        }
        info("");
    }
 
    void print_previous_active_ranges()
    {
        info("Active regions of previous accumulator: ");
        for (auto [label, range] : zip_view(block_labels, previous_active_ranges)) {
            std::cerr << std::left << std::setw(20) << label << ": (" << range.first << ", " << range.second << ")"
                      << std::endl;
        }
        info("");
    }
 
    void print_thread_ranges()
    {
        info("Thread ranges: ");
        for (const auto& ranges : thread_ranges) {
            std::cerr << "[" << std::endl;
            for (auto range : ranges) {
                std::cerr << "(" << range.first << ", " << range.second << ")" << std::endl;
            }
            std::cerr << "]" << std::endl;
        }
        info("");
    }
 
    void construct_thread_ranges(const size_t num_threads,
                                 const size_t full_domain_size,
                                 bool use_prev_accumulator = false)
    {
        // Convert the active ranges for each gate type into a set of sorted non-overlapping ranges (union of the input)
        std::vector<Range> simplified_active_ranges;
        if (!trace_settings.structure) {
            // If not using a structured trace, set the active range to the whole domain
            simplified_active_ranges.push_back(Range{ 0, full_domain_size });
        } else {
            simplified_active_ranges = use_prev_accumulator ? construct_union_of_ranges(previous_active_ranges)
                                                            : construct_union_of_ranges(active_ranges);
        }
 
        // Determine ranges in the structured trace that even distibute the active content across threads
        thread_ranges = construct_ranges_for_equal_content_distribution(simplified_active_ranges, num_threads);
    }
 
    static std::vector<Range> construct_union_of_ranges(std::vector<Range>& ranges)
    {
        std::vector<Range> union_ranges;
 
        // Sort the ranges by start index (secondarily by end_idx if start indices agree)
        std::sort(ranges.begin(), ranges.end());
 
        union_ranges.push_back(ranges.front());
 
        for (const Range& range : ranges) {
            Range& prev_range = union_ranges.back();
 
            // If the two ranges overlap or are contiguous, merge them
            if (range.first <= prev_range.second) {
                prev_range.second = std::max(range.second, prev_range.second);
            } else { // otherwise add the present range to the union
                union_ranges.push_back(range);
            }
        }
 
        return union_ranges;
    }
 
    static std::vector<std::vector<Range>> construct_ranges_for_equal_content_distribution(
        const std::vector<Range>& union_ranges, const size_t num_threads)
    {
        std::vector<std::vector<Range>> thread_ranges(num_threads);
 
        for (const Range& range : union_ranges) {
            size_t start_idx = range.first;
            size_t total_content = range.second - start_idx;
            size_t content_per_thread = total_content / num_threads;
            size_t leftovers = total_content % num_threads;
            for (size_t i = 0; i < num_threads; i++) {
                size_t end_idx =
                    start_idx + content_per_thread + (i < leftovers ? 1 : 0); // Distribute leftovers evenly
                if (start_idx < end_idx) {
                    thread_ranges[i].push_back(Range{ start_idx, end_idx });
                    start_idx = end_idx;
                }
            }
        }
 
        return thread_ranges;
    }
};
} // namespace bb