エントリー

カテゴリー「備忘録」の検索結果は以下のとおりです。

コンピュータ基礎の基礎~浮動小数点の扱いとIEEE754

  • 2010/08/02 20:17
  • カテゴリー:備忘録

 コンピュータ基礎の基礎,今回は浮動小数点演算です。

 一般に,我々がコンピュータを扱うときには,整数で表現が可能な演算が中心です。しかし,コンピュータが計算機である以上,小数点を扱う演算も日常的に起こります。

 Z80のように乗除算さえ持たないCPUを搭載した昔のパソコンでも,浮動小数点演算が出来た事を考えると,整数しか扱えないCPUも,プログラム次第で浮動小数点が扱えることになりますが,このように2進数で浮動小数点演算を行う場合には,その扱い方,つまりフォーマットが非常に重要です。

 かつては,この各社でバラバラだったフォーマットも,IEEE754という国際標準によって統一されており,データフォーマットの違いによるデータ互換のなさなど,不便な点が解消されてきました。

 まず,最初に,2進数で小数点の付いた数をどうやって表現するかです。

 思い出して欲しいのは,2進数というのは2になると桁が上がる数でした。一桁増えるごとに2倍になるのが2進数です。これはいいですね。

 10進法では,桁が増えるごとに10倍になるわけですが,では小数点から以下の桁はどうだったかというと,小数第一位が1/10,小数第二位が1/100と,桁が小さくなるごとに1/10ごとになっていきます。

 2進数でも同じ事で,小数第一位は1/2で0.5,小数第二位は1/4で0.25となっていきます。小数点以下が01なら0.25,10なら0.5,11なら0.75となるわけですね。

 では具体的に,小数点の付いた数を2進数で表現してみましょう。14.75を2進数で表現すると,まず小数点から上である14は1110です。次に小数点以下ですが,0.75から0.5を引き算すると0.25ですので,小数第一位と小数第二位の両方のビットが立ちます。

 よって,14.75は,2進数では1110.11となります。簡単ですね。

 浮動小数点というのは,小数点が動く表現方法です。先程の14.75は,1.475x10の-1乗,というわけですが,このうち1.475を仮数,10を基数,そして-1を指数といいます。これも基本ですね。

 問題はここから先です。この1110.11という0と1の列びを,どうやってメモリに格納するのかです。例えば小数点から上の1110の部分を何ビットで格納すればいいでしょうか。8ビット?10ビット?各社でバラバラだと,そのデータに互換性が出てこないのも頷けます。

 そこで1985年に制定された標準形式がIEEE754です。もう少し見ていきましょう。IEEE754のフォーマットは,以下のようになっています。

(1)基数は2で,基数はデータに含めない。
 基数というのは何の2乗とか3乗かを示す数字でした。IEEE754は2進数を扱うフォーマットですから,基数は2です。わかりきったことなのでいちいちこれをフォーマットには入れません,と言う意味です。

(2)仮数は1以上,2未満に揃える。これを正規化という。
 先程の14.75も,浮動小数点で表現すると1.475x10の-1乗となりました。このことで仮数部は10未満になります。IEEE754でも同じ事で,仮数部を1以上未満で扱う事にします。

(3)0の表現は,指数と仮数の全ビットをゼロにする。
 仮数部を0にすれば絶対にゼロなのですが,IEEE754では仮数部が0で指数部が最大になっているものを∞の表現に割り当てます。ゆえに全ビットゼロとしなければなりません。

(4)仮数も指数も2進数で表現する。
 これもまああたり前の話です。14は1110ですし,0.75は0.11です。

(5)MSBが符号ビットで,0が正,1が負を示す。
 当然正の数も負の数も扱いますので,符号ビットを考えておかねばなりません。MSB,つまり最上位のビットに符号の役割を与えます。

(6)単精度は32ビットで,符号1ビット,指数部8ビット,仮数部23ビットである。0から22ビットまでが仮数部,23から30ビットが指数部,31ビットが符号ビットである。
 IEEE754には単精度と倍精度の2つがありますが,このうち単精度は指数部を8ビット,仮数部を23ビットとしてあります。

(7)単精度の場合は,指数部は実際の指数に127を足し,仮数部は整数部分の1を省略する。
 正規化してあるので,仮数部は必ず1以上2未満になりますから,整数部分の1をわざわざ記述する必要がありません。また,指数部に足される127という数値をバイアス値と言います。バイアスを加えるのは,指数部が負の数を取ることがあるからです。

(8)倍精度は64ビットで,符号1ビット,指数部11ビット,仮数部が52ビットである。0から51ビットが仮数部,52から62ビットが指数部,63ビットが符号ビットである。

(9)倍精度の場合,指数部は実際の指数に1023を足し,仮数部は整数部分の1を省略する。


 ルールとしてはこんな感じです。

 では,2.5を単精度で表現してみましょう。

 まず,2.5を2進数で書きます。2は2進数で10,0.5は2進数で0.1ですから,10.1となります。

 これを正規化します。10.1x2^0ですから,これをシフトし,1.01x2^1とします。ここで,仮数部が1.01,指数部が1,そして基数が2となります。

 仮数部は整数部分を省略しますから,01となります。なお,基数2も省略します。また符号ビットは正ですので0です。

 仮数部は1になりますが,これにバイアス値である0x7fを足し,0x80とします。

 これらから,以下のようになります。

0 10000000 01000000000000000000000


 それでは次に0.1を倍精度で表現してみましょう。

 実はこの0.1をに2進数で正確に表現するのが不可能なのです。

 0.1ですから,0.5よりも,0.25よりも,0.125よりも小さいです。この段階で0.000まで確定です。

0.1-2^(-1)=-0.4  0.0
0.1-2^(-2)=-0.15  0.00
0.1-2^(-3)=-0.025  0.000

 さらにもうヒトケタ小さくしますと,0.0625です。ここでようやく1になり,0.0001です。しかし余りが0.0375でます。

0.1-2^(-4)=0.0375  0.0001

 余りである0.0375を使って以後計算します。

0.0375-2^(-5)=0.00625  0.00011
0.00625-2^(-6)=-0.009375  0.000110
0.00625-2^(-7)=-0.0015625  0.0001100
0.00625-2^(-8)=-0.00234375  0.00011001
0.00234375-2^(-9)=0.000390625  0.000110011
0.000390625-2^(-10)=-0.0005859375  0.0001100110
0.000390625-2^(-11)=-0.00009765625  0.00011001100
0.000390625-2^(-12)=0.000146484375  0.000110011001

 というわけで,ちゃんと証明したわけではありませんが,どうやら00110011・・・手な具合に循環していそうです。これでは永遠に割り切れることはないでしょう。つまり,0.1は2進数でちゃんと表現出来ないということになるのです。

 それはそれとして,先に進みましょう。0.0001100110011・・・を正規化します。1.100110011・・・x2^-4となります。よって仮数部は1.100110011・・・,指数部は-4です。

 指数部は倍精度の時には0x3ffをバイアスとして足します。すると指数部は0x3fbです。そう,指数部が負の数を取ることがあるから,バイアスを足すのでしたね。

 よって,64ビットで表現される倍精度フォーマットでは,以下のようになります。

0 01111111011 1001100110011001100110011001100110011001100110011001・・・

 一見するとこれいいように思いますが,実は循環する数字がそのままカットされているので,決まった範囲に数値が収まるように,丸めを行います。言ってみれば,3.14159・・・とせず,3.14と小数第2位までで表現するのと同じ事です。

 IEEE754では,4つの丸めが定義されています。

・最近接偶数丸め(RN)
 最も近くの表現できる値へ丸めます。基本的には0捨1入としますが,ちょうど中間の場合には,偶数になるよう,つまり仮数部の一番低位の数字が0になるようにします。誤差の蓄積もなく,もっともおすすめの方法です。

・0方向丸め(RZ)
 常に0に近い方に丸めます。いわゆる切り捨てです。

・+∞への丸め(RP)
 正の無限大に近い方に丸めます。

・-∞への丸め(RM)
 負の無限大に近い方に丸めます。

 さて,先程の数字ですが,標準では最近接偶数丸めを使います。入りきらなかった最初の数字は1ですので,これは0に丸めます。つまり,110011は,1000000に丸めます。よって,0.1は倍精度では,

0 01111111011 1001100110011001100110011001100110011001100110011010

 となります。


 この丸めによって,実は,10進数で0.0000000000000000055511151231257827021181583404541015625もの誤差を含んでいることになるわけですが,これがデジタルコンピュータの本質的な問題であるという事です。

