TritonVM / triton-vm / 9205343317 / 1
98%
master: 98%

DEFAULT BRANCH: master
Ran
Files 43
Run time 1s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
coverage: 99.287% (-0.03%) from 99.316%
9205343317.1

push

github

web-flow 
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)

44004 of 44320 relevant lines covered (99.29%)

3775698.57 hits per line

Source Files on job 9205343317.1