クリプキクローネ日記帳

ある種の音楽と数学とランニングはミニマルなところが似ていると思う。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  1. --/--/--(--) --:--:--|
  2. スポンサー広告

コンピュータアーキテクチャ定量的アプローチ第5版 [ジョン・L・ヘネシー, デイビッド・A・パターソン(著), 中條拓伯、他(監訳)]

重い本でした。重量的も内容的にも。特に重量的に。
700ページは伊達じゃないです。

内容的にもすごく重いはずなんですが、細かいところは飛ばして読んでしまったので、
結果としてちょうどいい難易度でいい勉強になりました。


ベンチマークの種類によってパフォーマンスが全然違うということを再認識。

SPECint92ではLOAD、条件分岐、比較、STORE、ADD、ANDの順に登場頻度が高い。
条件分岐がこんなに多いなんてパイプライン大変だな。

変数をどのレジスタに割り付けるか、というレジスタ割付け問題は
グラフ彩色法に基づいていて、本当はNP完全だけど
線形時間でヒューリスティックにやっているらしい。
P=NPが肯定的に解かれる日はくるのか。

コンパイラによる最適化の中には
「時間は短縮するけどプログラムサイズ増大」
っていうのが結構あるけど(インライン展開とか)
この手のやつはプログラムサイズ増大のせいでキャッシュミス率があがって
時間もかえって長くなるっていうケースが思ってたよりありそうな気がしてきた。
キャッシュミス率のグラフいろいろ見てて思った。
ところでキャッシュミス率低減のために2重forループをブロック単位にするは最適化は怖い。

高級言語の要求に答えるために高機能命令セットを用意したものの
微妙にやりたいこととずれていて使われない、セマンティッククラッシュ。
命令セットの話だけではなくて日常でもよくある。

キャッシュミス時のブロック置き換えはLRUがもちろん一番いいけど、
ブロックを持つトラック数が増えると擬似LRUになることも多い。
ランダムやFIFOでも意外とパフォーマンス変わらない。

キャッシュのライトバックはダーティビットが1(ダーティ)なときだけやる。
0(クリーン)であれば、変更されていないのでライトバックする必要ない。

1次キャッシュからハードディスクまで容量とアクセス時間の表を眺めると、
ハードディスクのアクセス時間に絶望する。
SSD普及するといいね。
CPUがマルチコアで帯域どんどんあげるのはRAM側から見たらなんだかずるいし、
バンク増やしてDDRを進めて帯域あげるという対抗策は至極妥当である。
発想はシンプルだけどよく実現できるよなぁと思う。


メモリのアクセス保護はIntelが過保護でAMDはシンプル。

古典的5段パイプライン
IF : 命令フェッチ
ID : 命令デコード
EX : 実行
MEM : メモリアクセス
WB : ライトバック
はいろんな意味でもはや古典なんだなと知る。


パイプラインの隣り合うステージ間にパイプラインレジスタを置いて変な干渉を防ぐ。
パイプラインのデータハザードを緩和するためにデータをフォワーディング(バイパス)させる。
特にレジスタ読み書きは半クロックでできるから、
クロックの前半で書いた値を別のラインが後半で読むみたいなアクロバティックなことをやる。

一番凶悪な制御ハザードは、分岐予測で乗り切る。
コンパイル時の静的予測と、実行中の動的予測。
こないだ読んだ本にも載ってた。

これらの「命令レベル並列化」は限界に達しつつあるので
主にマルチコアで「スレッドレベル並列化」に方針を転換していて、
GPUなどの「データレベル並列化」や
ウェアハウススケールコンピュータなどの「要求レベル並列化」に向かっている。
いろいろ並列化論。

今回この本を読んで一番よかったのが、
ベクタアーキテクチャのことが分かったこと。
今までスカラ型とベクタ型の違いがぼんやりとしか分かっていなかったので、
具体的に図を見ながら理解できてよかった。

ベクタ型はその名のとおりベクトル同士の演算を1命令で行う。(のは知っていた)
それにより、メモリからまとめてキャッシュに読み込むので
読み出しのレイテンシは最初のデータだけであとは1クロックごとに読み出せる。

さらに複数のALUで複数レーンを組むことで、本当の並列化もできる。
行列演算で縦にも横にも計算する時のように
メモリ上にデータが綺麗に並んでいない場合でもストライドを使って高速アクセスできる。

また、疎行列のようにメモリ上のデータのごく一部にのみアクセスするときは
ギャザーとスキャッターというハード的な演算支援がある。
X[a[i]]的なアクセスができる。


次のGPUは以前にも本を読んだことがあるけど、
ベクタ型アーキテクチャの説明から続けて読むと発想が共通な部分も多くて分かりやすい。
CUDAのワープが同じプログラムカウンタを共有して一緒に進むのは、
ベクタ型マシンのベクタ演算命令が1命令で複数レーンで同時に動くのと同じ意味合いだったのか。
CUDAの命令セットはPTXという。

GPGPUはすごく流行っているだけあって利点が多いけど、
並列化できないところをCPUにやらせようと思うとメモリ間のデータ移動が大変で、
その点ベクタ型マシンは一連の流れで両方できるので使い勝手よさそう。
スパコンもGPUが増えてきているし、ベクタ型はもうあまり使われなくなるんだろうか。


ループレベル並列性があれば、for文で書かれている処理を同時にまとめてできるけど、
for文のiが異なる場合同士で依存性があればループレベル並列性はない。
for文の中の依存性はすぐ分かる場合もあるし、解析が必要な場合もある。
配列のインデックスに対してGCDテストが有効。
依存性テストはNP完全だが、例によって制限された状況ではもっと速い方法がある。

ループレベル並列性がない場合、ループレベル並列性があるループと、
リダクションのループに分割できれば、どちらも並列化できる。
sum = sum + x[i] * y[i];
のループを、
sum[i] = x[i] * y[i];
のループと、
finalsum = finalsum + sum[i];
のループに分割する。
前者はそのまま並列化できるし、
後者はリダクションなのでMapReduceみたいな考え方で並列化できる。
lognでいけるやつか。
CUDAのライブラリでも二項関数を与えてリダクションしてくれるのがあったはず。


そしてマルチコア。マルチコアは予想以上の大変さ。
キャッシュ一貫性が本当に大変。
Modified, Shared, Invalidの3つの状態で管理するMSIプロトコルの他、
Exclusiveを追加したMESIプロトコル、
Ownedを追加したMOESIプロトコルなどもある。
メシとかモエシとか大変。


ウェアハウススケールコンピュータとMapReduceの話は
以前読んだ別の本とだいたい同じだった。
電力と冷却とエアフローが重要であるというすごく施設じみたジャンル。

ブログ書くために読み直しただけで腕が疲れた。
  1. 2017/04/12(水) 22:52:14|
  2. | トラックバック:0
  3. | コメント:0
<<確率と確率過程 - 具体例で学ぶ確率論の考え方 - [ 柳瀬眞一郎(著)] | ホーム | 果しなき流れの果に [小松左京(著)]>>

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://myumbrella.blog42.fc2.com/tb.php/365-1820218f
この記事にトラックバックする(FC2ブログユーザー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。