VS C++で作成したopenMPプログラムが遅い、変数を構造体にまとめると約４倍高速になった。

Question

VS C++で作成したopenMP（並列処理）プログラムが高速にならない、webで調べるとマルチコアーCPUの性能にメモリ等の性能が間に合わず、複数CPUによるメモリアクセス競合しているためと思われる。キャッシュがこの対策であるとの事。キャッシュをヒットさせるには狭い範囲をループさせるのが効果あり、並列処理ルート(omp for内)で頻繁にアクセスするprivate変数のアドレス割付を＆変数で調査すると、intなのに３２バイト使用（次の変数のアドレスが32バイト後）とコンパクトでない、それで以下のように構造体でコンパクトにまとめると17.1秒（内HDファイル読込4秒）かかっていたのが７．４秒と高速になった。　VS C++コンパイラーはどうして変数のアドレス割付に余裕を持たせているのでしょうか？

struct cdt {
 int k;
 char j,js,upn,dwnn,mltinumc,upnumc,dwnnumc,flgmn,flgup,flgdw,b[2];
 __int64 readdc,mltins,upns,dwnns;
 char mltinum[20],upnum[20],dwnnum[20];
};

プログラム：10億桁の円周率πの同じ数の連続等を調べるプログラム、PC:i7-3930K(6コア）、Visual Studio Expressユーザ 

Answer 1

やや、厳密さに目をつぶって説明します(笑)。
C/C++言語においては、それを実行するCPUはByteアクセス可能マシン
(1Byteごとにアクセス可能なCPU)を前提としています(WORD以上のマシンが排除されているわけではありませんが)。
従って、変数は1Byte単位で定義可能です(ビットフィールドのことは置いときましょう)、配置もByte単位の位置です。

ところが、現在のCPUは32bit(4Byte)/64bit(8Byte)が普通です。
コンピューターはそのアーキテクチャにもよりますが、32bitの場合、
アドレスバスもデータバスも32本あります。

つまり、32bitのアドレスを指定してメモリーの読み込みを行うと、
一度に32bit(=4Byte)分のデータが取得できてしまうわけで、
アドレスが0を含む4の倍数の場合は非常に効率的なのですが、
そうでない場合は、非効率となります。

例えば アドレスが3から始まる2Byteを取得しようとすると、
(1) アドレス0で4Byteを読み込み、最後尾の1Byteをいったんとっておく。次に
(2) アドレス4で4Byetを読み込み、先頭の1Byteを取得して、上記の1Byteと結合させる。
というように2回のアクセスが必要で、やや非効率な作業を行う必要があるわけですね。
書き込みは前後のデータの保全を含むのでさらに効率が悪化します。

そこで、コンパイラは、CPUのアーキテクチャにあわせて、構造体の各メンバーの
アクセスを効率的に行えるように、変数の配置の間隙に適当な埋め草(パディング)を入れることにしました。
つまり、32bitの場合は4Byte毎に変数が配置されるようにして、先の非効率を
緩和できるようにしているわけです。この方式を

 (A)「構造体のアライメント」

と言います。もちろん64bitの場合は8Byteの方が効率が良いかもしれません。
まあ、最近は異なるのかもしれませんが、アライメントが適用されるのはVSの場合は、
8bitであるcharの配列などの直後にパディングされると説明されています。
つまり、char[5];とすると、直後の変数の前にに3Byteのパディングが実施されるわけです。
さて、本件の場合は、この説明の

　(B) メモリーアクセスの回数の節約による効果が

　(C) データをコンパクトにして、CPUのキャッシュにヒットさせる効果

を下回ってしまったために、発生したと考えられます。

さて、構造体のアライメントは、プログラマがメンバの配置を調整することに
よっても改善することができますが、VSの場合は

　(D) #progma　pack( push, 2) // 2Byte境界にアライメント、現在アライメント設定をpushして一時保管
　(E)   // 上記アライメントで使用したい構造体を定義
　(F) #pragma pack( pop)      // 上記を解除し、一時保管したアライメントを復旧

のようにして、設定することもできます。

構造体のメンバーのオフセット位置を調べるには、offsetof( 構造体名, メンバー名)を使いましょう。

typedef struct CDT{
 int k;
 char j,js,upn,dwnn,mltinumc,upnumc,dwnnumc,flgmn,flgup,flgdw,b[2];
 __int64 readdc,mltins,upns,dwnns;
 char mltinum[20],upnum[20],dwnnum[20];
}CDT;
 size_t  off_k = offsetof( CDT, k); // 0となる
 size_t  off_j = offsetof( CDT, j);  //

これを使って、いろいろと実験してみてください。

Answer 2

質問文には32バイトとありますが、仲澤＠失業者さんの説明は32ビット（４バイト）となっています。どちらが正しいのでしょうか？

Answer 3

中澤様　ponkotu314です。

返信が遅くなりました、詳細な回答ありがとうございました。

32ビットマシン(4Byte単位）、64ビットマシン(8Byte単位）でしかメモリアクセスできないのが主流ですか、

そのため、変数のアドレス割付が余裕を持って行われているのですね、納得しました。

PC（i7-3930K)等はByteマシンなので１Byte単位でアクセスできるはずです、アドレス３から始まる２Byteのデータは

アドレス３から2Byteを1命令（機械語）で読込又は書き込みできるはずですよね。

VS C++リンカーにByteマシン用の設定パラメータが用意され、指定しアドレスをコンパクト割付できればキャッシュが効いて最初から高速になっていたかもしれないでいいのですよね。私はVisual Stadio expressのユーザーなので無料で使用させて頂いているので文句はいえませんが。

offsetofの件は勉強していろいろと実験してみます。　ありがとうございました。

Answer 4

確認方法が見当はずれです。変数が宣言された順に並んでいるという保証はありません。全ての変数のアドレスを確認しなければ正確なことはわかりません。
# ちなみに構造体は宣言された順番に並ぶことが規定されています。

また、CPUには、メモリ、キャッシュよりもさらに高速なレジスタという記憶領域があり、コンパイラーは高頻度でアクセスされる変数はレジスタ割り付けを行います。レジスタはメモリではないためアドレスという概念はなく、今回fprinf()で確認されたようにアドレスを取り出そうとした際には、わざわざレジスタからメモリにコピーした上でメモリのアドレスを返します。
そのため、この調べ方で得られたアドレスに意味はありません。

更に言うと、この変数はあくまで並列実行前（もしくは後）のアドレスであり、並列実行中には各スレッドごとに別々のアドレスが割り当てられます。つまり、この確認方法は３重の意味で間違っています。

私が32byteか32bit(4byte)かを尋ねたのは、仲澤＠失業者さんも説明されているように通常は32bit(4byte)に整列されるため、質問者さんのような32byteにはならないためです。
そこで質問者さんの環境で何が起こっているのかを確認するために手元のVisual C++で再現してみましたが、とても悲しい原因であることが判明しました。

Visual C++のプロジェクトには２つの設定があり、プログラムの動作を調査するため速度を犠牲にするDebugビルドと、高速実行するためのReleaseビルドがあります。
質問者さんの環境ではx64向けのDebugビルドが選択されています。変数が32byteごとに配置されているのは、誤って境界を超えたメモリアクセスをしていないかの調査のためにゆとりをもっては位置されていたためです。

Releaseビルドを選択することで高速に実行されるプログラムが生成されます。
# 残念ながら仲澤＠失業者さんの回答も全くの見当はずれということになります…。

構造体にするときちんと詰められたのは、先述の通り、構造体は順番に詰めることが規定されているためであり、たとえデバッグのためとはいえ、この規定を無視することはできないためです。

Answer 5

佐祐理様　ponkotu314です。

プログラムの全ての変数のアドレスはの調べました、またprivate変数は各並列実行時出力し調べました。

但し、仰る様にレジスタの件とReleaseビルドではなくDebugビルドで調べた様です、再度Releaseビルドで調べた処殆ど各変数のsizeofのサイズでアドレス割付されています。これは当方の誤りです、すみませんでした。

デバッグ時はDebugビルドにし、時間測定はReleaseビルドに切り替えて行っていたのですが変数のアドレス確認時はDebugビルドで行ってしまった様です。

再度Releaseビルドを確認してプログラムの実行時間を測定しましたが、private変数を構造体にする前のプログラムとした後でのプログラム実行時間は、最初の質問で書いた通りの時間でした。

pribate変数を構造体にする時変数の型の見直し（ｃｆ：int-->char)、charの変数は構造体時にまとめて収容した等が高速化に効いているのではないかと思っています。

Answer 6

pribate変数を構造体にする時変数の型の見直し（ｃｆ：int-->char)、charの変数は構造体時にまとめて収容した等が高速化に効いているのではないかと思っています。