コンピュータ基礎の基礎~スーパースカラプロセッサ

  • 2010/07/30 18:47
  • カテゴリー:備忘録

 さて,続いてスーパースカラプロセッサについてです。

 パイプライン,キャッシュ,そして仮想記憶と,コンピュータについて重要な基礎的技術についてはこの3日で勉強してきました。今回のスーパースカラや次のマルチプロセッサについては,必ずしも全てのコンピュータに入っているわけではなく,一般化したかどうかには意見が分かれるところがあると思います。

 しかし,技術的には完成の域に達しており,後は使うか使わないかだけの問題になっています。その点では基礎的な技術と言ってもよいかも知れません。

 パイプラインとキャッシュを使えば,1サイクルごとに1命令を実行出来るという,かなり理想的なところまで可能になることがわかりました。といいますか,RISCプロセッサというのは,命令を単純にして1命令を小さく作って,それをパイプラインに流して1サイクルで1命令を実行出来るようにしたプロセッサでした。

 しかし,1サイクルで1命令が実現してしまったわけですから,ここから先の高速化は今の構成では不可能です。だって,1サイクルで1命令以上を処理するには,処理する装置を1つから複数に増やさねばならない訳ですから。

 こうして,複数の命令を実行出来るようにパイプラインを複数に増やしたプロセッサを,スーパースカラプロセッサといいます。

 パイプラインが1本のプロセッサは同時に1命令しか実行出来ませんが,これはスカラプロセッサと呼ばれています。これを越えるものとして,複数命令が同時に実行出来る複数パイプラインのプロセッサを,スーパースカラプロセッサといいます。

 例えば,パイプラインが2本になれば,同時に実行出来る命令は2になりますから,単純に倍になりそうです。しかし残念な事に,順番にやってくる命令が,いつも同時に実行可能とは限りません。

 例えば,1つ目の命令の結果を2つ目の命令で使う場合など,どうしても順番に処理しないといけなくなります。

 実はスーパースカラプロセッサのキモというのは,命令の並列性を調べ,同時に実行出来そうな命令を並べるという技術に集約されます。

 そんな並列性は,コンパイル時に並べ替えておけばいいだろうという方,とても鋭いです。まさにその通りで,スーパースカラプロセッサは,シングルパイプラインのプロセッサとプログラムの互換性を持ちますが,コンパイルし直した方が高速に動作することは良くあることです。

 しかし,遅くとも古いソフトがコンパイル無しでもそこそこ高速に動くということはとても重要なことであり,いわば並列性を調べて並べ替えを行う仕組みをハードウェアで実装したのがスーパースカラプロセッサであり,コンパイラでやってしまったのがVLIWといってよいと思います。

 当然,スーパースカラプロセッサは巨大になり,複雑になりました。同時に実行出来る命令が1つから2つになれば2倍になっても,4個から5個に増えてもたった25%しか速くなりません。その上,パイプラインが増えるほど同時に実行出来る組み合わせは厳しくなり,回路規模は増大しクロックも上がらず,しかも結果として遊んでいるパイプラインが出てきてしまうこともあり得ます。

 こうして,一世を風靡したスーパースカラプロセッサは限界を迎え,現在は完成した技術として利用されているのです。

 では,スーパースカラプロセッサについて,もう少し詳しく見ていきましょう。パイプラインを複数並べて命令が同時に実行出来るということは,どのめいれいが同時に実行出来るかを判断し,必要に応じて命令の並べ替えを行うことが必要になります。前述のように,スーパースカラプロセッサというのは,これが最重要技術です。

 命令の順番を入れ替えて良い場合は,同時実行を行うことの出来るような組み合わせを作る事が出来ます。命令を順に実行することをインオーダ,命令の順を入れ替えることをアウトオブオーダといいます。

 しかし,命令が順番通りに実行されないと予期しない結果を招くことがあります。以下にその問題として3つのハザードを示します。

(1)リード・アフター・ライトハザード(RAW)
 読み出して利用したいレジスタの値が,先行の命令によって書かれたものであって欲しい場合に発生する問題です。書くのは先行の命令,読むのは後続の命令です。先行命令が書いた結果を後続命令が読んで利用するというのはよくあることですが,順番が変わってしまうと結果が出る前に読まなくてはいけませんから,これはどうにも回避不可能な問題で,命令の入れ替えは出来ません。

(2)ライト・アフター・ライトハザード(WAW)
 同じレジスタに2回の書き込みがあった場合,2回目の書き込みが残っていないといけないというものです。順番が入れ替わって1回目が後に書かれてしまうと,2回目の結果が上書きされますので,消えてしまいます。

(3)ライト・アフター・リードハザード(WAR)
 読み出して利用したいレジスタの値が,後続の命令によって変更される前のものであって欲しい場合に発生する問題です。書くのは後続の命令,読むのは先行の命令で,RAWハザードとは逆になります。順番が入れ替わると,先行の命令が使う値が後続の命令によって変わってしまう可能性があるわけです。

 このうち,(1)は命令の順番が変わってしまうと回避不可能,(2)と(3)については,レジスタリネーミングを使って回避が可能です。

 そのレジスタリネーミングというのは,レジスタの名前を付け替えることです。実際にはレジスタの数を増やして実現しますが,プログラムを書く人から見てレジスタが増えたわけではないので,リネーミングといいます。

 レジスタリネーミングを使うと,(2)は同じレジスタにせず異なるレジスタに書き込むようにし,命令の順番通りに結果を使うようにすれば回避できます。

 (3)についても同様で,リネームして異なるレジスタを相手にして動いてもらい,最終的に命令の順番通りに読み出せば,結果が出るまでの途中の順番が入れ替わっても問題はありません。

 こうして,レジスタリネーミングを用いれば,(1)のRAWハザードだけを考慮すれば,(2)と(3)は解決出来たことになります。つまり,レジスタを2つ用意して結果をどちらも潰さず残しておき,利用するときに書き込み前の値が欲しければ古い方を,書き込み後の値が欲しければ新しい方を読み出して使うという仕組みです。


 こうして,順番を入れ替えて実行することがある程度出来るようになりました。ここで,命令の実行が完了する時刻に注目すると,命令によって時間のかかるものとかからないものがあるわけですから,当然終わる時刻が同時とは限りません。そこで,命令の処理が開始された状態を発行,処理が終わった状態を完了と決めて,それぞれインオーダとアウトオブオーダと組み合わせます。すると,

 インオーダ発行
 インオーダ完了
 アウトオブオーダ発行
 アウトオブオーダ完了

 の4つの組み合わせが出来ます。


・インオーダ発行

 これはもっとも単純で,命令キューに入っている連続する命令が同時実行可能かどうかを判断するだけです。もし命令に依存性があり,同時実行出来ない場合には,1命令のみを発行します。

・アウトオブオーダ発行

 アウトオブオーダ発行の場合は,命令の順番が入れ替わって発行されるわけですから,命令キューに入っている命令の全てで依存性が調べられます。冷静に考えると,命令キューに入っている命令のオペランドを,互いに使っていないかどうかをざっと調べるだけでよいことになります。もし依存性が全ての命令であった場合は1命令のみを発行します。

・アウトオブオーダ完了

 スーパースカラプロセッサとしては最も完璧なものになりますが,命令を完了する順番さえも入れ替わっていてよい,ということですので,もうなんでもありです。しかし,命令の完了順番が違ってくると,ライト・アフター・ライトハザードが発生してしまいます。

 これはレジスタリネーミングで回避できるとしても,実は例外や割り込みのを考えるた場合,順番が入れ替わってしまうと優先順位が変わってしまうことと同じになり,大変まずいですから,実はこのアウトオブオーダ完了という仕組みは一般的には使用されません。

・インオーダ完了

 これは結果の出る順番を入れ替えないわけですから,早く終わった命令が遅い命令を待ってあげればいいだけのことです。先に出た結果をROB(ReOrder Buffer)と呼ばれるバッファに取り込んでおき,結果の順番を守るわけです。これだと,アウトオブオーダ完了で問題となった例外や割り込みの問題は発生しません。

 ということで,スーパースカラプロセッサには,現実的には,インオーダ発行でインオーダ完了のインオーダ型と,アウトオブオーダ発行でインオーダ完了のアウトオブオーダ型の2種類しかない,ということになります。


 スーパースカラプロセッサの場合,シングルパイプラインのプロセッサに比べて,時間的な前後関係が問題になることがわかります。従って,単にパイプラインを乱さないようにしていれば良かった話が,依存関係を崩さないという絶対に守らなければならないことを考慮しなくてはならず,大変難しくなります。

 例えば,遅延分岐で済ませていた分岐のペナルティも,スーパースカラでは分岐予測と投機実行を組み合わせるのが普通です。

 分岐予測には3つの種類があり,分岐しないと決め打ちする単純予測,プログラムの走っている向きに逆行する場合はループの終端だから分岐すると決め打ちし,順行する場合は分岐しないと決め打ちする静的な分岐予測,分岐回数と分岐先の履歴から次の分岐を予測する動的な分岐予測があり,後者の方がヒット率が高いと言われています。動的な分岐予測には様々な方法があり,現在では90%を越えるようなヒット率を実現している例もあります。

 投機実行は,その分岐予測の結果が出る前に命令をとりあえず実行してしまうのですが,当然外れることもあるわけで,その場合はやり直しになります。しかし,どうせ分岐先が決まるまで待ち時間が出てしまうわけですから,その間にとりあえず命令を実行しても,無駄にはなっていません。

 スーパースカラプロセッサは,確かに複雑さと性能向上のバランスが限界に達して,これ以上大きな進歩はないと思いますが,なにも闇雲にパイプラインの数を増やすことをしなくても,時間のかかる浮動小数点演算と整数演算を並列に同時実行するだけでもそのメリットは大変に大きく,コンパイラによる命令の並べ替えと併用し,今後のプロセッサに必須な技術になっていくと思います。

コンピュータ基礎の基礎~仮想記憶

  • 2010/07/30 14:19
  • カテゴリー:備忘録

 3日目の今日は,仮想記憶です。

 まだメインメモリが高価だった頃,プログラムを分割してハードディスクに置いておき,実際に動かすプログラムだけメモリに読み込むようにして,少ないメモリでも大きなプログラムを動かす工夫をしていました。

 キャッシュと同じで,プログラムには局所性がありますから,実際に動いていないプログラムを置いておくために高価なメモリを用意するのは不経済ですから,これを自動的に行ってくれる仕組みを考えました。

 これが仮想記憶です。

 仮想記憶を使うと,実際に用意されているメモリは小さくても,使っていないメモリのデータはハードディスクに待避しておき,必要に応じてハードディスクから読み出してメモリの中身を自動的に入れ替えてくれます。プログラムを書く人はメモリのサイズを気にしなくてもよくなります。

 必要なのは,ハードディスクから読み出したメモリのデータが持つアドレスに,実際に存在しているメモリのアドレスを変換してあげる仕組みです。

 マルチタスクの場合にはこの機能はとても重要で,複数のプログラムを実行させるとき,同じアドレスには同時にプログラムを置くことが出来ませんから,ずらさないといけなくなりますけども,それをプログラムを書く人がいちいち考えていたらきりがありません。

 そこで,アドレスは常にゼロから始まるものと考えてプログラムを作り,実体の存在するアドレスに変換する仕組みを使って,CPUに実行をさせるようにします。それぞれのタスクは,自分が使っているメモリを他のプログラムが使うとは思っていませんから,他のプログラムが存在する実アドレスをアクセス出来ないように,メモリの保護を行うことも必要です。

 実際に存在するメモリのアドレスを物理アドレス,CPUから見えているアドレスを仮想アドレスといいます。CPUから見えているアドレス,つまりプログラムを書く人にとっての先頭アドレスは常にゼロです。

 しかし,実際にプログラムが置かれているアドレスはゼロではなく,別のどこかです。毎回その場所は変わるだろうし,もしかしたらメモリにさえ存在せずハードディスクに追い出されているかも知れません。

 この仕組みは,普段我々はほとんど意識しませんが,少ないメモリを有効に利用するため,またマルチタスクを利用するためには必須であり,非常に大切な仕組みなのです。

----

問題:コンピュータの仮想記憶における次の説明のうち,最も不適切なものを選べ。

(1)仮想記憶方式とは,実アドレス空間よりも大きな仮想アドレス空間を作る方法である。

(2)仮想記憶方式を用いると,実装されている実記憶容量を気にせずに大きなプログラムを処理させることが出来る。

(3)仮想記憶方式を使えば,メインメモリの容量を小さくしてもCPUの性能の低下を防ぐ事が出来る。

(4)仮想記憶のページングアルゴリズムであるLRU方式は,プログラムの局所性が高いときはページイン,ページアウトを減らすことが出来る。

(5)マルチタスクのOSでは,通常,仮想空間を複数持った多重仮想アドレス空間方式を実装している。

----

回答:

(1)はその通りで,実アドレスよりも大きな仮想アドレス空間を作ることが可能な技術。よって正しい。

(2)は実際に搭載されている実メモリよりも大きなアドレス空間をプログラムに使うことができるので,容量という点では気にしないでよい。よって正しい。

(3)メインメモリの容量を小さくすることで,OSはハードディスクとのページの入れ替えを頻繁に行う必要が生じ,大きく処理速度の低下を招いてしまう。よって正しくない。

(4)LRU方式はアクセスの履歴を用いて,頻度の少ないものからページアウトさせる方式なので,プログラムの局所性が高い場合にはアクセス頻度も上がるため,ページイン,ページアウトを減らすことが出来る。よって正しい。

(5)マルチタスクOSでは,それぞれのタスクが固有の仮想アドレスで動作している。これを多重仮想アドレス空間方式という。よって正しい。

 ゆえに,正解は(3)となる。

