アウトオブコアと外部メモリアルゴリズム

アウトオブコアが必要になる場面

扱うデータが物理メモリ（RAM）に収まりきらない状況を、HPCの文脈ではアウトオブコア（out-of-core）と呼びます。テラバイト級の行列、ゲノム、ログ、格子データなどが典型です。データがメモリに収まる限り（in-core）は、性能は概ねCPUの演算速度やキャッシュ帯域で決まります。ところがデータがメモリを超えると、処理の大半はディスク（SSD/HDD）やネットワークストレージとの間のデータ移動に費やされ、CPUがどれだけ速くても意味をなさなくなります。

ここで問題になるのが階層間の速度差です。RAMアクセスが数十ナノ秒なのに対し、SSDは数十マイクロ秒、HDDのランダムシークはミリ秒級で、桁が3〜6つ違います。したがってアウトオブコア処理の設計目標は「CPU命令数を減らす」ことではなく「遅い階層への転送回数、とりわけランダムアクセスを減らす」ことに移ります。この転送量が支配的になる構図自体は、演算強度で性能を診断するRoofline性能モデルと同じ発想を、キャッシュとメモリの間から、メモリとディスクの間へ一段引き上げたものだと捉えられます。

外部メモリモデル（I/Oモデル）

アウトオブコア性能を解析する標準的な理論枠組みが、Aggarwal-Vitterの外部メモリモデル（external memory model、I/Oモデル）です。計算機を次の3つのパラメータで抽象化します。

横にスクロール

N : 処理対象データの総要素数
M : 内部メモリ（RAM）に収まる要素数     （M が N 未満）
B : 1回のI/Oでまとめて転送するブロックの要素数（B が M 以下）

このモデルの本質は、計算量をCPU命令数ではなく I/O回数（ブロック転送の回数）で数える点にあります。内部メモリ内での計算は無料とみなし、遅い外部メモリとの間で B 要素ずつやり取りする回数だけをコストに計上します。これは、遅い階層への転送が支配的なアウトオブコアの現実を正しく反映した計量です。

このモデルでの基本的な下限を押さえておきます。

走査（scan、全要素を順に1回なめる）: N/B 回のI/O
外部ソート（sort）              : 約 (N/B) × log_(M/B)(N/B) 回のI/O

走査の N/B は「全部でN要素あり、1回にB要素運べるのだから最低N/B回」という直感どおりの下限です。素朴に1要素ずつ扱えばI/OはN回になり得ますが、連続領域をブロック単位で読めばN/B回で済み、これがブロック化（blocking）の効き目です。対数の底が2ではなく M/B である点が外部ソートの肝で、後述します。

ブロック化とプリフェッチ

外部メモリモデルが教える第一の設計則は、アクセスをブロック境界にそろえ、連続的にすることです。行優先で格納された二次元配列を列方向になめると、要素ごとに別のブロックへ飛び、実効的にI/OがN回近くまで悪化します。同じデータを行方向になめればN/B回で済みます。アルゴリズムを変えずとも、アクセス順序をストレージの物理配置に合わせるだけで転送回数が桁で変わります。

第二の設計則がプリフェッチ（prefetch、先読み）です。I/Oモデルは転送回数を数えますが、実機では1回のI/Oにレイテンシ（応答までの待ち時間）が伴います。次に必要になるブロックを、現在のブロックを計算している 裏で 先に読み始めておけば、転送待ちと計算を時間的に重ねられ、レイテンシを隠せます。

素朴な逐次処理（レイテンシがそのまま積み上がる）
  [読み込み block0][計算 block0][読み込み block1][計算 block1] ...

ダブルバッファリング（読み込みと計算を重ねる）
  [読み込み block0]
                 [計算 block0][計算 block1][計算 block2] ...
                 [読み込み block1][読み込み block2] ...   ← 計算の裏で先読み

2枚のバッファを交互に使うダブルバッファリング（double buffering）が代表的な実装です。片方のバッファで計算している間に、もう片方へ次ブロックを読み込みます。ただしプリフェッチが効くのはアクセス順序が事前に予測できる場合に限られ、ランダムアクセスでは先読み対象が定まらず恩恵が薄い点に注意します。

外部ソート ── M/B分岐マージの原理

外部ソートは外部メモリアルゴリズムの代表例で、なぜ対数の底が M/B になるのかにこの分野の核心が凝縮されています。

ソート対象N要素はメモリに収まりませんが、メモリにはM要素までなら載せられます。そこで二段構えにします。まず入力をM要素ずつのチャンクに切り、各チャンクをメモリ内で普通にソートして、整列済みの一時ファイル（ラン、run）としてディスクに書き戻します。ランはおよそ N/M 本できます。

フェーズ1: ラン生成
  入力を M 要素ずつ読み込み → メモリ内ソート → 整列済みランを書き出す
  → 約 N/M 本のソート済みランができる（各フェーズは走査 N/B 回のI/O）

次にこれらのランをマージ（併合）して1本に統合します。ここで、一度に何本のランを同時にマージできるかが速度を決めます。各ランの先頭ブロック（B要素）を同時にメモリへ持てるだけ持ち込みたい。メモリ容量はMなので、M/B 個のブロックを同時に保持でき、すなわち 1回のマージパスで最大 M/B 本のランを1本に束ねられます。1本ずつ順に足す二分マージ（底2）ではなく、M/B 本を一気にまとめる多分岐マージ（M/B-way merge）になるため、必要なパス数の対数の底が M/B になります。

