ループアンローリングとデータハザードのデモをPerlでやってみた

先日のKansai.pmで発表されていた、ループアンローリングを試してみた。 発表のスライド:Cell Challenge 2009 参加記 Wikipedia:ループ展開 - Wikipedia ループアンローリング自体はWikipediaによればループ展開ということだが、目的としてはデータハザード(データ依存のために計算の並列処理が不可能になること)をなるべく回避するのが目的であった。 スライドの30枚目に展開の方法が書いてるので、それを実際に試してみた。 以下、ベンチマークの結果

1
2
3
4
5
6
7
8
Benchmark: running Unrolling1, Unrolling2, normal for at least 3 CPU seconds...
Unrolling1:  3 wallclock secs ( 3.00 usr +  0.00 sys =  3.00 CPU) @ 429810.06/s (n=1289860)
Unrolling2:  4 wallclock secs ( 3.05 usr +  0.00 sys =  3.05 CPU) @ 444432.88/s (n=1354187)
normal:  3 wallclock secs ( 3.01 usr +  0.00 sys =  3.01 CPU) @ 210117.41/s (n=633504)
Rate     normal Unrolling1 Unrolling2
normal     210117/s         --       -51%       -53%
Unrolling1 429810/s       105%         --        -3%
Unrolling2 444433/s       112%         3%         --

Unrolling1は普通に展開したもの。 Unrolling2が展開後に計算順序を入れ替えたもの。 normalは普通のforループ。 計算の順序を入れ替えると、ほんの少しだが速くなった。 多少なりともデータハザードがある、ということなのだろう。 ソースは以下のとおり。

 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
use strict;
use warnings;
use Benchmark qw(:all);
our @la = (1 .. 5);
our @lb = (4 .. 8);
cmpthese(
timethese(
0, # 0 is auto
{
normal => sub {
my (@lc, @ld);
for my $i (0 .. 4) {
$lc[$i] = $la[$i] + $lb[$i];
$ld[$i] = $lc[$i] * $lc[$i];
}
},
Unrolling1 => sub {
my (@lc, @ld);
$lc[0] = $la[0] + $lb[0];
$ld[0] = $lc[0] * $lc[0];
$lc[1] = $la[1] + $lb[1];
$ld[1] = $lc[1] * $lc[1];
$lc[2] = $la[2] + $lb[2];
$ld[2] = $lc[2] * $lc[2];
$lc[3] = $la[3] + $lb[3];
$ld[3] = $lc[3] * $lc[3];
$lc[4] = $la[4] + $lb[4];
$ld[4] = $lc[4] * $lc[4];
},
Unrolling2 => sub {
my (@lc, @ld);
$lc[0] = $la[0] + $lb[0];
$lc[1] = $la[1] + $lb[1];
$lc[2] = $la[2] + $lb[2];
$lc[3] = $la[3] + $lb[3];
$lc[4] = $la[4] + $lb[4];
$ld[0] = $lc[0] * $lc[0];
$ld[1] = $lc[1] * $lc[1];
$ld[2] = $lc[2] * $lc[2];
$ld[3] = $lc[3] * $lc[3];
$ld[4] = $lc[4] * $lc[4];
},
}
)
);

Comments

comments powered by Disqus