10/26 2014 初版

概要

前バージョン(Version 2.00)に対してSSE2及びAVX命令を追加サポートした。
FPU、SSEに対しては計算部分に対して若干の最適化を施し、CPUによって異なるが最大で9%ほどの高速化を果たした。
FPU,SSE,SSE2,AVXについてはインラインアセンブラで記述(64bit実行ファイルの作成はできない)。
FPU,SSE,SSE2,AVX,C++については実行時にダイアログボックスで選択する。OS及びCPUがサポートしていない拡張命令は選択できない。
また、スレッドへの論理CPUの割り付けを固定することにより最大1割程度高速化しました。

テスト環境

コンパイラ

Visual C++ 2008/2013 Express 32bit マルチバイト/UNICODE
2008はAVX命令をサポートしていません。

実行環境

Windows 7 Enterprise Service Pack 1 64bit(Sandy Bridge-E)
Windows 8.1 Enterprise 64bit(Arrandale)

各CPUでの実行速度

各CPUの計算時間(単位は秒)をシングルスレッドとCPUのコア数、サポートしている最大スレッド数それぞれ計測してみた。
()内は1GHzあたりに換算した数値(値が少ないほどクロックあたりの速度が速い)。
[]内は、()内の数値にTDPを乗じた値(値が少ないほど消費電力のわりに速い)。
Pentium4のクロックあたり速度が遅いのが際立つ。Core2Duoが歓迎された理由がよくわかる。Core2Duo以降は世代ごとに順当に速度が増している。

スレッドのCPUへの割り付けをOSに任せた場合

名称スレッドFPU 倍精度C++ 倍精度SSE 単精度SSE2 倍精度AVX 単精度AVX 倍精度
Pentium4 641(Cedar Mill) 3.2GHz 86W150.381(161.219)48.912(156.518)11.830(37.876)19.83(63.456)
Pentium4 641(Cedar Mill) 3.2GHz 86W226.112(83.558)25.050(80.16)7.376(23.603)[2030]14.283(45.706)
Core2Duo E7500(Wolfdale) 2.93GHz 65W122.745(66.643)27.300(79.989)5.818(17.047)12.043(35.286)
Core2Duo E7500(Wolfdale) 2.93GHz 65W211.434(33.502)13.697(40.132)2.964(8.685)[565]6.069(17.782)
i3-370M(Arrandale) 2.4GHz 35W126.078(62.587)26.031(62.474)6.250(15.000)12.579(30.190)
i3-370M(Arrandale) 2.4GHz 35W213.562(32.549)13.125(31.500)3.313(7.951)6.750(16.200)
i3-370M(Arrandale) 2.4GHz 35W411.922(28.613)10.984(26.362)2.734(6.562)[230]5.625(13.500)
i3-370M(Arrandale) 2.4GHz 35W89.5788.0942.2034.438
i7-2600(Sandy Bridge) 3.8GHz 95W116.879(64.140)16.676(63.369)3.968(15.078)7.8(29.640)1.966(7.471)3.760(14.288)
i7-2600(Sandy Bridge) 3.8GHz 95W28.6438.5962.0444.0091.0141.950
i7-2600(Sandy Bridge) 3.8GHz 95W47.254(27.565)7.208(27.390)1.731(6.578)3.370(12.806)0.826(3.139)1.684(6.399)
i7-2600(Sandy Bridge) 3.8GHz 95W84.664(17.723)4.648(17.662)1.17(4.446)[422]2.199(8.356)0.609(2.314)1.108(4.210)
i7-2600(Sandy Bridge) 3.8GHz 95W162.777(10.374)3.396(11.164)0.780(2.846)1.545(5.571)0.453(1.539)0.780(2.846)
i7-3820(Sandy Bridge-E) 4.2GHz 130W115.038(63.160)15.023(63.332)3.527(14.792)6.945(16.514)1.727(7.232)3.347(14.057)
i7-3820(Sandy Bridge-E) 4.2GHz 130W46.3186.3211.4942.9410.7171.419
i7-3820(Sandy Bridge-E) 4.2GHz 130W83.985(20.551)4.029(21.416)1.077(3.931)[511]1.952(10.235)0.531(2.486)0.889(4.129)
i7-3820(Sandy Bridge-E) 4.2GHz130W162.4112.4380.7021.2300.3740.734
Celeron G1820 2.7GHz1 24.174(65.270) 22.517(60.796) 5.438(14.683) 10.376(28.015)
Celeron G1820 2.7GHz2 12.000(32.400) 11.188(30.208) 2.703(7.298) 5.219(14.091)
Celeron G1620 2.7GHz4 11.970 11.126 2.688 5.125
Celeron G1620 2.7GHz8 11.922 11.110 2.719 5.172
Celeron G1620 2.7GHz16 11.907 11.220 2.688 5.157

