5 Commits

Author SHA1 Message Date
Mamy Ratsimbazafy
0f9b9e9606
Parallel Ethereum protocols (BLS signature and KZG) (#279)
* BLS sig: parallel batch verification

* BLS: speedup parallel batch verify with Miller loops on local threads

* shutdown bench

* nit: import style

* implement parallel KZG

* Parallel KZG commitments

* add benchmarks of KZG

* rename protocol file

* small optim: reorder await

* fix rebase

* Faster parallel BLS verification

* fix commitment status replacing previous error in verify_blob_kzg_proof_batch_parallel

* 2x faster parallel EC sum for less than 8192 points
2023-10-06 09:58:20 +02:00
Mamy Ratsimbazafy
d996ccd5d8
Path reorgs (#240)
* move tests

* move threadpool to root path

* fix hints and warnings, print nim versions for tests for debugging the new strange issue in CI

* print nim version

* mixup on branches

* mixup on branches reloaded
2023-05-29 20:14:30 +02:00
Mamy Ratsimbazafy
6c48975aee
Parallel Multi-Scalar-Multiplication (#226)
* try parallel reduction in batch add, but alas it's slower than custom chunking. Except maybe on arch with performance/efficiency cores

* initial impl of parallel MSM - scaling to debug, threads not woken fast enough

* improve comment [skip ci]

* skip top window when c divides the number of bits

* for some reason parallel-for loops scale on 5+ threads while spawn only on 2x threads. Thread wakeup issue?

* Add counters and timers to audit threadpool bottlenecks

* metrics and profiling fixes, (slower) latency hiding, activate tests

* fix thief thread trying to wake another before canceling its own sleep

* easier to sort metrics and parallel endomorphism application

* selective endomorphism acceleration

* some tuning

* spawn can handle compile-time literals, static and type parameters. Also introduce spawnAwaitable to await void procs

* improve MSM overview [skip ci]

* bench cleanup
2023-04-10 23:30:14 +02:00
Mamy Ratsimbazafy
e5612f5705
Multi-Scalar-Multiplication / Linear combination (#220)
* unoptimized msm

* MSM: reorder loops

* add a signed windowed recoding technique

* improve wNAF table access

* use batchAffine

* revamp EC tests

* MSM signed digit support

* refactor MSM: recode signed ahead of time

* missing test vector

* refactor allocs and Alloca sideeffect

* add an endomorphism threshold

* Add Jacobian extended coordinates

* refactor recodings, prepare for parallelizable on-the-fly signed recoding

* recoding changes, introduce proper NAF for pairings

* more pairings refactoring, introduce miller accumulator for EVM

* some optim to the addchain miller loop

* start optimizing multi-pairing

* finish multi-miller loop refactoring

* minor tuning

* MSM: signed encoding suitable for parallelism (no precompute)

* cleanup signed window encoding

* add prefetching

* add metering

* properly init result to infinity

* comment on prefetching

* introduce vartime inversion for batch additions

* fix JacExt infinity conversion

* add batchAffine for MSM, though slower than JacExtended at the moment

* add a batch affine scheduler for MSM

* Add Multi-Scalar-Multiplication endomorphism acceleration

* some tuning

* signed integer fixes + 32-bit + tuning

* Some more tuning

* common msm bench + don't use affine for c < 9

* nit
2023-02-16 12:45:05 +01:00
Mamy Ratsimbazafy
495ef4497b
Parallel batchadd (#215)
* [Threadpool] Fix syncAll releasing while a thread was attempting to steal + force no exception in tasks

* fix unguarded access on MacOS barriers

* parallel batchadd

* moved import
2023-01-29 01:06:37 +01:00