ハードドライブを増設するとコンピューターの性能が上がる理由

この物語 のオリジナル版はQuanta Magazineに掲載されました。

「明らかに」という言葉は、一見単純なシナリオであっても危険な言葉です。例えば、重要な計算をしなければならないとします。2台のコンピューターのどちらかを選ぶことになりますが、片方には大切な家族写真が詰まった予備のハードドライブが搭載されています。どちらの選択肢も同じように優れていると考えるのは自然なことです。空き容量のない予備ドライブでは計算に役立たない、と考えるでしょう。

「明らかに、役に立たないですよね？」とリスボン大学のコンピューター科学者ブルーノ・ロフ氏は言う。

それは間違いだ。2014年、ロフ氏と他の4人の研究者は、ストレージ容量をフルに増やすことで原理的にコンピューターの性能を向上できることを発見した。彼らの理論的枠組み「触媒コンピューティング」は、それ自体が研究対象となっている。そして最近、この理論枠組みは、コンピューターサイエンスの関連分野における驚くべき結果を証明するのにも役立った。計算におけるメモリの役割に関する大きな未解決の疑問を解決するための標準的なアプローチは、おそらく行き詰まっているのだ。

「これは本当に偉業です」と、モントリオール大学の複雑性理論家ピエール・マッケンジー氏は述べた。「この成果には本当に感謝しています。」

記憶がほとんどない

触媒コンピューティングは、様々な問題を解決するために必要なリソースに焦点を当てたコンピュータサイエンスの一分野である計算複雑性理論の研究から生まれました。複雑性理論家が考えるすべての問題は、アルゴリズムと呼ばれる段階的な手順で解決できます。しかし、すべてのアルゴリズムが同じように作られているわけではありません。あるアルゴリズムは他のアルゴリズムよりも高速に実行されたり、コンピュータのメモリ容量をあまり必要としなかったりします。複雑性理論家は、問題を、その問題を解決するために知られている最良のアルゴリズムの挙動に基づいて、様々なクラスに分類します。

最も有名なクラス「P」には、リスト内の最小の数字を求める問題や、ネットワーク内の2点間の最短経路を求める問題など、高速アルゴリズムが知られているすべての問題が含まれます。「L」と呼ばれる別のクラスは、より高度な基準を設けています。Lに属する問題は、高速であるだけでなく、メモリをほとんど消費しないアルゴリズムでなければなりません。「リスト内の最小の数字」問題はその一例です。定義上、Lに属するすべての問題はPにも当てはまりますが、研究者たちは長い間、逆もまた真であるのではないかと考えてきました。

「基本的な疑問は、P のあらゆる問題を非常に少ないメモリで解決できるかどうかだ」とマッケンジー氏は言う。

ほとんどの研究者は、答えは「ノー」だと考えています。それを証明するには、Pの特定の問題を選び、どんな巧妙なメモリ節約術を使っても解決できないことを示す必要があります。

2000年代後半、マッケンジーと複雑性理論の先駆者であるスティーブン・クックは、有望な候補と思われる問題を考案しました。木評価問題と呼ばれるこの問題は、2つの入力数値を1つの出力に変換する、より単純な数学問題を繰り返し解くというものです。この数学問題のコピーは、トーナメント表の試合のように層状に並べられます。各層の出力は次の層への入力となり、最終的に出力が1つになるまで続きます。異なる木評価アルゴリズムは、初期入力からこの最終出力を計算するための異なる戦略を表します。計算を実行する順序が異なったり、中間ステップの結果を記録する方法が異なったりします。

多くのアルゴリズムは木評価問題を迅速に解くことができ、クラスPに分類されます。しかし、そのようなアルゴリズムはどれも、処理対象の数値にメモリを割り当て、同時に後続のステップで使用するために既に計算済みの数値も保存する必要があります。そのため、クックとマッケンジーは、限られたメモリではこの問題を解くことは不可能だと考えました。彼らはこの直感を、他の3人の研究者と共著した2010年の論文で定式化し、木評価問題を解く一般的なアルゴリズムはすべて、Lに属するにはメモリが大きすぎることを証明しました。

しかし、彼らの研究は、何らかの方法で同じメモリをストレージと計算に同時に使用できる奇妙なアルゴリズムの可能性を排除したわけではなかった。これは、重要なメモがぎっしり詰まったページをメモ用紙として使うようなコンピューター上の話だ。クックとマッケンジーは、そのような突飛なアルゴリズムは存在しないと考え、自信を持って賭けに出た。彼らの誤りを証明できれば、なんと100ドルの賞金がもらえるというのだ。

触媒変換

プラハ・カレル大学の複雑性理論家、ミハル・コウキーは、2011年にトロントで休暇を過ごしていた際に、クックから木の評価結果について学びました。コウキーは、クックとマッケンジーが始めた研究を完遂しようと決意を固めました。つまり、データを後回しにするメモリを使って追加の計算を行う方法はないことを証明しようと。コウキーの探求は、彼を予期せぬ迂回路へと導き、触媒コンピューティングの発見へと繋がるのです。約10年後、この発見は二人の若い研究者を木の評価へと導き、クックとマッケンジーの賭けに決着をつけることになりました。

さて、触媒コンピューティングの話に戻りましょう。すべては、クーキーがアムステルダムの同僚を訪ね、ずっと気になっていた疑問をもっとシンプルな言葉で投げかけたことから始まりました。「すでにいっぱいになっているメモリで何ができるのか？」

