The final piece of the puzzle, GLV. Patent expired 2 days ago.
Recommended to review after rest of algorithmic optimisations have been merged.
A description of the approach taken for GLV and background knowledge can be found in this hackmd article.
3/3 of a series of PRs to scipr-lab/zexe.
Features:
Batch Affine ops
Batch and ordinary w-NAF
GLV framework, GLV precomputation script.
GLV impl for both batch affine and projective mul (only for BW6)
Batch bucket addition tree
Batched MSM (1.4-1.7x bump)
Batch subgroup verification based on addition to random buckets
2D test matrix feature-gating with axes (curve, test type)
Refactor tests to use common template
Code timing instrumentation with fine grained control of functions and callers
Combined speedup (with w-NAF) for
Batched mul (with GLV): 2.3-2.7x.
Non-batch projective mul (with GLV): 2.1x.
Without GLV: 1.65-1.8x and 1.4x resp.
Speedup for subgroup verification
Over old impl 25-80x.
Over new batch mul: 10-30x.
Future PRs:
Improved MSM scaling (free scaling to 100s of threads for problem sizes > 2^25). (Need to investigate if held back by Amdahl's law in serial portion of code).
Recursive batch verification that gives ~1.5x speedup for large n.
Accel-based CUDA scalar mul + load-balancing code/framework to balance between CPU and GPU. Performance is neck to neck between weak GPU (GTX 1650 GPU) and a powerful CPU (16T Ryzen 4800H that clocks a sustained 4.2GHz). Probably better than most laptop Intels.
The final piece of the puzzle, GLV. Patent expired 2 days ago. Recommended to review after rest of algorithmic optimisations have been merged. A description of the approach taken for GLV and background knowledge can be found in this hackmd article.
3/3 of a series of PRs to scipr-lab/zexe.
Features:
Combined speedup (with w-NAF) for
Speedup for subgroup verification
Future PRs:
Future work: