艦長日誌・私的記録 DS9

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

　パイプライン，キャッシュ，そして仮想記憶と，コンピュータについて重要な基礎的技術についてはこの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%を越えるようなヒット率を実現している例もあります。

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

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

　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でもそうですが，メモリをたくさん積むと快適になるというのは，このあたりの話からも容易に想像出来ます。

　コンピュータ基礎の基礎，第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.
ライトスルー　ＭＭＨＭＨ
ライトバック　ＭＭＨＨＨ

2.
ライトスルー　ＭＭＭＭＨ
ライトバック　ＭＭＨＭＭ

3.
ライトスルー　ＨＨＭＨＭ
ライトバック　ＨＭＨＭＭ

4.
ライトスルー　ＨＭＭＭＨ
ライトバック　ＨＨＭＭＨ

5.
ライトスルー　ＭＭＭＭＭ
ライトバック　ＭＭＨＭＨ

----

回答:

　ダイレクトマップ方式のキャッシュメモリということなので，問題にあるようにアドレス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に書き込みが発生する。

　よって，ライトスルーはＭＭＭＭＨ，ライトバックはＭＭＨＭＭとなり，正解は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と同じ速度で動作するという理想にほど遠いことを示していると言えるかも知れません。

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

　そこで，この場をちょっとした復習に使おうと思います。第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命令分処理するという事ですので，以下のように書くことができます。下の数字は時刻です。

　Ｆ　Ｄ　Ａ　Ｂ　Ｅ　Ｗ　Ｆ　Ｄ　Ａ　Ｂ　Ｅ　Ｗ　Ｆ　Ｄ　Ａ　Ｂ　Ｅ　Ｗ
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)

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

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

　マイクロソフトが，ARMのライセンスを受けることになったそうです。

　ここ最近のマイクロソフトの動きにはちょっと不可解なものがあり，かつての輝きを失った迷走っぷりに残念な気持ちになっている方も多かろうと思います。

　創業者が特に優れていた場合の世代交代が難しいという話は，世の東西を問わず，また規模の大小を問わないものだと，つくづく思います。

　今から20年ほど前の，WindowsNTの開発の顛末を語った「闘うプログラマ」という本には，DECから移ってきたデイブ・カトラーが，自由奔放なマイクロソフトのキャンパスの雰囲気に嫌悪感を示すシーンがあります。

　今のマイクロソフトに，そうした大人が煙たがるような「遊び心」があるのか，ないのか。

　部外者の私にはさっぱり分かりませんが，なにやら巨大企業が遭遇する「お疲れ感」をそれとなく感じているのは，私だけではないのでは，と思います。

　そんなおり，ARMのライセンスの話です。

　ARMのライセンスと聞いてもぴんと来ない方も多いと思うので，ごく簡単に説明をします。

　ARMというのは言うまでもなく，CPUメーカーのARMのことです。イギリスのケンブリッジに本社がある半導体メーカーの1つですが，彼らの売り物は自前の半導体製品ではなく，CPUの設計情報です。

　例えばインテルにしてもルネサスにしても，CPUの設計はあくまでCPUを作ってそれを売るために作るものであり，それ自身は売り物にしません。しかし，ARMは半導体の実物はそれぞれの半導体メーカーが作るものとし，自分達はその設計情報だけを販売することにして，もうけています。

　設計情報が売り物になるのか？と疑問に思う方もあると思いますが，CPUをゼロから作るというのはとてもとても大変です。CPUを作るだけでも死ぬ思いをするのに，コンパイラやデバッガ，ICEなどの開発環境に加え，周辺機能も一式用意しないといけません。これがとても大変です。それだけしても，そのCPUが売れるかどうかはわかりません。

　ARMというCPUは処理能力はそれほどでもなかったのですが，当時からビックリするほど低消費電力であり，携帯電話に採用されてから爆発的に普及するようになりました。開発環境もARM純正だけではなく，他の専門の会社がARM向けに作るようになり，周辺機能についてもARMに繋がるものがどんどん揃い始めます。

　ARMのライセンスを購入し，ARMのCPUの設計情報を手に入れることは，これら開発環境や周辺機能をすべて使えるようになることを意味します。（もちろん結構なお金がかかるのですが）