----

 さて,仮想記憶を実現するには,ハードディスクとメモリとの入れ替えを行う最小単位を決めて,これで入れ替えていく必要があります。プログラムやデータには局所性がありますので,あまり小さくしても意味がありませんし入れ替えばかりが発生してしまいますし,大きすぎると入れ替えは発生しにくくなりますが,そもそも入れ替えにくくなってしまいますので,仮想記憶のうまみが生かせません。

 また,入れ替える単位は機能や制限で分類を作らず,すべてが同一のものであると自由度が高いです。そこで現在は数kbyte単位で物理メモリを分割してこれをページと名付け,ページ単位でハードディスクとの入れ替えを行うような仕組みが主流となっています。この方式を,ページング方式といいます。

 現在主流のx86でもページング方式の仮想記憶がサポートされていますが,ページの大きさは4kByteです。4kbyteということは12ビットですので,全部で32ビットあるアドレスのうち下位の12ビットはページ内のアドレスを示し,上位の20ビットはページの通し番号を示すことになります。20ビットで表現出来るページ数は1Mページですので,1ページあたり4kByteということは,トータルで4Gbyteですね。まあ,32ビットのアドレスなのですから,当たり前のことです。

 ところで,仮想記憶というのは,ちょっと見方を変えるとキャッシュメモリとそっくりです。キャッシュメモリとメインメモリの関係は,そのままメインメモリとハードディスクの関係に相当します。

 先に言葉の話になりますが,キャッシュのラインに取り込まれるデータをブロックといいました。ページング方式の仮想記憶ではこれはページに相当します。キャッシュメモリに一度に取り込むデータの大きさをブロックサイズといいますが,仮想記憶ではこれをページサイズといいます。

 また,キャッシュにデータが入っていないことをミスといいましたが,仮想記憶ではこれをページフォールトといいます。そして,キャッシュにおけるタグは,仮想記憶では仮想ページ番号というのです。

 ということは,仮想アドレスを物理アドレスに変換する仕組みは,キャッシュメモリのそれとほとんど同じになるということです。

 では,具体的な仕組みを見ていきましょう。

 まず最初は,ページテーブルという仕組みです。

 x86を例に取ると,仮想アドレスの上位の20ビットはページ番号といいます。また,下位12ビットはページ内のアドレスで,これをページ内オフセットといいます。

 キャッシュメモリと同じように参照するアドレスのページを総当たりで比較してもいいのですが,現実的にページ数は100万個を超えますので,これを全て比較していては大変です。だからといってダイレクトマップや2ウェイセットアソシアティブなどでは有限の物理メモリを生かし切れないばかりか,ハードディスクとのスワップが多発して現実的な速度で動いてくれません。

 そこで,仕組みとしてはキャッシュにおけるフルアソシアティブ方式と同じにして,どの物理アドレスにも仮想アドレスを割り当てられるようにした上で,比較を行わずに済むようアドレスの変換表を作って,これを参照するようにします。また,メモリの内容が書き換わった場合に,いちいちハードディスクの内容を更新していては時間がかかって仕方がありませんので,キャッシュにおけるライトバック方式を用いて,メモリからハードディスクに追い出されるときに内容を更新します。

 この変換表と,ページ変換表,あるいはページ変換テーブルといいます。

 ページ変換テーブルは,ページ番号の順番にずらーっと列んでいて,そのページ番号が今どの物理アドレスに格納されているかを記録してあります。そして仮想アドレスの上位20ビットをインデックスとしてこの表を参照し,書かれている値を読み出します。これが物理アドレスになるわけです。

 この時読み出される項目をページ変換テーブルエントリ,略してPTEといいます。

 ただし,重要な事があります。仮想アドレスは,基本的にタスクごとに固有の値を持っています。先程書いたように,ソフト屋さんは自分のプログラムは全部ゼロ番地から書かれていると考えているわけで,3つタスクが走っていたら,それぞれのタスクは固有の仮想アドレス空間で動作しています。

 ということは,3つのタスクで同じ仮想アドレスを持つことはごく当たり前のことです。3つのタスクが同じ仮想アドレスをもち,その仮想アドレスでページ変換テーブルを参照しても,同じ物理アドレスしか手に入りません。これでは何のために変換しているのか分かりません。

 そこで,タスクごとにページ変換テーブルのベースアドレス(ページ変換テーブルの物理アドレスの先頭です)を変えてやります。タスク1のベースアドレスは0x4000から,タスク2が0x10000となっていると,それぞれここをゼロページ目にして,仮想アドレスの上位20ビットが示すページ番号を参照していくのです。

 さて,PTEはそれぞれに対応する物理アドレスが書かれているわけですから,1つあたり32ビットの大きさが必要になりますね。実際は下位12ビットのオフセットは仮想アドレスと物理アドレスで共通ですから記録する必要はないのですが,キャッシュのタグと同じで他の情報も書いておきたいので,やはり32ビットくらいは必要になります。

 思い出して頂きたいのですが,ページの数は100万個を超えますので,ページ変換テーブルだけで4MByte,下手をすると8Myteにもなってしまいます。従ってCPUに持たせるわけにはいかず,メインメモリに置かれることになります。

 CPUには,メインメモリのどこにページ変換テーブルが置かれているかを書いておくレジスタが用意されているので,任意のアドレスに置くことが可能です。

 さて,先程ページ変換テーブルが少なくとも4MByteにもなってしまうと書きました。今は数GByteのメインメモリを搭載できるのですが,それでもただのテーブルに4MByteというのはもったいないですし,組み込み用途などで少ないメモリしか搭載しない場合,物理メモリの大半をページ変換テーブルが占めるというバカバカしいことが起こってしまいかねません。

 そこで,こんな対策をします。

 まず,100万個を越えるPTEですが,その全てが公平に参照されるわけではなく,しょっちゅう参照されるところとほとんど参照されない部分が出てきます。例えば,1つのタスクに注目すると,そのタスクはまさか32ビットのアドレス空間を全部使っているわけではなく,そのうちのごく一部を使っているに過ぎません。

 ですから,仮想アドレスから物理アドレスへの変換を行うときでも,ある限られた仮想アドレスの範囲だけが参照されるはずです。

 こうして,よく参照されるものをメインメモリに残し,あまり参照されないものをハードディスクに逃がしてやります。

 例えば,20ビットあったページ番号を,上位の12ビットと下位の8ビットに分けます。まず上位12ビットをインデックスとして1つ目の変換テーブルを参照し,2つ目のテーブルを参照するために,2つ目のテーブルのベースアドレスを手に入れます。

 このベースアドレスと,先程の下位8ビットを合計して,2つ目の変換テーブルを参照して,ページ番号を手に入れます。

 ここで,1つ目のテーブルは12ビットですので4096個のエントリがあります。2つ目のテーブルは8ビットですので256個のエントリがあります。ということは,2つ目のテーブルは1枚ごとに256ページの物理ページ番号が書かれていて,その表は全部で4096枚存在しているわけです。


 そして,1つ目のテーブルは必ずメインメモリに残しておき,2つ目のテーブルは使っているテーブルだけメインメモリに残します。面倒なのでどの表もエントリの大きさは32ビットとしますと,1つ目のテーブルは16kByte,2つ目のテーブルは1枚あたり1kByteということになり,同時にメインメモリに置かれるテーブルはわずか17kByteと大幅に小さくなります。

 こうして,ページ変換テーブルを複数階層に分割する仕組みを,マルチレベルページングと言います。もちろんメインメモリが許せば,2つ目のテーブルも1つだけにせず,よく使うものを複数メインメモリに置けば高速に処理が出来ますし,最近の64ビットアドレスを持つCPUでは2階層でも膨大な数になりますから,3階層や4階層に分けることをします。


 ところが,ページ変換テーブルはメインメモリに置かれます。仮想アドレスを使って実行しているプログラムが,物理アドレスのどこにあるのかを知るのにいちいちメインメモリをアクセスするのでは,速度がなかなか上がりません。そこでCPU内部に,ページ変換テーブルのうち,よく使うものをコピーしておくメモリを少しだけ確保しておくことで,ここに残っているエントリであれば高速にアドレス変換を行う事が出来るようにしました。

 この,ページ変換テーブルの一部をコピーするCPU内蔵の小さなメモリを,TLBといいます。TLBはTranslation Look-aside Bufferの略で,ページ変換テーブルを横目でちらちら見ながら(look-aside)作ったバッファという意味です。

 ここでお気づきの方もいると思いますが,実はこのTLBは,キャッシュメモリそのものです。CPUはアドレスを参照するのに,まずTLBを見に行きます。TLBにエントリがあれば,そこから参照した物理アドレスを参照します。もしエントリがなければ,メインメモリにあるページ変換テーブルを参照し,TLBに登録するわけです。

 TLBは一種のキャッシュですので,その読み出しの方法は,キャッシュと全く同じで,フルアソシアティブ方式,ダイレクトマップ方式,そしてnウェイセットアソシアティブ方式の3つがあり,その仕組みも同一です。

 そして,TLBの入れ替えについても同じで,LRU方式,ランダム方式があります。どういうわけか,ラウンドロビン方式については用いられていないようです。

 さて,ちょっと思い出してもらいたいのですが,仮想アドレスはタスクごとに固有でした。ところがTLBはタスクの固有情報であるページ変換テーブルのベースアドレスを持っていませんから,タスクが変わるとその内容も入れ替える必要が出てきます。

 理想的には,TLBもタスクごとに別々に用意して,タスクが切り替わるごとにTLBも切り替えられればいいのですが,高価な高速メモリですからそんなに用意できませんし,そもそもタスクの数がいくつになるかわからないので,現実的には不可能です。

 そこで,多くのCPUはタスクの切り替えが起こると,TLBの中身をクリアしてしまいます。しかしこれでは,せっかくのTLBがしょっちゅう無効になり,あまり効果が期待できません。CPUによっては,TLBにタスクの識別番号を一緒に入れておくことで,TLBのクリアを行わないようにしているものもあります。

 TLBを命令用とデータ用に分ける例もあります。CPUにとって命令だろうがデータだろうが,メモリへのアクセスが発生することは同じです。命令の実行にはデータへのアクセスが必要な場合が多いことを考えると,実は命令とデータでアドレスの変換が同時に発生することが考えられます。

 しかし,TLBは1つしかありませんから,どちらかを待たせて順番に処理する事になりますが,こうするとパイプラインが乱れてしまい,速度の低下が起きます。

 そういうことなら命令とデータで別にTLBを持てば同時の変換ができますから,パイプラインは乱れません。キャッシュをメモリを命令とデータに分けるハーバードアーキテクチャというのがありますが,いわばこれのTLB版ということでしょう。

 ところが,データは別にして,命令は順番に処理されますから極めて局所的で,それで大きなTLBを持つ事はもったいないという考え方もあります。そこで命令用のTLBについては4エントリ程度の超小型サイズTLBを持たせることがあります。これをマイクロTLBと呼んでいます。

 本来のTLBはデータと命令を共通に持つごく普通のものですが,これをキャッシュする形でマイクロTLBを命令用に持ちます。こうすると命令とデータで2つTLBを持つのに比べて,TLBの更新のための回路が1つで済み,かつマイクロTLBだけで済んでしまう場合には消費電力も小さくすることが出来ます。なかなか合理的な方法ですね。

 次にページフォールトについてです。

 仮想アドレスを物理アドレスに変換した結果,そのページがメインメモリに存在せず,ハードディスクに追いやられていた場合に発生するのが,ページフォールトです。ページフォールトが起きると,メインメモリのどこかのページをハードディスクに追い出して,必要なページを取り込んできます。ハードディスクに追い出すことをページアウト,ハードディスクから取り込むことをページインといい,両方を総称してページスワップといいます。

 ページフォールトをもう少し具体的に見てみます。TLB,そしてページ変換テーブルを参照し,仮想アドレスを物理アドレスに変換し,結果その物理ページがハードディスクに追い出されていることがわかると,例外が発生し,OSがその事実を知ることになります。

 OSはページフォールトの発生を知り,ハードディスクとメインメモリのページを入れ替えます。あくまでこれはOSの仕事です。なかには,TLBに仮想アドレスが入っていないとすぐに例外をだして,TLBの更新さえOSに任せようとするCPUもあります。どこまでハードでやるのかソフトでやるのかは,その設計思想によるところも大きいわけです。

 さて,OSはページアウトとページインを行わなければなりませんが,どのページを捨てるのかは,キャッシュの時と同じく重要な問題です。よく使うページを捨ててしまってはスワップが頻発するでしょうし,かといって真面目に統計を取るような事をしていたら,その処理が重くて大変です。なにせメモリ空間はキャッシュに比べて広大です。

 そこで,ページ変換テーブルのエントリ(PTE)に,少し情報を持たせておきます。PTEに必要な情報は,言うまでもなくそのページが存在する物理アドレスですが,これにアクセスがあったことを示すフラグ,ライトがあったことを示すフラグ,メモリに存在することを示すフラグ,そしてそのページへのアクセス制限を示すフラグなどです。

 このうち,アクセスがあったことを示すフラグを,OSは定期的にチェックしてゼロにし,TLBのエントリを無効化しておきます(なぜ無効化するかというと,TLBにエントリがあったらPTEまでアクセスが及ばないからです)。そして,アクセスがあると1を書き込むのです。このフラグがOSによってチェックされたときに1になっている場合の数を数えておくと,数が多いほどその仮想アドレスへのアクセスが発生している頻度が高いとわかります。

 こうすると,擬似的にではありますが,LRU方式がかのうになり,頻度の高いページを捨てることが避けられます。

 もっとも,これはOSの仕事です。OSによっては,ランダムに捨てるものもあるでしょうし,ラウンドロビンで捨てるものもあると思いますが,これはもうプロセッサと言うよりOSの問題です。

 キャッシュと同じという事は,書き戻しの仕組みも似たような考え方をするということです。メインメモリから捨てられてハードディスクに追いやられるページがあったとして,このページの内容が書き換わっていないなら,すでにメインメモリとハードディスクで内容が一致しているわけですから,ハードディスクに書き戻す必要などありません。

 ということは先程のPTEのフラグに,メインメモリが書き換えられてハードディスクと不一致が起こっていることを示すものを用意しておけば,必要なものだけハードディスクに書き戻してやればよいことになります。これはつまり,キャッシュにおけるライトバックと同じ事です。

 もう1つ,PTEのフラグには,アクセス制限を行うものを用意してありました。CPUには実行レベルという考え方で,命令の実行やレジスタへのアクセスに制限を設けてあります。全てのリソースにアクセスせねばならないOSは最も上位のレベルでなければなりませんが,ユーザーアプリケーションなどは最低のレベルで動作させ,システム全体の信頼性を低下させるようなアクセスがあったら,例外を発生させてシステムダウンを防ぎます。

 このレベルに準じて,アクセス可能なページかどうかをフラグにしてあれば,実行モードによってアクセス出来るアドレスと出来ないアドレスを自動的に制御できることになります。これがメモリ保護という仕組みです。

 例えばx86のPTEでは,U/SというビットとR/Wというビットが存在します。U/Sがセットされている仮想ページには,ユーザーモード(レベル3)ではアクセスが出来ませんし,R/Wがセットされている仮想ページには,ユーザーモード(レベル3)に書き込むことが出来ません。


 さて,キャッシュと同じという割には,随分と長い話になってしまったのですが,パイプラインとキャッシュ,そしてメモリ管理の3つはコンピュータ技術の中でも特に基礎的な事項であり,普段意識しないように作られているが故に知らなくても構わない上,それなりにややこしい話なので,頑張って勉強しようという人は以前よりも少なくなっているように思います。

 Z80にCP/Mだったころは,こうした技術は大型の汎用機かスーパーミニコンという,雲の上のシステムで使われていた最先端技術だったわけで,コンピュータが好きでたまらない人はこうした最先端技術を強い憧れを動機とし,競って勉強したものと思います。

 しかし,今や数万円のネットブックにも,この3つの技術は当たり前のように使われていて,すでに珍しい物でも憧れの対象でもなくなりました。

 それでも,コンピュータは生まれ落ちたその時から,ひたすら高速であることを目指して突き進んでおり,その唯一とも言える目標のために,あらゆる工夫が試されてきました。

 ある工夫が新しい問題を引き起こし,それがまた別の工夫で回避される,そうした工夫の連鎖が,1つの歴史として積み重なっていることが,コンピュータ工学の醍醐味ではないかと私は思います。

 それは,こんな基礎的な事項にも,たくさん含まれているのです。

 最後に,ちょっと面白そうな問題をもう1つ。

