Loading article…
逆計算とは、可逆計算の概念をソフトウェアに応用したものである。
可逆コンピューティングは、チップメーカーが直面する熱問題に対する解決策となる可能性があるため、コンピュータアーキテクチャの分野で広く研究されてきました。可逆コンピューティングの利点は、トランジスタ数が非常に多い場合でも、可逆アーキテクチャの熱損失が最小限に抑えられることです。[ 1 ] [ 2 ] 可逆アーキテクチャは、破壊的な操作によってエントロピー（したがって熱）を生成するのではなく、システムの状態を維持する他の操作を実行することによってエネルギーを節約します。[ 3 ] [ 4 ]
逆計算の概念は、可逆計算よりもやや単純で、逆計算は、すべての可能な命令の集合の可逆性をサポートするのではなく、ソフトウェア アプリケーションの同等の状態を復元するだけでよい。可逆計算の概念は、データベース設計[ 5 ]、チェックポイントとデバッグ[ 6 ] 、コード差分[ 7 ] [ 8 ]などのソフトウェア アプリケーション分野で逆計算としてうまく適用されている。
逆計算の概念が他のソフトウェア領域で成功裏に適用されていることを踏まえ、Chris Carothers、Kalyan Perumalla、Richard Fujimoto [ 9 ]は、並列離散イベントシミュレーション(PDES)における状態保存のオーバーヘッドを削減するために逆計算を適用することを提案しています。彼らは、逆イベントコード (自動生成可能) に基づくアプローチを定義し、きめ細かいアプリケーション (イベントあたりの計算量が少ないアプリケーション) に対して、このアプローチが従来の状態保存よりも優れたパフォーマンスを発揮することを実証しています。逆計算が利用する重要な特性は、状態変数を変更する操作の大部分が本質的に「構成的」であるということです。つまり、このような操作の取り消し操作には履歴は必要ありません。操作を取り消すには、変数の最新の値のみが必要です。たとえば、++、––、+=、-=、*=、/= などの演算子がこのカテゴリに属します。ただし、*= および /= 演算子は、ゼロによる乗算または除算、およびオーバーフロー/アンダーフローの場合には特別な処理が必要であることに注意してください。循環シフト（スワップは特殊なケース）のようなより複雑な演算や、特定の種類の乱数生成もここに含まれます。
a = b の形式の操作、モジュロ演算、およびデータの損失をもたらすビット演算は、破壊的であると呼ばれます。通常、これらの操作は、従来の状態保存技術を使用してのみ復元できます。しかし、これらの破壊的操作の多くは、処理中のイベントに含まれるデータの到着の結果であることがわかります。たとえば、Yaun、Carothers、および al. による大規模なTCPシミュレーションの研究[ 10 ]では、最終送信時刻は、ルータの論理プロセスで転送された最後のパケットのタイムスタンプを記録します。スワップ操作により、この操作は可逆になります。
1985年、ジェファーソンは、タイムワープとして知られる並列離散イベントシミュレーションで使用される楽観的同期プロトコルを導入しました。[ 11 ]現在までに、リバース計算 として知られる技術は、楽観的に同期された並列離散イベントシミュレーションのソフトウェアにのみ適用されています。
1999年12月、マイケル・フランクはフロリダ大学を卒業した。彼の博士論文はハードウェアレベルでの逆算に焦点を当てていたが、逆算に基づくプロセッサの命令セットアーキテクチャと高水準プログラミング言語（R）の両方の説明も含まれていた。[ 12 ] [注1 ]
1998年、カロザーズとペルマラは、リチャード・フジモトの下での大学院研究の一環として、高度分散シミュレーションの原理ワークショップ[ 13 ]で論文を発表し、楽観的に同期された並列離散イベントシミュレーション（タイムワープ）における代替ロールバックメカニズムとして逆計算の手法を紹介した。1998年、カロザーズはレンセラー工科大学の准教授になった。大学院生のデイビッド・バウアーとショーン・ピアースと共に、カロザーズはジョージア工科大学のタイムワープ設計をレンセラーの楽観的シミュレーションシステム（ROSS）に統合した。ROSSはロールバックメカニズムとして逆計算のみをサポートしていた。カロザーズはまた、ゼネラル・エレクトリックのBitTorrentのRCモデルや、学生と共に多数のネットワークプロトコル（BGP4、TCP Tahoe、マルチキャスト）のRCモデルも構築した。カロザーズは、学生がROSSでRCモデルを構築することを義務付ける並列分散シミュレーションのコースを作成した。
ほぼ同時期に、ペルマラはジョージア工科大学を卒業し、オークリッジ国立研究所（ORNL）に就職した。そこで彼は、楽観的／保守的なプロトコルを組み合わせたPDESシミュレータであるuSikを構築した。このシステムは、LPに最適なプロトコルを動的に決定し、実行中にモデルのダイナミクスに応じてそれらを再マッピングすることができた。2007年、ペルマラはBlue Gene/LでuSikをテストし、純粋なTime Warp実装ではスケーラビリティが8Kプロセッサに制限されるのに対し、保守的な実装では16Kプロセッサまで拡張できることを発見した。ベンチマークは、PHOLDを使用して実行され、リモートイベント率は10%に制限された。イベントのタイムスタンプは平均1.0の指数分布によって決定され、各イベントに1.0の先読みが追加された。これは、逆計算を使用してBlue GeneでPDESを実装した最初の例である。
1998年から2005年まで、バウアーはRPIでカロザースの下で大学院生として研究を行い、逆算のみに焦点を当てた。彼は、共有メモリと分散メモリを組み合わせたシステム向けに、逆算のみに基づく最初のPDESシステムであるRensselaer's Optimistic Simulation System (ROSS)を開発した。 [ 14 ] 2006年から2009年まで、バウアーはMitre CorporationでEH Pageの下で働き、カロザースとピアースと共同でROSSシミュレータを131,072プロセッサのBlue Gene/P ( Intrepid )に移植した。この実装は、リモートイベントレート100% (すべてのイベントがネットワーク経由で送信される) で安定していた。RPIとMITRE在籍中、バウアーはROSSで実行されるネットワークプロトコルモデルのブラックボックス最適化のための半自動実験設計をサポートするネットワークシミュレーションシステムROSS.Netを開発した。[15]例えば、同じシミュレーションマシン上のネットワークプロトコルLP間でイベントが渡されないようにLPレイヤリング構造を作成すると、TCPとIPプロトコル間のゼロオフセットタイムスタンプがなくなるため、TCP/IPネットワークノードのシミュレーションが最適化されます。Bauerはまた、感染症、特にパンデミックインフルエンザの影響を研究するために、数億のエージェントにまで拡張可能なソーシャルコンタクトネットワーク用のRCエージェントベースモデルを構築しました。さらに、モビリティ（近接検出）機能と高精度な物理層電磁波伝搬（伝送線路マトリックスモデル）を実装するモバイルアドホックネットワーク用のRCモデルも構築しました。[ 16 ]
PDESコミュニティは近年、連続シミュレーションの領域にも力を入れています。例えば、藤本とペルマラは、Tangら[ 17 ]と共同で、粒子インセルRCモデルを実装し、光を粒子として扱うモデルにおいて、連続シミュレーションよりも優れた高速化を実現しました。BauerとPageは、マイクロ波周波数で光を波としてモデル化するRC伝送線路行列モデル（PB Johns、1971）において、優れた高速化を実現しました。Bauerはまた、感染症の蔓延の分野で連続モデルよりも大幅な改善をもたらすSEIRのRC版を作成しました。さらに、RC SEIRモデルは複数の疾患を効率的にモデル化できるのに対し、連続モデルは集団全体で可能な疾患の組み合わせの数に対して指数関数的に爆発的に増加します。