外部メモリアルゴリズム

コンピューティングにおいて、外部メモリアルゴリズムまたはアウトオブコアアルゴリズムとは、コンピュータのメインメモリに一度に収まらないほど大きなデータを処理するように設計されたアルゴリズムです。このようなアルゴリズムは、ハードドライブやテープドライブなどの低速バルクメモリ（補助メモリ）に格納されているデータ、またはメモリがコンピュータネットワーク上にある場合に、データを効率的にフェッチしてアクセスできるように最適化する必要があります。^[¹^]^[²^]外部メモリアルゴリズムは、外部メモリモデルで分析されます。

モデル

{\displaystyle {\tfrac {M}{B}}} — 左側のキャッシュには ${\tfrac {M}{B}}$ サイズのブロック $B$ それぞれが、合計 $M$ 個のオブジェクトとなる。右側の外部メモリは無制限である。

外部メモリアルゴリズムは、外部メモリモデル (またはI/O モデル、またはディスクアクセスモデル)と呼ばれる理想化された計算モデルで分析されます。外部メモリモデルは、 RAM マシンモデルに似た抽象マシンですが、メインメモリに加えてキャッシュがあります。このモデルは、キャッシュでの読み書き操作がメインメモリよりもはるかに高速であること、およびディスクの読み書きヘッドを使用してランダムに読み取るよりも、連続した長いブロックを読み取る方が高速であることを捉えています。外部メモリモデルにおけるアルゴリズムの実行時間は、メモリへの読み書きに必要な回数によって定義されます。^[³^]このモデルは、 1988 年にAlok Aggarwal とJeffrey Vitterによって導入されました。^[⁴^]外部メモリモデルはキャッシュ非依存モデルに関連していますが、外部メモリモデルのアルゴリズムはブロックサイズとキャッシュサイズの両方を知っている場合があります。このため、このモデルはキャッシュ認識モデルと呼ばれることもあります。^[⁵^]

このモデルは、サイズ $M$ の内部メモリまたはキャッシュを備えたプロセッサと、無制限の外部メモリで構成されています。内部メモリと外部メモリの両方は、サイズ $Bの$ ブロックに分割されています。1つの入出力またはメモリ転送操作は、 $B個$ の連続する要素のブロックを外部メモリから内部メモリに移動することからなり、アルゴリズムの実行時間は、これらの入出力操作の数によって決まります。^[⁴^]

アルゴリズム

$外部メモリモデルのアルゴリズムは、外部メモリから1つのオブジェクトを取得すると、サイズB$ のブロック全体が取得されるという事実を利用します。この特性は、局所性と呼ばれることもあります。

外部メモリモデルでは、分岐係数 $Bの$ B ツリーを使用して $N$ 個のオブジェクトの中から要素を検索することが可能です。B ツリーを使用すると、検索、挿入、削除が実現できます。 $O(\log _{B}N)$ 時間（ビッグオー記法）。情報理論的には、これはこれらの操作で可能な最小実行時間なので、Bツリーを使用することが漸近的に最適です。^{[ 4 ]}