----

問題:仮想記憶のOSで,あるプロセスが参照しているページ番号の順序が,

3,5,2,0,2,5,4,3,0,3,5

 であるとする。実ページの数を4とするとき,ページ置き換えのアルゴリズムにLRUアルゴリズムを用いたとき,ページフォールトの回数はいくつか。なお,ページ割り当ての初期状態として,すべてのページは未割り当てとする。

回答:

 ページ参照の順に,実メモリの様子を見ていく。

3 3,X,X,X ページフォールト1回目
5 3,5,X,X ページフォールト2回目
2 3,5,2,X ページフォールト3回目
0 3,5,2,0 ページフォールト4回目

2 3,5,2,0 ページフォールトなし
5 3,5,2,0 ページフォールトなし
4 4,5,2,0 ページフォールト5回目
3 4,5,2,3 ページフォールト6回目
0 4,5,0,3 ページフォールト7回目
3 4,5,0,3 ページフォールトなし
5 4,5,0,3 ページフォールトなし

 よって,ページフォールトの回数は7回。

---

 ここで,もし実ページが1つ増えて,5になったらどうなるでしょうか。

3 3,X,X,X,X ページフォールト1回目
5 3,5,X,X,X ページフォールト2回目
2 3,5,2,X,X ページフォールト3回目
0 3,5,2,0,X ページフォールト4回目
2 3,5,2,0,X ページフォールトなし
5 3,5,2,0,X ページフォールトなし
4 3,5,2,0,4 ページフォールト5回目
3 3,5,2,0,4 ページフォールトなし
0 3,5,2,0,4 ページフォールトなし
3 3,5,2,0,4 ページフォールトなし
5 3,5,2,0,4 ページフォールトなし

 実ページが5になったということは,実は全てのページが収まってしまうので,ページアウトは発生しません。ということで,5回のページフォールト,つまり5ページ全てが割り当てられるまでのページフォールトで済みます。

 逆に,実ページが1つ減って,3になってしまったらどうなるでしょう。

3 3,X,X ページフォールト1回目
5 3,5,X ページフォールト2回目
2 3,5,2 ページフォールト3回目

0 0,5,2 ページフォールト4回目
2 0,5,2 ページフォールトなし
5 0,5,2 ページフォールトなし
4 4,5,2 ページフォールト5回目
3 4,5,3 ページフォールト6回目
0 4,0,3 ページフォールト7回目
3 4,0,3 ページフォールトなし
5 5,0,3 ページフォールト8回目

 1回増えただけですね。結構激しく入れ替えがあったように思いますが,この程度のならそんなに差がなさそうだという気もします。とはいえ,実メモリが5の時に比べて,ページフォールトの起きている回数は1.6倍になっていますから,ハードディスクへのアクセスの遅さを考えると,数倍の速度低下になっていることは間違いないでしょう。

 WindowsでもMacでもそうですが,メモリをたくさん積むと快適になるというのは,このあたりの話からも容易に想像出来ます。

