数学と計算

ランダム行列の実験

乱数を詰めた大きな行列を繰り返し対角化し、固有値の統計を調べます。

答える問い: ランダム行列の固有値は、どんなパターンに落ち着くのでしょうか。また、それは数学や物理のほかの分野と一致するでしょうか。

含まれないもの： 可能な行列の無限の空間の、ごく小さな一角しか標本にできません。

動かすのに必要： 約10¹² FLOPS 概算 多数の大きな行列を生成して対角化する大学のクラスター最初の年： 1955 Wigner による、ランダム行列の固有値統計についての初期の研究

ランダムグラフの実験

ノードごと、または辺ごとにランダムな規則でグラフを作り、連結性やクラスタリングなど、どんな性質が典型的に現れるかを調べます。

答える問い: ノードと辺を足すこの規則のもとで、「典型的な」ネットワークはどんな姿をしているでしょうか。

含まれないもの： 実世界のネットワークが、モデルを生む規則ほどきれいであることは、まれです。

動かすのに必要： 約10¹⁰ FLOPS 概算 デスクトップで、最大数百万ノードのグラフまで動きます最初の年： 1959 Erdos と Renyi のランダムグラフ・モデル

パーコレーションのシミュレーション

格子やネットワークの点や結合をランダムに開いていき、つながった経路が系全体を突然貫く点を観察します。

答える問い: どのくらいの密度で、ランダムなネットワークは突然、端から端までつながるのでしょうか。

含まれないもの： 理想化された格子は、実際のどんな多孔質材料やネットワークよりも、すっきりと振る舞います。

動かすのに必要： 約10¹⁰ FLOPS 概算 大規模な格子の掃引に使うデスクトップ機最初の年： 1957 Broadbent と Hammersley による、パーコレーション理論の導入

実験数学の探索

数どうしのパターン、反例、厳密な関係を力ずくの数値探索で探すこと。手作業では確かめられない範囲をはるかに超えて実行されます。

答える問い: この予想は、誰もが確かめられる範囲のすべての場合に成り立つでしょうか。そして、そこにパターンは現れるでしょうか。

含まれないもの： 確かめたケースをいくら重ねても、それは証明ではありません。成り立つ例がどれだけ見つかっても同じです。

動かすのに必要： 約10¹¹ FLOPS 概算 ひとつの探索のために数日間動かし続ける大学のクラスター最初の年： 1963 1963年までに、整数関係と素数のパターンのコンピューター探索

モンテカルロ法による定数の推定

点を散らして面積を推定するように、ランダムなサンプリングで数学的な定数や積分を推定します。物理モデルのためではなく、練習問題として行います。

答える問い: でたらめな無作為抽出だけで、正確な数学的な量をどこまで絞り込めるでしょうか。

含まれないもの： より洗練されたほとんどの数値手法よりも、はるかにゆっくりと収束します。

動かすのに必要： 約10⁹ FLOPS 概算 ノートパソコンで数秒から数分で動きます最初の年： 1946 1946年の Ulam の着想です。von Neumann が1947年3月に電子計算機版を提案し、この方法は1949年に初めて発表されました 出典シミュレーションのツリーで: モンテカルロ法

インタラクティブ・モデルを動かす

計算による整数論の探索

大きな数について、素数判定、素因数分解、あるいは完全数のような特別な性質の探索を、手作業ではなく大規模に動かすアルゴリズムで行います。

答える問い: この巨大な数は、探している性質をもつでしょうか。また、探索は記録をどこまで押し上げられるでしょうか。

含まれないもの： 記録を更新する探索は、まだ誰も確かめようと思いついていない数については、ほとんど何も語りません。

動かすのに必要： 約10¹³ FLOPS 概算 多数の寄付されたマシンにまたがる、分散型のボランティア・コンピューティング・プロジェクト最初の年： 1951 リュカによるメルセンヌ素数の手計算での判定。1951年に初めてコンピューターで実行されました

カオス的アトラクターの数値計算

少数の非線形方程式を1段ずつ積分し、初期条件への敏感な依存と、フラクタルなアトラクターを明らかにします。

答える問い: 単純な決定論的システムが、予測不能になるのはなぜでしょうか。

含まれないもの： 数値の丸めのせいで、長い軌道は真の軌道ではなく、真の軌道の近くにとどまるだけのものです。

