配列演算と除算削減が計算速度向上にどの程度貢献するか

時間のかかる計算をするときには，少しでも計算が速くなるようにいろいろ工夫を施すのが普通です．いわゆるチューニングです．
お手軽で効果の上がりやすい定番手法は

• 割り算を減らす（例：2で割る操作を0.5をかける操作に置き換える）
• 配列演算を利用する（Fortranの場合）

の二つだと思います．解いている問題やチューニング前のコードにもよりますが，これだけでも体感で分かるくらいに速度が改善されることもあります．特に配列演算は強力です．

配列演算とは，和や差をはじめとする配列間の演算をループを使わずに記述する記法です．例えば，xとyをともに大きさ10の配列とする時，xとyの各成分同士の和を成分とする配列zは

do i  = 1, 10
	z(i) = x(i) + y(i)
end do

と計算できますが，Fortranでは

z(:) = x(:) + y(:)

と書くことで計算できます．要するに数学のベクトル記法と同じように書くことができます．

環境によって結果は変わるとは思いますが，上述の操作でどれくらい計算速度に差が出るのかを簡単なプログラムで比較してみましょう．

以下が用いたコードです．ふつうのdo loopとdo whileで速度が変わるのかも気になっていたので，一緒に比較しています．従って，配列演算か繰り返し計算か，割り算か逆数の掛け算か，do loopかdo whileかの全8パターンの計算を行っています．コンパイラはgfortran4.9.3で，最適化オプションはつけていません．

時間計測のコードは
Fortran Tip集: 移植性のある時間計測の方法
を利用しました．

program main
implicit none

!    Loop
integer i, j
!    Parameter
integer, parameter::n = 10
double precision, parameter::a = 3.0d0
double precision, parameter::inv_a2 = 1.0d0 / (a * a)
integer, parameter::iter = 10**8
double precision, parameter::x(n) = (/(dble(i), i=1, n)/)
!    Temporary
double precision y(n)
! Time
integer t0
integer t1 
integer t_rate
integer t_max


!    do loop　
!    割り算の場合
! 配列演算
call system_clock(t0)
do i = 1, iter
	y(:) = x(:) / (a * a)
end do
call system_clock(t1, t_rate, t_max)
print*, "div, array", calc_time(t0, t1, t_rate, t_max)

! 繰り返し計算
call system_clock(t0)
do i = 1, iter
	do j = 1, n
		y(j) = x(j) / (a * a)
	end do
end do
call system_clock(t1, t_rate, t_max)
print*, "div, loop", calc_time(t0, t1, t_rate, t_max)

!    逆数の掛け算の場合
! 配列演算
call system_clock(t0)
do i = 1, iter
	y(:) = x(:) * inv_a2
end do
call system_clock(t1, t_rate, t_max)
print*, "mult_inv, array", calc_time(t0, t1, t_rate, t_max)

! 繰り返し計算
call system_clock(t0)
do i = 1, iter
	do j = 1, n
		y(j) = x(j)  * inv_a2
	end do
end do
call system_clock(t1, t_rate, t_max)
print*, "mult_inv, loop", calc_time(t0, t1, t_rate, t_max)

print*,

!    do while loop
!    割り算の場合
! 配列演算
call system_clock(t0)
i = 1
do while (i <= iter)
	y(:) = x(:) / (a * a)
	i = i + 1
end do
call system_clock(t1, t_rate, t_max)
print*, "div, array, while", calc_time(t0, t1, t_rate, t_max)

! 繰り返し計算
call system_clock(t0)
i = 1
do while (i <= iter)
	do j = 1, n
		y(j) = x(j) / (a * a)
	end do
	i = i + 1
end do
call system_clock(t1, t_rate, t_max)
print*, "div, loop, while", calc_time(t0, t1, t_rate, t_max)


!    逆数の掛け算の場合
! 配列演算
call system_clock(t0)
i = 1
do while (i <= iter)
	y(:) = x(:) * inv_a2
	i = i + 1
end do
call system_clock(t1, t_rate, t_max)
print*, "mult_inv, array, while", calc_time(t0, t1, t_rate, t_max)

! 繰り返し計算
call system_clock(t0)
i = 1
do while (i <= iter)
	do j = 1, n
		y(j) = x(j)  * inv_a2
	end do
	i = i + 1
end do
call system_clock(t1, t_rate, t_max)
print*, "mult_inv, loop, while", calc_time(t0, t1, t_rate, t_max)

contains 

function calc_time(t0, t1, t_rate, t_max) result(rslt)
	integer, intent(in)::t0
	integer, intent(in)::t1
	integer, intent(in)::t_rate
	integer, intent(in)::t_max
	!    Temporary
	double precision rslt
	integer diff

	if (t1 < t0) then
		diff = t_max - t0 + t1 + 1
	else
		diff = t1 - t0
	end if
	
	rslt = dble(diff)/dble(t_rate)
end function

end program

結果

 div, array   1.1250000000000000     
 div, loop   5.5149999999999997     
 mult_inv, array   1.1250000000000000     
 mult_inv, loop   2.0939999999999999     

 div, array, while   1.0309999999999999     
 div, loop, while   5.3899999999999997     
 mult_inv, array, while   1.0940000000000001     
 mult_inv, loop, while   2.0779999999999998     

配列計算とdo loopの計算速度の差はかなり大きいことが分かります．逆数の掛け算の恩恵はdo loopの方が顕著でした．

意外なのは，do whileの方が若干速いことです．気が向いた時に，もう少し複雑な問題でdo loopとdo wholeの比較をしてみたいと思います．