コンピュータ基礎の基礎~キャッシュメモリ

  • 2010/07/29 13:49
  • カテゴリー:備忘録

 コンピュータ基礎の基礎,第2回目はキャッシュメモリです。

 CPUの速度はドンドン速くなっているのに,メモリの速度は絶望的に速くなっていません。

 もちろんDRAMだってSDRからDDR,DDR2,DDR3と世代を経るごとに速度は上がっていますが,実はDRAMというのはコンデンサを使って電気をためることで記憶する仕組み自身に速度的な限界があって,DDRだのDDR2だのという速度向上の工夫は,そのアクセスの方法に工夫を行って高速化を試みたものに過ぎません。

 だから,高速化されたとはいえ,例えば連続でアクセスした時だけとか,そういう特定の条件の時だけ速度がアップするようになっているので,悪い条件でアクセスすると,昔のDRAMに比べて劇的に高速化されるというわけではありません。

 そんなですから,数GHzという超高速で動作するCPUの足を引っ張っているのがメモリということになります。もっとも,こういう状況はコンピュータが生まれてからずっと続いている問題ですので,なんとかこれを工夫して,遅いメモリに足を引っ張られないようにCPUを動かす方法が昔から考えられてきました。

 それがキャッシュメモリです。

 プログラムやデータには時間的あるいは空間的な局所性があり,ある命令の次に実行される命令は,その近所にあるという性質があります。また一度読み出したプログラムやデータは,もう一度使われることもあるし,その前後にあるものが使われることも多いことが経験的にわかっています。

 そこで,一度メインメモリから読み出したデータを,メインメモリよりもずっと高速なメモリに蓄えておき,以後はこれを使うようにすると遅いメモリにいちいち取りに行くことがなくなります。

 ただし,高速なメモリというのはとても高価ですから,たくさん用意することができません。そこで,出来るだけ少ない容量で性能改善が行われるように,様々な方式が考えられてきました。

 また,アドレス1つに対してキャッシュに蓄えられるデータの大きさは1ワードとは限らず,最近は4ワードや8ワードを蓄えるものも多くなってきました。

 キャッシュの大きさは有限ですから,1アドレスごとにたくさんのデータを蓄えておけば,アドレス情報が少なくて済むので有効利用が出来そうですが,なにせ格納できるアドレス情報が少ないですから,プログラムがあちこちをアクセスするようになると,キャッシュにちっともヒットしなくなります。

 かといって,1ワードごとにアドレスを割り振っていたら,アドレス情報の格納のためにメモリが使われてしまうので,無駄遣いになります。このあたりはそのCPUやどんなプログラムを走らせるのかによって最適解が変わってきますので,良く検討されなければなりません。

 ところで,メインメモリの遅さというのは,なにも読み出しの時だけではありません。結果を書き込む際にも遅いわけですが,これもキャッシュメモリに一時的に蓄えておけば,CPUは書き戻しを待たずに次の処理にとりかかれます。つまり,キャッシュメモリというのは,読み出しと書き戻しの2つの動きがあるということです。

----

問題:ダイレクトマップ方式のキャッシュにおいて,アドレスA,Bは同一のキャッシュブロックアドレスに割り当てられているため,アクセス時にコンフリクトミスを生じる。このキャッシュに接続されたプロセッサが,次に示す順にアクセスを行った。

a)アドレスAから読み出し
b)アドレスBに書き込み
c)アドレスBから読み出し
d)アドレスAに書き込み
e)アドレスBに書き込み

 ライトスルーキャッシュは,書き込み時にキャッシュと同時に主記憶を書き換える方式であり,この中で,書き込みミス時に直接主記憶のみを更新する方式をNo-write allocate(direct write)方式のライトスルーキャッシュと呼ぶ。

 一方,ライトバックキャッシュは書き込みの度に主記憶を更新せず,書き戻しの際にまとめて更新する方式である。

 今,この2つの方式について,上のa)からe)までのアクセスを順に行った際ヒットするかどうかを示した組み合わせの中で正しいものを選べ。ただし,Hがヒット,Mがミスヒットを示す。

1.
ライトスルー MMHMH
ライトバック MMHHH

2.
ライトスルー MMMMH
ライトバック MMHMM

3.
ライトスルー HHMHM
ライトバック HMHMM

4.
ライトスルー HMMMH
ライトバック HHMMH

5.
ライトスルー MMMMM
ライトバック MMHMH

----

回答:

 ダイレクトマップ方式のキャッシュメモリということなので,問題にあるようにアドレスAとアドレスBの内容は同時にキャッシュメモリ内には存在できない。

 また,No-write allocateのライトスルー方式というのは,書き込み時のアドレスがキャッシュに存在した場合(ヒットした場合)はキャッシュとメインメモリの両方を書き換え,キャッシュに存在しない場合(ミスの場合)には,メインメモリだけを更新し,このアドレスをキャッシュには取り込まないものである。

 一方のライトバック方式というのは,書き込み時のアドレスがキャッシュに存在した場合(ヒットした場合)には,キャッシュのみを書き換え,メインメモリには書き込まない。キャッシュに存在しない場合(ミスの場合)には,キャッシュメモリにそのデータを読み込んだ後,キャッシュメモリを書き換える。メインメモリへの書き込みは,キャッシュを追い出されてしまった時に行われる。

 まず,ライトスルーを検証する。

a)ではアドレスAのデータがキャッシュに存在せず,ミス。ここでキャッシュにはアドレスAのデータが入る。

b)ではアドレスBへの書き込みが発生するが,キャッシュに存在するのはアドレスAのデータなので,ミス。アドレスBのデータはメインメモリに書き込まれ,キャッシュはそのまま。

c)ではアドレスBからの読み出しをするが,キャッシュにはアドレスAのデータが入っているため,ミス。ここでキャッシュはアドレスBのデータを格納する。

d)ではアドレスAへの書き込みが発生するが,キャッシュに存在するのはアドレスBのデータなので,ミス。アドレスAのデータはメインメモリに書き込まれ,キャッシュはそのまま。

e)ではアドレスBに書き込みが発生するが,キャッシュにはアドレスBのデータが存在するため,ヒット。キャッシュメモリとメインメモリの両方にアドレスBのデータが書き込まれる。

 次に,ライトバックを検証する。

a)ではアドレスAのデータがキャッシュに存在せず,ミス。ここでキャッシュにはアドレスAのデータが入る。

b)では,アドレスBに書き込みが発生するが,キャッシュに存在するのはアドレスAのデータなので,ミス。アドレスBのデータはキャッシュに書き込まれ,メインメモリには追い出されたアドレスAに書き込みが発生する。

c)ではアドレスBからの読み出しをするが,キャッシュに存在するのはアドレスBのデータなので,ヒット。

d)ではアドレスAに書き込みが発生するが,キャッシュに存在するのはアドレスBのデータなので,ミス。アドレスAのデータはキャッシュに書き込まれ,メインメモリには追い出されたアドレスBに書き込みが発生する。

e)ではアドレスBに書き込みが発生するが,キャッシュに存在するのはアドレスAのデータなので,ミス。アドレスBのデータはキャッシュに書き込まれ,メインメモリには追い出されたアドレスAに書き込みが発生する。

 よって,ライトスルーはMMMMH,ライトバックはMMHMMとなり,正解は2.となる。

----

 さて,前述のようにキャッシュメモリにはメインメモリからの読み出しと,メインメモリへの書き戻しの2つ,キャッシュの中身の入れ替えを加えた3つの作業が発生しますが,それぞれの方法によって,いくつかの分類がなされています。

 まず,読み出しの方法による分類です。

・フルアソシアティブ方式

 各ラインにデータを格納する部分と,そのデータの存在するアドレス情報を格納するタグと呼ばれる部分を持ち,CPUが要求したアドレスとタグに書かれたアドレスの一致を確認する方式。
 キャッシュメモリの全ての部分にどのアドレスのデータも格納できるために効率が良く,ヒット率も高いが,総当たりをしなければならないので回路規模も大きくなり,速度も厳しくなる。

・ダイレクトマップ方式

 各ラインにデータの存在するアドレス情報をタグとして持つことは同じであるが,アドレスの中位ビットによって示されるインデックスによってラインが1つに決定される方式。回路規模も小さく,高速動作が可能だが,インデックスが同一でもアドレスが異なる場合はミスヒットとなり,データの入れ替えが頻繁に発生して大幅に速度が低下するという欠点がある。