動かすのに必要： 約10³ FLOPS 概算 いくつかの方程式、ノートパソコンで数秒。最初の年： 1963 ローレンツの決定論的な非周期流。コンピューターで動かした対流モデルです。 出典シミュレーションのツリーで: ローレンツのカオス的対流

非線形格子の実験

非線形のばねでつないだ質点の鎖を、ひとつのモードで動かし始め、熱力学が示すようにエネルギーが均等に広がるかどうかを追います。

答える問い: 非線形の鎖は、そのすべての運動に、エネルギーを均等に分け与えるでしょうか。

含まれないもの： 結果は、選んだ鎖と初期状態に左右されます。

動かすのに必要： 約10³ FLOPS 概算 現代の基準ではごく小さく、もとのものは数十個の質量を使っていました。最初の年： 1955 Fermi、Pasta、Ulam による、初期のデジタルコンピューターでの非線形問題の研究。 出典

ソリトンの数値実験

非線形の波動方程式を格子上で解き、パルスが互いをすり抜けても形を保つようすを観察します。線形の波ではこうなりません。

答える問い: ある非線形波が、互いに変わらずにすり抜けるのはなぜでしょうか。

含まれないもの： 方程式の一つの族を示すだけで、非線形波の一般的な振る舞いは示しません。

動かすのに必要： 約10⁴ FLOPS 概算 1次元の格子で、今ならわけもない。最初の年： 1965 Zabusky と Kruskal による、無衝突プラズマ中のソリトンの相互作用と初期状態の回帰です。 出典

フラクタル集合のレンダリング

複素平面の各点で、単純な反復式を試して発散するかを調べ、安定した点の集合の境界を描きます。

答える問い: 単純な反復が有界にとどまる集合は、どんな形をしているでしょうか。

含まれないもの： 発散の判定は、集合に属するかを示唆するだけで、この図は、無限に細かい集合を有限の解像度でサンプリングしたものです。

動かすのに必要： 約10⁹ FLOPS 概算 深いズームでは、数百万点で拡張精度の反復が必要です。最初の年： 1980 Mandelbrot による、z を λz(1-z) に反復することのフラクタルな側面。マンデルブロ集合を初めてコンピューターで描いた画像。 出典

砂山の自己組織化臨界

格子上に砂粒を落とし、傾きが急になりすぎると崩れる仕組みです。調整しなくてもあらゆる大きさの雪崩が起き、システムが臨界状態に至る様子のモデルになります。

答える問い: 調整しなくても、あらゆる大きさの雪崩が現れるのはなぜでしょうか。

含まれないもの： 実際のシステムが同じスケーリングを共有しているかどうかは、争われています。

動かすのに必要： 約10⁹ FLOPS 概算 スケーリングを見るための、大きな格子上の長い計算。最初の年： 1987 Bak、Tang、Wiesenfeld の自己組織化臨界現象。1/fノイズの説明。 出典

リーマンゼータ関数の零点の計算

ゼータ関数の臨界線上の値を計算して、その零点の位置を突き止めて数え、予想が言う場所にあることを確かめます。

答える問い: ゼータ関数の自明でない零点は、すべてひとつの直線上にあるでしょうか。

含まれないもの： どれほど長く有限の範囲を調べても、その先に臨界線上にない零点が存在しないことは証明できません。

動かすのに必要： 約10¹⁸ FLOPS 概算 最大規模の探索では数十年ぶんのCPU時間。最初の年： 1953 Turing による、リーマンゼータ関数の計算です。 出典

コンピューターによる円周率の桁

π の級数を厳密な算術で膨大な桁数まで足し合わせ、数と機械の両方を試します。

答える問い: 円周率の桁はランダムに見えるでしょうか。また、この規模で機械を信頼できるでしょうか。

含まれないもの： 桁の並びは、未解決の問いのどれにも答えを出しません。また、検算が見つけられるのは、方法が独立している場合のハードウェアの誤りだけです。

動かすのに必要： 約10¹⁷ FLOPS 概算 数百兆桁のために、サーバーで数か月。最初の年： 1950 Reitwiesner による ENIAC での円周率 π と e の2000桁以上の決定(1950年に発表、Pi: A Source Book に再録)。 出典

AIによる予想の発見の支援

数学的対象の大きな表を機械学習にかけて、どの性質が結びついているかを見つけ、数学者があとで証明を試みる予想を示唆します。