フェーズ2: M/B分岐マージ
  各パスで最大 M/B 本のランを1本に統合
  → ランの本数が 1/(M/B) ずつ減る
  → 必要なパス数 ≈ log_(M/B)(N/M)
  各パスは全データを1回なめる = N/B 回のI/O

総I/O ≈ (N/B) × log_(M/B)(N/B)

実機では M/B が数百〜数千に達することも珍しくないため、対数はほぼ1〜2に収まり、外部ソートは事実上「入力を数回なめる」コストで完了します。二分マージ（底2）だとパス数が log_2 に膨れ、同じデータを何十回もなめることになるため、多分岐にする効果は絶大です。この「メモリに載る分だけ束ねて一気に処理する」という発想は、外部ソートに限らず外部メモリアルゴリズム全般に共通します。

タイル化（キャッシュブロッキング）

タイル化（tiling、ブロック化）は、データを小ブロック（タイル）に区切り、1つのタイルを速い階層に載せている間にそのタイルを可能な限り再利用してから次へ進む技法です。狙いは、ワーキングセット（同時に必要となる作業データ）を容量Mに収め、遅い階層への転送を削ることにあります。この考え方はメモリとディスクの間だけでなく、キャッシュとメモリの間（キャッシュブロッキング）でもまったく同じ形で効きます。

古典例が行列積 C = A × B です。素朴な三重ループでは、内側で行列全体を何度もなめ直すため、各要素がMに収まらないサイズでは繰り返し再ロードされ、I/Oが N³/B 級に達します。ここで三つの行列を一辺 T のタイルに分割し、T × T のブロック3枚がメモリ（容量M）に同時に収まるよう T を選ぶと、各ブロックはメモリ上で T 回再利用されてから捨てられます。

タイル化行列積（ブロックサイズ T、3枚が M に収まるよう T を選ぶ）

  for ii in 0..N step T:          # C のブロック行
    for jj in 0..N step T:        # C のブロック列
      for kk in 0..N step T:      # 内積方向
        # A,B の T×T ブロックをメモリに読み込み
        # C の T×T ブロックにブロック積を加算（メモリ内で完結）

  総I/O ≈ N³ / (B × T)   → T を大きくするほど I/O が減る

再利用が T 倍に増える分、遅い階層への転送は 1/T に減ります。より精密には、キャッシュ／メモリを最適に使い切ったブロック化行列積のI/O下限は N³/(B√M) 級であることが知られており、√M に比例して、使える速い階層の容量が大きいほど転送が減ります。演算量（N³ に比例）は変えず、分母の転送量だけを削る点が要で、これは疎行列のブロック格納（BCSR）がインデックス再利用で間接参照を減らすのと同じ「再利用で転送を削る」思想です。

キャッシュオブリビアスという別解

ここまでのタイル化は、ブロックサイズ B やメモリ容量 M を明示的に知って T を調整する キャッシュアウェア（cache-aware）な手法でした。これに対し、B も M もコードに一切埋め込まずに、あらゆる階層で自動的にほぼ最適なI/O効率を達成するキャッシュオブリビアス（cache-oblivious）アルゴリズムという系統があります。

要点は、問題を再帰的に半分ずつ分割し続けることです。分割を進めれば、部分問題はいつか必ず未知の容量Mに収まる大きさに到達します。パラメータを知らなくても、再帰の途中で「たまたまMに収まった」段より下は自動でブロック化された挙動になるため、値を明示せずとも階層全体で良好な局所性が得られます。行列積の再帰的分割や、キャッシュオブリビアスな行列転置がその代表例です。多段階層のそれぞれに合わせてタイルを手で調整する手間を、再帰という一つの仕掛けで肩代わりさせる発想だと捉えられます。

なお、扱うデータがメモリを超えるほど巨大になると、単一ノードのディスクでも追いつかず、複数ノードのメモリ・ストレージに分散して処理する構成へ移ります。障害時に途中結果を失わないためのチェックポイント・リスタートも、大量の状態を効率よくストレージへ書き出すという意味で外部メモリI/Oの設計と地続きです。

まとめ

• アウトオブコアではCPU速度ではなく遅い階層への転送回数が性能を支配するため、計量をCPU命令数からブロック単位のI/O回数に切り替える外部メモリモデル（パラメータ N・M・B）で解析する。
• 走査はN/B回、外部ソートは約 (N/B)×log_(M/B)(N/B) 回のI/Oで済む。外部ソートの対数の底が M/B になるのは、1回のマージパスで各ランの先頭ブロックをメモリに載せられる M/B 本を同時にマージできるからである。
• アクセスをブロック境界にそろえて連続化すればI/Oはブロック単位にまとまり、プリフェッチ（ダブルバッファリング）で転送と計算を重ねればレイテンシを隠せる。
• タイル化はワーキングセットを容量Mに収めて再利用を T 倍に増やし、遅い階層への転送を 1/T へ削る。パラメータを埋め込まず再帰分割で階層全体に効かせるキャッシュオブリビアスという別解もある。