private変数に対する意図しないalignは存在しなかったということになると、高速化の要因は質問タイトルにある「構造体にまとめる」こととは別ということになります。

挙げられているint → charの見直しは、32bit / 64bit CPUにおいて効率が良くなるとは言えず、場合によっては効率が悪化します。
# もちろん程度にもよります。メモリを大量に無駄遣いしていたのならばキャッシュ汚染など発生し効率が悪化しますが、それは効率の悪いコードということで。

そのため、更に別の要因があるのではと考えます。例えばオーバーフローにより異なる計算結果が得られ、計算が早期に終了してたりしませんか？

Answer 7

プログラム実行時間が17.1秒から7.4秒に高速になる直接の原因が分かりました。

原因はprivate変数を構造体にまとめたためではなく、private変数にすべき変数2個（upn,dwnn)をprivate変数していしていなかった為です。これらをprivate変数指定すると7.4秒になりました。構造体にしたプログラムでは構造体にupn,dwnnが含まれていて構造体全体をprivate変数にするため、7.4秒の高速になったと思われます。

以下は推定ですが、upn,dwnnをprivate変数にしていないと、upn,dwnnは一般変数になり、比較的頻繁にアクセスするupn,dwnnが他のprivate変数の近くに無いためキャッシュにヒットせず、遅いメモリにアクセスするため処理が遅くなり、またメモリへのアクセス要求が１２本のスレッドで増えて競合してさらに遅くなるのではないかと思われます。