答える問い: これらの数学的な量のあいだの、まだ見えていないどんな関係が、証明する価値をもつでしょうか。

含まれないもの： パターンを示唆するだけで、それ自体は何も証明せず、データに見える規則性の一部は、データの作り方による見かけのものかもしれません。

動かすのに必要： 約10¹⁵ FLOPS 概算 データセットごとに、数基のGPUで数日。最初の年： 2021 Davies らによる、AIで人間の直観を導いて数学を前進させる試み。 出典

学習による、アルゴリズムと構成の探索

ゲームをプレイするシステムや言語モデルのシステムが、新しい手順や数学的な対象を探します。コンピューターが各候補の正しさを検証します。

答える問い: プログラムは、人が見つけたより速いアルゴリズムや、より大きな例を発見できるでしょうか。

含まれないもの： 各結果は新しい例がひとつあるだけで、探索が扱うのは、設計者がゲームとして定式化した種類の対象だけです。

動かすのに必要： 約10¹⁷ FLOPS 概算 アクセラレーターのクラスターで数日から数週間。最初の年： 2022 Fawzi らによる AlphaTensor。強化学習でより速い行列乗算のアルゴリズムを発見。 出典

モデル検査

プロトコルや回路設計のような有限なシステムの、到達しうるすべての状態を、コンピューターで列挙し、すべてで性質が成り立つことを確かめます。

答える問い: この設計が自分のルールを破ってしまう、到達可能な状態はあるでしょうか。

含まれないもの： 状態空間は検証できる範囲を超えて爆発的に増えるため、実際の設計はまず簡略化されます。

動かすのに必要： 約10¹² FLOPS 概算 大きいが有限の状態空間を網羅する大学のクラスター最初の年： 1981 Clarke と Emerson による、モデル検査の導入

自動定理証明の探索

論理的推論の連鎖をコンピューターが1段ずつ生成して探索し、数学的な命題の証明または反証を探します。

答える問い: 公理からこの命題に至る、論理的な段階の正しい連鎖は存在するでしょうか。

含まれないもの： 人間なら選ばない証明を見つけ、手の届く範囲では、まったく見つからないこともあります。

動かすのに必要： 約10¹¹ FLOPS 概算 数時間から数日にわたって探索する大学のクラスター最初の年： 1956 初期の自動証明探索プログラム、ロジック・セオリスト

SAT と制約の充足

真偽の値の何百万もの組み合わせを系統的に探索して、大きな論理制約の集合を満たすものを見つけます。スケジューリング、経路探索、設計の検証に使います。

答える問い: これらの制約をすべて同時に満たす値の割り当ては、存在するでしょうか。

含まれないもの： どんなに優れたソルバーでも、時間内に終わらないほど難しい問題があります。

動かすのに必要： 約10¹¹ FLOPS 概算 ワークステーションからクラスターまで、問題の大きさしだい最初の年： 1962 充足可能性探索のためのダヴィス・パトナム法

暗号への攻撃のモデリング

暗号や鍵交換の方式を、シミュレーションで数百万回攻撃します。総当たり、統計的な偏り、モデル化した弱点を使い、破るのに本当にどれだけの労力が要るかを測ります。

答える問い: これを破るには実際に何回の演算が必要で、その数はいまも安全なほど大きいでしょうか。

含まれないもの： アナリストがモデル化しようと考えた攻撃しか検査せず、まだ誰も見つけていない攻撃は検査しません。

動かすのに必要： 約10¹⁴ FLOPS 概算 多数のマシンで攻撃の試行を動かす分散クラスター最初の年： 1976 1976年までに、暗号と鍵交換の強度のコンピューターによる解析

サイドチャネル漏洩のシミュレーション

暗号処理を実行しているあいだの機器の消費電力、タイミング、電磁放射をモデル化し、外から聞き取る人が何を知りうるかを調べます。

答える問い: 数学ではなく装置の物理的な振る舞いを通して、秘密鍵のどれくらいが漏れるでしょうか。

含まれないもの： 実験室の条件では、ノイズの多い実際の装置がふつう漏らすよりも、きれいな信号が得られます。

動かすのに必要： 約10¹⁰ FLOPS 概算 デバイス1つの消費電力やタイミングのトレースをモデル化するワークステーション最初の年： 1996 Kocher による、暗号の実装へのタイミング攻撃の実証

セキュリティプロトコルの検証

