Loading article…
メモリ制限とは、特定の計算問題を完了するのにかかる時間が、主に作業データを保持するために必要な空きメモリの量によって決まる状況を指します。これは、基本的な計算ステップの数が決定要因となる 計算制限アルゴリズムとは対照的です。
メモリと計算の境界は、たとえば予備結果を保存して再利用したり、ルックアップ テーブルを使用したりすることで、互いにトレードオフになることがあります。
メモリバウンド関数とメモリ関数
メモリバインド関数とメモリ関数は、どちらも広範なメモリアクセスを伴うという点で関連していますが、両者の間には違いがあります。
メモリ関数は、発生する可能性のある再帰の非効率性を軽減するために、メモ化と呼ばれる動的プログラミング手法を使用します。これは、サブ問題の解を計算して保存し、後でサブ問題を再計算せずに解を再利用するという単純なアイデアに基づいています。メモ化を利用する最もよく知られた例は、フィボナッチ数列を計算するアルゴリズムです。次の疑似コードは、再帰とメモ化を使用し、線形 CPU 時間で実行されます。
フィボナッチ( n ) { i = 0からn -1までの結果[ i ] = -1 // -1 は未定義を意味します
Fibonacci_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 // この結果を再利用のために保存します。
戻り値}
上記を、再帰のみを使用し、指数関数的なCPU 時間で実行されるアルゴリズムと比較します。
Recursive_Fibonacci ( n ) { if ( n == 0 ) 0を返すif ( n == 1 ) 1を返す
再帰フィボナッチ( n -1 ) +再帰フィボナッチ( n -2 )を返す}
再帰のみのアルゴリズムは、再帰とメモ化を使用するアルゴリズムよりもシンプルでエレガントですが、後者は前者よりも 時間の複雑さが大幅に低くなります。
「メモリバウンド関数」という用語はごく最近登場したばかりで、主に XOR を使用し、各計算が前の計算に依存する一連の計算で構成される関数を説明するために使用されます。メモリ関数は長い間、時間計算量の改善に重要な役割を果たしてきましたが、メモリバウンド関数の用途ははるかに少なくなりました。しかし最近[いつ? ]、スパマーによるリソースの乱用を阻止する手段としてメモリバウンド関数を使用する方法を科学者が提案しました。これは、この分野で大きな進歩となる可能性があります。
メモリバウンド関数を使用してスパムを防ぐ
メモリにバインドされた関数は、インターネット上で蔓延する問題となっているスパムを阻止できるプルーフ・オブ・ワーク・システムで役立つ可能性がある。
1992年、IBMの研究科学者であるシンシア・ドワークとモニ・ナオールは、 CRYPTO 1992で「ジャンクメールの処理または対策による価格設定」と題する論文[1]を発表し、CPUバウンド機能を使用してスパム送信を阻止する可能性を示唆しました。このスキームは、リソースの悪用にかかるコストが無視できるほど小さい場合、コンピューターユーザーがリソースを悪用する可能性が非常に高くなるという考えに基づいています。スパムがこれほど蔓延している根本的な理由は、スパム送信者にとって電子メールの送信コストがごくわずかであることです。
Dwork 氏と Naor 氏は、高価なCPU計算という形で追加コストを投入することでスパムを削減できると提案しました。CPU にバインドされた関数は、メッセージごとに送信者のマシンの CPU リソースを消費し、短期間に大量のスパムが送信されるのを防ぎます。
不正使用を防ぐための基本的な仕組みは次のとおりです。
送信者、受信者、および電子メール メッセージがあるとします。受信者が送信者からの電子メールを受信することに事前に同意している場合、メッセージは通常の方法で送信されます。そうでない場合、送信者は何らかの関数G(Message)を計算し、(Message, G(Message)) を受信者に送信します。受信者は、送信者から受信したものが(Message, G(Message))の形式であるかどうかを確認します。そうである場合、受信者はメッセージを受け入れます。そうでない場合、受信者はメッセージを拒否します。
関数G()は、受信者による検証が比較的高速 (たとえば、1 ミリ秒かかる) で、送信者による計算がやや低速 (少なくとも数秒かかる) になるように選択されます。したがって、送信者は事前の合意なしに複数の受信者にメッセージを送信することは控えることになります。G() を繰り返し計算する時間と計算リソースのコストは、何百万通もの電子メールを送信しようとするスパマーにとっては非常に高額になります。
上記の方式を使用する際の主な問題は、高速 CPU は低速 CPU よりも計算がはるかに高速であることです。さらに、ハイエンドのコンピュータ システムには、計算を容易にする洗練されたパイプラインやその他の有利な機能もあります。その結果、最先端のシステムを使用するスパマーはこのような抑止力の影響をほとんど受けませんが、平凡なシステムを使用する一般的なユーザーは悪影響を受けます。新しいPCで計算に数秒かかる場合、古い PC では 1 分、PDAでは数分かかることがあります。これは、古い PC のユーザーにとっては煩わしいかもしれませんが、PDA のユーザーにとってはおそらく受け入れられないでしょう。クライアント CPU 速度の不一致は、CPU バウンド機能に基づく方式の広範な採用に対する主な障害の 1 つを構成します。したがって、研究者は、ほとんどのコンピュータ システムでほぼ同じ速度で評価される関数を見つけることに関心があります。これにより、CPU の差異が示唆するように、ハイエンド システムはこれらの関数をローエンド システムよりもいくらか速く評価する可能性があります (2 ～ 10 倍の速さですが、10 ～ 100 倍の速さではありません)。これらの比率は、意図されたアプリケーションにとって十分に「平等」です。つまり、関数は不正使用を阻止するのに効果的であり、さまざまなシステムで正当なやり取りに法外な遅延を追加しません。
新しい平等主義的アプローチは、メモリバウンド関数に頼ることです。前述のように、メモリバウンド関数とは、計算時間がメモリへのアクセスに費やされる時間によって左右される関数です。メモリバウンド関数は、予測できない方法でメモリの大きな領域内の場所にアクセスするため、キャッシュの使用は効果的ではありません。近年、CPU の速度は劇的に向上しましたが、より高速なメインメモリの開発は比較的小さな進歩しかありません。過去 5 年間に製造されたマシンのメモリ レイテンシの比率は通常 2 を超えず、ほとんどの場合 4 未満であるため、メモリバウンド関数は、近い将来、ほとんどのシステムに対して平等主義的になります。
参照
参考文献
- ^ Dwork, Cynthia ; Naor, Moni (1992). 「処理による価格設定または迷惑メール対策」。暗号学の進歩 — CRYPTO' 92。コンピュータサイエンスの講義ノート。第 740 巻。pp. 139–147。doi : 10.1007 / 3-540-48071-4_10。ISBN 978-3-540-57340-1。（同じものの更新版）
- Abadi, M., Burrows, M., Manasse, M., & Wobber, T. (2005 年 5 月)。「中程度に難しい、メモリにバインドされた関数」、ACM Transactions on Internet Technology。
- Dwork, C.、Goldberg, A.、Naor, M. (2003)。スパム対策のためのメモリ結合関数について、Advances in Cryptology。
- Hellman, ME (1980)。暗号解析における時間とメモリのトレードオフ、IEEE Transactionson Information Theory。
外部リンク
- メモリバウンド関数の実装
- コンピュータアーキテクチャ
- コンピュータメモリの仕組み
- 動的プログラミング
- CPU バウンドと I/O バウンド
- スパム – FTC 消費者情報