・nウェイセットアソシアティブ方式

 フルアソシアティブ方式とダイレクトマップ方式の欠点を補う方式で,ダイレクトマップ式をn個並列に並べたもの。ダイレクトマップ式ではインデックスが同じものは1つしかキャッシュされなかったが,この方式ではn個がキャッシュされる。nは2や4が多いが,例えば各ウェイのラインが1つで,nがライン総数に等しい場合はフルアソシアティブ方式と同じ意味となる。


 とまあ,言葉で書いてもなかなかわかりにくいので,例を挙げてみましょう。アドレスが32ビット,1ワード32ビットのプロセッサを例に取ります。キャッシュの容量は256バイトとし,キャッシュの1ラインあたり1ワードすなわち4バイトを格納するものとして,3つの方式を書き表してみます。

(1)フルアソシアティブ方式の場合
キャッシュラインの構成 タグ部30ビット+データ部4バイト(32ビット)
ラインの本数 256 / 4 = 64本
アドレスの使い道 上位30ビットがタグの30ビットと比較される
         残った2ビットは各ラインに入っているバイトを示す

(2)ダイレクトマップ方式の場合
キャッシュラインの構成 タグ部24ビット+データ部4バイト(32ビット)
ラインの本数 256 / 4 = 64本(ということはインデックスは6ビット必要)
アドレスの使い道 上位24ビットをタグの24ビットと比較
         続く6ビットがどのラインに入っているかを示す
         残った2ビットは各ラインに入っているバイトを示す

(3)2ウェイセットアソシアティブ方式
キャッシュラインの構成 タグ部24ビット+データ部4バイト(32ビット)
ラインの本数 256 / 4 / 2 = 32本が2つ並列に存在,合計64本
アドレスの使い道 上位24ビットをタグの24ビットと比較
         続く1ビットがウェイの選択
         さらに続く5ビットがラインを示す(インデックス)
         残った2ビットは各ラインに入っているバイトを示す

(4)4ウェイセットアソシアティブ方式
キャッシュラインの構成 タグ部24ビット+データ部4バイト(32ビット)
ラインの本数 256 / 4 / 4 = 16本が4つ並列に存在,合計64本
アドレスの使い道 上位24ビットをタグの24ビットと比較
         続く2ビットがウェイの選択
         さらに続く4ビットがラインを示す(インデックス)
         残った2ビットは各ラインに入っているバイトを示す

 こうして具体例を並べてみると,言葉で書いてみるとややこしい話でも,32ビットあるアドレスの各ビットにどんな役割を与えるかという話だけになります。

 フルアソシアティブ方式だと,64本のキャッシュラインにどんなアドレスでも入る代わりに,比較は30ビット行う必要があります。それに,キャッシュの入れ替えを行う対象がキャッシュ全域に及ぶため,その判定に時間がかかります。

 これがダイレクトマップ式だとアドレスの比較は24ビットで済みますし,キャッシュの入れ替えは機械的に判断されますから楽ですが,アドレスの6ビットで入るキャッシュラインが決まっています。言ってみれば6ビットの比較があらかじめ済んでいる,ということでしょうか。

 4ウェイアソシアティブ方式では,ダイレクトマップ式においてキャッシュラインを決めていた6ビットのうち2ビットをウェイの切り替えに使っているので,インデックスは4ビットとなり,16本のラインが決まってしまいます。しかし4ウェイですので,同じインデックスでも4つまで格納できるというわけです。


 続いて,書き戻し方式による分類です。

・ライトスルー方式

 CPUからデータの書き出しを行う際に,キャッシュメモリと同時にメインメモリも逐一書き直す方式。通常はキャッシュにデータが存在しない場合にはメインメモリのみに書き込みを行うNo-write allocate方式を採用する。キャッシュとメインメモリとの間のデータの不一致が起きない代わりに,CPUからのデータ書き戻しには時間がかかってしまう。

 書き込み時に,そのアドレスのデータがキャッシュに存在した場合はヒットとなり,キャッシュとメインメモリの両方に書き込まれる。そのアドレスのデータがキャッシュに存在しない場合はミスとなり,メインメモリのみに書き込まれる。write allocate方式の場合には,ここでキャッシュにも書き込まれるが,その根拠である書かれたデータは次に読まれるはずというのは案外あてにならず,一般的ではない。

・ライトバック方式

 CPUからデータの書き出しを行う際に,キャッシュメモリだけを書き換える方式。当然キャッシュメモリとメインメモリの不一致が発生するが,不一致であるという事をとりあえず記録しておき,キャッシュの内容が入れ替えのために捨てられるときに,メインメモリにラインごと一括して書き込む。ライトバック方式では,write allicate方式が採用される。

 書き込み時に,そのアドレスのデータがキャッシュに存在した場合はヒットとなり,キャッシュのみに書き込まれ,メインメモリは更新されない。その代わり両者が不一致であることがタグに書き込まれ,このデータがキャッシュから追い出されるタイミングでメインメモリに書き込まれることを示しておく。

 そのアドレスのデータがキャッシュに存在しない場合はミスとなるが,まず最初にキャッシュのリフィル(入れ替え)を行い,そのアドレスの内容をキャッシュに取り込む。続けてキャッシュのデータを新しいデータで上書きし,不一致をタグに記録する。

 メインメモリへの書き込みは,そのアドレスがリフィルによってキャッシュから消されてしまう時で,この結果時間のかかる書き込みの回数が少なくできる。


 どちらが良いかは使い道に寄るところがあって,ライトスルー方式でもライトバッファを入れれば速度的な問題は起きにくい上に,回路も簡単でキャッシュとメモリとの不一致が原理的に起きませんから,小容量のキャッシュならメリットがあります。例えばCPUに内蔵される1次キャッシュに使うとおいしいです。

 これに対してライトバック方式ですが,なんと言ってもメモリへのアクセス回数が減りますから,例えばマルチプロセッサなどバスマスタが複数ある場合にはバスが効率よく使えるので有利です。


 最後に,キャッシュの入れ替えに関する分類です。

・LRU方式

 Least Recently Used方式の略で,最も古くアクセスされたデータを捨てて入れ替える方法。新しいものほど良く使われるだろうという局所性を根拠としている。効率の良い方法ではあるが,アクセスの履歴を取らねばならず,タイミングが厳しい。

・ラウンドロビン方式
 データを履歴によらず,順番に捨てて入れ替える方式。取り込みの古いデータから捨てるという根拠による。回路が簡単というメリットがある一方,使用頻度が考慮されず,ヒット率の高いデータでも捨てられることになってしまうので,効率は悪い。

・ランダム方式
 捨てるデータをランダムに選ぶ方式であるが,これはどのデータも平均的に使われる(使われない)だろうという根拠に基づく。効率はそれほど良くないがなんといっても回路が簡単である。


 注目すべき点は,ダイレクトマップ式の場合には,同じインデックスのデータが来たら無条件にそのラインを捨てて書き換えるので,こうした入れ替えの仕組みを持つ必要がないということです。

 しかし,nウェイセットアソシアティブ方式ではn個あるウェイのうちどちらを捨てるのか決めねばなりませんし,フルアソシアティブ方式に至ってはたくさんあるラインの内どれを捨てるか決めねばなりません。

 当然,良くヒットしているものを捨ててしまっては効率が落ちますから,それなりの理由で捨てるものを選ぶ必要があるわけですが,それが複雑になってしまってはCPUの処理速度全体の足を引っ張ってしまいます。

 一方,ダイレクトマップ式では捨てるデータが決まっていることから一見すると合理的ですが,同じインデックスで異なるアドレスを交互にアクセスするようなケースでは,毎回キャッシュの入れ替えが起こってしまうという最悪の事態が起こります。


 このように,キャッシュメモリというのはなかなか複雑で,データの読み込み方,データの捨て方,データの書き戻し方の3つの分類による組み合わせで,様々なものが考え出されます。データと命令をそれぞれ別のキャッシュ取り込むことや,キャッシュの容量,キャッシュの階層を分けることなど,さらにたくさんのバリエーションが存在するのは,それだけキャッシュメモリにはお金がかかり,メインメモリ全部がCPUと同じ速度で動作するという理想にほど遠いことを示していると言えるかも知れません。

コンピュータ基礎の基礎~パイプライン

  • 2010/07/27 19:47
  • カテゴリー:備忘録

 コンピュータは,これまで様々な工夫で速く動作するように作られてきました。その当時は最先端だったことでも,今は非常に基礎的なものとなっていたりするのですが,何分普段使うものではないので,ついつい忘れてしまいがちです。

 そこで,この場をちょっとした復習に使おうと思います。第1回目はパイプラインです。

