Open mratsim opened 7 months ago
Looking into the rayon ecosystem and issues:
There is a solution via: https://crates.io/crates/rayon-scan though a quick glance at it and I'm concerned at:
With a delay time of 100ns, the parallel speedup is 2.99 With a delay time of 10000ns, the parallel speedup is 5.27
So it can be used as a stop-gap (but then again we can re-add the old parallelize
as a stopgap as well) but if this is a bottleneck, we likely might still want an optimized implementation.
Discovered by Axiom in the process of porting Scroll/Geometry LogUp (Multivariate Lookups) to their own lib and kindly pointed out to us when we're preparing to upstream the work.
Scroll+Geometry PRs:
Axiom / @jonathanpwang comment:
The MV Lookup PR assumes that
parallelize
chunks the iteration domain into same sized chunks. This has been removed in https://github.com/privacy-scaling-explorations/halo2/pull/186 to fix load imbalance:Instead we need a load-balanced prefix sum algorithm / parallel scan.
This is a common parallelization problem due to being well constrained but difficult enough with several approaches to teach CS student about parallelization algorithms and also cache concerns.
There is an excellent overview here on 3 different algorithms https://github.com/matteomazza91/parallel-prefix-sum/blob/master/report.pdf
An another:
And High-Performance Computing courses:
And GPU techniques (which are quite relevant now that CPUs have 100+ cores)
Also, unsure yet of how MV-lookups are implemented but it seems like currently the code builds a big table and do a prefix sum once everything is there. An alternative, streaming, approach could be to use Fenwick Trees so the prefix sum is updated on-the-fly. Note that this only make sense if the data isn't available at once but cumulated over many parts.