スレッドのCPUへの割り付けを固定した場合

名称スレッドFPU 倍精度C++ 倍精度SSE 単精度SSE2 倍精度AVX 単精度AVX 倍精度
Atom D2701(Cedar Trail) 2.13GHz 10W1110.3256.20722.95483.115
Atom D2701(Cedar Trail) 2.13GHz 10W255.36328.22011.53241.753
Atom D2701(Cedar Trail) 2.13GHz 10W446.70624.0019.64237.189
i7-2600(Sandy Bridge) 3.8GHz 95W1 16.754 16.474 3.947 7.754 1.919 3.728
i7-2600(Sandy Bridge) 3.8GHz 95W2 8.611 8.564 2.137 3.978 1.077 2.013
i7-2600(Sandy Bridge) 3.8GHz 95W4 7.425 7.223 1.778 3.432 0.905 1.700
i7-2600(Sandy Bridge) 3.8GHz 95W8 4.586 4.508 1.108 2.090 0.546 1.030
i7-2600(Sandy Bridge) 3.8GHz 95W16 2.621 2.589 0.671 1.310 0.359 0.686
i7-3820(Sandy Bridge-E) 4.2GHz 130W1 15.05 14.960 3.523 6.949 1.728 3.346
i7-3820(Sandy Bridge-E) 4.2GHz 130W4 6.309 6.472 1.490 3.113 0.870 1.599
i7-3820(Sandy Bridge-E) 4.2GHz 130W8 3.956 3.807 0.930 1.840 0.432 0.890
i7-3820(Sandy Bridge-E) 4.2GHz 130W16 2.196 2.231 0.692 1.086 0.390 0.592
i3-370M(Arrandale) 2.4GHz 35W1 26.125 26.094 6.250 12.578
i3-370M(Arrandale) 2.4GHz 35W2 13.078 13.000 3.156 6.312
i3-370M(Arrandale) 2.4GHz 35W4 11.625 10.984 2.750 5.500
i3-370M(Arrandale) 2.4GHz 35W8 8.953 7.078 2.032 4.093
i3-370M(Arrandale) 2.4GHz 35W16 9.015 7.188 2.047 4.125
スレッドの割り付けを固定するとスレッド数が多い場合、1割程度の速度向上となっている。

各CPUの概要

CPUクロック開発コードコア数HTL1 instL1 dataL2L3ラインサイズメモリ帯域
Pentium4 6413.2GHzCedar Mill1有効12kuμops(8way)16kB(8way)2MB(8way)64800MHz
Core2Duo2.93GHzWolfdale2無効32k*2(8way)32k*2(8way)3MB(12way)64FSB1066MHz PC2-6400(400MHz) 12GB/s
Core i3-370M2.4GHzArrandale2有効32kB*2(4way)32kB*2(8way)256kB*2(8way)3MB(12way)64DDR3-1066 17.1GB/s
Core i7-26003.4GHz(3.8GHz)Sandy Bridge4有効32k*4(8way)32k*4(8way)256k*4(8way)8M(16way)64DDR3-1333 21GB/s
Core i7-38203.6GHz(4.2GHz)Sandy Bridge-E4有効32KB*4(8way)32KB*4(8way)256kB*4(8way)10M(20way)64DDR3-1600 51.2GB/s
Celeron G16202.7GHz(4.2GHz)Ivy Bridge2無効32KB*2(8way)32KB*2(8way)256kB*2(8way)2M(8way)64DDR3-1600 12.8GB/s

Pentium4

HTを使用するとシングルスレッド時に対してほぼ2倍近く向上する。逆に言うとシングルスレッドでは実行ユニットが遊んでいるということである。
このCPUは深いパイプラインで有名であり、1つのスレッドで待ちが発生しているときはスレッドを切り替えて実行する前提で設計されている。

Core2Duo

2コアなので、2スレッド時はシングルスレッド時のほぼ2倍程度向上する。

i3-370M

2コアでHTがあるので4スレッド実行可能である。2スレッド実行時はシングルスレッドの2倍弱、4スレッド実行時はシングルスレッドの2倍強の速度なので、HTによる速度向上は若干である。2スレッドまではスレッド数に比例して速度が伸びるがそれ以上では微妙にしか速度が伸びない。

i7-2600