問題:あるCPUも命令実行におけるパイプライン処理が,以下の6段のステージをもつとする。

 F:命令読みだし(instruction fetch)
 D:命令解読(instruction decode)
 A:番地計算(address calculation)
 B:オペランド読みだし(operand fetch)
 E:命令実行(instruction execution)
 W:結果格納(write back)

 パイプライン処理を行わない場合,命令実行Eの所要時間は15ns,Eを除く各ステージの所要時間は10nsであるとする。また,パイプライン処理を行う場合は,上記の他に各ステージにおいて2ns必要となる。2nsの打ち合わせは,クロックスキューの調整とパイプライン処理の準備のための時間である。この時,以下の問いに答えよ。

1)パイプライン処理を行わない場合の実行過程(時間を横軸)を3命令分図示せよ。
2)パイプライン処理を行う場合,ステージの所要時間(パイプラインピッチ)はいくらとなるか?
3)パイプライン処理を行う場合の命令実行過程を3命令分図示せよ。
4)パイプライン処理による定常状態における速度向上率を求めよ。
5)命令実行パイプライン処理の流れを阻害する要因(ハザード)について説明せよ。

回答:

1)

 このCPUは6つのステージを持っていますが,Eステージだけは15nsかかり,それ以外は10nsで処理が出来るということです。Eステージというのは実際の命令の処理を行う部分ですから,時間が余計にかかる傾向があります。そこでここをさらに2つに分けるなどして,処理時間を短くするようなことも行われます。

 パイプライン処理を行わない,つまり順番に3命令分処理するという事ですので,以下のように書くことができます。下の数字は時刻です。

 F D A B E W F D A B E W F D A B E W
0 10 20 30 40 55 65 75 85 95 105 120 130 140 150 160 170 185 195
 
 このCPUは,3命令を実行するのに195nsかかるという事になりますね。1命令当たりの65nsかかっています。

2)

 パイプライン処理というのは,各ステージを同時に実行していく方法です。パイプラインというより,ベルトコンベアという感じが正しいと思います。1つの製品を作るのに1時間かかるとしても,1つの行程が10分の流れ作業で作ると,完成品は10分に一度の割合で出てきます。ということは,見た目には1つの製品を10分で作っているように見えるわけです。

 一見ウソのように思いますが,これはウソでもなんでもなく,6つの行程がひっきりなしに動いているからです。いわば,1つの製品を作るの必要な工程を順番にせず,一気に同時に行っているから時間が短くなっていると考えられるわけですね。

 ややこしいのは,ステージの時間が揃っていない場合です。自分が5分で出来ても,次の人が10分かかっていたら,次の人の手前にものが溜まってしまい,結局10分に一度しかものが完成しません。つまり,一番長い時間のかかる処理に全ての処理を揃えて上げないと,パイプライン処理というのは成り立たないのです。

 さて,このCPUは,6つのステージに分かれています。それぞれのステージの処理時間は,Eを除いて10ns,Eだけは15nsかかります。

 このCPUでパイプライン処理を行う場合,一番遅いステージに揃えて上げる必要があります。一番遅いのはEの15nsに2nsを確か足した17nsですので,全てのステージを17nsで並べて上げるとよさそうです。この17nsという数字が,パイプラインピッチです。

3)

 では,実際にパイプライン処理を図示してみましょう。

 F D A B E W
   F D A B E W
     F D A B E W
0 17 34 51 68 85 102 119 136

 どうですか,始めと終わりに全てのステージが動いていない部分がありますが,3命令とは言わずたくさんの命令を流せば,ほとんどの時刻で全てのステージが動いてくれそうです。

 実際,同じ3命令の仕事をパイプライン処理することで60ns近くも早く終わらせることに成功しています。この威力は大きいです。

4)

 まず,パイプライン処理をしなかった場合の処理時間ですが,これは1)にあるように,195nsです。

 これをパイプライン処理にした場合,3)のように136nsで済んでいます。速度向上率は,(195-136)/136*100=43.38%です。

 一番遅いステージに揃え,なおかつ各ステージに2nsの余計な時間がかかってしまうとしても,4割も速度が上がっています。これがパイプライン処理の効能です。

5)

 ところで,4)の「定常状態」なのですが,では定常状態ではない時というのはどういう時かというと,ステージが遊んでしまうような状態をさします。例えば分岐命令があった場合に起こる状態です。

 分岐命令があると,その後に続く命令が確定しません。ですから確定するまで,次の命令が取り込まれることなく,各ステージはしばらく遊んでしまいます。

 これをハザードといいます。

 パイプライン処理というのは並列処理の一種ですから,前後の命令が時間的に相関がある,つまり前の命令の結果が後ろの命令に影響を与えるような場合,同時に処理することは出来ません。

 分岐もそうですし,他にも前の命令で計算した結果を次の命令で使うような場合,前の命令の処理が完了しないと後ろの命令が実行できません。

 こうしたハザードをなんの対策も行わずに放置すると,せっかくのパイプライン処理が台無しになってしまうので,いろいろな対策を盛り込むことになります。

 まず,前の命令の結果を続く命令が利用する場合です。これは,前の命令の計算結果が出るステージから,結果を次に使うステージにバイパスしてやれば,前の命令の完了を待たずに済みます。これをレジスタフォワーディングといいます。

 レジスタフォワーディングでも間に合わない様な場合,残念ながら結果が出るまで次の命令の実行を止めます。この待ち時間をロード遅延といい,ロード遅延を行うために必要なパイプラインを止める仕組みを,インタロックといいます。

 ロード遅延を許さず,必ずパイプラインを止める方法もありますが,もしも後の命令と依存関係のない命令と順番を入れ替えることが出来るなら,パイプラインを止めずに済みます。これを遅延ロードといいます。

 しかし,現実的に命令の入れ替えが可能になることは少なく,その場合は何もしない命令(NOP)を入れて,パイプラインを止めないようにします。これで,インタロックを実装しなくても待ち時間(ロード遅延)を確保出来ます。

 ですが,結局なにもしない命令を入れることは,パイプラインを止めることと同じ事です。なら,インタロックを入れてパイプラインを止めてしまっても結果は同じですし,何もしない命令が入ってこない分プログラムが小さくなるということもあり,こちらの仕組みを使うCPUも多くあります。

 もう1つ,分岐命令ですね。分岐命令は,実行結果によって処理する命令が違ってきますから,分岐の結果が確定するまで次の命令を取り込むことが出来ません。

 当たり前のこととはいえもったいないですから,分岐命令に続く命令が置かれる場所を遅延スロットという特別な場所とし,ここに置かれた命令を,実際の分岐を遅らせて先に実行してしまいます。分岐を遅らせることから,これを遅延分岐といいます。

 こうすると分岐命令があっても命令の実行が行われるようになります。そして,もしこの遅延スロットに入れる命令が,分岐の結果に依存しないような命令だったりしたら,1つ余計に命令が実行出来た事になりますね。

 これを目指してコンパイラは,遅延スロットに置くことの出来る命令を探し出して,入れ替えるように動いてくれます。それでも入れ替えることの出来る命令がなかった場合には,なにもしない命令(NOP)を入れる事になります。

 この仕組みは,CPUの回路規模がほとんど大きくならずに済み,分岐が行われる場合でも余計に1命令実行することが可能になるというメリットがあります。

 なお,遅延スロットは1つとは限りません。2つの場合も3つの場合もありますが,それぞれ実際の分岐が行われるより先に2つもしくは3つの命令が先に実行されるように作ってあります。だから,遅延スロットの数が変わるとプログラムの互換性が損なわれますので,その数は互換性を維持する限りは変更が許されません。

 もう1つ,最近は,ふんだんに使えるようになったトランジスタを利用し,こっと積極的に分岐先を予測する分岐予測と,予測された命令を実行する投機実行が使われるようになりました。予測の精度上げれば遅延分岐よりも効率が良く,遅延分岐のようなわかりにくさもないため,新しいプロセッサでは遅延分岐よりも分岐予測と投機実行が好まれる傾向にあるようです。

ページ移動

  • ページ
  • 1
  • 2
  • 3
  • 4

ユーティリティ

2020年05月

- - - - - 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31 - - - - - -

検索

エントリー検索フォーム
キーワード

ユーザー

新着画像

新着エントリー

過去ログ

Feed