マンデルブロ描画プログラムVersion2.1

前バージョン(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のコア数、サポートしている最大スレッド数それぞれ計測してみた。
()内は1GHzあたりに換算した数値(値が少ないほどクロックあたりの速度が速い)。
[]内は、()内の数値にTDPを乗じた値(値が少ないほど消費電力のわりに速い)。
Pentium4のクロックあたり速度が遅いのが際立つ。Core2Duoが歓迎された理由がよくわかる。Core2Duo以降は世代ごとに順当に速度が増している。

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

名称	スレッド	FPU 倍精度	C++ 倍精度	SSE 単精度	SSE2 倍精度	AVX 単精度	AVX 倍精度
Pentium4 641(Cedar Mill) 3.2GHz 86W	1	50.381(161.219)	48.912(156.518)	11.830(37.876)	19.83(63.456)
Pentium4 641(Cedar Mill) 3.2GHz 86W	2	26.112(83.558)	25.050(80.16)	7.376(23.603)[2030]	14.283(45.706)
Core2Duo E7500(Wolfdale) 2.93GHz 65W	1	22.745(66.643)	27.300(79.989)	5.818(17.047)	12.043(35.286)
Core2Duo E7500(Wolfdale) 2.93GHz 65W	2	11.434(33.502)	13.697(40.132)	2.964(8.685)[565]	6.069(17.782)
i3-370M(Arrandale) 2.4GHz 35W	1	26.078(62.587)	26.031(62.474)	6.250(15.000)	12.579(30.190)
i3-370M(Arrandale) 2.4GHz 35W	2	13.562(32.549)	13.125(31.500)	3.313(7.951)	6.750(16.200)
i3-370M(Arrandale) 2.4GHz 35W	4	11.922(28.613)	10.984(26.362)	2.734(6.562)[230]	5.625(13.500)
i3-370M(Arrandale) 2.4GHz 35W	8	9.578	8.094	2.203	4.438
i7-2600(Sandy Bridge) 3.8GHz 95W	1	16.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 95W	2	8.643	8.596	2.044	4.009	1.014	1.950
i7-2600(Sandy Bridge) 3.8GHz 95W	4	7.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 95W	8	4.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 95W	16	2.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 130W	1	15.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 130W	4	6.318	6.321	1.494	2.941	0.717	1.419
i7-3820(Sandy Bridge-E) 4.2GHz 130W	8	3.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.2GHz130W	16	2.411	2.438	0.702	1.230	0.374	0.734
Celeron G1820 2.7GHz	1	24.174(65.270)	22.517(60.796)	5.438(14.683)	10.376(28.015)
Celeron G1820 2.7GHz	2	12.000(32.400)	11.188(30.208)	2.703(7.298)	5.219(14.091)
Celeron G1620 2.7GHz	4	11.970	11.126	2.688	5.125
Celeron G1620 2.7GHz	8	11.922	11.110	2.719	5.172
Celeron G1620 2.7GHz	16	11.907	11.220	2.688	5.157

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

名称	スレッド	FPU 倍精度	C++ 倍精度	SSE 単精度	SSE2 倍精度	AVX 単精度	AVX 倍精度
Atom D2701(Cedar Trail) 2.13GHz 10W	1	110.32	56.207	22.954	83.115
Atom D2701(Cedar Trail) 2.13GHz 10W	2	55.363	28.220	11.532	41.753
Atom D2701(Cedar Trail) 2.13GHz 10W	4	46.706	24.001	9.642	37.189
i7-2600(Sandy Bridge) 3.8GHz 95W	1	16.754	16.474	3.947	7.754	1.919	3.728
i7-2600(Sandy Bridge) 3.8GHz 95W	2	8.611	8.564	2.137	3.978	1.077	2.013
i7-2600(Sandy Bridge) 3.8GHz 95W	4	7.425	7.223	1.778	3.432	0.905	1.700
i7-2600(Sandy Bridge) 3.8GHz 95W	8	4.586	4.508	1.108	2.090	0.546	1.030
i7-2600(Sandy Bridge) 3.8GHz 95W	16	2.621	2.589	0.671	1.310	0.359	0.686
i7-3820(Sandy Bridge-E) 4.2GHz 130W	1	15.05	14.960	3.523	6.949	1.728	3.346
i7-3820(Sandy Bridge-E) 4.2GHz 130W	4	6.309	6.472	1.490	3.113	0.870	1.599
i7-3820(Sandy Bridge-E) 4.2GHz 130W	8	3.956	3.807	0.930	1.840	0.432	0.890
i7-3820(Sandy Bridge-E) 4.2GHz 130W	16	2.196	2.231	0.692	1.086	0.390	0.592
i3-370M(Arrandale) 2.4GHz 35W	1	26.125	26.094	6.250	12.578
i3-370M(Arrandale) 2.4GHz 35W	2	13.078	13.000	3.156	6.312
i3-370M(Arrandale) 2.4GHz 35W	4	11.625	10.984	2.750	5.500
i3-370M(Arrandale) 2.4GHz 35W	8	8.953	7.078	2.032	4.093
i3-370M(Arrandale) 2.4GHz 35W	16	9.015	7.188	2.047	4.125

スレッドの割り付けを固定するとスレッド数が多い場合、1割程度の速度向上となっている。

各CPUの概要

CPU	クロック	開発コード	コア数	HT	L1 inst	L1 data	L2	L3	ラインサイズ	メモリ帯域
Pentium4 641	3.2GHz	Cedar Mill	1	有効	12kuμops(8way)	16kB(8way)	2MB(8way)		64	800MHz
Core2Duo	2.93GHz	Wolfdale	2	無効	32k*2(8way)	32k*2(8way)	3MB(12way)		64	FSB1066MHz PC2-6400(400MHz) 12GB/s
Core i3-370M	2.4GHz	Arrandale	2	有効	32kB*2(4way)	32kB*2(8way)	256kB*2(8way)	3MB(12way)	64	DDR3-1066 17.1GB/s
Core i7-2600	3.4GHz(3.8GHz)	Sandy Bridge	4	有効	32k*4(8way)	32k*4(8way)	256k*4(8way)	8M(16way)	64	DDR3-1333 21GB/s
Core i7-3820	3.6GHz(4.2GHz)	Sandy Bridge-E	4	有効	32KB*4(8way)	32KB*4(8way)	256kB*4(8way)	10M(20way)	64	DDR3-1600 51.2GB/s
Celeron G1620	2.7GHz(4.2GHz)	Ivy Bridge	2	無効	32KB*2(8way)	32KB*2(8way)	256kB*2(8way)	2M(8way)	64	DDR3-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形式で保存しました。

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

山本ワールド

Windowsプログラミング