　こうしてARMが普及すれば，ARMのCPUならすぐに製造できますよ，と言う工場が当たり前になってきます。半導体というのは，実は製造会社によってちょっとずつ違いがあって，設計情報に互換性がありません。それも最近は強い製造会社のルールに統一されてきましたが，ARMの設計情報と互換性を持たない工場は仕事を受けられませんから，自ずと対応するようになります。

　結果，上流から下流まで，ARMを選べば全部問題なく揃うという状況が作られます。

　ARMは技術的には低消費電力を売りにしたものですが，技術的なメリットよりむしろ，エコシステムについての魅力が圧倒的で，同業他社の追随を許しません。

　このARMを使うために必要なものがライセンスですが，実はこれも2種類があります。1つはインプリメンテーションライセンス，もう1つはアーキテクチャライセンスです。

　実はこれらのライセンスの中身は機密扱いになっていて，実際に契約を結んだ人でないと詳しい内容はわかりません。私ももちろんわかりませんが，そこはそれ，憶測も入れて書きますので，話半分で読んで下さい。

　インプリメンテーションライセンスというのは，ARMのCPUコアを「買う」ライセンスです。買い方には2つあって，1つは中身をブラックボックスとして買う方法，もう1つはソースコードで買う方法です。前者をハードマクロ，後者をソフトマクロと呼んだりします。

　ハードマクロはブラックボックスで買いますからそのまま工場で作るだけになってしまいますが，ソフトマクロで買った場合は，ちょっとしたカスタマイズ，例えばキャッシュメモリのサイズを変更するとか，その工場の半導体に最適化するとか，そういうことが可能になります。

　ただし，基本的にソースコードはいじれません。もしそんなことを許したら，ARMと微妙に互換性を失った「なんちゃってARM」があちこちにいっぱい出来てしまい，大混乱になってしまいます。

　ということで，あくまで作るのはARMで，それをそのまま利用するのがインプリメンテーションライセンスです。ARMを利用するメリットは，このインプリメンテーションライセンスでほぼ手に入ります。

　もう1つのライセンスであるアーキテクチャライセンスというのは，CPUのソースコードをいじることが許されるライセンスです。もっというと，ARMの互換プロセッサを「作る」ライセンスです。

　ARMのプログラムが走り，ARMが持つ機能が実装されていて，外側から見るとARMそのものでも，中身は完全に別物であるということが許されるライセンスなわけですが，なにぶん機密扱いですので，アーキテクチャライセンスでどこまで出来るのか，あるいはアーキテクチャライセンスが何種類あるのか，私にはわかりませんし，本当に互換プロセッサを作ってよいのかどうか，確かめたわけではありません。

　でも，本家ARMが作ったCPUに互換CPUを作っても，おおむね勝てるわけがありません。互換CPUを作ってもメリットがあるという「実力のある」会社だけが，どうしても既存のARMコアでは実現出来ない「なにか」を仕込むときに，このライセンスを手に入れる事になります。

　例えば，ARMはどんな工場でも作る事が出来るようにゆとりのある設計になっていますが，これを自社の工場に最適化して，カリカリにチューンするということも，このライセンスで可能になります。

　噂ではものすごく高価だとか，お金を出してもなかなか手に入らないとか，A社だけではなく実はB社もこのライセンスを持っているとか，優れた設計は無条件にARMにフィードバックしないといけないとか，まあそんな邪推を私も耳にしたことがありますが，本当に所は何度も言うように，私にはわかりません。

　はっきりしていることが1つあって，このアーキテクチャライセンスを受けた最初の1社が，旧DECです。DECは，ARMの低消費電力に適したアーキテクチャに目を付け，さらに低消費電力でさらに高速クロックで動作する新しいARM互換コア，StrongARMを開発しました。ARM7では3段パイプラインだったものを5段に増やしてクロックを向上させ，DEC自身が持つ製造プロセスに最適化した設計を行っています。

　そしてこの開発成果がDECからARMにフィードバックされて誕生したのが，ARM9です。ARM9も5段パイプラインですが，内部はより余裕のある設計がなされていて，どんな工場で作っても大丈夫なような汎用性のある設計がなされています。

　DECのARM部門はこの貴重なライセンスごとインテルに買収されてしまいます。一説になかなか手に入らないアーキテクチャライセンスを手に入れるのがDECを買った理由だとも言われていたのですが，StrongARMの後継として生まれたXscaleは，インテルの製造プロセスに最適化されてさらに高クロックで動作するARM互換プロセッサとなりました。

　この成果がフィードバックされたのが，ARM11と言われています。