「何もない」というのが当然の答えだった。「『わかった、これはもちろん全く役に立たない。だから証明してみせる』と思ったんです」と、アムステルダム・グループのリーダー、ハリー・バーマンは言った。「でも、結局証明できなかったんです」

ブレイクスルーは数ヶ月後、バーマンがウォータールー大学で長年の共同研究者であるリチャード・クリーブを訪ねていた時に起こりました。彼らは、メモリ容量が非常に大きいという極端なシナリオに焦点を当てることにしました。空きメモリがほとんどないコンピューターが、この膨大なメモリ容量にアクセスできるとしたら、空きメモリだけでは解決できない問題を解決できるでしょうか？これは「家族写真でいっぱいのハードドライブ」の問題に似ていますが、ハードドライブの容量はデータセンターほどです。

もしその追加データが触れられない、つまり全く操作できないのであれば、それは全く役に立ちません。しかし、もしこのデータをエンコードするビットの一部を微調整できるとしたらどうでしょうか。ただし、変更後はリセットすることを約束すれば良いのです。変更内容を単に記録するだけでは、さらに多くのスペースを消費してしまうので、変更が簡単に元に戻せるようにする必要があります。さらに、追加データの内容を選択できないため、何をしても、ビットの初期設定がどのようなものであっても、必ず適用されなければなりません。

これらは非常に厳しい制約であるため、追加メモリが実際に役立つかどうかは明らかではありませんでした。しかし、Buhrman氏とCleve氏は驚くべきことに、適切な方法でビットを調整することで、メモリがいっぱいの状態からさらに計算能力を引き出せることを実証しました。

「それは誰にとっても衝撃的でした」と、当時バーマンのグループの大学院生で、同僚のフロリアン・スピールマンと共に記憶の問題に取り組んでいたロフは語った。チームはすぐにこの結果をさらに広範な問題群に拡張し、2014年に統合結果を発表した。

彼らはこの新しい枠組みを、化学用語を借用して「触媒コンピューティング」と名付けた。「触媒がなければ、反応は進行しなかったでしょう」と、インド工科大学カンプール校の複雑性理論家、ラグナス・テワリ氏は述べた。「しかし、触媒そのものは変化しません。」

木から遠くない

少数の研究者が触媒コンピューティングの開発を続けましたが、コウキーの探求のきっかけとなった木評価問題にそれを適用しようと試みる者は誰もいませんでした。この問題において、残された未解決の問題は、少量のメモリをストレージと計算に同時に使用できるかどうかでした。しかし、触媒コンピューティングの技術は、余分なメモリが非常に大きいことを前提としていました。メモリを縮小すると、この技術はもはや機能しなくなります。

それでも、ある若い研究者は、これらの手法を木評価アルゴリズムのメモリ再利用に応用する方法があるのではないかと考えずにはいられませんでした。彼の名前はジェームズ・クック。彼にとって木評価問題は個人的な問題でした。木評価を考案した伝説的な複雑性理論家、スティーブン・クックは彼の父です。ジェームズは大学院時代にも木評価に取り組んでいましたが、主に全く関係のない分野に注力していました。2014年に触媒コンピューティングの最初の論文に出会った頃、ジェームズは卒業を控え、学界を離れてソフトウェアエンジニアリングの道に進むところでした。しかし、新しい仕事に落ち着いてからも、彼は触媒コンピューティングのことを考え続けていたのです。

「私はそれを理解し、何ができるかを知る必要があった」と彼は語った。

ジェームズ・クックは長年、余暇を利用して木構造評価問題に対する触媒的アプローチに取り組んでいました。2019年、複雑性理論における父の画期的な研究を称えるシンポジウムで、彼は自身の研究の進捗状況について講演しました。講演後、イアン・メルツという大学院生が彼に近づきました。メルツは5年前、感受性の強い若い学部生時代に触媒コンピューティングについて知り、その魅力に魅了されていました。

「それはまるで雛鳥の刷り込みのシナリオのようでした」とメルツ氏は語った。

クックとメルツは協力し、その努力はすぐに実を結んだ。2020年、彼らはクックとマッケンジーが推測した必要最小限のメモリよりも少ないメモリで木評価問題を解くアルゴリズムを考案した。ただし、その閾値をわずかに下回る程度だった。それでも、100ドルの賭け金を回収するには十分だった。クック夫妻にとって都合の良いことに、その半分は一族の財産となった。

しかし、まだやるべきことは残っていました。研究者たちは、木評価の研究を始めました。なぜなら、木評価が、LにはないPの問題、つまり非常に少ないメモリでは解けない比較的簡単な問題の例をついに提供してくれるかもしれないと思ったからです。クックとメルツの新しい手法は、他のどの木評価アルゴリズムよりもメモリ使用量は少なかったものの、Lの問題を扱うどのアルゴリズムよりも大幅に多くのメモリを消費しました。木評価は成功しましたが、完全に消えたわけではありませんでした。

2023年、クックとメルツは、メモリ使用量を大幅に削減した改良アルゴリズムを発表しました。これは、Lの問題に許容されるメモリの最大値とほとんど変わらないものでした。現在、多くの研究者は、木構造の評価は結局Lで行われ、証明は時間の問題であると考えています。複雑性理論家は、P対L問題に対して異なるアプローチを必要とするかもしれません。

一方、クックとメルツの研究成果は触媒コンピューティングへの関心を刺激し、新たな研究ではランダム性とのつながりや、完全なメモリを元の状態にリセットする際にいくつかの間違いを許容することの影響が研究されている。

「これらの新しい技術で何ができるかの探求はまだ終わっていません」とマッケンジー氏は述べた。「さらに驚くべき発見が期待できます。」

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。