recursion gpu oom

[kunxian-xia]

For block 23817600, the instructions executed in each leaf verifier are listed below.

counter	instructions_executed (before #1205)	instructions_executed (after #1205)	overhead
0	5,192,392	5,914,202	13.8%
1	4,591,137	5,261,022	14.5%
2	4,739,462	5,410,186	14%
3	4,720,177	5,390,841	14%
4	4,500,028	5,159,592	14.6%
5	4,000,743	4,629,469	15.7%
6	9,481,332	10,329,164	9%
7	8,708,566
8	8,250,002
9	8,887,487
10	9,035,483
11	4,997,661
12	4,606,814
13	4,569,378
14	4,349,447
15	3,957,818
16	3,957,580
17	3,958,251
18	3,958,148
19	3,957,729
20	2,465,799
21	1,644,104
22	1,635,174

[kunxian-xia]

come up with a new segmentation strategy s.t. the Risc-V proof is not too large.

[kunxian-xia]

Another way is to reduce the number of cells in each chip of Native Extension.

[kunxian-xia]

For block 23817600, the total trace cells in each leaf STARK prover are

counter	total_trace_cells (before #1205)	total_trace_cells (after #1205)
0	938_151_402	1_360_072_170
1	906_694_122	1_239_158_250
2	906_694_122	1_257_311_722
3	906_694_122	1_257_311_722
4	767_757_802	1_239_158_250
5	680_725_994	1_115_688_426
6	1_684_803_050	2_349_731_306
7	1_376_783_850
8	1_376_783_850
9	1_654_787_562
10	1_654_787_562
11	938_151_402
12	906_694_122
13	770_379_242
14	680_725_994
15	608_127_458
16	608_127_458
17	608_127_458
18	608_127_458
19	608_127_458
20	335_366_626
21	217_426_402
22	217_426_402

[kunxian-xia]

0th shard leaf prover's circuit layout before #1205.

AIR Resource Utilization Summary

Air Name	Rows	Cells	Prep	Main	Perm
ProgramAir	8,388,608	150,994,944	0	[9, 1]	[8]
VmAirWrapper<AluNativeAdapterAir, FieldArithmeticCoreAir>	4,194,304	272,629,760	0	[29]	[36]
AccessAdapterAir<2>	4,194,304	113,246,208	0	[11]	[16]
VolatileBoundaryAir	2,097,152	67,108,864	0	[12]	[20]
AccessAdapterAir<4>	2,097,152	60,817,408	0	[13]	[16]
VmAirWrapper<NativeLoadStoreAdapterAir<1>, NativeLoadStoreCoreAir<1>	1,048,576	63,963,136	0	[21]	[40]
VmAirWrapper<BranchNativeAdapterAir, BranchEqualCoreAir<1>	1,048,576	53,477,376	0	[23]	[28]
VmAirWrapper<NativeVectorizedAdapterAir<4>, FieldExtensionCoreAir>	524,288	38,797,312	0	[38]	[36]
VmAirWrapper<NativeLoadStoreAdapterAir<4>, NativeLoadStoreCoreAir<4>	262,144	17,563,648	0	[27]	[40]
AccessAdapterAir<8>	262,144	8,650,752	0	[17]	[16]
VariableRangeCheckerAir	262,144	2,359,296	2	[1]	[8]
AccessAdapterAir<16>	131,072	5,373,952	0	[25]	[16]
JalRangeCheckAir	131,072	5,242,880	0	[12]	[28]
NativePoseidon2Air<BabyBearParameters>, 1>	65,536	61,734,912	0	[446]	[496]
NativeSumcheckAir	65,536	15,007,744	0	[105]	[124]
PhantomAir	65,536	1,179,648	0	[6]	[12]
VmAirWrapper<NativeAdapterAir<2, 0>, PublicValuesCoreAir>	64	3,520	0	[27]	[28]
VmConnectorAir	2	42	1	[5]	[16]
Total	24,182,850	938,150,408	-	-	-

[kunxian-xia]

diff of circuit layout in 6th shard

before
NativePoseidon2Air<BabyBearParameters>, 1> | Rows = 65_536     | Cells = 61_734_912  | Prep Cols = 0     | Main Cols = [446] | Perm Cols = [496]

after
NativePoseidon2Air<BabyBearParameters>, 1> | Rows = 524_288    | Cells = 493_879_296 | Prep Cols = 0     | Main Cols = [446] | Perm Cols = [496]
FriReducedOpeningAir | Rows = 2_097_152  | Cells = 232_783_872 | Prep Cols = 0     | Main Cols = [27]  | Perm Cols = [84] 

[kunxian-xia]

After #1238, the leaf prover's #cells is reduced a lot.

before #1205 
NativePoseidon2Air<BabyBearParameters>, 1> | Rows = 65_536     | Cells = 61_734_912  | Prep Cols = 0     | Main Cols = [446] | Perm Cols = [496]

after #1205 
NativePoseidon2Air<BabyBearParameters>, 1> | Rows = 524_288    | Cells = 493_879_296 | Prep Cols = 0     | Main Cols = [446] | Perm Cols = [496]
FriReducedOpeningAir | Rows = 2_097_152  | Cells = 232_783_872 | Prep Cols = 0     | Main Cols = [27]  | Perm Cols = [84] 

after #1238 
NativePoseidon2Air<BabyBearParameters>, 1> | Rows = 262_144    | Cells = 246_939_648 | Prep Cols = 0     | Main Cols = [446] | Perm Cols = [496]
FriReducedOpeningAir | Rows = 1_048_576  | Cells = 116_391_936 | Prep Cols = 0     | Main Cols = [27]  | Perm Cols = [84] 

[kunxian-xia]

After #1238, the #cells consumed by the chips in the recursion vm for a typical shard (includes Keccak, Secp256K1_Add/Double/Scalar_invert/Decompress precompiles)

[kunxian-xia]

Air Cells Distribution Statistics

Air Type	Rows	Cells	Percentage
VmAirWrapper<AluNativeAdapterAir, FieldArithmeticCoreAir>	8,388,608	545,259,520	27.45%
NativePoseidon2Air<BabyBearParameters>, 1>	262,144	246,939,648 (493M in #1205)	12.43%
AccessAdapterAir<2>	8,388,608	226,492,416	11.40%
ProgramAir	8,388,608	150,994,944	7.60%
VolatileBoundaryAir	4,194,304	134,217,728	6.76%
VmAirWrapper<NativeLoadStoreAdapterAir<1>, NativeLoadStoreCoreAir<1>	2,097,152	127,926,272	6.44%
AccessAdapterAir<4>	4,194,304	121,634,816	6.12%
FriReducedOpeningAir	1,048,576	116,391,936 (232M in #1205)	5.86%
VmAirWrapper<BranchNativeAdapterAir, BranchEqualCoreAir<1>	2,097,152	106,954,752	5.38%
VmAirWrapper<NativeVectorizedAdapterAir<4>, FieldExtensionCoreAir>	1,048,576	77,594,624	3.91%
NativeSumcheckAir	262,144	60,030,976	3.02%
VmAirWrapper<NativeLoadStoreAdapterAir<4>, NativeLoadStoreCoreAir<4>	524,288	35,127,296	1.77%
AccessAdapterAir<8>	524,288	17,301,504	0.87%
AccessAdapterAir<16>	262,144	10,747,904	0.54%
JalRangeCheckAir	131,072	5,242,880	0.26%
VariableRangeCheckerAir	262,144	2,359,296	0.12%
PhantomAir	65,536	1,179,648	0.06%
VmAirWrapper<NativeAdapterAir<2, 0>, PublicValuesCoreAir>	64	3,520	0.00%
VmConnectorAir	2	42	0.00%
Total	-	1,986,399,722	100.00%

[kunxian-xia]

2B cells -> 2 * 4*(1+2^1) = 24G

[kunxian-xia]

Opcode distributions for handling Ecall_Keccak

DSL Instruction	Opcode	Count
ImmE	ADD	150,324
LoadV	LOADW	63,540
AddEI	ADD	63,012
LoadV	ADD	51,540
MulE	BBE4MUL	46,390
LoadE	LOADW	44,141
IfEq	NativeBranchEqualOpcode(BNE)	43,478
AddE	FE4ADD	33,094
AddVI	ADD	26,198
AddV	ADD	21,148
LoadE	ADD	10,651
LoadE	MUL	10,651
LoadV	MUL	9,506
AssertEqE	NativeBranchEqualOpcode(BNE)	5,336
ImmV	ADD	3,771
DivEIN	ADD	2,952
Alloc	ADD	2,862
Alloc	RANGE_CHECK	2,862
MulVI	MUL	1,922
Alloc	MUL	1,431
AssertEqVI	NativeBranchEqualOpcode(BNE)	1,235
ImmF	ADD	1,049
AddFI	ADD	990
LoadF	LOADW	951
IfNe	NativeBranchEqualOpcode(BEQ)	912
ExtFromBaseVec	ADD	912
DivEIN	BBE4DIV	738
IfNeI	NativeBranchEqualOpcode(BEQ)	228
IfEqI	NativeBranchEqualOpcode(BNE)	208
IfNe	JAL	193
MulV	MUL	189
IfEqI	JAL	189
Poseidon2MultiObserve	MULTI_OBSERVE	189
AddEFFI	ADD	156
MulEI	ADD	156
MulF	MUL	120
CastFV	ADD	106
LoadF	ADD	39
MulEI	BBE4MUL	39
CT-IOPVerifierState::verify_round_and_update_state	PHANTOM	38
IfNeI	JAL	35
CT-check expected evaluation	PHANTOM	34
CT-derive next layer's expected sum	PHANTOM	34
CT-derive rt_prime	PHANTOM	34
CT-sumcheck verify	PHANTOM	34
AssertEqV	NativeBranchEqualOpcode(BNE)	23
AddF	ADD	17
CT-Compute eq_eval_less_or_equal_than	PHANTOM	6
CT-Verify GKR Circuit	PHANTOM	2
CT-Verify rotation	PHANTOM	2
CT-initial sum	PHANTOM	2
CT-verify tower proof for opcode Ecall_Keccak	PHANTOM	2
CT-Verify chip proof Ecall_Keccak	PHANTOM	1