forked from chenzomi12/AISystem
-
Notifications
You must be signed in to change notification settings - Fork 0
/
04.srt
1221 lines (917 loc) · 20.4 KB
/
04.srt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1
00:00:00,015 --> 00:00:05,056
【字幕生成: 奔崩 字幕校对: 奔崩】
(进——片——头)
2
00:00:05,056 --> 00:00:07,400
Hello,大家好,我是ZOMI
3
00:00:07,400 --> 00:00:10,000
今天我要给大家带来的就是
4
00:00:10,000 --> 00:00:13,080
AI编译器后端优化的循环优化
5
00:00:13,640 --> 00:00:14,920
具体是指
6
00:00:14,920 --> 00:00:17,680
算子调度里面的循环优化
7
00:00:17,680 --> 00:00:19,874
也就是针对我们的循环进行
8
00:00:19,874 --> 00:00:23,480
展开、分块、重排、融合还有拆分
9
00:00:23,480 --> 00:00:26,560
这几个内容进行详细的展开
10
00:00:26,760 --> 00:00:29,040
这几个内容主要是围绕一个话题
11
00:00:29,040 --> 00:00:32,000
就是loop我们的循环
12
00:00:33,400 --> 00:00:34,920
而不管是循环优化
13
00:00:34,920 --> 00:00:36,880
指令优化、存储优化也好
14
00:00:36,880 --> 00:00:39,360
它都是作为我们ops optimizer
15
00:00:39,360 --> 00:00:40,360
就是我们的
16
00:00:40,960 --> 00:00:42,360
后端优化里面的
17
00:00:42,360 --> 00:00:44,520
算子优化这一个部分
18
00:00:45,880 --> 00:00:48,080
现在我们详细的去展开
19
00:00:48,080 --> 00:00:49,440
loop optimization
20
00:00:49,440 --> 00:00:51,720
里面的一些细节的内容
21
00:00:53,080 --> 00:00:56,120
首先第一个就是循环展开
22
00:00:56,200 --> 00:00:58,040
循环展开很明确
23
00:00:58,040 --> 00:01:00,800
就是我们需要对循环进行展开
24
00:01:00,800 --> 00:01:02,320
以便我们每一次迭代
25
00:01:02,480 --> 00:01:05,440
都可以加载或者处理更多的数据
26
00:01:05,640 --> 00:01:07,120
这个时候为的就是
27
00:01:07,120 --> 00:01:09,680
使得我们每一个时钟周期的流水线上
28
00:01:09,680 --> 00:01:11,760
尽可能的在芯片上面
29
00:01:11,760 --> 00:01:13,560
满负荷的去计算
30
00:01:14,000 --> 00:01:17,000
实际上在芯片的时钟周期的流水线当中
31
00:01:17,000 --> 00:01:18,880
我们可能很大程度
32
00:01:19,000 --> 00:01:21,600
会因为指令的顺序的排布不合理
33
00:01:21,600 --> 00:01:23,560
导致我们的NPU或者CPU
34
00:01:23,560 --> 00:01:25,240
GPU的处理器空转
35
00:01:25,240 --> 00:01:27,280
影响我们整个流水线的效率
36
00:01:27,480 --> 00:01:29,600
这个时候我们的AI编译器
37
00:01:29,600 --> 00:01:31,320
就可以为我们的指令调度
38
00:01:31,320 --> 00:01:33,800
带来更大的收益空间
39
00:01:34,240 --> 00:01:37,200
我们现在来看看什么叫循环展开
40
00:01:37,200 --> 00:01:38,720
下面我们有一个例子
41
00:01:38,720 --> 00:01:39,920
有两个迭代
42
00:01:40,160 --> 00:01:41,920
第一个迭代是for j
43
00:01:41,920 --> 00:01:43,800
第二个迭代是for i
44
00:01:44,000 --> 00:01:46,240
这个时候我的计算比较简单
45
00:01:46,240 --> 00:01:48,720
A(j) = A(j) + B(i)
46
00:01:48,960 --> 00:01:51,600
这个时候其实我对循环进行展开
47
00:01:51,600 --> 00:01:55,280
现在我对j这一个循环进行展开
48
00:01:55,280 --> 00:01:56,880
j 在迭代的时候
49
00:01:56,880 --> 00:01:59,120
在循环的时候跳两个位
50
00:01:59,120 --> 00:02:01,320
然后我在计算的时候
51
00:02:01,320 --> 00:02:02,680
多一次计算
52
00:02:02,680 --> 00:02:03,720
先算A(j)
53
00:02:03,720 --> 00:02:05,600
然后再算A(j + 1)
54
00:02:05,600 --> 00:02:09,360
下一次就算A(j + 2)和A(j + 3)
55
00:02:09,360 --> 00:02:11,680
这种方式就叫做循环展开
56
00:02:14,280 --> 00:02:16,320
关于循环的第二个内容
57
00:02:16,320 --> 00:02:20,320
就是循环的分块 loop tiling
58
00:02:20,920 --> 00:02:23,000
其实我们在内存空间
59
00:02:23,120 --> 00:02:25,320
或者在我们的处理器里面
60
00:02:25,320 --> 00:02:27,400
我们的显存内存
61
00:02:27,400 --> 00:02:29,320
或者我们的cache都是有限的
62
00:02:29,320 --> 00:02:31,000
我们代码的访问量
63
00:02:31,000 --> 00:02:33,160
或者代码访问数据量过大的时候
64
00:02:33,480 --> 00:02:35,320
没有办法一次过 把我们想要
65
00:02:35,320 --> 00:02:36,480
或者想要处理的数据
66
00:02:36,840 --> 00:02:39,360
直接加载到我们的设备里面
67
00:02:39,600 --> 00:02:42,800
这个时候如果我们对循环进行分块
68
00:02:42,800 --> 00:02:45,080
可以有效的去提高我们NPU
69
00:02:45,320 --> 00:02:46,800
或者CPU里面cache
70
00:02:46,800 --> 00:02:48,680
上面的一个访存的效率
71
00:02:48,680 --> 00:02:51,280
从而改善我们整个数据的局部性
72
00:02:51,760 --> 00:02:52,680
说白了
73
00:02:52,680 --> 00:02:56,440
我们的显存 存储 cache的空间是有限的
74
00:02:56,440 --> 00:02:58,680
所以我们需要对循环的
75
00:02:59,240 --> 00:03:02,080
循环里面的数据进行分块
76
00:03:02,800 --> 00:03:05,080
希望能够一次过处理的时候
77
00:03:05,240 --> 00:03:07,680
是刚好满足我们的cache的大小
78
00:03:07,680 --> 00:03:10,040
让我们整个的吞吐量变大
79
00:03:10,600 --> 00:03:12,360
不过值得注意的有两个点
80
00:03:12,560 --> 00:03:13,760
第一个点就是分块
81
00:03:13,760 --> 00:03:15,840
如果我们应用在循环的外部
82
00:03:15,840 --> 00:03:16,800
就是我们loop的外部
83
00:03:17,080 --> 00:03:20,160
我们会增加计算的空间和时间的局部性
84
00:03:20,480 --> 00:03:22,560
这个一点是需要去注意的
85
00:03:22,680 --> 00:03:24,640
当然了我们很多AI编译器
86
00:03:25,000 --> 00:03:26,920
其实我们了解这个循环分块
87
00:03:27,040 --> 00:03:28,520
或者其他循环的方式
88
00:03:28,520 --> 00:03:30,600
只是方便我们更好地去
89
00:03:30,920 --> 00:03:33,600
写AI编译器自动调度的策略
90
00:03:34,320 --> 00:03:36,560
另外一个值得注意的点就是分块
91
00:03:36,560 --> 00:03:39,000
应该与缓存块一起去使用的
92
00:03:39,920 --> 00:03:42,320
这样可以提高我们的流水线的效率
93
00:03:42,320 --> 00:03:43,360
那简单的来说
94
00:03:43,360 --> 00:03:45,800
就是我们分块 分块的大小
95
00:03:45,800 --> 00:03:47,640
应该跟我们的缓存块
96
00:03:47,640 --> 00:03:50,040
这个时候就提高了整个系统
97
00:03:50,040 --> 00:03:52,200
或者我们的处理器的整体的效率
98
00:03:53,560 --> 00:03:56,560
而实现的思路其实比较简单
99
00:03:56,840 --> 00:03:59,320
但是我们后面会提出两个问题
100
00:03:59,320 --> 00:04:02,080
这两个问题也是值得大家一起去思考的
101
00:04:02,400 --> 00:04:04,000
一般来说我们的实现思路
102
00:04:04,000 --> 00:04:07,080
在CPU里面可能它会相对简单一点
103
00:04:07,800 --> 00:04:09,000
假设我们一个数据
104
00:04:09,160 --> 00:04:10,960
没有办法都放在cache里面的时候
105
00:04:11,120 --> 00:04:12,800
我们就会把大的数据
106
00:04:12,800 --> 00:04:14,120
分成一个个tile
107
00:04:14,120 --> 00:04:16,560
就一个个块去进行访问的
108
00:04:16,560 --> 00:04:18,440
令每一个块都可以满足
109
00:04:18,440 --> 00:04:21,200
我们处理器上面cache的一个大小
110
00:04:21,240 --> 00:04:23,560
具体的做法就是把一层
111
00:04:23,560 --> 00:04:24,920
就是内层的循环
112
00:04:24,920 --> 00:04:27,000
分成outer loop和inner loop
113
00:04:27,000 --> 00:04:28,880
就分成两个不同的loop
114
00:04:28,880 --> 00:04:31,440
把outer loop移到更外层里面
115
00:04:31,440 --> 00:04:33,320
从而确保我们的inner loop
116
00:04:33,320 --> 00:04:35,120
能够满足我们的cache
117
00:04:35,120 --> 00:04:37,000
虽然说起来有点拗口
118
00:04:37,000 --> 00:04:39,680
我们现在看一个具体的例子
119
00:04:41,120 --> 00:04:43,240
现在我们以一个简单的例子
120
00:04:43,240 --> 00:04:44,800
那里面有两个迭代
121
00:04:44,800 --> 00:04:47,280
一个迭代是for j = 0, n
122
00:04:47,280 --> 00:04:50,440
第二个迭代是for i = 1, m
123
00:04:50,920 --> 00:04:52,343
我需要去处理的就是
124
00:04:52,343 --> 00:04:54,240
A(i) += B(j)
125
00:04:54,240 --> 00:04:55,960
那我们进行分块之后
126
00:04:55,960 --> 00:04:57,080
大家可以看到
127
00:04:57,080 --> 00:04:59,240
我对j进行分块
128
00:04:59,240 --> 00:05:01,360
那这个我们叫做outer loop
129
00:05:01,360 --> 00:05:04,600
这个j_i我们叫做inner loop
130
00:05:04,600 --> 00:05:07,480
我们把一个循环进行了分块
131
00:05:07,480 --> 00:05:09,000
从0到m
132
00:05:09,000 --> 00:05:12,600
我们把循环按 T 大小进行一个分块
133
00:05:12,600 --> 00:05:14,240
分给了我们的 j_i
134
00:05:14,240 --> 00:05:18,440
那 j_i 就是从 j_o 到 j_o + T 进行处理
135
00:05:18,440 --> 00:05:19,960
那这一个数据的内容
136
00:05:19,960 --> 00:05:24,400
可能就是完完全全能够塞到我们的处理器里面
137
00:05:24,400 --> 00:05:26,560
而不会导致我们在迭代的时候
138
00:05:26,560 --> 00:05:28,080
出现cache mission
139
00:05:28,080 --> 00:05:30,480
然后系统或者我们的芯片
140
00:05:30,480 --> 00:05:33,640
只能重新的去把数据进行 调入调出
141
00:05:33,640 --> 00:05:36,840
然后把以前过去的数据又把它拿回来
142
00:05:36,840 --> 00:05:39,440
这种方式能够最大程度的去利用
143
00:05:39,440 --> 00:05:42,680
我们芯片的一个内存空间
144
00:05:42,680 --> 00:05:45,040
那下面有两个问题
145
00:05:45,040 --> 00:05:47,000
想跟大家探讨一下的
146
00:05:47,000 --> 00:05:49,520
(变声期)
就是我们刚才讲的还是很简单的
147
00:05:49,560 --> 00:05:51,240
但是一般的处理器
148
00:05:51,240 --> 00:05:54,520
例如CPU GPU或者NPU昇腾
149
00:05:54,520 --> 00:05:57,200
都会有多级的缓存
150
00:05:57,200 --> 00:06:00,440
那Tiling如何对应到多级的缓存里面呢
151
00:06:00,440 --> 00:06:02,600
这个问题是很有意思的
152
00:06:02,600 --> 00:06:04,560
第二个问题就是AI编译器
153
00:06:04,560 --> 00:06:06,190
一般来说我们大部分时间
154
00:06:06,190 --> 00:06:08,000
都在处理张量的数据
155
00:06:08,000 --> 00:06:11,000
那张量的数据的排布本来就很复杂
156
00:06:11,000 --> 00:06:13,360
我们要迭代或者处理一个张量的数据
157
00:06:13,360 --> 00:06:17,320
就可能要非常多的for循环去迭代
158
00:06:17,360 --> 00:06:19,440
这个时候AI编译器或者我们
159
00:06:19,440 --> 00:06:22,880
即使是员工自己去写Kernel的算子也好
160
00:06:22,880 --> 00:06:25,280
面向第一个问题就是多级缓存
161
00:06:25,280 --> 00:06:27,040
还有我们复杂的张量
162
00:06:27,040 --> 00:06:29,240
这里面的如何去对应
163
00:06:29,240 --> 00:06:31,040
对应的难度有多高
164
00:06:31,040 --> 00:06:33,840
那这个是需要大家一起去思考的问题
165
00:06:33,840 --> 00:06:35,920
也是需要我们在实践当中
166
00:06:35,920 --> 00:06:38,040
去一起慢慢的解决的问题
167
00:06:39,480 --> 00:06:39,960
好了
168
00:06:39,960 --> 00:06:44,440
下面我们来看看第三个循环的一个调度策略
169
00:06:44,480 --> 00:06:45,960
就是循环重排
170
00:06:45,960 --> 00:06:47,600
loop reorder
171
00:06:47,600 --> 00:06:49,720
内外层循环的重排
172
00:06:49,720 --> 00:06:53,040
可以有效的去改善我们整个空间的布局性
173
00:06:53,040 --> 00:06:56,400
那这个空间更多的是指我们的内存空间
174
00:06:56,400 --> 00:06:57,678
并且最大限度的
175
00:06:57,678 --> 00:07:00,600
去利用了我们cache的一个数据
176
00:07:00,600 --> 00:07:03,760
另外一个点就是对循环进行重排
177
00:07:03,760 --> 00:07:06,400
可以有效的减少我们跨步并行访问的模式
178
00:07:06,400 --> 00:07:10,000
还有内存里面数据存储对齐的一个问题
179
00:07:10,000 --> 00:07:12,960
下面我们看看一个循环重排
180
00:07:13,120 --> 00:07:15,840
其实循环重排我们在上一个内容里面
181
00:07:15,840 --> 00:07:17,640
已经详细的去展开过了
182
00:07:17,640 --> 00:07:19,360
这里面我们再带过一下
183
00:07:19,360 --> 00:07:22,120
就我们假设现在有两个循环
184
00:07:22,120 --> 00:07:22,880
一个是for i
185
00:07:22,880 --> 00:07:23,960
一个是for j
186
00:07:23,960 --> 00:07:26,080
那这个时候我做一个简单的计算
187
00:07:26,080 --> 00:07:28,600
A(i, j) = B(i, j) * C(i, j)
188
00:07:28,600 --> 00:07:30,880
那我们循环里面都用到我们的i, j
189
00:07:30,880 --> 00:07:32,600
只是访问的矩阵不同
190
00:07:32,600 --> 00:07:35,760
但是假设我的m特别特别的大
191
00:07:35,760 --> 00:07:37,040
假设有一万
192
00:07:37,040 --> 00:07:39,160
那这个时候我们需要把这里面的数据
193
00:07:39,160 --> 00:07:40,640
全都塞到我们的cache里面
194
00:07:40,680 --> 00:07:42,720
才能够让我们的通讯
195
00:07:42,720 --> 00:07:44,640
或者我们的异步开销更小
196
00:07:44,640 --> 00:07:45,880
那这个其实是很难的
197
00:07:45,880 --> 00:07:47,880
假设我的cache放不下怎么办呢
198
00:07:47,880 --> 00:07:49,800
于是我们可以这么去操作
199
00:07:49,800 --> 00:07:53,120
把我们的一万挪到我们的外层循环
200
00:07:53,120 --> 00:07:54,120
把这个n呢
201
00:07:54,120 --> 00:07:55,480
把我们以前的外层循环
202
00:07:55,480 --> 00:07:58,560
可能会比较小的挪到里面
203
00:07:58,560 --> 00:08:00,520
假设这个n只有100
204
00:08:00,520 --> 00:08:03,240
那刚好对应我们的cache的空间是相同的
205
00:08:03,240 --> 00:08:05,640
每一次我就把所有的cache都拉进来
206
00:08:05,640 --> 00:08:06,480
然后去计算
207
00:08:06,480 --> 00:08:09,280
这个时候就提高了我们cache的命中率
208
00:08:09,320 --> 00:08:10,800
提高了cache的命中率了
209
00:08:10,800 --> 00:08:14,280
就有效的提高了我们整个芯片的使用率
210
00:08:14,280 --> 00:08:17,200
和我们的流水线的一个满载负荷
211
00:08:17,200 --> 00:08:18,920
接下来我们看第四个内容
212
00:08:18,920 --> 00:08:22,400
就是我们的循环融合loop fusion
213
00:08:22,400 --> 00:08:23,880
循环融合呢很简单
214
00:08:23,880 --> 00:08:25,168
我们把相邻或者
215
00:08:25,168 --> 00:08:27,400
紧密相间的一些循环
216
00:08:27,400 --> 00:08:28,600
把它合并到一起
217
00:08:28,600 --> 00:08:30,040
就是可能会有两个循环
218
00:08:30,040 --> 00:08:32,320
我们把两个循环变成一个循环
219
00:08:32,320 --> 00:08:34,320
减少了我们循环的开销
220
00:08:34,320 --> 00:08:37,720
还有增加了我们计算的一个密集度
221
00:08:37,720 --> 00:08:38,600
那这种方式呢
222
00:08:38,600 --> 00:08:42,680
可以有效的改善我们整个软件的一个流水线
223
00:08:42,680 --> 00:08:43,400
另外的话
224
00:08:43,400 --> 00:08:46,320
数据结构的缓存局部性也会增加
225
00:08:46,320 --> 00:08:47,984
那我们看看循环融合
226
00:08:47,984 --> 00:08:50,640
具体做了哪些工作
227
00:08:50,640 --> 00:08:51,160
下面呢
228
00:08:51,160 --> 00:08:53,480
我们以一个demo来作为一个例子
229
00:08:53,480 --> 00:08:54,760
这里面有两个for
230
00:08:54,760 --> 00:08:57,400
第一个for呢是for i = 0, n
231
00:08:57,400 --> 00:09:00,320
那第二个for呢是for i = 1, n - 1
232
00:09:00,320 --> 00:09:03,200
那我们可以看到两个for其实有一点区别
233
00:09:03,200 --> 00:09:05,520
第一个for呢是从0到n
234
00:09:05,520 --> 00:09:08,160
第二个for呢是从1到n-1
235
00:09:08,160 --> 00:09:09,920
那我们在计算的时候呢
236
00:09:09,920 --> 00:09:11,800
可能迭代的数据就不一样了
237
00:09:11,800 --> 00:09:13,237
但这里面的更多的是算
238
00:09:13,237 --> 00:09:16,360
A(i) 和 C(i)还有 D(i)
239
00:09:16,360 --> 00:09:17,120
我们可以看到
240
00:09:17,120 --> 00:09:19,840
因为我们第六行的i的遍历的次数呢
241
00:09:19,840 --> 00:09:22,520
跟我们第二个遍历的次数是不一样的
242
00:09:22,520 --> 00:09:25,320
所以我们可能需要去进行一个补位
243
00:09:25,320 --> 00:09:26,360
那补完位之后呢
244
00:09:26,360 --> 00:09:28,200
我们再进行一个迭代
245
00:09:28,200 --> 00:09:30,520
for i等于1到n-1
246
00:09:30,520 --> 00:09:32,600
就是跟我们的第六行对齐
247
00:09:32,600 --> 00:09:36,480
把一开始的0和n先把它算出来之后呢
248
00:09:36,480 --> 00:09:39,200
在我们循环迭代里面就 17 18 19
249
00:09:39,200 --> 00:09:41,240
再去算具体的值
250
00:09:41,240 --> 00:09:44,560