外部メモリアルゴリズム

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

モデル

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

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

アルゴリズム

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

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

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

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

アプリケーション

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

典型的な例は地理情報システム、特にデジタル標高モデルで、完全なデータセットは簡単に数ギガバイト、さらにはテラバイトのデータを超えます。

この方法論は汎用 CPUを超えて、GPUコンピューティングや従来のデジタル信号処理にも適用されます。グラフィックスプロセッシングユニット (GPGPU) での汎用コンピューティングでは、メモリが少ない強力なグラフィックスカード (GPU) (より一般的なシステムメモリ (通常は単にRAMと呼ばれます) と比較) が、比較的低速の CPU から GPU へのメモリ転送 (計算帯域幅と比較) で使用されます。

歴史

「アウトオブコア」という用語が形容詞として最初に使われたのは1962年で、IBM 360のコアメモリ以外のデバイスを指して使われた。^{[6] 「アウトオブコア」という用語が}アルゴリズムに関して最初に使われたのは1971年である。^[7]

参照

参考文献

^ Vitter, JS (2001). 「外部メモリアルゴリズムとデータ構造: 大量データの処理」. ACM Computing Surveys . 33 (2): 209–271. CiteSeerX 10.1.1.42.7064 . doi :10.1145/384192.384193. S2CID 2155038.
^ ab 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。
^ abcd Aggarwal, Alok; Vitter, Jeffrey (1988). 「ソートおよび関連問題の入出力複雑性」Communications of the ACM . 31 (9): 1116–1127. doi : 10.1145/48529.48535 . S2CID 6264984.
^ Demaine, Erik (2002). キャッシュ無視アルゴリズムとデータ構造(PDF) . 大規模データセットに関する EEF サマースクールの講義ノート。オーフス: 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] 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] 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). キャッシュ無視アルゴリズムとデータ構造(PDF) . 大規模データセットに関する EEF サマースクールの講義ノート。オーフス: BRICS。

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

[7] 危機に瀕したコンピュータ。ACM。1971年、296ページ。