　そのXscaleも，現在はインテルからMarvellに売却されており，Marvellがそのままアーキテクチャライセンスを保有しています。

　とまあ，このように，インプリメンテーションライセンスではどうしても越えられない壁があって，それをどうしても取り払いたい会社が，それ相応の技術力を認められた上で，ようやく手にすることのできる「なんでもできる」ライセンスが，アーキテクチャライセンスです。

　ライセンスにも多額の費用がかかりますし，これを使ってCPUを1から開発するわけですから，その開発費用も膨大です。それでも十分儲ける事が出来るという目算がなければ，およそこんな恐ろしいライセンスを取得しても，得なことはありません。

　さてさて，今回の主役であるマイクロソフトが手に入れたライセンスは，なんとこのアーキテクチャライセンスだというのです。

　？？？

　CPUを売って儲ける会社になるつもり？インプリメンテーションライセンスではダメだったの？わざわざアーキテクチャライセンスを手に入れて何をするつもり？

　いろいろ業界で憶測は飛び交っているとは思いますが，ここから先は全くの私の私見に基づく想像です。

　まず，マイクロソフトはCPU市場に参入するのか？答えはノーです。単に参入するだけならインプリメンテーションライセンスだけでもいいはずです。

　それに，マイクロソフトはソフト，特にOSの会社です。今さら設備産業である半導体に乗り込む理由は見当たりません。ファブレスの設計会社という選択肢もあるかも知れませんが，それこそそんな会社は世界中にいくらでもあり，悪いことにどの会社もそんなに儲かっていません。

　ではアーキテクチャライセンスでなにをするのか？これは，おそらくですが，OSを作る過程で感じていた，ARMアーキテクチャに対する不平不満を根本的に改善しようとしているのではないでしょうか。

　ご存じの通り，マイクロソフトはWindowsCEの時代から，ARMをサポートしていました。ARMと言うCPUに取って，WindowsCEというOSが動くことは何より心強いものがあったはずです。

　当時はMIPSやSH3などでも動いたWindowsCEですが，WindowsMobileとなった現在ではARMでしか動作しないOSになっています。マイクロソフトは売り物であるOSを，別にアーキテクチャライセンスを取得しなくても，十分に作ってこれたはずでした。

　しかし，実はARMというCPUは，私の言葉で「トルクのない」CPUです。粘りがないというか，底力がないというか，高クロックでぱぱーっと回るんですが，負荷がかかると途端にパワーが落ちるという印象があるのです。このあたり，x86や良くできたMIPSが，まるでディーゼルエンジンのトラックやバスでも運転しているかのような頼もしい感じがしたことを思い出します。

　ARMコアが原因と言うより，バス設計に問題があったからこういう印象があったのかもなと思い当たるところもあるのですが，では実際，1GHzのARMで動いているiPadと，似たようなクロックでもx86で動いているネットブックを比べてみると，どちらの方がサクサク動くかと少し考えて頂ければ，なんとなく想像出来るのではないでしょうか。

　WindowsCEは昔からもっさり動いているOSです。これがもしARMのアーキテクチャによるものだとマイクロソフトが結論していたら，アーキテクチャライセンスを手に入れて改善しようと考えても不思議ではありません。

　他にもあります。低消費電力を実現するには，主体的にCPUの消費電力を下げる必要がありますが，突き詰めるとそれだけでは限界があり，ソフトウェア，特にOSが頑張らないと下がりません。

　x86はインテルがだけが作っている（AMDも作っていますが，一応オリジナルはインテルです）ので，マイクロソフトとしてはWindowsをチューニングする過程で，インテルにどうしてもらえるとうれしいか，伝える機会を持っているはずです。

　インテルも，x86がWindowsを前提としてCPUであることを知っているので，マイクロソフトからの意見には真摯に耳を傾けていることでしょう。

　しかし，ARMは半導体会社には違いありませんが，実際に半導体を作っているわけではありません。マイクロソフトがARMにいろいろ意見を言っても，それがそのまま聞き入れられるとはちょっと考えにくいものがあります。

　WindowsCEとタブレットや携帯電話に向けて本格的に投入するにあたり，もうOSだけではどうにもならないところまで来てしまった・・・だからいよいよCPUそのものに手を入れて，より自分達に最適化されたCPUを作ろうとしている，というのが，私の考えです。