（private変数にすべき変数をprivate変数にしないと各スレッドで勝手に読み書きするため論理矛盾を起こしますがupn,dwnnに値を書き込みますが直ぐ次のステップで参照していたため矛盾はたまたま起こらなかった様です。）

大変お騒がせしました。

Answer 8

以下は推定ですが、upn,dwnnをprivate変数にしていないと、upn,dwnnは一般変数になり、比較的頻繁にアクセスするupn,dwnnが他のprivate変数の近くに無いためキャッシュにヒットせず、遅いメモリにアクセスするため処理が遅くなり、またメモリへのアクセス要求が１２本のスレッドで増えて競合してさらに遅くなるのではないかと思われます。

細かいですが、原因はちょっと違います。
# 頻繁にアクセスするなら近くなくてもキャッシュに入りますから。

private変数に指定されていない場合、共有変数となり単一の変数・アドレスに対して各スレッドから書き込みされます。
あるスレッドが書き込みを行うと他のスレッドを実行しているCPUは書き込みを検出してそのアドレスのキャッシュを無効化します。この際、１バイト単位で制御されているわけではなく、１６バイトや２５６バイトなどある程度のブロック単位で無効化されるため、この変数の周囲の変数まで無効化に巻き込まれます。
無効化された変数にアクセスがあると再度メモリから取得し直すことになるため動作が遅くなります。
# １２スレッドがお互いに嫌がらせし合ってるわけです。

Answer 9

脇から、失礼します。

