search

0xPolygonMiden / miden-vm

STARK-based virtual machine
MIT License
632 stars 161 forks source link

Optimize trace generation #1558

Open Al-Kindi-0 opened 3 weeks ago

Al-Kindi-0 commented 3 weeks ago

Currently, trace generation, both main and auxiliary, takes roughly about 10% of the total proving time. We should benchmark and profile this step in order to get an idea of the bottlenecks. Witness generation is an inherently sequential process but there are still strategies that one could explore in order to improve things. One such approach is multi-stage building of the main trace through several passes, where for example the first pass could fill the minimal amount of trace values needed in order to be able to fill the hasher chiplet in parallel.

plafer commented 3 weeks ago

Additional context: https://github.com/0xPolygonMiden/miden-vm/pull/1533#issuecomment-2449052138

bobbinth commented 6 days ago

I think a good target here would be to get main trace generation to run at at least 50 MHz on something like an M1. And a stretch goal could be 100 MHz. I think it should be double but would require quite a bit of investigation and potential refactoring.