　この話が本当だとして，マイクロソフトの強力なライバルで，むしろ押され気味なAppleとGoogleには，およそ出来そうにないことをやって頭一つ抜け出ようとしたように思えてなりません。

　AppleのiPadやiPhone4には，彼ら独自開発といわれるA4というプロセッサが使われています。しかし実際にこれを設計しているのはSamsungで，AppleもSamsungもアーキテクチャライセンスを持っていませんから，既製品のARMコアをそのまま使っているはずです。

　1GHzという高クロックのわりには，そんなに高速で動作しているわけではないiPadは，消費電力の低さによる電池寿命の長さで評価は高いですが，でもそれだけです。処理能力で3年前のMacBookにさえ及びません。

　GoogleはAndroidをフリーでばらまいていますが，誰にでも使ってもらえるものであるためには，誰にでも手に入るCPUをターゲットにせねばなりません。Androidが実質ARM専用OSになっているのは，この戦略が故です。

　AppleもGoogleも，プロセッサそのものを作って，それ用のOSを作る事の出来ない事情があります。マイクロソフトもかつてはそうでしたが，彼らは果敢にもアーキテクチャライセンスを手に入れ，自分達のOSが最も効率よく動くCPUを作ろうとしています。

　マイクロソフトの主力製品はあくまでOSです。ですから，アーキテクチャライセンスにかかった多額の費用を，CPUを売ることによって回収しようとは考えていないと思います。マイクロソフトが狙っているのは，その主力製品であるOSが最も効率よく動くCPUを自ら用意して，これをリファレンスデザインとして提供し，他のライバルには到底実現出来ないような完成度の高い製品を，誰にでも簡単に作る事が出来るようにすることです。

　ここから先はいろいろなオプションがあるでしょうが，1つにはOSを売るためのオマケとして，CPUの設計情報とそのCPUを使ったリファレンスデザインの回路図を無償で提供し，これを使ってCPUと回路を作る事を最終製品のメーカーに許可するというシナリオです。

　あるいは，このCPUの設計情報を一部の半導体メーカーにライセンスし，そのCPUで高性能を発揮するOSをマイクロソフトが最終製品メーカーに対して供給する，とぃう話です。いわばスマートフォンのウィンテルを目指そうという作戦です。

　インテルはARMのアーキテクチャライセンスを手放しましたし，いくらATOMが低消費電力だといってもARMには全然かないませんから，実用的な電池寿命のスマートフォンをインテルのCPUで作ることは無理です。さりとて現状のARMでは処理能力に物足りないものがあり，しかもARMコアのCPUはARMからインプリメンテーションライセンスを受ければ製造できるので，多くの半導体メーカーが手がけています。

　マイクロソフトはこのあたりをよく分かった上で，PCにおけるインテルのような，スマートフォンにおけるパートナーを，自ら育てようとしているのかも知れません。

　いずれにせよ，スマートフォンを作るのに，これまでは既存のハードウェアにOSをあわせ込んで作っていたものを，それでは限界があるのでOSとハードウェアの両面から作る事にした，ということは間違いないでしょう。これはAppleにもGoogleにも現時点では真似の出来ないことです。

　言い方を変えると，マイクロソフトはソフトだけではもう改善できないと白旗を揚げたとも言えます。AppleもGoogleもまだまだソフトでがんばれると思っているのかも知れません。

　多額の費用を投じて，OSだけにとどまらずCPUにまで手を突っ込み，最終製品の性能向上を目論むマイクロソフトという会社は，いったいどれだけの巨大企業なのかと，背筋が寒くなる思いがします。

　Appleは，かつてPAsemiというCPUメーカーを買収しました。直接間接にこの会社の持っていた資産がA4というプロセッサの実現に役に立ったことは想像に難くありませんが，このPAsemiという会社は，もともとDECでStrongARMを開発した人々が作った会社だということを，最後に添えておきます。

　Appleは，PAsemiの直接の成果物や人的資産でA4を作ったのではなく，設計と製造を依頼したSamsungのいいなりにならず，自分達の欲しいCPUを作ってもらうためにちゃんと意思疎通ができるよう，その道の専門家（それもこの業界なら知らない人はいないと思われるCPU設計のカリスマです）を手に入れたかったというのが，現在の大方の見解です。

　AppleもGoogleもマイクロソフトも，しっかりしたビジョンと良いOSを持っている業界のリーダーですが，それぞれが専門外の半導体に対して，これだけスタンスが違ってくるというのが，大変に興味深いですね。