通信プロトコルで攻撃者が送りうる、再生しうる、偽造しうるすべてのメッセージを、コンピューターで列挙し、秘密や身元を引き出せないかを調べます。

答える問い: どんなメッセージの並びでも、このプロトコルをだまして、秘密を漏らさせたり、偽の身元を受け入れさせたりできるでしょうか。

含まれないもの： 検証するのは、仕様として書かれたプロトコルであって、実際の実装がとる近道ではありません。

動かすのに必要： 約10¹¹ FLOPS 概算 ワークステーションからクラスターまで。ひとつのプロトコルのメッセージ空間を検査最初の年： 1989 プロトコル検証の基礎となる、ドレフ・ヤオモデル

全数検査によるコンピューター支援証明

定理を有限個の場合のリストに帰着させ、それぞれをプログラムで検証します。人間には、そのすべてを確かめることはできないからです。

答える問い: すべての場合を機械が確認することで、証明を完成させられるでしょうか。

含まれないもの： 信頼は、プログラム、ハードウェア、場合分けの議論に移ります。

動かすのに必要： 約10⁹ FLOPS 概算 元のプログラムで約千時間のメインフレーム時間。今でははるかに少なくて済みます。最初の年： 1977 Appel と Haken による、すべての平面地図は4色で塗り分けられるという証明。コンピューターで検証した可約性を用いました。 出典

検証された数値計算

保証された上下界つきで行う計算。そのため、カオス的アトラクターの存在のように、数値の結果が数学的な命題を証明します。

答える問い: 計算で出した答えは、おそらく正確というだけでなく、正しいと証明できるでしょうか。

含まれないもの： 上界は長い時間で発散することがあり、証明は短い問題や扱いやすい問題に限られます。

動かすのに必要： 約10⁹ FLOPS 概算 区間演算は、計算コストを数倍程度に増やします。最初の年： 2002 Tucker の厳密な常微分方程式ソルバーと、ローレンツ・アトラクターの存在を証明した Smale の第14問題です。 出典

チューリングマシンの列挙

最小の機械の小さなプログラムをすべて動かし、どれが停止し、どれが永遠に動き続けるかを調べて、各サイズで最も長く動いてから停止するものを探します。

答える問い: 小さなプログラムは、止まるまでどれくらい動き続けられるでしょうか。

含まれないもの： 決定不能性とは、どれだけ長く動かしても、分類できない機械が存在するということです。

動かすのに必要： 約10¹⁵ FLOPS 概算 数十億台のマシン。停止しないものについては証明つき。最初の年： 1965 Lin と Rado による、チューリングマシンの問題のコンピューター研究。 出典

統計的モデル検査

ランダムな振る舞いをするシステムを何度もシミュレートし、ある性質に違反する可能性がどれだけあるかを、信頼性をもって見積もります。

答える問い: ランダムなシステムが安全規則を破る確率はどれくらいでしょうか。

含まれないもの： 統計的な実行から得られるのは、信頼水準つきの確率であって証明ではありません。まれな故障には重点サンプリングが必要です。

動かすのに必要： 約10⁹ FLOPS 概算 数千から数百万の、サンプリングされた実行です。最初の年： 2002 Younes と Simmons による、受容サンプリングを用いた離散事象システムの確率的検証です。 出典

ファズテスト

プログラムに膨大な数のランダムな入力や変異させた入力を与え、クラッシュするものを探します。実質的には、敵意のある、あるいは不注意な世界をシミュレートしています。

答える問い: どんな入力が、このソフトウェアを失敗させるでしょうか。

含まれないもの： 見つかるのは、ランダムな入力が届く故障だけです。まれなケースの陰にバグが隠れたまま、プログラムが何年も合格することもあります。

動かすのに必要： 約10¹⁴ FLOPS 概算 大規模なコードベースで、マシン年単位の CPU 時間。最初の年： 1990 Miller、Fredriksen、So による、UNIX のユーティリティの信頼性についての実証研究。 出典

記号実行

プログラムを、未知の入力を記号で書いたまま動かし、各経路の条件を集めます。そのうえでソルバーが、各分岐に進む値を見つけます。

答える問い: どんな入力なら、このプログラムの各経路が実行され、そのどれかがバグに行き着くでしょうか。

含まれないもの： 経路の数はプログラムの大きさとともに指数関数的に増えるので、大きなプログラムは一部しか網羅できません。

