Finding the barrier toward better parallelism

[weikengchen]

More updates will be added to this note.

I measured the cost for Groth16 to prove a constraint system with two million constraints, with a different number of cores, using cargo bench in this repo with appropriate command line parameters.

Below I focus on the main cost in my constraint system, which turns out to be in the witness map and computation of C.

Going from 1 core to 4 cores, the improvement is significant. But later when more cores are added, the time for the witness map seems to not change a lot.

Since the witness map involves a lot of FFT, it may suggest that the current implementation of FFT has a barrier toward many-many-core parallelism.

Such a barrier, maybe avoidable, maybe unavoidable. I will take a look at the detailed breakdown of the cost of the witness map.

===== Groth16 =====

1 core
R1CS to QAP witness map ... 32.102s
Compute C ................. 56.453s
Total ..................... 93.780s

4 cores
R1CS to QAP witness map ... 12.476s
Compute C ................. 16.54s
Total ..................... 34.203s

20 cores
R1CS to QAP witness map ... 8.856s
Compute C ................. 8.631s
Total ..................... 23.99s

40 cores
R1CS to QAP witness map ... 8.300s
Compute C ................. 4.414s
Total ..................... 18.319s

48 cores
R1CS to QAP witness map ... 8.166s
Compute C ................. 4.682s
Total ..................... 18.230s

[weikengchen]

new numbers after the FFT change. Seems to be still similar @ValarDragon

Note: the result is one iteration, so there could be statistical fluctuation.

===== Groth16 =====

1 core
R1CS to QAP witness map ... 31.945s
Compute C ................. 55.35s
Total ..................... 92.371s

4 cores
R1CS to QAP witness map ... 12.143s
Compute C ................. 16.867s
Total ..................... 34.371s

20 cores
R1CS to QAP witness map ... 7.408s
Compute C ................. 4.489s
Total ..................... 17.283s

40 cores
R1CS to QAP witness map ... 7.754s
Compute C ................. 4.484s
Total ..................... 17.738s

48 cores
R1CS to QAP witness map ... ~8.40s~ (rerun: 7.807s)
Compute C ................. ~4.715s~ (rerun: 4.421s)
Total ..................... ~18.349s~ (rerun: 17.680s)

[ValarDragon]

Oh that PR didn't actually change the FFT algorithm, just documented the existing one and identified the problem

I'll let you know once I update the algorithm

[Pratyush]

what was the exact command that you ran, @weikengchen ?

[NikZak]

was this ever completed? Can we move this forward?

[dkales]

During some of our work implementing a MPC variant of the Groth16 prover we noticed that a rather simple change in the rayon utilization of the main prover and witness map functions brings a considerable speedup already compared to the current one.

The main idea is to not only use intra-MSM/FFT parallelism, since this has some scaling issues as noted above, but also do parallelism across MSMs/FFTs as well using rayon::join. We have a small PoC of this in https://github.com/TaceoLabs/groth16/, and the benches there show a simple 2x performance improvement on the same machine compared to ark-groth16 v0.5.

I think a similar cfg-macro based on parallel wrapping rayon::join or sequential computation can be used to keep the configurable parallelism aspect and still get the performance benefits. If this is something that is wanted we can prepare a PR to include this here as well (and maybe in the witness map of the circom-compat crate as well?)

[Pratyush]

That PR would be great and much appreciated, thank you @dkales !

[dkales]

Hmm, apparently recent changes in main actually improved the internal parallelization enough that the additions of join here no longer help as much. Still investigating if it still might improve some parts though.