Parallelize provers #33
Description
What's the deal with this issue?
- We want to know how well the Blended algorithm parallelizes compared to VSBW, CTY
- for these loops: https://github.com/compsec-epfl/space-efficient-sumcheck/blob/main/src/provers/tradeoff_prover.rs#L75, we should be able to unroll like so: https://ppc.cs.aalto.fi/ch3/nested/ see "The correct solution is to collapse it into one loop"
- an added complexity here is that each thread might be required to initialize their own seq_lag_poly. The number of calls to next() should remain the same, but you might pickup an overhead where instead of one call to new() you do num_threads * new()
- should be straightforward to parallelize compute_round it's only one loop: https://github.com/compsec-epfl/space-efficient-sumcheck/blob/main/src/provers/tradeoff_prover.rs#L108
- prefix sum as well should be trivially parallelizable: https://en.wikipedia.org/wiki/Prefix_sum