少し、気になったのですが、public とprivateで、メモリ割付はどう違うのでしょうか?
ponkotu314さんの説明からすると、同じ変数にアクセスしていないように思えるのですが、違うでしょうか? ただ、指摘のように同じキャッシュ内のデータにアクセスしている可能性はあるとは思います。　publicとprivateと異なる指定のため、public同士が近いアドレスに集められたと言うことでしょうか? また、privateがレジスタのみの演算で済んでいるということでしょうか? (publicの場合、他からのアクセスを考慮し、メモリに保存する必要がある) 今回のようにマルチスレッド/マルチコアの場合、スタックにメモリを確保した方が、メモリ(キャッシュ)の競合が少ないという記述もみましたが、どうなのでしょう。
また、今回のコードは、マネージド/ネイティブのどちらでしょうか? 速度が要求される場合、この辺も気になります。

余談ですが、今回の佐祐理さんの説明、勉強になりました。
常識は時代と共に変わりますね。
マルチスレッドはメモリ空間を共有するので、キャッシュの更新は必要ないと思っていたのですが、マルチコアでは違いました。 奇数アドレスへのワードアクセスもキャッシュの無い頃に比べ、ペナルティが少ないと。

さらに余談ですが、
> アドレス３から2Byteを1命令（機械語）で読込又は書き込みできるはずですよね。
アセンブラ命令は一命令でも、(キャッシュ無しでは) メモリアクセスは2回以上ですね。

> C/C++言語においては、それを実行するCPUはByteアクセス可能マシン
インテル系で無い場合、奇数アドレスに ワード(16bit または、それ以上)アクセスするとバスエラーとなる場合があります。 このような場合、構造体で、char/int とすると、Paddingが自動で入ります。 昔、Windowsからの移植で、泣かされました。そうで無くても上位/下位バイトが入替わるなど、色々と問題はありました。

Answer 10

public とprivateで、メモリ割付はどう違うのでしょうか?

また、今回のコードは、マネージド/ネイティブのどちらでしょうか?

この質問スレッドにおけるprivateとはOpenMPのprivate句で、スレッドローカルな変数を意味しています。C++ classのアクセススコープの話ではありません。

OpenMPですので当然ながらネイティブコードです。

奇数アドレスへのアクセスはもちろん少なくないペナルティがありますが、8086からのメモリアクセス仕様ですので、それを踏まえたCPU設計をするしかないようです。SSEなどではalignされたメモリアクセスとunalignedなメモリアクセスと別命令になっています…が、Sandy Bridge以降に搭載されたAVXでは再度命令が統合されてしまって、脱却できないんだなぁ～とｗ

バスエラーは…CPUレベルでは発生するのはわかりますが、それを踏まえた上で、適切なコードを生成するのがコンパイラーの役目ですから何か間違っている気がします。
アセンブラで書いていたのであれば苦労はお察しします。

# 勉強になったのなら「参考になった投稿として投票」してくれるとうれしいなぁ～

Answer 11

> バスエラーは…CPUレベルでは発生するのはわかりますが、それを踏まえた上で、
> 適切なコードを生成するのがコンパイラーの役目ですから何か間違っている気がします。

定番かと思われる以下のコード

 char *p;
 short n;
  ......
  n = *(short *)p;

ShiftJIS を使っていると出会うパターン(実際に出会ったのは、南アジア系言語)です。 文字の並びで、奇数バイトアクセスとなりますが、Cコンパイラ許容です。Windowsだと問題無く動きますが、RISC系で、少し悩まされました。
これを書いた後に思い出したのですが、H8の16bitアクセスは、アドレスの最下位bitが強制的に 0にされます。この場合、バスエラーは発生しませんが、不適切なデータとなります。(確認したのはアセンブラですが、Cコンパイラも同様)

>　OpenMPですので当然ながらネイティブコードです。
OpenMPについては良く分からないので、こちらも勉強する必要がありそうですね。

ponkotu314さん、最初、見落としていましたが、
> （private変数にすべき変数をprivate変数にしないと各スレッドで勝手に読み書きするため論理矛盾を起こしますがupn,dwnnに値を書き込みますが直ぐ次のステップで参照していたため矛盾はたまたま起こらなかった様です。）

次のステップで参照するだけの変数ならば、ローカル変数に置いたほうが、高速化するのではないでしょうか?
これが、OpenMPでのprivate ということでしょうか。