外部ソートは、外部メモリ設定でのソートです。外部ソートは、クイックソートに似た分散ソート、または ${\tfrac {M}{B}}$ - 方向マージソート。どちらのバリアントも漸近的に最適な実行時間を達成します。 $O\left({\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)$ $N$ 個のオブジェクトをソートする。この上限は、外部メモリモデルにおける高速フーリエ変換にも適用される。 ^{[ 2 ]}

順列問題とは、 $N$ 個の要素を特定の順列に並べ替える問題です。これは、上記のソート実行時間を必要とするソートを行うか、各要素を順番に挿入して局所性の利点を無視するかのいずれかで実行できます。したがって、順列は次のように実行できます。 $O\left(\min \left(N,{\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)\right)$ 時間。

アプリケーション

外部メモリモデルは、ランダムアクセスマシンなど、データ構造の分析に使用される他の一般的なモデルではモデル化されていないメモリ階層を捉えており、データ構造の下限を証明するのに役立ちます。このモデルは、内部メモリに収まらないほど大きなデータセットを扱うアルゴリズムの分析にも役立ちます。^[⁴^]

典型的な例としては、地理情報システム、特にデジタル標高モデルが挙げられます。この場合、データセット全体は容易に数ギガバイト、あるいはテラバイトを超えるデータ量になります。

この手法は汎用CPUにとどまらず、GPUコンピューティングや従来のデジタル信号処理にも適用されます。グラフィックス処理ユニット（GPGPU）による汎用コンピューティングでは、メモリ容量が少ない（一般的に RAMと呼ばれるシステムメモリに比べて）高性能グラフィックスカード（GPU）が使用され、CPUからGPUへのメモリ転送速度は（計算帯域幅に比べて）比較的遅くなります。

歴史

「out-of-core」という用語が形容詞として使われた初期の例は、1962年にIBM 360のコアメモリ以外のデバイスを指して使われた例である。^[⁶^]アルゴリズムに関して「out-of-core」という用語が使われた初期の例は1971年に見られる。^[⁷^]

参考文献

↑ Vitter, JS (2001). "外部メモリアルゴリズムとデータ構造: 大量データの処理". ACM Computing Surveys . 33 (2): 209–271 . CiteSeerX 10.1.1.42.7064 . doi : 10.1145/384192.384193 . S2CID 2155038 .
1 2 Vitter, JS (2008).外部メモリのためのアルゴリズムとデータ構造(PDF) . 理論計算機科学の基礎と動向シリーズ。第 2 巻。ハノーバー、マサチューセッツ州: Now Publishers。pp. 305–474。CiteSeerX 10.1.1.140.3731。doi : 10.1561 / 0400000014。ISBN 978-1-60198-106-6。{{cite book}}:|journal=無視されました (ヘルプ)
↑張東輝。ツォトラス、ヴァシリス J.レヴィアルディ、ステファノ。ジョルジュ・グリンスタイン。ベリー、デイモン・アンドリュー。グエ＝ブリュネ、ヴァレリー。コッシュ、ハラルド。デラー、マリオ。デラー、マリオ。コッシュ、ハラルド。マイヤー、ポール。バタチャリヤ、アルナブ。リヨサ、ヴェビョルン。ナック、フランク。イラリア州バルトリーニ。グエ＝ブリュネ、ヴァレリー。メイ、タオ。ルイ、ヨン。クルシアーヌ、ミシェル。シー、フランク Y.ファン、ウェンフェイ。ウルマン・クレール、モリー。クラーク、ユージン。アロンソン、サミュエル。メリン、ジョナス。ベルントソン、ミカエル。グラネ、ゲスタ。ベルトッシ、レオポルド。ドン、グオジュ。他。 (2009). 「I/O 計算モデル」.データベースシステム百科事典. Springer Science+Business Media . pp. 1333–1334 . doi : 10.1007/978-0-387-39940-9_752 . ISBN 978-0-387-35544-3。
1 2 3 4 Aggarwal, Alok; Vitter, Jeffrey (1988). "ソートおよび関連問題の入出力複雑性" . Communications of the ACM . 31 (9): 1116– 1127. doi : 10.1145/48529.48535 . S2CID 6264984 .
↑ Demaine, Erik (2002). Cache-Oblivious Algorithms and Data Structures (PDF) . Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS.
↑ NASAのSP。 NASA。 1962 年。276.
↑コンピュータ危機。ACM。1971年。296ページ。

外部リンク

コアSVDとQRのアウトオブ
コアグラフィックス外
Scalapack 設計

[1] Vitter, JS (2001). "外部メモリアルゴリズムとデータ構造: 大量データの処理". ACM Computing Surveys . 33 (2): 209–271 . CiteSeerX 10.1.1.42.7064 . doi : 10.1145/384192.384193 . S2CID 2155038 .

[Vitter-2] 1 2 Vitter, JS (2008).外部メモリのためのアルゴリズムとデータ構造(PDF) . 理論計算機科学の基礎と動向シリーズ。第 2 巻。ハノーバー、マサチューセッツ州: Now Publishers。pp. 305–474。CiteSeerX 10.1.1.140.3731。doi : 10.1561 / 0400000014。ISBN 978-1-60198-106-6。{{cite book}}:|journal=無視されました (ヘルプ)

[Springer-3] 張東輝。ツォトラス、ヴァシリス J.レヴィアルディ、ステファノ。ジョルジュ・グリンスタイン。ベリー、デイモン・アンドリュー。グエ＝ブリュネ、ヴァレリー。コッシュ、ハラルド。デラー、マリオ。デラー、マリオ。コッシュ、ハラルド。マイヤー、ポール。バタチャリヤ、アルナブ。リヨサ、ヴェビョルン。ナック、フランク。イラリア州バルトリーニ。グエ＝ブリュネ、ヴァレリー。メイ、タオ。ルイ、ヨン。クルシアーヌ、ミシェル。シー、フランク Y.ファン、ウェンフェイ。ウルマン・クレール、モリー。クラーク、ユージン。アロンソン、サミュエル。メリン、ジョナス。ベルントソン、ミカエル。グラネ、ゲスタ。ベルトッシ、レオポルド。ドン、グオジュ。他。 (2009). 「I/O 計算モデル」.データベースシステム百科事典. Springer Science+Business Media . pp. 1333–1334 . doi : 10.1007/978-0-387-39940-9_752 . ISBN 978-0-387-35544-3。

[Aggarwal88-4] 1 2 3 4 Aggarwal, Alok; Vitter, Jeffrey (1988). "ソートおよび関連問題の入出力複雑性" . Communications of the ACM . 31 (9): 1116– 1127. doi : 10.1145/48529.48535 . S2CID 6264984 .

[Demaine02-5] Demaine, Erik (2002). Cache-Oblivious Algorithms and Data Structures (PDF) . Lecture Notes from the EEF Summer School on Massive Data Sets. Aarhus: BRICS.

[6] NASAのSP。 NASA。 1962 年。276.

[7] コンピュータ危機。ACM。1971年。296ページ。

[

[

[

[

[

[

[

外部メモリアルゴリズム

モデル

アルゴリズム

アプリケーション

歴史

関連項目

参考文献

外部リンク

関連するトピック

コンピューティング

メインメモリ

アルゴリズム

ハードドライブ