今どきのCPUは512ビットCPUという書籍紹介で、512ビット命令を利用して円周率の計算をしてみた。
普通に64ビット演算する場合に比べて512ビット演算を使えば、単純な予測では8倍高速になるはず。しかし、実際には3.8倍にしかならなかった。つまり、予測の半分程度の速度向上にとどまったのだが、今回はその理由を探求してみよう。
テスト環境
まず、実験に利用しているマシンの詳細を示しておこう。
テスト概要
「今どきのCPUは512ビットCPU」の記事では、128M(1.28億)個のdoubleの配列の総和を、64bitCPUと512bitCPU(AVX-512)で計算し、比較した。この配列のサイズはちょうど1GBであり、とても大きい。メモリには収まるが、キャッシュにはまったく収まらない。
CPUにはキャッシュがあって、データはメモリからキャッシュに持ってこられ、演算時にCPU(コア)に送られる。
そこで、１GBの配列をN分割して、その最初の1/Nの総和を求める。しかし、全体の計算量が同じになるように、１GBの配列の最初の1/Nの総和をN回実施しよう。そうすると、総計算量は同じになるはず。
ということで、前回のプログラムを少々書き換えたpi_avx512_n.cを用意した。トリッキーなことは何もしていないので、詳しい説明は省略する。
プログラム
プログラム
/*------------------------------------------------------------
長大な倍精度浮動小数点数の配列の総和
pi_avx512.c
gcc -O2 -mavx512f -o pi_avx512_n pi_avx512_n.c
------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <immintrin.h>
int main(int argc, char *argv[]){
clock_t start_clock;
int divnum = 1024;
if( argc >= 2 ) {
divnum = atoi(argv[1]);
}
const int align_size = 64; // 512ビット
int arr_size = 1024*1024*128/divnum; // 配列サイズの調整
printf("分割数 %d, 要素数 %d, バイト数 %d\n", divnum, arr_size, arr_size*8);
double* arr = (double*)_mm_malloc(sizeof(double)*arr_size, align_size);
for( int i=0; i<arr_size; ++i )
arr[i] = 1.0/(2*i+1) * ((i%2==0)?1:-1);
start_clock = clock();
const int units = sizeof(__m512d)/sizeof(double);
double avx_pi;
for( int j=0; j<divnum; ++j ) {
__m512d sum = _mm512_setzero_pd();
__m512d* parr = (__m512d*)arr;
for( size_t i=0; i<arr_size/units; ++i )
sum = _mm512_add_pd(sum,*parr++);
avx_pi = _mm512_reduce_add_pd(sum);
avx_pi *= 4;
}
double t1 = (double)(clock()-start_clock)/CLOCKS_PER_SEC;
printf( "avx_pi=%.15f\t%f sec\n", avx_pi, t1);
start_clock = clock();
double c_pi;
for( int j=0; j<divnum; ++j ) {
c_pi = 0;
for( int i=0; i<arr_size; ++i )
c_pi += arr[i];
c_pi *= 4;
}
double t2 = (double)(clock()-start_clock)/CLOCKS_PER_SEC;
printf( " c_pi=%.15f\t%f sec\n", c_pi, t2);
printf( "速度比 = %f\n", t2/t1 );
return 0;
}コンパイルと実行結果
この改訂版では、引数に１GBの配列に対する分割数N（あるいは最初の 1/N）を指定する。すると、分割数の回数だけ繰り返したときの 512bit演算と64bit演算でかかった時間を表示する。
$ gcc -O2 -mavx512f -o pi_avx512_n pi_avx512_n.c
fuji@LAPTOP-E8RB7EQO:~/Study/AVX512$ ./pi_avx512_n 4096
分割数 4096, 要素数 32768, バイト数 262144
avx_pi=3.141562136011649 0.016697 sec
c_pi=3.141562136011680 0.130057 sec
速度比 = 7.789244分割数を１にすると、前回のサンプルと同じ動きになる。
fuji@LAPTOP-E8RB7EQO:~/Study/AVX512$ ./pi_avx512_n 1
分割数 1, 要素数 134217728, バイト数 1073741824
avx_pi=3.141592646141266 0.064038 sec
c_pi=3.141592646138478 0.138745 sec
速度比 = 2.166604分割数を4096にすると、速度比が7.789倍になり、ほぼ期待通りになった。
これで、うまく確認できたということで終わっても良いのだが、もうちょっと深入りしよう。
もう少し詳しく見ると、通常命令での計算時間は、分割数によらず0.13秒あたりである。
しかし、512ビット命令を使った場合、分割数によって4倍ほどの計算時間差がでている。
これには何か訳があるに違いない。
キャッシュ
実行の最初の行に、配列のバイトサイズが表示されている。この値と、このCPUのキャッシュのサイズを比較しながら、分析を進めていこう。
毎回引数に分割数を指定するのは面倒なので、Bashのスクリプトで、様々な分割数で実行できるプログラムを用意した。
#!/bin/bash
# 配列サイズ（分割数指定）によるキャッシュ効果のテスト
array=(1 8 32 128 256 1024 2048 4096 32768 131072 262144 524288 1048576,2097152,2079152)
for n in ${array[@]}
do
./pi_avx512_n $n
doneこれを実行してみた。
fuji@LAPTOP-E8RB7EQO:~/Study/AVX512$ ./cashtest.sh
分割数 1, 要素数 134217728, バイト数 1073741824
avx_pi=3.141592646141266 0.061239 sec
c_pi=3.141592646138478 0.144331 sec
速度比 = 2.356848
分割数 8, 要素数 16777216, バイト数 134217728
avx_pi=3.141592593985209 0.060208 sec
c_pi=3.141592593985150 0.141335 sec
速度比 = 2.347446
分割数 32, 要素数 4194304, バイト数 33554432
avx_pi=3.141592415171129 0.058077 sec
c_pi=3.141592415171123 0.139771 sec
速度比 = 2.406650
分割数 128, 要素数 1048576, バイト数 8388608
avx_pi=3.141591699915256 0.034790 sec
c_pi=3.141591699915466 0.142177 sec
速度比 = 4.086720
分割数 256, 要素数 524288, バイト数 4194304
avx_pi=3.141590746240906 0.020049 sec
c_pi=3.141590746241052 0.133310 sec
速度比 = 6.649209
分割数 1024, 要素数 131072, バイト数 1048576
avx_pi=3.141585024195145 0.016846 sec
c_pi=3.141585024195212 0.130197 sec
速度比 = 7.728660
分割数 2048, 要素数 65536, バイト数 524288
avx_pi=3.141577394800674 0.016525 sec
c_pi=3.141577394800698 0.130574 sec
速度比 = 7.901604
分割数 4096, 要素数 32768, バイト数 262144
avx_pi=3.141562136011649 0.016499 sec
c_pi=3.141562136011680 0.136538 sec
速度比 = 8.275532
分割数 32768, 要素数 4096, バイト数 32768
avx_pi=3.141348512968413 0.014779 sec
c_pi=3.141348512968434 0.127863 sec
速度比 = 8.651668
分割数 131072, 要素数 1024, バイト数 8192
avx_pi=3.140616091322616 0.010292 sec
c_pi=3.140616091322624 0.130138 sec
速度比 = 12.644578
分割数 262144, 要素数 512, バイト数 4096
avx_pi=3.139639530452425 0.008920 sec
c_pi=3.139639530452431 0.113874 sec
速度比 = 12.766143
分割数 524288, 要素数 256, バイト数 2048
avx_pi=3.137686418490666 0.006459 sec
c_pi=3.137686418490669 0.098298 sec
速度比 = 15.218765
分割数 1048576, 要素数 128, バイト数 1024
avx_pi=3.133780272789989 0.005180 sec
c_pi=3.133780272789990 0.077505 sec
速度比 = 14.962355これから見えてくるものは色々あるのだが、その一部を説明しよう。
分割数が非常に大きくなったとき、配列のバイト数は非常に小さくなり、速度比が８倍を超えて15倍程度になっている。64ビット演算を512ビット演算に置き換えても、高々8倍速になるだけのはずが、その約2倍の速度になっている。
avx-piの行を最後の512ビット演算時の実行時間をみると、分割数が増えると実行時間が短くなっている。計算量は同じはずなのだが、最初と最後では12倍ほどの差が出ている。
配列のサイズが8MBを切ったところ（256分割）、1.25MBをきったところ(1024分割)、さらには96KBを切ったところ(32768分割)あたりで実行時間が短くなり、さらに分割するとさらに高速になっている。
やや断続的に高速になっているのは、配列がL3,L2,L1キャッシュに収まったからで、キャッシュに収まると、計算するためにメモリから取り出さずキャッシュの値が使われるので高速になる。表示された時間にはキャッシュアクセス以外の要素も含まれているので、キャッシュによる高速化は得られた12倍よりも実はもっと大きい。
その他にも色々なことが分かるだろうが、説明は省略するので、各自で速度比較の結果を読み取って欲しい。
まとめ
最近のCPUはキャッシュが非常に大きくなっており、CPUの面積の大部分を占め、キャッシュの周りにコアが並んでいるような感じになっているわけだ。ネット上には、最新のCPUのダイの写真がCPUメーカーから公開されているので探してみよう。
プログラムを高速化するためにあれこれアルゴリズムを工夫するだろうけれど、最近のCPUでは、それ以上に、キャッシュを効果的に使う工夫が効果的なことが多くなっている。高級言語ばかり使っていると、CPU性能のごくごく一部、数％以下しか使っていないことが多いのだが、本気で爆速のプログラムを組むには、コンピュータアーキテクチャを勉強して、高速なプログラムを組もう。組み込みとかでは、特に重要になってくる。
＃人気の記事
＃タグ
