『コンピュータの構成と設計 MIPS Edition 第6版 下』 はコンピュータサイエンスの教科書です. ハードウェアを知り, ソフトウェアを適合させる方法が説明されます.

上下巻に分かれていますが, 内容は完全に上巻の続きです. 各巻で相互に参照されている箇所もあるので, 両方を手元に置いて置くと理解しやすいでしょう. 下巻のメインはメモリ (キャッシュや仮想メモリなど) と並行処理で, アセンブラや論理回路についての付録も含まれています.

キャッシュ

キャッシュをどのように保存するか考える. キャッシュはメインメモリ中の値を保持するものだから, メモリアドレスに基づいてキャッシュを入れる場所を決定するのは自然だろう. アドレスによってキャッシュの場所を一箇所に定める方法をダイレクトマップ方式という.
アドレスが 4bit, キャッシュのブロック数が 4 個なのであれば, アドレス上位の 2bit をインデックスとして用いる. つまりアドレス 0000, 0001, 0010, 0011 は同じインデックスが割り当てられる. 残りの下位 2bit をタグとしてデータと合わせて保持して, 現在キャッシュにあるのがどのアドレスのデータなのか特定できるようにする.
もし 0000, 0010 を交互にアクセスするとどうなるだろうか. 両者とも同じインデックスに保存されているためキャッシュ位置が競合し, キャッシュミスが繰り返される.

競合を減らす柔軟な方法はないだろうか.
一つのインデックスに二つのブロックを保存できるようにすればどうだろう. そうすれば二つのブロックを持つセット二つから成るキャッシュができる. 元々 4 * 1 だった構造が 2 * 2 になったということだ.
キャッシュを格納するとき, 各セットにある二つのブロックどちらを使っても良い.もちろん空きがなければ追い出すしかなく, LRU(Least Recently Used) 法などに従って捨てるキャッシュを選び, 新たにキャッシュを入れる.
一般化して, 一つのインデックスに複数のブロックを保存する方法をセット・アソシエイティブ方式という. 究極はセットが一つしかないフル・アソシエイティブ方式だ. 一セット当たりのブロック数のこと指す連想度という用語を使えば, ダイレクトマップ方式からフル・アソシエイティブ方式に向けて連想度が上がると表現できる.

どの方式が優れているか, 一概に決めることはできない. 連想度を上げれば柔軟なキャッシュ配置が可能となりミスが減るが, あるセットから目当てのデータを見つけるためのタグ検索に時間がかかる. 現実的にはセット・アソシエイティブ方式で最もミス率と検索時間のバランスが取れている.
キャッシュは階層化されているため, 各階層によって配置方式を使い分けることも可能だ. 例えば L1 キャッシュは高速であることを重視して連想度を低く, L2 キャッシュではミス率を減らすことを重視して連想度を高くするといった具合である. L2 でのキャッシュミスは L1 でのミスと比較して数倍ものペナルティとなるため, L2 の連想度を上げることは理に適っている.
キャッシュの性能は結局のところデータを取得するのに掛かる時間で最も正確に表すことができる. 連想度やブロックサイズなどのパラメータが性能にどのような影響を与えるか, 総合的に考えることが重要だ.

性能
= 平均的なアクセス時間
= ヒット時のアクセス時間 + ミス時のアクセス時間 * ミス率

ブロック化 - キャッシュを意識したアルゴリズム

キャッシュがうまく機能するようなアルゴリズムを考えることは重要である.
行列の積を計算するプログラムで例を見よう. N * N の行列 A,B,C に対して, C = A * B を計算するコードだ.

for (int i = 0; i < N; ++i) {
  for (int j = 0; j < N; ++j) {
    double cij = 0.0;
    for (int k = 0; k < N; ++k) {
      cij += A[i * N + k] * B[k * N + j];
    }
    C[i * N + j] = cij;
  }
}

簡単のため二次元の行列を一次元の配列で持っている. ここでキャッシュのことを考えよう. もし N が小さくて A,B,C 全てが L1 キャッシュに乗るのであれば何も問題はない. しかし N が大きい場合, ある領域がキャッシュから追い出された後に再び要求され, ミスが生じる (容量性ミス). どうにかしてミスを減らすことができないだろうか.
ブロック化の鍵は行列の全てではなく一部を扱うことにある. 以下のコードは N * N ではなく BLOCK * BLOCK の行列についての乗算を繰り返している.

void f() {
  for (int si = 0; si < N; si += BLOCK) {
    for (int sj = 0; sj < N; sj += BLOCK) {
      for (int sk = 0; sk < N; sk += BLOCK) {
        block(si, sj, sk);
      }
    }
  }
}

void block(int si, int sj, int sk) {
  for (int i = si; i < si + BLOCK; ++i) {
    for (int j = sj; j < sj + BLOCK; ++j) {
      double cij = 0.0;
      for (int k = sk; k < sk + BLOCK; ++k) {
        cij += A[i * N + k] * B[k * N + j];
      }
      C[i * N + j] += cij;
    }
  }
}

メモリアクセスの違いを見てみよう. BLOCK = 3 のとき, 計算にどの値が必要が確認するため式を書き並べてみる(なぜか\(LaTeX\)記法が使えない).

C00 = A00 * B00 + A01 * B10 + A02 * B20
C01 = A00 * B01 + A01 * B11 + A02 * B21
C02 = A00 * B02 + A01 * B12 + A02 * B22

C10 = A10 * B00 + A11 * B10 + A12 * B20
C11 = A10 * B01 + A11 * B11 + A12 * B21

