You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Currently, the parallelization of the constraint system solver is a bit naive. It relies on the "level builder". Essentially, we look at all the wires that appears in each instructions (constraints and hints), to build a dependency tree.
Then at solving time, we say "at level 0, we can solve constraint 0,2,5,7 independently". "at level 1, we can solve constraint 1,8,9,10... independently" etc. So the solver fires n go routines that synchronize at each level.
Main issues and avenue for improvements;
there is no weight. a constraint which needs 4 multiplication to solve as the same weight (1) as a hint that may need 40x time CPU time using big.Int arithmetic. So work is not necessary equally distributed.
the strategy is the same, independently of the number of CPU the target system has.
This is an optimization problem (job / task scheduling) and we want to optimize for wall clock. Some approaches reduce need for synchronization by solving several times the same constraint in different threads, etc..
Should be possible to build a tool, possibly completly independent from gnark that takes as input a constraint system and a number of CPUs, and output a data structure that gnark solver uses at run time to solve the constraint system. Using an external solver like Google's OR Tool could help, though ideally, for build convenience like the rest of gnark framework, pure Go with no CGO would be better.
The text was updated successfully, but these errors were encountered:
(post #641 ).
Currently, the parallelization of the constraint system solver is a bit naive. It relies on the "level builder". Essentially, we look at all the wires that appears in each instructions (constraints and hints), to build a dependency tree.
Then at solving time, we say "at level 0, we can solve constraint 0,2,5,7 independently". "at level 1, we can solve constraint 1,8,9,10... independently" etc. So the solver fires n go routines that synchronize at each level.
Main issues and avenue for improvements;
This is an optimization problem (job / task scheduling) and we want to optimize for wall clock. Some approaches reduce need for synchronization by solving several times the same constraint in different threads, etc..
Should be possible to build a tool, possibly completly independent from gnark that takes as input a constraint system and a number of CPUs, and output a data structure that gnark solver uses at run time to solve the constraint system. Using an external solver like Google's OR Tool could help, though ideally, for build convenience like the rest of gnark framework, pure Go with no CGO would be better.
The text was updated successfully, but these errors were encountered: