Fixing stream_to_linear() for round 0

If we are guaranteed that the first linear phase in the schedule is round zero, then the optimisation is relatively easy. We just need to adapt the compute_first_quadratic_evals_and_bound_polys function. This immediately matches us with the linear sum-check (as was the only thing that we needed to improve.) NOTE: We also use the existing optimisations for small values. The code can be found here

Each unit of work is described by the processing of an array of size \(2\sqrt{T}\) and there are \(\sqrt{T}\) such units being shared/stolen from inside the thread pool.

Fixing stream_to_linear() for any round

We’ve fixed the issue when the first linear round is the first round of sum-check, but we have not yet optimised the code path for any other streaming schedule. That is where the sum-check actually has a streaming phase, and recomputing Az and Bz involves accounting for a prefix of bound variables.

Towards this we investigate two solutions:

1. Optimising the existing implementation which has a rather complicated structure but includes small value optimisations. Observe that the current stream_to_linear_time() code only takes 7ms as opposed to the 17ms we started with. Code

This is owing to us changing

 // Final reductions once per j.
    for j in 0..jlen {
        let az_j = acc_az[j].barrett_reduce();
        let bz_first_j = acc_bz_first[j].barrett_reduce();
        let bz_second_j = acc_bz_second[j].barrett_reduce();
        grid_az[j] = az_j;
        grid_bz[j] = bz_first_j + bz_second_j;
    }

to the following code. The unsafe block is because the compiler does not realise we actually write to different parts of the array.

 let grid_az_ptr = grid_az.as_mut_ptr() as usize;
        let grid_bz_ptr = grid_bz.as_mut_ptr() as usize;
        let chunk_size = 4096;
        let num_chunks = (jlen + chunk_size - 1) / chunk_size;
        (0..num_chunks).into_par_iter().for_each(move |chunk_idx| {
            let start = chunk_idx * chunk_size;
            let end = (start + chunk_size).min(jlen);

            let az_ptr = grid_az_ptr as *mut F;
            let bz_ptr = grid_bz_ptr as *mut F;

            for j in start..end {
                let az_j = acc_az[j].barrett_reduce();
                let bz_first_j = acc_bz_first[j].barrett_reduce();
                let bz_second_j = acc_bz_second[j].barrett_reduce();

                unsafe {
                    *az_ptr.add(j) = az_j;
                    *bz_ptr.add(j) = bz_first_j + bz_second_j;
                }
            }
        });

2. We write a simple parallel version without small value optimisation, but one where we know the cache lines are well aligned. Notice that stream_to_linear_time is not as fast as our linear_schedule version, but it is still nearly twice as fast as the existing parallelised version. The reason it’s likely much faster is due to simplicity – we iterate over arrays just once. The reason it’s slower than the original version, is because in this version we need to multiply all the \(\text{eq}(r,x_r)\) polynomials, and additionally the window size is 3. So the chunking is not as nice and uniform. Still we loose about 2ms, which in the grand scheme of things is negligible. Code

Next Steps

fn compute_message(&mut self, round: usize, previous_claim: F) -> UniPoly<F> {
        // If this is a window start, materialize the window grid
        if self.schedule.is_window_start(round) {
            self.compute_window_evals_for_new_window(round);
        }
        // Use the window grid to compute this round's prover message
       self.get_prover_message_from_window_evals(previous_claim)
    }