gate_separator.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/common/compiler_hints.hpp"
#include "barretenberg/common/op_count.hpp"
#include "barretenberg/common/thread.hpp"
#include "barretenberg/stdlib/primitives/bool/bool.hpp"
 
#include <cstddef>
#include <vector>
namespace bb {
 
template <typename FF> struct GateSeparatorPolynomial {
    std::vector<FF> betas;
 
    std::vector<FF> beta_products;
    size_t current_element_idx = 0;
    size_t periodicity = 2;
    FF partial_evaluation_result = FF(1);
 
    GateSeparatorPolynomial(const std::vector<FF>& betas, const size_t log_num_monomials)
        : betas(betas)
        , beta_products(compute_beta_products(betas, log_num_monomials))
    {}
 
    GateSeparatorPolynomial(const std::vector<FF>& betas)
        : betas(betas)
    {}
 
    GateSeparatorPolynomial(const std::vector<FF>& betas, const std::vector<FF>& challenge)
        : betas(betas)
    {
        for (const auto& u_k : challenge) {
            partially_evaluate(u_k);
        }
    }
 
    FF const& operator[](size_t idx) const { return beta_products[idx]; }
    FF current_element() const { return betas[current_element_idx]; }
 
    FF univariate_eval(FF challenge) const { return (FF(1) + (challenge * (betas[current_element_idx] - FF(1)))); };
 
    void partially_evaluate(FF challenge)
    {
        FF current_univariate_eval = univariate_eval(challenge);
        partial_evaluation_result *= current_univariate_eval;
        current_element_idx++;
        periodicity *= 2;
    }
 
    void partially_evaluate(const FF& challenge, const FF& indicator)
    {
        FF current_univariate_eval = univariate_eval(challenge);
        // If dummy round, make no update to the partial_evaluation_result
        partial_evaluation_result = (FF(1) - indicator) * partial_evaluation_result +
                                    indicator * partial_evaluation_result * current_univariate_eval;
        current_element_idx++;
        periodicity *= 2;
    }
 
    BB_PROFILE static std::vector<FF> compute_beta_products(const std::vector<FF>& betas,
                                                            const size_t log_num_monomials)
    {
 
        size_t pow_size = 1 << log_num_monomials;
        std::vector<FF> beta_products(pow_size);
 
        // Determine number of threads for multithreading.
        // Note: Multithreading is "on" for every round but we reduce the number of threads from the max available based
        // on a specified minimum number of iterations per thread. This eventually leads to the use of a single thread.
        // For now we use a power of 2 number of threads simply to ensure the round size is evenly divided.
        size_t max_num_threads = get_num_cpus_pow2(); // number of available threads (power of 2)
        size_t min_iterations_per_thread = 1 << 6; // min number of iterations for which we'll spin up a unique thread
        size_t desired_num_threads = pow_size / min_iterations_per_thread;
        size_t num_threads = std::min(desired_num_threads, max_num_threads); // fewer than max if justified
        num_threads = num_threads > 0 ? num_threads : 1;                     // ensure num threads is >= 1
        size_t iterations_per_thread = pow_size / num_threads;               // actual iterations per thread
 
        // TODO(https://github.com/AztecProtocol/barretenberg/issues/864): This computation is asymtotically slow as it
        // does pow_size * log(pow_size) work. However, in practice, its super efficient because its trivially
        // parallelizable and only takes 45ms for the whole 6 iter IVC benchmark. Its also very readable, so we're
        // leaving it unoptimized for now.
        parallel_for(num_threads, [&](size_t thread_idx) {
            size_t start = thread_idx * iterations_per_thread;
            size_t end = (thread_idx + 1) * iterations_per_thread;
            for (size_t i = start; i < end; i++) {
                auto res = FF(1);
                for (size_t j = i, beta_idx = 0; j > 0; j >>= 1, beta_idx++) {
                    if ((j & 1) == 1) {
                        res *= betas[beta_idx];
                    }
                }
                beta_products[i] = res;
            }
        });
 
        return beta_products;
    }
};
} // namespace bb