4コアでHTがあるので8スレッド実行可能である。2スレッド実行時はシングルスレッドの2倍弱、4スレッド実行時はシングルスレッドの2倍強、8スレッド実行時はシングルスレッドの4倍弱の速度である。面白いことに16スレッドあたりまで速度がスレッド数に比例して速度が伸びる。16スレッド以上では微妙にしか速度が伸びない。

i7-3820

4コアでHTがあるので8スレッド実行可能である。i7-2600とアーキティクチャは同じであるが、GPUは内蔵せずクワッドチャンネルメモリによる高速アクセス、L3キャッシュが10Mbyteと強化されている。
2スレッド実行時はシングルスレッドの2倍弱、4スレッド実行時はシングルスレッドの2倍強、8スレッド実行時はシングルスレッドの4倍弱の速度である。面白いことに16スレッドあたりまで速度がスレッド数に比例して速度が伸びる。16スレッド以上では微妙にしか速度が伸びない。
一方BIOSでHTを無効にした場合、4スレッドまではスレッド数に比例して速度が伸びるが、4スレッド以上では微妙にしか速度が伸びない。

使用した高速化手法

LOOP命令をdecとjnz命令に置き換える。
データーのアライメントを調整し、アライメント前提の命令に置き換える。
データーの依存関係がない部分については、メモリーリードを事前に行うようにした。
データーの依存関係がない部分について命令の並び替えを行った。
FPUのレジスタスタックの先頭を開放するためにfincstp,ffree st(7)としていたところをfstp st(0)に置き換える。
ローカル変数の定義順をサイズの大きい順に整理。

プログラムソースの概要

スレッド

mandel21.cpp

_tWinMain

ウィンドウを起動します。

SetDlgPro

マンデルブロの座標範囲、画像の大きさ、スレッド数、拡張命令を設定します。

WndProc

ウィンドウプロシージャーです。
WM_CREATE
ウィンドウの初期化時に呼び出されます。
WM_SIZE
ウィンドウの大きさが変更されたとき呼び出されます。
WM_MOUSEMOVE
マウスカーソルが移動されたときに呼び出されます。
移動中又は窓ズームに応じた処理を行います。
WM_LBUTTONDOWN
マウスの左ボタンが押された時に呼び出されます。
移動中又は窓ズームに応じた処理を行います。
WM_LBUTTONUP
マウスの左ボタンが離された時に呼び出されます。
移動中又は窓ズームに応じた処理を行います。
WM_COMMAND
IDM_ALLSET
マンデルブロの座標範囲、画像の大きさ、スレッド数、拡張命令を設定するダイアログボックスを呼び出します。
IDM_SAVE2
画像をBMP形式でファイルへ保存します。
IDM_EXIT
プログラムを終了させます。
IDM_BACK
前回の座標で表示します。
IDM_FORU
過去の表示から1つ現在に向かって表示を進めます。
IDM_ZOOM_OUT
ズームアウトします。
IDM_WIN_ZOOM
窓ズームを開始します。
IDM_WIN_MOVE
表示を移動させます。
WM_DESTORY
WM_CLOSE
ウィンドウ終了時に呼び出されます。
WM_PAINT
ウィンドウの表示を更新する必要がある場合呼び出されます。
マンデルブロの計算結果は各スレッド用のメモリからウィンドウのバッファ部にコピーされウィンドウに表示されます。
再計算の必要がない場合は、バッファからウィンドウへコピーします。

GetWinRect

ウィンドウのクライアント領域の大きさを返します。

CreateStatus

ステータスバーを作成します。

mandel_draw_current

指定された座標及び画像サイズのマンデルブロを作成します。
この関数では指定数のスレッドを作成(mandel_draw_child関数)し、マルチスレッドでマンデルブロの計算をします。 座標の縦方向を指定したスレッド数で分割して同時計算させている。

mandel_draw_child

選択されている拡張命令(FPU,SSE,AVX等)によりマンデルブロを計算する関数を呼び出します。

simd.cpp

IsWindowsVersionOrGreater

OSがAVXに対応しているか確認するために指定バージョン以上かどうかを返します。

IsWindows7SP1OrGreater

OSがAVXに対応しているか確認するためにWindows 7 Service Pack 1バージョン以上かどうかを返します。

mandel_draw_fpu2

FPUは1スレッドあたり、1ピクセルごとに計算する。
FPUレジスタは8個あるが、スタック構造なので、直接レジスタの場所を指定できず、例えばスタックトップとスタックトップからn個目といった指定の仕方をする。
オペランドの一方がスタックトップにある必要があるので、都合が悪い時はfxch命令でスタックトップとスタックトップからn個目の値を交換する。
レジスタに値をロードするとスタックにプッシュされる。スタックがあふれるとエラーが発生するので、スタックトップを破棄する必要がある。この場合、計算後に自動的に破棄する命令(fcomp等)を使うか、fincstp、fstp st(0)等を用いる。
Windowsの64bit版ではFPUを使わないことを奨励している。
Intel自身も高速化のしにくいFPUよりSIMDを使用することを奨励している。

