TritonVM / triton-vm / 9197427793

98%

Build Type

push

github

Committed by web-flow

Commit Message

Parallelize Filling of Degree-Lowering Table (#284)

This PR modifies the auto-generated code for filling the degree-lowering
table, essentially upgrading it from sequential to parallel iteration.
To achieve this, the master base and extension tables are split into
left and right parts at the column index separating original columns
from degree-lowering columns. Then parallel iteration over the rows
allows filling in the degree-lowering rows left to right. No value in
any degree-lowering row depends on values to its right.

A complication arises when filling the degree-lowering columns for
*transition constraints* as the degree-lowering values depend on two
rows, current and next. The solution is already implied by the AIR
constraints, which ensures that all degree-lowering values live in the
current row. Therefore, by parallel iteration over *single* rows of the
degree-lowering part, and *overlapping row pairs* of the original part,
one can fill the former left to right. Note that the overlapping row
pairs do not interfere with parallel execution because these are
*immutable* references. Rust disallows multiple *mutable* references to
the same data, but in this case only the right half of the table is
mutable, and there we select one row per iteration.

Much of the kudos goes to @jan-ferdinand who came up with the blueprint
for the solution.

On my desktop machine, benchmarking `prove_halt` --

sequential: 

![image](https://github.com/TritonVM/triton-vm/assets/1583170/42bf1900-3b4f-4d52-be7d-060b8090a701)

parallel:

![image](https://github.com/TritonVM/triton-vm/assets/1583170/d6072176-fb03-4a25-99e1-369765976350)

Run Details

85 of 105 new or added lines in 1 file covered. (80.95%)

1 existing line in 1 file now uncovered.

44006 of 44320 relevant lines covered (99.29%)

3672625.44 hits per line