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/bb_bench.hpp"
#include "barretenberg/common/compiler_hints.hpp"
#include "barretenberg/common/thread.hpp"
#include "barretenberg/numeric/bitop/get_msb.hpp"
#include "barretenberg/stdlib/primitives/bool/bool.hpp"
 
#include <cstddef>
#include <vector>
namespace bb {
 
template <typename FF> struct GateSeparatorPolynomial {
    std::vector<FF> betas;
 
    Polynomial<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)
    {
        if (!betas.empty()) {
            for (const auto& u_k : challenge) {
                partially_evaluate(u_k);
            }
        }
    }
 
    FF const& operator[](size_t idx) const
    {
        // At round i, we only iterate over beta_products of indices that are multiples of 2^i,
        // Hence for the idx-th element we need to get the (idx * 2^i)-th element in #beta_products.
        return beta_products.at((idx >> 1) * periodicity);
    }
    FF current_element() const
    {
        if (betas.empty()) {
            return FF(1);
        };
        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)
    {
        if (!betas.empty()) {
            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)
    {
        if (!betas.empty()) {
            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 Polynomial<FF> compute_beta_products(const std::vector<FF>& betas,
                                                           const size_t log_num_monomials,
                                                           const FF& scaling_factor = FF(1))
    {
        if (betas.empty()) {
            Polynomial<FF> out(1);
            return out;
        }
 
        BB_BENCH_NAME("GateSeparatorPolynomial::compute_beta_products");
        size_t pow_size = 1 << log_num_monomials;
        Polynomial<FF> beta_products(pow_size, Polynomial<FF>::DontZeroMemory::FLAG);
 
        // 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
        const size_t num_betas_per_thread = numeric::get_msb(iterations_per_thread);
 
        // Explanations of the algorithm:
        // The product of the betas at index i (beta_products[i]) contains the multiplicative factor betas[j] if and
        // only if the jth bit of i is 1 (j starting with 0 for the least significant bit). For instance, i = 13 = 1101
        // in binary, so the product is betas[0] * betas[2] * betas[3]. Observe that if we toggle the kth bit of i (0 to
        // 1), i.e., we add 2^k to i, then the product is multiplied by betas[k]: beta_products[i + 2^k] =
        // beta_products[i] * betas[k]. If we know the products for the interval of indices [0, 2^k), we can compute all
        // the products for the interval of indices [2^k, 2^(k+1)) by multiplying each element by betas[k]. Iteratively,
        // starting with beta_products[0] = 1, we can double the number of computed products at each iteration by
        // multiplying the previous products by betas[k]. We first multiply beta_products[0] = 1 by betas[0], then we
        // multiply beta_products[0] and beta_products[1] by betas[1], etc...
        //
        // We distribute the computation of the beta_products evenly across threads, i.e., thread number
        // thread_idx will handle the interval of indices [thread_idx * iterations_per_thread, (thread_idx + 1) *
        // iterations_per_thread). Note that for a given thread, all the processed indices have the same
        // prefix in binary. Therefore, each beta_product of the thread is a multiple of this "prefix product". The
        // successive products are then populated by the above algorithm whereby we double the interval at each
        // iteration and multiply by the new beta to process the suffix bits. The difference is that we initialize the
        // first product with this "prefix product" instead of 1.
 
        // Compute the prefix products for each thread
        std::vector<FF> thread_prefix_beta_products(num_threads);
        thread_prefix_beta_products.at(0) = scaling_factor;
 
        // Same algorithm applies for the prefix products. The difference is that we start at a beta which is not the
        // first one (index 0), but the one at index num_betas_per_thread. We process the high bits only.
        // Example: If num_betas_per_thread = 3, we compute after the first iteration:
        //          (1, beta_3)
        // 2nd iteration: (1, beta_3, beta_4, beta_3 * beta_4)
        // 3nd iteration: (1, beta_3, beta_4, beta_3 * beta_4, beta_5, beta_3 * beta_5, beta_4 * beta_5, beta_3 * beta_4
        // * beta_5)
        // etc ....
        for (size_t beta_idx = num_betas_per_thread, window_size = 1; beta_idx < log_num_monomials;
             beta_idx++, window_size <<= 1) {
            const auto& beta = betas.at(beta_idx);
            for (size_t j = 0; j < window_size; j++) {
                thread_prefix_beta_products.at(window_size + j) = beta * thread_prefix_beta_products.at(j);
            }
        }
 
        parallel_for(num_threads, [&](size_t thread_idx) {
            size_t start = thread_idx * iterations_per_thread;
            beta_products.at(start) = thread_prefix_beta_products.at(thread_idx);
 
            // Compute the suffix products for each thread
            // Example: Assume we start with the prefix product = beta_3 * beta_5
            // After the first iteration, we get: (beta_3 * beta_5, beta_0 * beta_3 * beta_5)
            // 2nd iteration: (beta_3 * beta_5, beta_0 * beta_3 * beta_5, beta_1 * beta_3 * beta_5, beta_0 * beta_1 *
            // beta_3 * beta_5)
            // etc ...
            for (size_t beta_idx = 0, window_size = 1; beta_idx < num_betas_per_thread; beta_idx++, window_size <<= 1) {
                const auto& beta = betas.at(beta_idx);
                for (size_t j = 0; j < window_size; j++) {
                    beta_products.at(start + window_size + j) = beta * beta_products.at(start + j);
                }
            }
        });
 
        return beta_products;
    }
};
} // namespace bb