動かすのに必要： 約10¹² FLOPS 概算 プログラム1本あたり数時間のソルバー時間。経路数が増えると急激に増えます。最初の年： 1976 King による、記号実行とプログラムのテスト。 出典

抽象解釈

プログラムを1つの値ではなく範囲のような値の集合で動かし、すべての入力で成り立つ性質を証明します。

答える問い: このプログラムは、どんな入力でも、ゼロで割ったりオーバーフローしたりすることがありえるでしょうか。

含まれないもの： 安全側の近似は誤報を増やすため、人はそれでも一つ一つの警告を確かめなければなりません。

動かすのに必要： 約10¹¹ FLOPS 概算 大規模な航空電子機器のコードベースでワークステーションで数時間。最初の年： 1977 Cousot と Cousot による抽象解釈。プログラムの静的解析のための、統一された束のモデル。 出典

有界モデル検査

設計の一定のステップ数までの振る舞いを論理式として書き、充足可能性ソルバーに渡して、バグにつながる短い経路を見つけます。

答える問い: この回路やプログラムは、決められたステップ数以内にエラー状態に到達しうるでしょうか。

含まれないもの： 別の議論でそれで十分だと示されない限り、ステップ数の上限を超えたことは何も証明しません。

動かすのに必要： 約10¹³ FLOPS 概算 1物件あたりサーバーで数時間。最初の年： 1999 Biere、Cimatti、Clarke、Zhu による、BDDを使わない記号的モデル検査。 出典

プロパティベースのランダムテスト

いつも成り立つはずの規則を書き、コンピューターが多数のランダムな事例を作ります。失敗があれば、小さな反例になるまで縮めます。

答える問い: このコードは、幅広い入力に対して、自らの仕様に従うでしょうか。

含まれないもの： ランダムなケースでは、まれな条件に決して届かないかもしれず、書き出した性質が、重要なものでないかもしれません。

動かすのに必要： 約10⁹ FLOPS 概算 ノートパソコンで数千のケースに数分。最初の年： 2000 Claessen と Hughes による、Haskellプログラムのためのランダム・テストの軽量ツール QuickCheck。 出典

ニューラルネットワークの検証

制約ソルバーが、領域内のすべての入力についてニューラルネットワークの出力が範囲内にとどまることを、標本を試すのではなく証明します。

答える問い: 入力をほんの少し変えるだけで、ネットワークが間違った答えを出すことはありえるでしょうか。

含まれないもの： 証明は小さなネットワークまでしか広げられず、検証できる摂動の範囲も狭いままです。

動かすのに必要： 約10¹³ FLOPS 概算 小さなネットワークでサーバーで数時間から数日。最初の年： 2017 Katz らによる Reluplex。深層ニューラルネットワークを検証するための SMT ソルバー。 出典

コンピューターアーキテクチャのシミュレーション

提案されたプロセッサーのパイプライン、キャッシュ、分岐予測器を命令ごとにモデル化し、作る前にチップの速度を見積もります。

答える問い: このプロセッサ設計は、シリコンを作る前に、実際のプログラムをどれくらい速く動かせるでしょうか。

含まれないもの： 実際のチップを十分に単純化しているため、最終的なシリコンはモデルと必ず少し違います。

動かすのに必要： 約10¹¹ FLOPS 概算 ベンチマーク・プログラムをモデルで動かす大学のクラスター最初の年： 1990 1990年までに、アーキテクチャ研究のためのサイクル精度のプロセッサー・シミュレーター

分散システムとコンセンサスのシミュレーション

多数のコンピューターが、遅延、取りこぼし、故障を伴ってメッセージを送り合う様子をモデル化し、分散アルゴリズムがそれでも正しい答えで合意できるかを試します。

答える問い: このアルゴリズムは、メッセージが失われたり遅れたり、ノードがクラッシュしたりしても、なお正しい合意に到達するでしょうか。

含まれないもの： 注入される故障は設計者が予想したものであり、本番で思いがけず起きるものではありません。

動かすのに必要： 約10¹⁰ FLOPS 概算 数百の仮想ノードをシミュレートするクラスター最初の年： 1978 Lamport による、分散システムにおける順序づけと障害についての初期の研究

ストレージシステムのシミュレーション

ディスク、ドライブ、ファイルシステムを、データの配置のしかた、故障、復旧についてモデル化し、実際のドライブを買って埋める前に、ストレージの設計を試します。