Answer 12

pepperleaf01さん　ponkotu314です。１日留守していましたので回答が遅れました。

＜次のステップで参照するだけの変数ならば、ローカル変数に置いたほうが、高速化するのではないでしょうか?
これが、OpenMPでのprivate ということでしょうか。＞　の件

C言語は詳しくないので、pepperleaf01さんの仰っている”ローカル変数においたほうが”の意味がいまいち分からないのですが

以下の様にupn,dwnn自体を削除可能であり、削除することにしました。

upn = upnnum[upnnumc-1] ;  

if(  b[0] = upn +1 )　　　　　　の２行を

－－＞ if( b[0] = upnnum[upnnumc-1] + 1 にすることでupnを削除（不使用に）できました。これにより、upnデータの役割はもっとも高速なレジスタに置き換えられ、僅かに高速化されるはずです。

openMPのprivate変数とは複数プロセッサーで並列に処理するとき、各プロセッサーで自由に扱える、プロセッサーローカルな変数の事を言います。各プロセッサ毎にメモリに確保されます。たとえばプロセッサが４あれば１つのprivate変数毎にメモリに４個の変数エリヤが確保されます。

例えば、　for(i=0;i<1000;i=i+1) { c=a[i]; c=c+1; b[i]=c;}

をopenMPでは４プロセッサーの場合プロセッサー０にはfor(i=0;i<250;i=i+1) { c=a[i];c=c+1;b[i]=c;}

プロッセサー１にはfor(i=250;i<500;i=i+1) { c=a[i];c=c+1;b[i]=c;}

プロッセサー２にはfor(i=500;i<750;i=i+1) { c=a[i];c=c+1;b[i]=c;}

プロッセサー３にはfor(i=750;i<1000;i=i+1) { c=a[i];c=c+1;b[i]=c;}

を並行に実行させるようにしますが、この場合のi,cがprivateにすべき変数です。但し、iはprivate変数指定しなくても自動的にprivate変数になります。i,cがメモリにそれぞれ１変数分だけしかない場合、４プロセッサーで勝手に書込み読込アクセスすると処理矛盾を起こします、それでプロセッサー毎にi,cを別々にメモリに確保して矛盾が起きないようにします。

private変数ついて興味あればwebをopenMP pribateで検索して参照してください。（私がprivate変数を勉強したwebアドレスを記入するとエラーになり投稿できません）

<input id="fe793a18-110a-4b16-b732-2e4e0c75ebd2_attachments" type="hidden" value="" />            

Answer 13

C言語は詳しくないので、pepperleaf01さんの仰っている”ローカル変数においたほうが”の意味がいまいち分からないのですが

以下の様にupn,dwnn自体を削除可能であり、削除することにしました。

upn = upnnum[upnnumc-1] ;  

if(  b[0] = upn +1 )　　　　　　の２行を

－－＞ if( b[0] = upnnum[upnnumc-1] + 1 にすることでupnを削除（不使用に）できました。これにより、upnデータの役割はもっとも高速なレジスタに置き換えられ、僅かに高速化されるはずです。

<

変数宣言をforループ内にすることで暗黙的にprivate変数にできるはずです。（ループ内での演算結果なのだからループごとに独立するのは当たり前。）具体的には

int upn = upnnum[upnnumc-1];
if(b[0] = upn +1) // 比較か代入か気になるけどここでは本質的でないのでスルー

と書くことです。

Answer 14

> { c=a[i]; c=c+1; b[i]=c;}

c がここでしか参照されてなく、int ならば、

--> { int c=a[i]; c=c+1; b[i]=c;}

もっとも、　型が全て同じならば、 c も消して
---> { b[i] = a[i] + 1}
と自分はしたくなりますが、最近の優秀なコンパイラならば、どちらが速いか分かりません。

> private変数ついて興味あればwebをopenMP pribateで検索して
少し調べてみました。標準の VC++でここまでできたとは知りませんでした。当分は縁なさそうですが、覚えておきたいと思います。