Loading article…
コンピュータサイエンスにおいて、計算問題の完了にかかる時間が、主に処理データを保持するために必要な空きメモリ量によって決まる場合、その計算問題はメモリバウンドであると言えます。これは、基本計算ステップの数が決定要因となる計算量バウンドのアルゴリズムとは対照的です。
メモリと計算の制約は、例えば予備的な結果を保存して再利用したり、ルックアップテーブルを使用したりすることで、互いにトレードオフされることがあります。
メモリ依存関数とメモリ関数は、どちらも大規模なメモリアクセスを伴うという点で関連しているが、両者の間には違いが存在する。
メモリ関数は、発生する可能性のある再帰の非効率性を軽減するために、メモ化と呼ばれる動的計画法の手法を使用します。これは、部分問題の解を計算して保存し、後で部分問題を再計算することなく解を再利用できるようにするという単純なアイデアに基づいています。メモ化を活用した最もよく知られた例は、フィボナッチ数列を計算するアルゴリズムです。次の擬似コードは再帰とメモ化を使用しており、線形CPU時間で実行されます。
Fibonacci ( n ) { for i = 0 to n -1 results [ i ] = -1 // -1 は未定義を意味しますreturn Fibonacci_Results ( results , n ); }Fibonacci_Results ( results , n ) { if ( results [ n ] != -1 ) // 以前に解かれた場合は、results [ n ]を返します// 調べます。if ( n == 0 ) val = 0 else if ( n == 1 ) val = 1 else val = Fibonacci_Results ( results , n -2 ) + Fibonacci_Results ( results , n -1 ) results [ n ] = val // 再利用のためにこの結果を保存します。return val }上記を、再帰のみを使用し、 CPU時間が指数関数的に増加するアルゴリズムと比較してみましょう。
Recursive_Fibonacci ( n ) { if ( n == 0 ) return 0 if ( n == 1 ) return 1return Recursive_Fibonacci ( n -1 ) + Recursive_Fibonacci ( n -2 ) }再帰のみを用いるアルゴリズムは、再帰とメモ化を用いるアルゴリズムよりも単純で洗練されているが、後者のアルゴリズムは前者よりも時間計算量が大幅に低い。
「メモリ制約関数」という用語は比較的最近になって使われるようになったもので、主にXOR演算を用い、各計算が前の計算に依存する一連の計算から構成される関数を指す。メモリ関数は時間計算量を改善するための重要なツールとして長年用いられてきたが、メモリ制約関数の応用例ははるかに少ない。
メモリに制約された関数は、インターネット上で蔓延している問題となっているスパムを抑止できるプルーフ・オブ・ワークシステムにおいて有用である可能性がある。
1992年、IBMの研究科学者であるシンシア・ドワークとモニ・ナオールは、 CRYPTO 1992で「処理による価格設定または迷惑メール対策」[ 1 ]というタイトルの論文を発表し、 CPUバウンド関数を使用してスパム送信者を抑止できる可能性を示唆した。このスキームは、リソースを悪用するコストが無視できるほど小さい場合、コンピュータユーザーがリソースを悪用する可能性がはるかに高くなるという考えに基づいていた。スパムがこれほど蔓延している根本的な理由は、電子メールの送信コストがスパマーにとって非常に小さいからである。
ドワークとナオールは、高コストなCPU計算という形で追加コストを導入することで、スパムを減らすことができると提案した。CPU負荷の高い関数は、メッセージごとに送信者のマシンのCPUリソースを消費するため、短期間に大量のスパムが送信されるのを防ぐことができるというのだ。
不正利用を防ぐための基本的な仕組みは次のとおりです。 送信者、受信者、および電子メールメッセージが与えられた場合、受信者が事前に送信者からの電子メールの受信に同意していれば、メッセージは通常の方法で送信されます。そうでない場合、送信者は何らかの関数G(メッセージ)を計算し、(メッセージ、G(メッセージ))を受信者に送信します。受信者は、送信者から受信したものが(メッセージ、G(メッセージ))の形式であるかどうかを確認します。形式が正しい場合、受信者はメッセージを受け入れます。そうでない場合、受信者はメッセージを拒否します。
関数G()は、受信者による検証が比較的速く（例えば1ミリ秒程度）、送信者による計算がやや遅く（少なくとも数秒かかる）なるように選択されています。そのため、送信者は事前の合意なしに複数の受信者にメッセージを送信することを躊躇するようになります。G ()を繰り返し計算する時間と計算リソースの両面におけるコストは、何百万通もの電子メールを送信しようとするスパマーにとって非常に大きな負担となるからです。
上記の方式を使用する際の主な問題点は、高速なCPUは低速なCPUよりもはるかに高速に計算できるという点です。さらに、高性能なコンピュータシステムには、計算を容易にする高度なパイプラインやその他の有利な機能も備わっています。その結果、最新鋭のシステムを持つスパマーは、このような抑止策の影響をほとんど受けませんが、性能の低いシステムを持つ一般的なユーザーは悪影響を受けます。新しいPCでは数秒で済む計算が、古いPCでは1分、PDAでは数分かかる場合があり、古いPCのユーザーにとっては迷惑かもしれませんが、PDAのユーザーにとっては恐らく許容できないでしょう。クライアントCPUの速度の差は、CPUバウンド関数に基づく方式の普及を阻む大きな障害の一つとなっています。そのため、研究者たちは、ほとんどのコンピュータシステムがほぼ同じ速度で評価できる関数を見つけることに注力しています。そうすることで、高性能システムは低性能システムよりもこれらの関数を多少高速に評価できる（CPUの差が示唆するような10～100倍ではなく、2～10倍高速）ようにできるからです。これらの比率は、意図された用途において十分に「平等」である。つまり、これらの機能は不正行為を抑制するのに効果的であり、幅広いシステムにおいて正当なやり取りに不当な遅延を加えることはない。
新しい平等主義的なアプローチは、メモリバウンド関数に依存することです。前述のとおり、メモリバウンド関数とは、計算時間がメモリへのアクセス時間によって支配される関数です。メモリバウンド関数は、メモリの広い領域内の場所に予測不可能な方法でアクセスするため、キャッシュを使用しても効果的ではありません。近年、CPUの速度は飛躍的に向上しましたが、より高速なメインメモリの開発は比較的小さな進歩にとどまっています。過去5年間に製造されたマシンのメモリレイテンシの比率は通常2以下であり、ほとんどの場合4以下であるため、メモリバウンド関数は、当面の間、ほとんどのシステムにとって平等な選択肢となるでしょう。