このくらいで項を観察してみる.
まず A は同じ要素に連続してアクセスされる. 上の例だと C00, C01, C02 を計算するときに繰り返し A00, A01, A02 にアクセスしている. つまり空間的局所性があると言える.
B は一度アクセスされた値が少し後に再度要求される. C00 で B00 が使われた後, C10 でも B00 が使われる. つまり時間的局所性を持つ.
キャッシュに乗り切る程度に BLOCK を小さくすることで, A についての空間的局所性と B についての時間的局所性を利用するのがブロック化方式だ. 実際に手元で実験してみたところ, 数十 % の速度向上が得られた.

普段アルゴリズムを評価するときは計算量やメモリ使用量を考える. コンピュータの性能を引き出すためには, それらと同様にキャッシュ効率も考えなければならない.

ハードウェアレベルの並列処理

命令流とデータ流によるコンピュータの分類方法がある. それぞれの流れが単一か複数かによる分類で, 例えば単一命令複数データなら SIMD(Single Instruction stream, Multiple Data stream) と呼ばれる. 古典的な分類方法だが SIMD は現在も x86 のストリーミング SIMD 拡張やベクトル拡張 (AVX) によって実現されている.

MIMD は分類上存在するが, その複雑さ故に現在はそれほど一般的ではない. 複数のスレッドを複数のプロセッサで処理しようとする MIMD と似た方法で, 複数スレッドが単一プロセッサ内の機能ユニットを共有するハードウェア・マルチスレッディングがある.
一命令ごとにラウンドロビンなどでスレッドを切り替える細粒度マルチスレッディングや, 大きなストールが発生したときにスレッドを切り替える荒粒度マルチスレッディング, 各スレッドからの複数命令発行を利用して常に複数スレッドからの複数命令を実行する同時マルチスレッディングといった方式がある.

DSA(ドメイン固有アーキテクチャ)

GPU はグラフィックス処理に特化したプロセッサだ.
CPU を補完する立場であるため, 全ての処理をこなせる汎用性は不要である. そのため, CPU が備える多くの機構を排除し, 代わりにマルチスレッド方式の SIMD プロセッサを複数持つ. マルチスレッド方式の SIMD プロセッサとは, SIMD 計算ができるユニットを複数持つプロセッサである. それぞれのユニットは独立していて, フェッチされた命令が空いているユニットに割り振られ, 並行に実行される.
GPU は CPU よりも扱うデータのサイズがかなり大きい. そのため CPU で使われる階層構造のキャッシュはあまり役に立たない. 最下層のキャッシュにさえデータが乗り切らないからだ. 代わりに, ハードウェア・マルチスレッディングを利用してメモリアクセスのレイテンシを隠蔽する. メモリとしてはキャッシュよりもバンド幅が重要だ.

Moore の法則が鈍化し, Dennerd のスケーリング則が終了し, Amdahl の法則からマルチコア CPU の性能限界が見え, 業界は行き詰まり感に包まれていた. そんな中 GPU は目覚ましい成果を上げたことで, 従来の汎用的なプロセッサではなく, 特定の領域のみを対象としたプロセッサを搭載したコンピュータ DSA(ドメイン固有アーキテクチャ) が脚光を浴びた. 特定領域に特化することで, その領域固有のデータや計算に合わせた設計を行える. 汎用性を持たせた複雑な機能を排除すれば, 浮いた資源を処理装置の増加やメモリの拡大に使えるのだ.

DSA が特に普及しているのは ML(機械学習) の分野だ. Google の開発した TPUv1(Tensor Processing Unit) は ML の隆盛に応じて開発された.
ML による音声認識モデルをユーザが一日三分使うと, データセンターを倍増しなければならない——2013 年に Google が出した驚愕の試算である. コスト性能比を 10 倍改善するという目標の下急速に推進されたプロセッサ開発計画は, わずか 15 か月で設計から製造, 配備までが行われた. こうして開発された TPUv1 の電力当たりの性能は GPU の 29 倍, CPU の 83 倍であった. クロック周波数は 700MHz と控えめでありながら, 256 * 256 個もの ALU は毎秒 90 テラ演算のピーク性能を叩き出す.

Google は TPUv1 を搭載した数多のサーバから成るデータセンターで巨大な Web サービスを提供している. ネットワークにより連結されたサーバ群全体を一台のコンピュータとして捉え, ウェアハウススケールコンピュータと呼称する.
5 万台ものサーバ, それに付随する電力や冷却システムといったインフラには膨大な運用費が掛かるが, 規模の経済により格安でハードウェアパワーを貸すことができるようになった. こうしてクラウドの時代が幕を開けた.

数年でプロセッサの性能が倍増する時代は終焉を迎えた. 汎用プロセッサの性能は年間数％しか向上しないだろう.
この 20 年間で並列処理を模索してきた業界は, DSA の時代を迎える. ハードウェアの特徴を理解し, それを活かすソフトウェアを作る努力が, これから生まれる新たなアイデアに結びつくだろう.

結語

上巻同様既知の内容は多かったのですが, 曖昧にしか理解していなかった部分が補強されたり, より深い知識を得たりすることができました. キャッシュのブロック配置方式やブロック化の意味が少し分かったような気がします. そしてハードウェア・マルチスレッディングやキャッシュ・コヒーレンスを知り, プロセッサはなんと精巧なことだろうかと畏敬の念を抱きました.

DSA の重要性がアピールされていて, 今後はこういう流れになるのだろうかと思いました. 時代が多少変わってもハードを理解してソフトを作る営みは普遍でしょうから, 本書が長らく読み継がれているのも納得です.