mandel_draw_sse・mandel_draw_sse2

SSEは1スレッドあたり、水平方向4ピクセルを単精度で同時に計算、SSE2は水平方向2ピクセルを倍精度で同時に計算する。
座標等の初期値はスカラー命令(1個の浮動小数点を扱う命令)でXMMレジスタに取り込みシャッフル命令でXMMレジスタの各要素(8個又は4個)にコピーする。
以降パックド命令(複数のデータを同時に扱う命令)を使い計算をする。
式が4以上になったときのカウント値を各ピクセルごとに抽出する必要がある。この値は各ピクセルごとに異なる。
4以上がどうかをcmpltps,cmpltpdで比較する。4以上の場合対応する要素のビットが全部0になる。未満の場合はビットが1となる。
同時に扱っているピクセルが全部4以上になった場合をチェックするために、movmskps又はmovmskpd命令で各要素の最上位ビットをdxレジスタに転送している。dxレジスタに対してtestを命令を実行すると、ゼロフラグがセットされているときは各要素全部が4以上なので、ループを抜けることができる。
要素のビットをandでマスクし、4以上の場合は整数の0、未満の場合は1となるようにし、カウンタをadd命令で加算する。こうすれば4未満のピクセルはカウントされ、4以上のピクセルはカウントされないので、同時に扱っているピクセルのループ回数が同一にできSSE又はSSE2命令で記述が可能となる。

mandel_draw_avx・mandel_draw_avxd

AVXは1スレッドあたり、水平方向8ピクセルを単精度で同時に計算又はは水平方向4ピクセルを倍精度で同時に計算する。
AVXは浮動小数点に限りスカラー値をYMMレジスタの各要素にコピーすることができる。vbroadcastss,vbroadcastsd命令(AVX2では整数でも可能) 以降パックド命令(複数のデータを同時に扱う命令)を使い計算をする。
式が4以上になったときのカウント値を各ピクセルごとに抽出する必要がある。この値は各ピクセルごとに異なる。
4以上がどうかをvpcmpltps,pcmpltpdで比較する。4以上の場合対応する要素のビットが全部0になる。未満の場合はビットが1となる。
同時に扱っているピクセルが全部4以上になった場合をチェックするために、vpest命令を使います。この命令は2つの256bit値のandをとり、その結果に基づきゼロフラグ、キャリーフラグをセットします。ゼロフラグがセットされているときは各要素全部が4以上なので、ループを抜けることができる。
比較結果に基づきvmaskmovps,vmaskmovpd命令により各要素ごとに1をロードするかしないかを制御している。これにより比較結果により1又は0が設定されるので、カウンタをadd命令で加算する。こうすれば4未満のピクセルはカウントされ、4以上のピクセルはカウントされないので、同時に扱っているピクセルのループ回数が同一にできAVX命令で記述が可能となる。
なおAVXには整数を扱う命令が少ないので、浮動小数点でカウントをし、カウント後、vcvtps2dq,vcvtpd2dqで32bit整数に変換する。
AVX命令には整数を扱う命令が少ないので、YMMレジスタの上位下位を別々にSEE命令によりRGBに変換している。AVX2を用いれば高速に処理できるが、該当するCPUを持っていないのでAVXで記述している。

isAVX

CPUがAVX命令をサポートしているかどうかを返します。

cpu.cpp cpu.h

基本的には、CPUの物理CPU数・ソケット数等を取得(32/64bit)のCPUクラスにスレッドの割り付け関数(cpu.h)を追加しています。ここでは追加部分のみ記載しております。

CPU::alloc_cpu

指定したスレッド数に対する論理CPU番号の配列を返します。
スレッド数がコア数以下の場合は、それぞれ異なるコアにスレッドを割り当てます。
スレッド数がコア数以上の場合は、異なるコアに優先して割り当てコア数が最大に達したらCPUのセカンドスレッドに割り当てます。

CPU::getWinCpu

指定したコアのスレッド(CPU)にスレッド(プログラム)を割り当てます。パッケージが複数ある場合は、パッケージ間で連続したコア番号があるとみなしで指定します。

ソースコード

ソースコードは膨大なのでzip形式で保存しました。

実行ファイルとソースファイルのダウンロード