答える問い: このストレージの設計は、まず実機で試すには費用がかかりすぎる規模で、どれだけ性能を出し、故障に耐えるでしょうか。

含まれないもの： 実際のドライブは、モデルのランダムな故障率よりも、もっと乱雑で、相関のある形で壊れます。

動かすのに必要： 約10¹⁰ FLOPS 概算 ワークステーションから小規模なクラスターまで。ストレージ・アレイをモデル化最初の年： 1988 1988年までに、ディスクアレイの信頼性のシミュレーション・モデル

オペレーティングシステムのスケジューラーのシミュレーション

到着してプロセッサーを奪い合う計算タスクの流れをモデル化し、さまざまなスケジューリング規則で動かして、どれがもっとも公平か、もっとも速いかを調べます。

答える問い: 作業の待ち行列をどう並べれば、いちばん多くの仕事が片づくか、あるいは、どの作業にもいちばん公平になるでしょうか。

含まれないもの： 合成したワークロードが、実際の機械が出会うまちまちなタスクの混ざり方と一致することはめったにありません。

動かすのに必要： 約10⁹ FLOPS 概算 ノートパソコンまたはワークステーションで数秒から数分で動きます最初の年： 1968 1968年までに、プロセッサーのスケジューリング方針のシミュレーション研究

コンパイラとプログラム最適化の探索

コードの小さな変種を膨大に試して測定し、同じ仕事をする最も速い、あるいは最も短い版を探します。

答える問い: この小さなコードを書き表す同等の方法のうち、実際にいちばん速いのはどれでしょうか。

含まれないもの： 見つかるプログラムには、あまりに変わっていて、なぜ動くのか説明がつかないものもあります。

動かすのに必要： 約10¹⁰ FLOPS 概算 膨大なコードの変種を探索するクラスター最初の年： 2006 2006年までに、短い命令列に対するスーパー最適化の探索

アルゴリズムの性能を実際に測るテスト

ランダムに生成した、あるいは現実の、大きさを増していく入力でアルゴリズムを何千回も動かし、紙の上で証明するのではなく、実行時間が実際にどう増えるかを測ります。

答える問い: このアルゴリズムの実行時間は、実際に出会う入力に対して、現実にはどう伸びるでしょうか。

含まれないもの： テスト入力にない最悪のケースは、実際に起きるまで見つかりません。

動かすのに必要： 約10⁹ FLOPS 概算 多数の生成されたテスト入力にわたって、ワークステーションで動きます最初の年： 1970 1970年までに、アルゴリズムの実行時間の体系的な実証テスト

言語モデルによるプログラム実行

言語モデルが、プログラムが計算するはずの中間状態を、段階を追って書き出します。

答える問い: 言語モデルは、コードの実行をエミュレートできるでしょうか。

含まれないもの： 出力が正しいとは限らず、長いプログラムは失敗します。

動かすのに必要： 約10¹⁴ FLOPS 概算 問い合わせごとの推論最初の年： 2021 Show your work: scratchpads for intermediate computation with language models (2021) 出典

ブロックチェーンのコンセンサスのシミュレーション

遅延のもとでブロックを作って共有するノードのネットワークで、ブロックの大きさ、タイミング、攻撃者がセキュリティとスループットにどう影響するかを調べます。

答える問い: ネットワークの遅延や攻撃のもとで、ブロックチェーンはどれくらい安全で、どれくらい速いでしょうか。

含まれないもの： 実際のノードの振る舞いとネットワークの構造は、部分的にしか測られていません。

動かすのに必要： 約10⁸ FLOPS 概算 数千ノードのイベント駆動の実行。最初の年： 2016 Gervais らによる、シミュレーターを用いたプルーフ・オブ・ワーク型ブロックチェーンの安全性と性能の分析。 出典

並列離散事象シミュレーション

時間の中の出来事のシミュレーションを多数のプロセッサーに分け、それぞれが自分の時計を進め、遅れて届くものがあれば巻き戻します。

答える問い: ネットワークや戦場のような、巨大なイベント駆動のシミュレーションを、多数のマシンで高速に動かすにはどうすればよいでしょうか。

含まれないもの： ロールバックは連鎖することがあり、高速化の度合いは、事象がどれだけ密に結びついているかに大きく左右されます。

