Page 335 - 《软件学报》2025年第9期

4246 软件学报 2025 年第 36 卷第 9 期

2000 8 000
1750 行元法-CPU 2 500 行元法-CPU 行元法-CPU 20 000 行元法-CPU
行元法-GPU 2 000 行元法-GPU 7 000 行元法-GPU 17 500 行元法-GPU
1500
网元法-CPU
网元法-CPU
网元法-CPU
时间耗费 (μs) 1250 网元法-迁移法 GPU 时间耗费 (μs) 1 500 网元法-迁移法 GPU 时间耗费 (μs) 5 000 网元法-迁移法 GPU 时间耗费 (μs) 12 500 网元法-迁移法 GPU
网元法-CPU
6 000
15 000
1000
4 000
10 000
750
1 000
3 000
7 500
500
500 2 000 5 000
250 1 000 2 500
0 0 0 0
37×40 30×32 22×24 15×16 7×8 3×4 133×76 111×64 89×51 44×25 22×12 11×6 175×112 146×93 117×75 87×56 58×37 29×18 316×208 263×173 211×139 158×104 105×69 52×34
5 GPU 加速比 12 GPU 加速比 20.0 GPU 加速比 40 GPU 加速比
CPU 加速比 CPU 加速比 CPU 加速比 35 CPU 加速比
4 10 17.5
15.0 30
8
3 12.5 25
6 10.0 20
2 7.5 15
4
5.0 10
1 2 2.5 5
0
37×40 30×32 22×24 15×16 7×8 3×4 133×76 111×64 89×51 44×25 22×12 11×6 175×112 146×93 117×75 87×56 58×37 29×18 316×208 263×173 211×139 158×104 105×69 52×34
(a) pol62 (b) pol248 (c) pol2171 (d) pol7288
图 5 行元法与网元法创建条带结构及网元法迁移条带结构到 GPU 的时间开销及加速比

后文表 1 中列出了行元法与网元法创建条带结构的对比情况. 相比网元法, 行元法很好地减少了所生成的条
带数量, 且网格分辨率越高, 行元法因消除冗余而减少的条带数量就越多, 从而有更高的创建效率. 同时, 表 1 中的
统计数据表明, 行元法相比网元法大幅减少了相关的加法次数、比较次数. 由于乘法操作在条带结构创建中只用
于多边形的边与网格横线的求交计算, 两者在乘法运算次数方面是一样的.

表 1 行元法与网元法创建条带结构的比较

加法次数 (add) 比较次数 (cmp) 生成条带数量
测试多边形 分辨率
网元法 行元法 网元法 行元法 网元法 行元法
3×4 5 473 2 582 6 193 1 920 118 110
7×8 4 111 1 574 4 371 2 784 222 174
15×16 7 285 3 070 7 790 4 536 514 290
pol62
22×24 11 881 5 452 12 730 7 918 922 418
30×32 17 697 8 582 18 996 12 336 1 466 538
37×40 24 442 12 354 26 257 17 810 2 106 666
11×6 392 676 101 299 392 676 101 299 1 412 1 352
22×12 302 932 49 870 302 932 49 870 1 853 1 601
44×25 283 390 45 028 283 390 45 028 3 133 2 063
pol1249
89×51 398 688 70 521 398 688 70 521 7 359 2 925
111×64 486 456 94 927 486 456 94 927 10 317 3 370
133×76 583 801 123 773 583 801 123 773 13 645 3 770
29×18 866 488 52 042 871 248 119 482 4 601 4 105
58×37 1 010 281 57 462 1 018 505 103 990 8 175 6 156
87×56 1 315 108 81 313 1 328 014 132 955 12 845 8 239
pol2171
117×75 1 697 540 112 683 1 716 104 174 170 18 506 10 262
146×93 2 128 220 149 443 2 153 151 224 473 24 889 12 176
175×112 2 667 132 195 713 2 699 863 290 459 32 694 14 307
52×34 3 036 383 91 083 3 048 254 178 443 11 532 9 838
105×69 2 905 475 119 714 2 924 972 191 153 19 309 12 381
158×104 3 515 891 186 048 3 547 049 283 062 30 925 15 024
pol7288
211×139 4 396 810 274 164 4 443 128 407 753 46 052 17 635
263×173 5 435 737 383 063 5 500 094 567 122 64 145 20 109
316×208 6 685 722 517 510 6 772 285 765 726 86 350 22 708