動かすのに必要： 約10¹⁴ FLOPS 概算 数十億のイベントでスーパーコンピューターで数時間。最初の年： 1985 Jefferson の仮想時間。楽観的同期のための Time Warp 機構。 出典

グラフィックスプロセッサのアーキテクチャ・シミュレーション

グラフィックス・プロセッサーのコア、ワープ、メモリをサイクル単位でモデル化し、実際のプログラムを動かして、作る前に設計を評価します。

答える問い: 設計を変えると、グラフィックスチップ上の並列プログラムの速度にどう影響するでしょうか。

含まれないもの： 実際のチップの詳細は秘密か不明であるため、モデルは既存の設計の数値とおおまかにしか合いません。

動かすのに必要： 約10¹² FLOPS 概算 シミュレーション上の実行1秒あたり、ホスト時間で数時間から数日。最初の年： 2009 Bakhoda らによる、詳細なGPUシミュレーターを使ったCUDAワークロードの分析。 出典

FPGAで高速化したシステム・シミュレーション

チップの設計を多数の再構成可能な回路に読み込み、メガヘルツの速度でサイクル単位まで正確に動かして、サーバー全体やそのネットワークをシミュレートします。

答える問い: このプロセッサとそのクラスターは、作られる前に、実際のソフトウェアを動かしてどう振る舞うでしょうか。

含まれないもの： 実際のチップよりはるかに遅く、回路に収まらない設計は動かせません。

動かすのに必要： 約10¹⁵ FLOPS 概算 数百の再構成可能な回路のクラウドで数日。最初の年： 2018 Karandikar らによる FireSim。パブリッククラウド上での、FPGA で加速したサイクル精度のスケールアウト型システムシミュレーション。 出典

システム全体のシミュレーション

プロセッサー、メモリ、ディスク、ネットワークカードを備えたコンピューター全体を、修正していないオペレーティングシステムを起動してプログラムを動かせるほど忠実にシミュレートします。

答える問い: まだ存在しない機械や、好きなだけ一時停止して再生できる機械の上で、実際のソフトウェアはどう動くでしょうか。

含まれないもの： 速度のためにタイミングは近似されているので、正確な性能は出せず、機能的な振る舞いだけがわかります。

動かすのに必要： 約10¹¹ FLOPS 概算 シミュレートする機械1台につきサーバーでほぼリアルタイム。最初の年： 2002 Magnusson らによる Simics。システム全体をシミュレートするプラットフォーム。 出典

軽量なネットワークエミュレーション

数十から数百の仮想のホストとスイッチが、1台のノートパソコンで実際のネットワーク・ソフトウェアを動かし、速度と遅延を設定したエミュレートされたケーブルでつながります。

答える問い: このネットワーク制御プログラムは、展開される前に、トポロジー全体で動くでしょうか。

含まれないもの： ホスト自身のプロセッサーがすべての仮想ノードで共有されるので、高速な回線は遅くなってしまいます。

動かすのに必要： 約10¹⁰ FLOPS 概算 1台のワークステーションでリアルタイム。最初の年： 2010 Lantz、Heller、McKeown による「A network in a laptop」。ソフトウェア定義ネットワークの迅速なプロトタイピング。 出典

焼きなまし法

コンピューターが、原子や設計のモデルをゆっくり冷やしながら、ときには悪い配置も受け入れ、難しい最適化問題のよい解を探します。

答える問い: 天文学的な数の可能性のなかで、最善に近い配置やスケジュールは何でしょうか。

含まれないもの： 最良の答えは保証されず、結果は冷却スケジュールに左右されます。

動かすのに必要： 約10¹² FLOPS 概算 チップ配置1回あたりワークステーションで数時間。最初の年： 1983 Kirkpatrick、Gelatt、Vecchi による、焼きなまし法による最適化。 出典

近似ベイズ計算

シミュレーターを多数の試行パラメーター値で動かし、観測データに近いデータを生むものを残して、どの値がありうるかの全体像を得ます。

答える問い: 複雑なモデルのどんな設定なら、私たちが観測するデータを生み出せたでしょうか。

含まれないもの： 結果は、データのどの要約を使うか、どこまで近ければ一致とみなすかに左右されます。

動かすのに必要： 約10¹³ FLOPS 概算 クラスターで数百万回のシミュレーター実行。最初の年： 1997 Tavaré らによる、シミュレーションを使ってDNA配列データから合着時間を推定する研究です。 出典