数値積分のハードウエアおよび方法
移動時間データ容量からのＸ軸、Ｙ軸およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められる平面上の単一の点のルンゲ−クッタ積分を介してデータを変換するための、システム、方法およびチップ。前記システムは、少なくとも１つのメモリーバンクと、少なくとも１つの代替のメモリーバンクと、および前記メモリーバンクと連絡する少なくとも１つの単一サイクルのルンゲ−クッタ移動時間発生器を含む。前記単一サイクルのルンゲ−クッタ移動時間発生器は、前記少なくとも１つのメモリーバンクからのデータを読み出し、半工程によって進められる積分による値の別の平面を作り出すために、移動時間データ容量および緩慢データにおけるＸ軸、Ｙ軸およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められる平面の点上においてルンゲ−クッタ積分を行うことによって前記データを変換し、および前記データを、前記少なくとも１つの代替のメモリーバンクにライトバックする。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００９年３月１０日に出願の、米国仮出願第６１／１５，８３９号（発明の名称「数値積分のハードウエアおよび方法（HARDWARE AND METHOD OF NUMERICAL INTEGRATION）」）に開示された１以上の発明を請求するものである。
米国仮特許出願のアメリカ合衆国法典第３５巻第１１９条第（ｅ）項の利益は、本明細書によって請求され、前述の出願は、引用によって本明細書に組み込まれる。
【背景技術】
【０００２】
本発明は、コンピュータシステムおよびデータを処理する方法の分野に関する。特に、本発明は、移動時間の処理を加速するために、アプリケーション特有の集積回路（ＡＳＩＣ）またはフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）コプロセッサの形でハードウエア加速を使用するコンピュータシステムに関する。
【０００３】
科学的な計算での多くの応用は微分方程式の解法を含んでおり、重要な決定を下すために使用される結果を生む。例えば、地球科学では、光線トレーシングの技術は、微分方程式のシステムのための初期値問題の数値解法になる。これらの光線方程式は、アイコナール方程式の特徴的な線を記載する。当該解法は、移動時間の数値の格子を生じ、地震波トレースとあいまってアルゴリズム（例えば、キルヒホッフ・マイグレーション）への入力として用いられ、地球の表面画像を生成する。これらの画像は、石油及びガス産業における調査と掘削の決定に重要な役割を果たす。
【０００４】
地球の地表下の土壌の多数のトレースは、どこに炭化水素が存在するか、および炭化水素が存在するか否かを、正確に決定するために要求される。現在、多数のトレースはデータで得られ、コンピュータに送信され、コンピュータは地球の表面下の画像を生成するために、音波の移動時間に近似させる。数値微分方程式の解法の計算上集約的な本質が、これらの決定手順の多くをバッチ処理に変える。従って、微分方程式解法のスピードアップが多くの決定手順を可能にし、集約的な方向に向かい、多くの「仮定」のシナリオの試みを利用する。したがって、これらの計算の加速は、大きな経済的価値を有する。
【０００５】
本発明は、データを変換し、計算のためにハードウエアでの直接的実行を提供することによってデータについての計算を加速する手段を提供し、それにより、中央処理装置（ＣＰＵ）上の計算上の負荷を軽減すると共にデータの変換を等価のソフトウェアより著しく速く行なう。
【発明の概要】
【課題を解決するための手段】
【０００６】
移動時間データ容量から、Ｘ軸、Ｙ軸およびＺ軸に沿ってＸ、ＹおよびＺの値によって定められた平面上の単一の点のルンゲ−クッタ積分を介したデータ変換のためのシステム、方法及びチップ。前記システムは少なくとも１つのメモリーバンクおよび少なくとも1つの代替のメモリーバンク並びに前記メモリーバンクと通信する少なくとも１つの単一サイクルのルンゲ−クッタ移動時間発生器を含む。単一サイクルのルンゲ−クッタ移動時間発生器は、前記少なくとも１つのメモリーバンクからデータを読み出し、移動時間データ容量及び緩慢データにおけるＸ軸、Ｙ軸およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められた平面の点でルンゲ−クッタ積分を行なうことにより、データを変換し、積分によって半工程だけ進めて数値の他の平面を発生させ、前記少なくとも１つの代替のメモリーバンクにデータをライトバックする。
【図面の簡単な説明】
【０００７】
【図１】図１は、ルンゲ−クッタ積分の第２オーダーの各半工程が連続的に実行されるダイアグラムを示す。
【図２】図２は、ルンゲ−クッタ積分の第２オーダーの各半工程が同時に実行されるダイアグラムを示す。
【図３】図３は、図１および２から単一サイクルのルンゲ−クッタ移動時間発生器の詳細を示す。
【図４】図４は、第１実施形態の図１〜３での移動時間発生器によって行なわれた移動時間発生の工程のフローダイアグラムを示す。
【図５】図５は、各Ｚに対するＸ−Ｙ平面を算出するための工程を示す。
【図６】図６は、移動時間容量全体でのＸ軸とＺ軸とのスワップのための工程を示す。
【図７】図７は、各Ｘに対するＺ−Ｙ平面を算出するための工程を示す。
【図８】図８は、移動時間容量全体でのＺ軸とＸ軸とのスワップのための工程を示す。
【図９】図９は、各Ｙに対するＸ−Ｚ平面を算出するための工程を示す。
【図１０】図１０は、第２実施形態の図１〜３での移動時間発生器によって行なわれた移動時間発生の工程のフローダイアグラムを示す。
【図１１】図１１は、各Ｙに対するＸ−Ｚ平面を算出して、Ｚ−Ｘ平面としてメモリーにライトバックするための工程を示す。
【図１２】図１２は、各Ｙに対するＺ−Ｘ平面を算出して、Ｘ−Ｚ平面としてメモリーにライトバックするための工程を示す。
【図１３】図１３は、ルンゲ−クッタ移動時間発生器に対するメモリーインターフェースの概要を示す。
【発明を実施するための形態】
【０００８】
本発明は、ルンゲ−クッタ積分の第２オーダーを用いる方法を実行して、ソース・トレースデータおよび速度モデルから移動時間を発生するシステムである。好ましくは、前記方法は、専用の集積回路（「チップ」）などの特殊目的のハードウエアで実行される。
【０００９】
ルンゲ−クッタ積分は、オリジナルのソフトウェアのハードウエア内の実行からＸｉｌｉｎｘからＶｉｒｔｅｘ−ＩＩＰｒｏまたはＶｉｒｔｅｘ−５ＦＰＧＡデバイスなどのフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）に元々移植されたが、これが高い容量のアプリケーションのために特定用途の集積回路（ＡＳＩＣ）を含む他のハードウエア構成への取り込みにも適していることが理解されるだろう。ＦＰＧＡは、仕様が更新され得るという利点、または同じハードウエアが他のアプリケーションを実行するために構成され得るという利点を有している。しかしながら、ＡＳＩＣは、高性能を示し、大きな生産量に対して、低コストを示し得る。
【００１０】
上述されたハードウエアで実行されるルンゲ−クッタ（数値）積分は、多くのアプリケーション用のデータを処理するために使用され得る。一実施形態において、ハードウエアで実行される数値積分は、地球の地表下の地震のデータに関係する移動時間の値を処理するために使用される。
【００１１】
図３は、ルンゲ−クッタコアの構造を示す。コアは、トレースデータのソースと速度モデルから移動時間の値の平面上で、ルンゲ−クッタ積分を実行し、図４〜１２に記載されたとおり半工程だけ前に進められた積分（すなわち、深さを増加させて下向き）による値の別の平面を発生させる。したがって、これらのコアのいずれか２つは、図２に示されるような１工程だけ積分を進めることが要求されるか、又は２つのコアが図１に示されるのと同じコアを通過する。これは、ハードウエアコストと速度の間で何らかのトレードオフができる。言いかえれば、ルンゲ−クッタ積分は、次の１Ｄベクトルに移る前にデータの１Ｄベクトル上での両方の半工程で行なわれる。第２オーダー近似が３つのデータポイントを必要とするので、各々のベクトルはパイプライン構造で保持される各方向に、その２つの至近の隣接対を有している必要がある。したがって、５つのベクトルへの同時アクセスが必要である。
【００１２】
単一サイクルのルンゲ−クッタ移動時間発生器（６０）、（６１）はメモリーインターフェース（８２）と相互作用する。当該メモリーインターフェース（８２）は中央コントローラ（８０）を含んでいて、図１３に示されるように、移動時間外部メモリー（５４）、（５５）と、緩慢外部メモリー（４４）、（４５）とを制御する。中央コントローラ（８０）は、中央処理装置（ＣＰＵ）（８３）と相互作用するメモリーインターフェース（８２）によって制御される。中央処理装置（８３）は、中央コントローラ（８０）によって制御されるレジスタに書き込んだり、レジスタから読み出したりすることができる。図３の単一サイクルのルンゲ−クッタ移動時間発生器ブロック（６０）は、移動時間外部メモリー（５４）、（５５）に存在する現在の平面から移動時間の入力を受け取り、緩慢外部メモリー（４４）、（４５）に存在する速度モデルから局所的緩慢値を受け取る。
【００１３】
移動時間外部メモリー（５４）、（５５）は、好ましくはＳＳＲＡＭなどの高速アクセスメモリーである。ＳＳＲＡＭなどのスタティックメモリーはそのメモリー空間内の任意のアドレスに高速アクセスを提供する。しかしながら、スタティックメモリー容量は制限されており、本明細書では一例として１００万ワードと仮定した。高速ランダムアクセスメモリーは、インデクサ（８４）と、中央コントローラ（８０）によって制御されるレジスタマップを有している。高速ランダムアクセスメモリーは、Ｘ−Ｙ平面を算出するためにＸに対して、Ｙに対するＸ−Ｚ平面を算出する際のＺに対して、およびＺ−Ｙ平面を算出する際のＺに対して１のユニットを算入する（counts in units）。高速ランダムアクセスメモリーは、各Ｚに対するＸ−Ｙ平面を算出する際のＹに対して、および各Ｙに対するＸ−Ｚ平面を算出する際にＺに対してＸサイズのユニットを算入する。高速ランダムアクセスメモリーは、データの移動時間容量におけるＸ軸及びＹ軸またはＺ軸及びＸ軸をスワップするために、１及びＸサイズ又はＺサイズのユニットを算入する。移動時間データ全体におけるＸ軸及びＺ軸はスワップされ得るか、又はデータの一部がアプリケーションに応じてスワップされ得る。
【００１４】
緩慢外部メモリー（４４）、（４５）は、好ましくはＤＤＲＡＭなどの大容量メモリーである。バルクストレージは、典型的な配置で、１０億ワードを提供する。それは、一連の列および行として内部に配列される。また、このメモリの位置へのアクセスは３段階の手順であり、潜在的に非常に遅い。まず、列がアクセスに開かれる。ついで、その列内の任意の位置またはカラムへのアクセス（「カラムアクセス」）が行なわれる。この段階で、一連のカラムアクセスは高速で行なわれることがあり、すべてのデータの提供は同じ列内にある。最後に、列は「プレチャージ」動作を行なうことにより閉じられる。少数の列（典型的に４つの列）が一度に開かれることを可能にする拡張がある。しかし、これは明らかに、一般的な場合に任意の記憶場所への高速アクセスを許さない。したがって、大容量メモリーは、リニアアクセス、例えば内部ループでのＸ上の反復など、高度に局所的なアクセスパターンに適する。大容量メモリーは外部ループまたはＹ軸及びＺ軸に対して同じアクセス時間を有している。
【００１５】
大容量メモリーは、内側の方向においてアドレスをインクリメントせず、Ｙ軸に対して単独に又はＺ軸に対してＹサイズずつのいずれかで列アドレスをインデックスする（indexes）。大容量メモリーは、算出と書き込みを同時にすることができる。
【００１６】
移動時間外部メモリー（５４）、（５５）が「代替のメモリーバンク」と等価であり、また、緩慢外部メモリー（４４）、（４５）が、図４乃至１２に関連して記述された「メモリーバンク」と等価であることは注目されるべきである。ルンゲ−クッタ移動時間発生器（６０）、（６１）は、半工程だけ進められた積分によって移動時間を生成する。各クロックサイクルにおいて、完全な積分は１つの移動時間点上で行なわれる。
【００１７】
図３を参照すると、現在の平面に対するＴＴ（Ｘ）（Ｙ＋２）の移動時間データ（２）は、移動時間外部メモリー（５４）、（５５）から単一サイクルのルンゲ−クッタ移動時間発生器（６０）へ送られる。ＴＴ（Ｘ）（Ｙ＋２）の移動時間データ（２）は、移動時間データの現在の平面の到着ベクトルであり、追加の４つのベクトルは、Ｙ軸計算のためのライン格納器（４）、（６）、（８）、（１０）内に格納される。同様に、Ｘ軸計算に対してＴＴ（Ｘ＋２）（Ｙ）のライン格納器（６）から移動時間データの現在の平面から到着するベクトルは、レジスタ（２８）、（３０）、（３２）及び（３４）における４つの他のベクトルと共に格納される。ライン格納器又はレジスタのいずれか内に格納された利用可能な到着するベクトルおよび４つの他のベクトルをもつことによって、５つのベクトルへの同時アクセスは、利用可能な第１及び第２オーダーの近似である。
【００１８】
ルンゲ−クッタ移動時間発生器（６０）内では、移動時間データＴＴ（Ｘ）（Ｙ＋２）は直接入力としてライン格納器（４）と微分ブロック（１２）へ送られる。ライン格納器（４）はループカウンターおよびアドレス発生器（４６）からＸ アドレス Ａｄｄｒ Ｘを受け取る。ライン格納器（４）からＴＴ（Ｘ）（Ｙ＋1）の直接出力は、直接入力としてライン格納器（６）へ送られ、および微分ブロック（１２）と微分ブロック（１４）へ送られる。ライン格納器（６）はＸ書き込みアドレス Ａｄｄｒ Ｘ Ｗ Ａｄｄｒを受け取り、そしてＸ＋２は読み出しアドレスＡｄｄｒ Ｘ＋２ Ｒｄ Ａｄｄｒを受け取る。ライン格納器（６）に送られたＸ＋２読み出しアドレスは、ＴＴ（Ｘ＋２）（Ｙ）のライン格納器（６）に格納されたベクトルがライン格納器の他のベクトルの少なくとも２サイクル前に読まれることを可能にし、Ｘ軸計算のために使用されるレジスタ（２８）に送られた出力を生成する。ループカウンターおよびアドレス発生器（４６）からライン格納器（６）への別々の書き込みアドレスＷ ａｄｄｒと読み出しアドレスＲｄ Ａｄｄｒ入力を有することによって、書き込みアドレスは、読み出しアドレスに影響を及ぼすことなく、読み出しアドレスから別々に計算することができる。
【００１９】
ライン格納器（６）の直接出力ＴＴ（Ｘ＋２）（Ｙ）は、レジスタ（２８）およびＹブロック（３６）に関する
【００２０】
【化１】
【００２１】
に送られる。レジスタ（２８）からのＴＴ（Ｘ＋１）（Ｙ）の出力は、Ｙブロック（３６）に関する
【００２２】
【化２】
【００２３】
と、パイプラインにおける次のレジスタ（３０）に送られる。レジスタ（３０）からのＴＴ（Ｘ）（Ｙ）の出力は、Ｙブロック（３６）に関する
【００２４】
【化３】
【００２５】
と、パイプラインの次のレジスタ（３２）に送られる。レジスタ（３２）からのＴＴ（Ｘ−１）（Ｙ）の出力は、Ｙブロック（３６）に関する
【００２６】
【化４】
【００２７】
と、パイプラインの次のレジスタ（３４）に送られる。ＴＴ（Ｘ−２）（Ｙ）の出力はレジスタ（３４）からＹブロック（３６）に関する
【００２８】
【化５】
【００２９】
に送られる。図３には示されていないが、レジスタ（２８）、（３０）、（３２）および（３４）からの出力が、Ｙ軸計算のために図３に示された微分ブロック（１２）、（１４）、（１６）、（１８）、（２０）、（２２）および（２４）に類似した微分ブロック（示されず）を用いて微分されていることを留意されたい。Ｙブロック（３６）に関する
【００３０】
【化６】
【００３１】
は、数値の現在の平面内のＸ軸に等しく間隔をあけられた５つの微分計算された移動時間の値の配列を分析し、当該値の導関数を比較し、中心点で波頭伝達の方向を推定する。Ｙブロック（３６）に関する
【００３２】
【化７】
【００３３】
は、ハミルトニアン（および緩慢補間）ブロック（３８）に送られる。
【００３４】
レジスタ（３０）からＴＴ（Ｘ）（Ｙ）の出力もまた、直接入力として、ライン格納器（８）及び微分ブロック（１４）及び（１６）に送られる。ライン格納器（８）はループカウンター及びアドレス発生器（４６）からＸアドレス、ＡｄｄｒＸを受け取る。ライン格納器（８）の直接出力は、微分ブロック（１６）および（１８）に送られ、かつライン格納器（１０）の直接入力として送られる。ライン格納器（１０）は、ループカウンターおよびアドレス発生器（４６）からＸアドレス、ＡｄｄｒＸを受け取る。ライン格納器（１０）の直接出力は、ＴＴ（Ｘ）（Ｙ−２）およびＤｅｌａｙｅｄＴＴである。ＤｅｌａｙｅｄＴＴは、一連のライン格納器（４）、（６）、（８）及び（１０）において遅延した、入力された移動時間ＴＴ（Ｘ）（Ｙ＋２）である。ＤｅｌａｙｅｄＴＴは、ルンゲ−クッタ移動時間発生器（６０）ブロックから出力され、ＴＴ（Ｘ）（Ｙ−２）は微分ブロック（１８）に送られる。
【００３５】
微分ブロック（１２）の出力ｄＴＴ／ｄＹ（２）は、微分ブロック（２０）およびＥＮＯ決定論理ブロック（２６）に送られる。微分ブロック（１４）からの出力ｄＴＴ／ｄＹ（１）は、微分ブロック（２０）および（２２）、ならびにＥＮＯ決定論理ブロック（２６）に送られる。微分ブロック（１６）からの出力ｄＴＴ／ｄＹ（０）は、微分ブロック（２２）および（２４）、ならびにＥＮＯ決定論理ブロック（２６）に送られる。微分ブロック（１８）からの出力ｄＴＴ／ｄＹ（−１）は、微分ブロック（２４）およびＥＮＯ決定論理ブロック（２６）に送られる。代わりに、微分ブロック（２０）、（２２）及び（２４）からのｄ２ＴＴ（１）ｄＹ2、ｄ2ＴＴ（０）ｄＹ2及びｄ2ＴＴ（０）ｄＹ2の出力は、それぞれ、すべてＥＮＯ決定論理ブロック（２６）に送られる。ＥＮＯ決定論理ブロック（３６）は、数値の現在の平面内のＹ軸に等しく間隔をあけられた、５つの微分計算された移動時間の値の配列を分析し、当該値の導関数を比較し、中心点で波頭伝達の方向を推定する。
【００３６】
ＥＮＯ決定論理ブロック（２６）の出力
【００３７】
【化８】
【００３８】
は、ハミルトニアン（及び緩慢補間）ブロック（３８）に送られる。ハミルトニアン（及び緩慢補間）ブロック（３８）はまた、緩慢外部メモリー（４４）に格納される速度モデルから緩慢データ（４４）を受け取る。ハミルトニアン（及び緩慢補間）ブロック（３８）は、ＥＮＯ決定論理ブロック（２６）の出力
【００３９】
【化９】
【００４０】
から次の平面、および時間＝距離／速度の関係を使用して緩慢外部メモリー（４４）に格納される速度モデルから緩慢データ（４４）に達するために、波頭に要する時間を計算する。ハミルトニアン（及び緩慢補間）ブロック（３８）の出力Ｈａｍ（Ｘ、Ｙ）は、ルンゲ−クッタ半工程ブロック（４０）に送られ、ＴＴ２（Ｘ、Ｙ）（５２）の出力は、計算されているトレースのためのメモリに送られ、書き込まれる。緩慢データが、積分が行なわれる移動時間容量内のすべての点のために格納されないことを留意されたい。したがって、緩慢の局所値は、隣接点での緩慢値間のブロック（３８）の緩慢補間部分によって計算される。
【００４１】
２つの単一サイクルのルンゲ−クッタ移動時間発生器（６０）、（６１）が、半工程を計算するために各々使用されているのであれば、古い移動時間データ、ＯｌｄＴＴ（Ｘ、Ｙ）は、図２に示されるように、他の半工程移動時間データを出力するためにルンゲ−クッタ半工程ブロック（４０）に入力されるだろう。第２のルンゲ−クッタ移動時間発生器（６１）は、第１のルンゲ−クッタ移動時間発生器（６０）と同じであることが好ましい。
【００４２】
一方の半工程における現在の（過去の）平面、他方の半工程における次の平面、およびそれらの間の補間を読み出すことによって、始めるためのデータがないかもしれないことを留意されたい。もし１つの緩慢外部メモリーだけが存在し、それにより、１つの緩慢データ値だけが一度に読み出されることがあると、２つの値が必要とされるので、補間は起こり得ない。通常、第２の値は、ライン格納器または移動時間外部メモリーのような他のメモリーから供給されるが、移動時間発生の開始時では、あらかじめ格納されている値はないことがある。その場合、補間は、前半工程に必要ではなく、平面境界上にある必要もない（the first half step and needs to be on a plane boundary to that no interpolation is necessary）(例えば、単一の値は直接読み出され得る)。半工程を使用することによって、インクリメンタルな移動時間発生がどこで開始し得るかに制限ができる。言いかえれば、移動時間のインクリメントは、速度モデルのグリッド境界上で開始しなければならない。
【００４３】
本願における用語
【００４４】
【化１０】
【００４５】
は、Ｘ軸またはＹ軸いずれかに沿った距離の予想値、およびそれによる波頭方向の水平成分を表す。この予想値は、伝播波の方向のＺと比較した、ＸまたはＹにおける導関数であり得る。
【００４６】
図４乃至１２は、現在の平面からの移動時間、および速度モデルからの第１実施形態および第２実施形態において実行される半工程進められた移動時間までの局所的緩慢値の変換を示す。
【００４７】
下方積分だけでは、全データ容量にわたって十分に正確ではない。(初期のショット（initial shot）の位置からの水平移動が比較的大きい)データ容量の外側領域における精度には、各水平軸に沿った積分を必要とし;この積分のパスは「サイドスウィープ（sidesweep）」として言及されるであろう。
【００４８】
単一サイクルのルンゲ−クッタ移動時間発生器（６０）、（６１）はサイドスウィープに使用される。サイドスウィープを使用することにより、移動時間容量の周辺領域における精度が向上する。しかしながら、上述されるインデクシングは、（＋）Ｚ方向の計算を進めるために，計算がＸ−Ｙ平面に沿って生じることを示唆する。サイドスウィープは、（＋及び−）Ｙ方向に進むためのＸ−Ｚ平面、及び（＋及び−）Ｘ方向に進むためのＹ−Ｚ平面を交互に算出する、このプロセスに従うことを必要とする。−Ｚ方向(上向きのスウィープ)に進むことが、移動時間の正確な積分を提供するためには必要ではないことを留意されたい。サイドスウィープは、図４乃至１２に、より詳細に記載される。
【００４９】
大容量メモリーのこのアクセスパターンの制限は、（Ｘ上の反復に続いてＹ上を反復し、その後Ｚ上の最も外側を反復する）下向きのサイドスウィープが、（Ｘ上の反復に続いてＺ上を反復し、その後（＋及び−）Ｙ上を反復する）Ｙ軸のサイドスウィープの次に直接来ることが可能であるが、Ｘ軸のサイドスウィープが同じ方法では達し得ないことを意味する。これは、Ｘ軸が主軸であることを、Ｘ軸のサイドスウィープが要求するからであり、高性能順次アクセスに必要なように、それが短軸ではあり得ない。引用により本明細書に組み込まれる、２００１年５月２２日に公表の、米国特許第６，２３７，０２１号（発明の名称「データ集約型アプリケーションの能率的に処理するための方法および装置（METHOD AND APPARATUS FOR THE EFFICIENT PROCESSING OF DATA-INTENSIVE APPLICATIONS）」）の単一サイクルの構造を使用することにより、（ＺまたはＹいずれかの）反復の主軸は、大容量のダイナミックメモリーを利用することができる一方で、反復の残りの(短)軸は、高速アクセスのスタティックメモリーを利用する。
【００５０】
本発明の１つの実施形態において、大容量メモリーに関係するアクセスパターンの制限を克服するために、データの移動時間容量（および緩慢データの関連するセクション）は、コピーされ、Ｘ軸のスウィープの前に、そのプロセスにおいて軸をスワップし;（容量全体にわたるセカンドパスが一般的に精度を必要とするために)その後、プロセスを逆行させる。したがって、Ｙ軸は、Ｘ軸のサイドスウィープのための短軸になる。このスワップが可能なのは、全Ｘ−Ｙ平面がスタティックメモリーに格納されることができ、一方の軸に沿った高速アクセスが可能であるからである。各平面は全体的に、その短軸としてＸ軸を備える、スタティックメモリーに順番に読み込まれる。それは、その後、その短軸としてＹ軸を備える大容量(ダイナミック)メモリーにライトバックされる。この軸スワップを他の処理と組み合わせることは可能であり、軸スワップには、更なる時間を消費する必要はない。この技術が、任意の３つの軸を、その軸におけるデータへの高速アクセスのための短軸に変換させる、または任意の３つの軸が、アルゴリズム考察のための主軸となることを可能にするように拡張され得ることを留意されたい。しかしながら、現在の埋め込みは、ＸおよびＹ軸が主軸として３つのすべての軸をカバーする短軸として扱われることを必要とするのみである。これらの工程は、以下に詳細に記載される。
【００５１】
図４
総体的な方法記述−第１の実施形態
【００５２】
（１０４）．各Ｚに対するＸ−Ｙ平面を算出し、メモリーにライトバックする。
【００５３】
移動時間は、メモリーバンク、好ましくはＤＤＲメモリーのような大容量メモリーから代替のメモリーバンクに、またはＳＳＲＡＭメモリーのような高速アクセスメモリーであることが好ましい、図１および図２に示された移動時間外部メモリー（５４）、（５５）にコピーされる。代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるため、移動時間容量全体を包含することができない。したがって、各Ｘ−Ｙ平面が工程（１０４）で各Ｚに対して算出された後、データはメモリーバンクまたは大容量メモリーにコピーバックされる。メモリーバンクのデータは、次のＺ平面を発生させるための始点として使用される。したがって、移動時間容量全体は、大容量メモリーに蓄積され、１つの平面は代替のメモリーバンクに格納される。
【００５４】
新しい移動時間容量の第１のスウィープの第１の平面に関して、メモリーバンクからロードするデータはない。代わりに、ＣＰＵは、関連する値を、直接代替のメモリーバンクに初期化する。
【００５５】
代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるため、移動時間容量全体を包含することができない。したがって、各Ｘ−Ｙ平面が工程（１０４）で各Ｚに対して算出された後、データはメモリーバンクまたは大容量メモリーにコピーバックされる。
【００５６】
（１０６）．その後、移動時間容量のＸ軸およびＺ軸はスワップされる。
【００５７】
工程（１０４）で計算され、メモリーバンクにコピーバックされた移動時間容量は、代替のメモリーバンクにロードされ、その後、メモリーバンクの異なる部分にライトバックされ、Ｘ軸およびＺ軸をスワップする。
【００５８】
（１０８）． 各Ｘに対するＺ−Ｙ平面は、いずれかのＸ方向において算出され、メモリーにライトバックされる。
【００５９】
用語「いずれかのＸ方向」は、2つの方向、増加するＸ座標、または減少するＸ座標を指す。代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるため、移動時間容量全体を包含することができない。したがって、各Ｚ−Ｙ平面が工程（１０８）で各Ｘに対して算出された後、データはメモリーバンクまたは大容量メモリーにコピーバックされる。
【００６０】
（１１０）．その後、移動時間容量のＺ軸およびＸ軸はスワップされる。
【００６１】
工程（１０８）で計算され、メモリーバンクにコピーバックされた移動時間容量は、代替のメモリーバンクにロードされ、その後、メモリーバンクの異なる部分にライトバックされ、Ｚ軸およびＸ軸をスワップする。
【００６２】
（１１２）．次に、いずれかの方向における各Ｙに対するＸ−Ｚ平面は、算出され、メモリーにライトバックされる。
【００６３】
用語「いずれかのＹ方向」は、2つの方向、増加するＹ座標、または減少するＹ座標を指す。
【００６４】
（１１６）．メモリーまたはＣＰＵに完全な移動時間を送る。
【００６５】
他の半工程がまだ完了していなければ、工程（１１２）からのデータは、別のパスのために工程（１０４）に送り返される。全工程が完了していれば、その後、移動時間データは外部メモリーまたはＣＰＵへ送信される。
【００６６】
図５乃至９
図４におけるブロック１０４乃至１１２の詳細。
【００６７】
図５− ブロック１０４の詳細
各Ｚに対するＸ−Ｙ平面を算出し、メモリーにライトバックするための工程。
【００６８】
（１２０）． 第１の工程において、データは初期化される。
【００６９】
第１のＺ平面ループ：
【００７０】
（１２１）．その後、第１のＺ平面で開始し、
【００７１】
（１２２）．各Ｙに対するＸデータを読み出し、代替のメモリーバンクにコピーする。
【００７２】
（１２３）．ＹサイズずつＺをインクリメントする（１２３）。
【００７３】
（１２４）．各Ｙに対するすべてのＸデータが読み出されたか否かを決定する（１２４）。各Ｙに対するＸデータの読み出しが終了していなければ、工程（１２２）に戻る。
各Ｙに対するＸデータの読み出しが終了していれば、先に進む。
【００７４】
現在のＺ平面ループ：
【００７５】
読み出しループ：
【００７６】
（１２５）現在のＺ平面に対するＸ緩慢データを読み出す。
【００７７】
（１２６）．次のＺ平面に対するＸ緩慢データを読み出す。
【００７８】
（１２７）．１ずつＹをインクリメントする。
【００７９】
（１２８）．（１２８）が終了していなければ、工程（１２５）に戻る。（１２８）が終了していれば、先に進む。
【００８０】
書き込みループ：
【００８１】
（１２９）．次のＺに対するＸデータを代替のメモリーバンクに読み込む。
【００８２】
（１３０）．最小値を算出する。
【００８３】
算出された最小値は、以前の格納されたデータ、および平面内の各ポイントに対する現在の平面のその新しく計算されたデータの間の最小値である。最小値のデータは、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーに格納される。最小値のデータは、新しい平面の開始として使用され、メモリーバンク、好ましくは、ＤＤＲAMのような大容量メモリーにライトバックもされる。
【００８４】
（１３１）．メモリーバンクにデータまたは最小値を書き込み、代替のメモリーバンクにデータのコピーを保存する。
【００８５】
最小値は、代替のメモリーバンク、好ましくは、ＳＳＲAMのような高速アクセスメモリー、およびメモリーバンク、好ましくは、ＤＤＲAMのような大容量メモリーの両方に書き込まれる。最小値のデータは、新しい平面の開始として使用される。
【００８６】
（１３２）．ＹサイズずつＺをインクリメントする（１３２）。
【００８７】
（１３３）．すべてのＹのインクリメントが終了していなければ、工程（１３４）において現在のおよび代替のメモリーバンクをスワップし、工程（１２５）に戻る。
【００８８】
（１３３）．終了していれば、移動時間容量全体においてＸ軸およびＺ軸をスワップする工程（１０６）（図６）に進む。
【００８９】
（１３４）．現在のおよび代替のメモリーバンクをスワップする。
【００９０】
図６−ブロック（１０６）の詳細
移動時間容量全体においてＸ軸およびＺ軸をスワップするための工程
【００９１】
（１３５）．第１の工程において、Ｙ、Ｘを初期化する。
【００９２】
読み出しＸ移動時間ループ：
【００９３】
（１３６）．Ｚに対するＸ移動時間データを読み出し、代替のメモリーバンクにコピーする。
【００９４】
（１３７）．ＹサイズずつＺをインクリメントする（１３７）。
【００９５】
工程（１４１）からのＸのインクリメントが、工程（１３７）におけるＺのインクリメントと異なるならば、データは、メモリーバンク内の別々のエントリーに書き込まれる。
【００９６】
（１３８）．Ｚに対するすべての移動時間データが読み出されたか否かを決定する。各Ｚに対するＸデータの読み出しが終了していなければ、工程（１３６）に戻る。各Ｚに対するＸデータの読み出しが終了していれば、先に進む。
【００９７】
書き込みＺ移動時間ループ：
【００９８】
（１３９）．ＹおよびＸを初期化する。
【００９９】
（１４０）．Ｘに対するＺ移動時間データをメモリーバンクに書き込む。
【０１００】
（１４１）．その後、ＹサイズずつＸをインクリメントする（１４１）。
【０１０１】
工程（１４１）からのＸのインクリメントが、工程（１３７）におけるＺのインクリメントと異なるならば、データは、メモリーバンク内の別々のエントリーに書き込まれる。
【０１０２】
（１４２）．Ｘに対するすべてのＺ移動時間データがメモリーに書き込まれたかどうかを決定する。各Ｘに対するＺ移動時間データの書き込みが終了していなければ、工程（１４０）に戻る。各Ｘに対するＺ移動時間の書き込みが終了していれば、いずれかのＸ方向において各Ｘに対するＺ−Ｙ平面を算出する工程（１０８）（図７）に進む。
【０１０３】
図７−ブロック（１０８）の詳細
いずれかのＸ方向において各Ｘに対するＺ−Ｙ平面を算出し、メモリーにライトバックするための工程
【０１０４】
（１４３）．第１の工程において、データは初期化される。
【０１０５】
第１のＸ平面ループ：
【０１０６】
（１４４）．その後、第１のＸ平面で開始し、
【０１０７】
（１４５）．各Ｙに対するＺデータを読み出し、代替のメモリーバンクにコピーする。
【０１０８】
（１４６）．＋／−ＹサイズずつＸをインクリメントする（１２３）。
【０１０９】
用語「＋／−」は、直後の（immediately after）変数の増加または減少のいずれかとして定義される。
【０１１０】
（１４７）．各Ｙに対するすべてのＺデータが読み出されたかどうかを決定する。
各Ｙに対するＺデータの読み出しが終了していなければ、工程（１４４）に戻る。各Ｙに対するＺデータの読み出しが終了していれば、先に進む。
【０１１１】
現在のＸ平面ループ：
【０１１２】
読み出しループ：
【０１１３】
（１４８）．現在のＸ平面に対するＺ緩慢データを読み出す。
【０１１４】
（１４９）．次のＸ平面に対するＺ緩慢データを読み出す。
【０１１５】
（１５０）．＋／−１ずつＹをインクリメントする。
【０１１６】
用語「＋／−」は、直後の変数の増加または減少のいずれかとして定義される。
【０１１７】
（１５１）．終了していなければ、工程（１４８）に戻る。終了していれば、先に進む。
【０１１８】
書き込みープ：
【０１１９】
（１５２）．次のＸに対するＺデータを代替のメモリーバンクに読み込む。
【０１２０】
（１５３）．最小値を算出する。
【０１２１】
算出された最小値は、以前の格納されたデータ、および平面内の各ポイントに対する現在の平面のその新しく計算されたデータの間の最小値である。最小値のデータは、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーに格納される。最小値のデータは、新しい平面の開始として使用され、メモリーバンク、好ましくは、ＤＤＲAMのような大容量メモリーにライトバックもされる。
【０１２２】
（１５４）．メモリーバンクにデータまたは最小値を書き込み、代替のメモリーバンクにデータのコピーを保存する。
【０１２３】
最小値は、代替のメモリーバンク、好ましくは、ＳＳＲAMのような高速アクセスメモリー、およびメモリーバンク、好ましくは、ＤＤＲAMのような大容量メモリーの両方に書き込まれる。最小値のデータは、新しい平面の開始として使用される。
【０１２４】
（１５５）．＋／−ＹサイズずつＸをインクリメントする。
【０１２５】
用語「＋／−」は、直後の変数の増加または減少のいずれかとして定義される。
【０１２６】
（１５６）．すべてのYインクリメントが終了していなければ、工程（１５７）において現在のおよび代替のメモリーバンクをスワップし、工程（１４８）に戻る。終了していれば、移動時間容量全体においてＺ軸およびＸ軸をスワップする工程(１１０)（図８）に進む。
【０１２７】
（１５７）．現在のおよび代替のメモリーバンクをスワップする。
【０１２８】
図８− ブロック（１１０）の詳細
移動時間容量全体においてＺ軸およびＸ軸をスワップするための工程（１１０）。
【０１２９】
（１５８）．第１の工程において、Ｙ、Ｘを初期化する。
【０１３０】
読み出しＺ移動時間ループ：
【０１３１】
（１５９）．Ｘに対するＺ移動時間データを読み出し、代替のメモリーのバンクにコピーする。
【０１３２】
（１６０）．ＹサイズずつＸをインクリメントする。
【０１３３】
（１６１）．Ｘに対するすべてのＺ移動時間データが読み出されたかどうかを決定する。各Ｘに対するＺデータの読み出しが終了していなければ、工程（１５９）に戻る。各Ｘに対するＺデータの読み出しが終了していれば、先に進む。
【０１３４】
書き込みＸ移動時間ループ：
【０１３５】
（１６２）．ＹおよびＺを初期化する。
【０１３６】
（１６３）．Ｚに対するＸ移動時間データをメモリーバンクに書き込む。
【０１３７】
（１６４）．その後、ＹサイズずつＺをインクリメントする。
【０１３８】
（１６５）．Ｚに対するすべてのＸ移動時間データがメモリーに書き込まれたかどうかを決定する。各Ｚに対するＸ移動時間の書き込みが終了していなければ、工程（１６３）に戻る。各Ｚに対するＸ移動時間の書き込みが終了していれば、いずれかのＹ方向において各Ｙに対するＸ−Ｚ平面を算出する工程（１１２）（図９）に進む。
【０１３９】
図９−ブロック（１１２）の詳細
いずれかのＹ方向において各Ｙに対するＸ−Ｚ平面を算出し、メモリーへライトバックするための工程
【０１４０】
（１６６）．第１の工程において、データは初期化される。
【０１４１】
第１のＺ平面ループ:
【０１４２】
（１６７）．その後、第１のＹ平面で始める。
【０１４３】
（１６８）．各Ｚに対するＸのデータを読み出し、代替のメモリーバンクへとコピーする。
【０１４４】
（１６９）．＋／−１ずつＺをインクリメントする。
【０１４５】
用語「＋／−」は、その後すぐ変数を増加させるか、または減少させるかのいずれかとして定義される。
【０１４６】
（１７０）．各Ｚに対する全てのＸデータが読み出されたか否かを判断する。各Ｚに対するＸのデータの読み出しが終了していないならば、工程（１６８）に戻る。各Ｚに対するＸのデータの読み出しが終了しているならば、先へ進む。
【０１４７】
現在のＺ平面ループ：
【０１４８】
読み出しループ：
【０１４９】
（１７１）．現在のＹ平面に対するＸ緩慢データを読み出す。
【０１５０】
（１７２）．次のＹ平面に対するＸ緩慢データを読み出す。
【０１５１】
（１７３）．＋／−１ずつＹをインクリメントする。
【０１５２】
用語「＋／−」は、その後すぐ変数を増加させるか、または減少させるかのいずれかとして定義される。
【０１５３】
（１７４）．終了していなければ、工程（１７１）に戻る。終了しているならば、先に進む。
【０１５４】
書き込みループ：
【０１５５】
（１７５）．代替のメモリーバンクに次のＹに対するＸデータを読み出す。
【０１５６】
（１７６）．最小値を算出する。
【０１５７】
算出された最小値は、以前に格納されたデータと、平面内の各点に対する現在の平面の新しく算出されたデータとの間の最小値である。最小値は、代替のメモリーバンク、好ましくはＳＳＲＡＭのような高速アクセスメモリーに格納される。最小値は、新しい平面のスタートとして使用され、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーにもライトバックされる。
【０１５８】
（１７７）．データまたは最小値をメモリーバンクへ書き込み、代替のメモリーバンクにコピーを保存する。
【０１５９】
最小値は、代替のメモリーバンク、好ましくはＳＲＡＭのような高速アクセスメモリーバンクと、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーの両方に書き込まれる。最小値のデータは、新しい平面のスタートとして使用される。
【０１６０】
（１７８）．＋／−ＹサイズずつＺをインクリメントする。
【０１６１】
用語「＋／−」は、その後すぐ変数を増加させるか、または減少させるかのいずれかとして定義される。
【０１６２】
（１７９）．すべてのＺインクリメントが終了していないならば、工程（１８０）における現在および代替のメモリーバンクをスワップして、工程（１７１）に戻る。終了していれば、データを介するセカンドパスが必要か否かを決定する工程（１１４）（図４）へ進む。
【０１６３】
（１８０）．現在および代替のメモリーバンクをスワップする。
【０１６４】
図１０−全体の方法の記載−第２の実施形態
代替的に、第２の実施形態では、軸スワップは処理時間を減らすためにＹ軸算出と組み合わされる。
【０１６５】
（１０４）．Ｘ−Ｙ平面が各Ｚに対して算出され、メモリーにライトバックされる。
【０１６６】
移動時間はメモリーバンク、好ましくはＤＤＲメモリーのような大容量メモリーから、代替のメモリーバンクまたは図１および２に示される移動時間外部メモリー（５４）、（５５）、（これは、好ましくは、ＳＳＲＡＭメモリーのような高速アクセスメモリーである）へコピーされる。代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるので、それは移動時間容量全体を包含することができない。従って、工程（１０４）において各Ｘ−Ｙ平面が各Ｚに対して算出された後、データは、メモリーバンクまたは大容量メモリーにコピーされる。メモリーバンクのデータは、次のＺ平面を作り出すための始点として使用される。その後、全体の移動時間容量が大容量メモリーに構築され、１つの平面が代替のメモリーバンクに格納される。
【０１６７】
新しい移動時間容量の第１のスワップの第１の平面に対して、メモリーバンクからロードするデータはない。その代わり、ＣＰＵは、代替のメモリーバンクへ関連する値を直接初期化する。
【０１６８】
代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるので、それは移動時間容量全体を包含することができない。従って、工程（１０４）において、各Ｚに対して各Ｘ−Ｙ平面が算出された後、データはメモリーバンクまたは大容量メモリーにコピーされる。
【０１６９】
（１１８）．１つのＹ方向における各ＹのＸ−Ｚ平面を算出して、メモリーをＺ−Ｘ平面としてライトバックする。
【０１７０】
（１０８）．各Ｘに対するＺ−Ｙ平面がいずれかのＸ方向において算出され、メモリーにライトバックされる。
【０１７１】
用語「いずれかのＸ方向」は、２つの方向、Ｘ座標を増加させること、または、Ｘ座標を減少させること、を指す。代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるので、それは移動時間容量全体を包含することができない。従って、工程（１０８）において各Ｘに対して各Ｚ−Ｙ平面が算出された後、データはメモリーバンクまたは大容量メモリーにコピーされる。
【０１７２】
（１２０）．他方のＹ方向における各Ｙに対するＺ−Ｘ平面を算出して、Ｘ−Ｚ平面としてメモリーにライトバックする。
【０１７３】
（１１６）．メモリーまたはＣＰＵに完全な移動時間を送る。
【０１７４】
別の半工程がまだ完了していないならば、工程（１１２）からのデータは別のパスのために工程（１０４）に送られる。全工程が完了しているならば、移動時間データは外部メモリーまたはＣＰＵへ送られる。
【０１７５】
ブロック（１０４）、（１０８）および（１１６）の詳細は上論され、これによって参照によってここで繰り返される。ブロック（１１８）および（１２０）の詳細を以下に示す。
【０１７６】
図１１−ブロック（１１８）の詳細
１方のＹ方向において各Ｙに対するＸ−Ｚ平面を算出し、Ｚ−Ｘ平面としてメモリーに書き込むための工程
【０１７７】
（１８１）．第１の工程で、データは初期化される。
【０１７８】
第１のＹ平面ループ：
【０１７９】
（１８２）．その後、第１のＸ平面から始めて、
【０１８０】
（１８３）．各Ｚに対するＸのデータを読み出し、代替のメモリーバンクにコピーする。
【０１８１】
（１８４）．＋あるいは−ＹサイズずつＺをインクリメントする（１２３）。
【０１８２】
（１８５）．各Ｚに対する全てのＸデータが読み出されたか否かを判断する。各Ｚに対するＸのデータの読み出しが終了していないならば、工程（１８３）に戻る。各Ｚに対するＸのデータの読み出しが終了しているならば、先に進む。
【０１８３】
現在のＹ平面ループ：
【０１８４】
読み出しループ：
【０１８５】
（１８６）．現在のＹ平面に対するＸ緩慢データを読み出す。
【０１８６】
（１８７）．次のＹ平面に対するＸ緩慢データを読み出す。
【０１８７】
（１８８）．＋／−１ずつＺをインクリメントする。
【０１８８】
用語「＋／−」は、その後すぐ変数を増加させるか、または減少させるかのいずれかとして定義される。
【０１８９】
（１８９）．終了していないならば、工程（１８６）に戻る。終了しているならば、先へ進む。
【０１９０】
書き込みループ：
【０１９１】
（１９０）．次のＹのためのＸデータを代替のメモリーバンクに読み込む。
【０１９２】
（１９１）．最小値を算出する。
【０１９３】
算出された最小値は、以前に格納されたデータと、平面内の各点に対する現在の平面の新しく算出されたデータとの間の最小値である。最小値のデータは、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーに格納される。最小値のデータは、新しい平面のスタートとして使用され、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーにもライトバックされる。
【０１９４】
（１９２）．データをＺ−Ｘオーダーにおける次のＹへまたはメモリーバンクへの最小値にライトバックし、代替のメモリーバンクにコピーを保存する。
【０１９５】
最小値は、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーと、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーの両方に書き込まれる。最小値のデータは、新しい平面のスタートとして使用される。
【０１９６】
（１９３）．＋あるいは−ＹサイズずつＺをインクリメントする。
【０１９７】
（１９４）．すべてのＺのインクリメントが終了していないならば、工程（１９５）で現在および代替のメモリーバンクをスワップして、工程（１８６）に戻る。終了しているならば、いずれかのＹ方向における各Ｙに対するＺ−Ｘ平面を算出し、Ｘ−Ｚ平面としてメモリーにライトバックする工程（１１６）（図１１）へ進む。
【０１９８】
（１９５）．現在および代替のメモリーバンクをスワップする。
【０１９９】
図１２−ブロック（１２０）の詳細
他方のＹ方向における各ＹのＺ−Ｘ平面を算出し、Ｘ−Ｚ平面としてメモリーにライトバックするための工程
【０２００】
（１９６）．第１の工程において、データは初期化される。
【０２０１】
第１のＹ平面ループ：
【０２０２】
（１９７）．その後、第１のＹ平面で始めて、
【０２０３】
（１９８）．各Ｘに対するＺデータを読み出し、代替のメモリーバンクにコピーする。
【０２０４】
（１９９）．他方の＋又は−YサイズずつＺをインクリメントする（１２３）。
【０２０５】
（２００）．各Ｘに対する全てのＺデータが読み出されたか否かを判断する。各Ｘに対するＺデータの読み出しが終了していないならば、工程（１９８）に戻る。各Ｘに対するＺデータの読み出しが終了しているならば、先へ進む。
【０２０６】
現在のＹ平面ループ：
【０２０７】
読み出しループ：
【０２０８】
（２０１）．現在のＹ平面に対するＺ緩慢データを読み出す。
【０２０９】
（２０２）．次のＹ平面に対するＺ緩慢データを読み出す。
【０２１０】
（２０３）．＋/−１ずつＺをインクリメントする。
【０２１１】
用語「＋／−」は、その後すぐ変数を増加させるか、または減少させるかのいずれかとして定義される。
【０２１２】
（２０４）．終了していないならば、工程（２０１）に戻る。終了しているならば、先へ進む。
【０２１３】
書き込みループ：
【０２１４】
（２０５）．次のＹに対するＺデータを代替のメモリーバンクに読み込む。
【０２１５】
（２０６）．最小値を算出する。
【０２１６】
算出された最小値は、前に格納されたデータと、平面内の各点に対する現在の平面の新しく計算されたデータとの間の最小値である。最小値のデータは、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーに格納される。最小値のデータは、新しい平面のスタートとして使用され、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーにもライトバックされる。
【０２１７】
（２０７）．データを、Ｘ−Ｚオーダーの次のＹへまたはメモリーバンクへの最小値へライトバックし、代替のメモリーバンクにコピーを保存する。
最小値は、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーと、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーの両方に書き込まれる。最小値のデータは、新しい平面のスタートとして使用される。
【０２１８】
（２０８）．他の＋または−ＹサイズずつＺをインクリメントする。
【０２１９】
（２０９）．すべてのＺのインクリメントが終了していないならば、工程（２１０）において現在および代替のメモリーバンクをスワップし、工程（２０１）に戻る。終了しているならば、図２に示されるような別の単一サイクルのルンゲ−クッタ移動時間発生器、または図１に示されるようなライン格納器（６４）およびマルチプレクサ（６２）に、データを送る工程（１１８）へ進む。
【０２２０】
（２１０）．現在および代替のメモリーバンクをスワップする。
【０２２１】
図１−３のハードウエア実行の詳細な記載
図３の単一サイクル移動時間発生器を使用する２つの方法が、図１および２に例証される。図１は、２つのルンゲ−クッタの半工程を連続的に実行するための、上記のコアの１つを使用する実行の図式を示す。図２は、パラレルに２つのルンゲ−クッタの半工程を実行するために、上記のコアの２つを使用する実行の図式を示す。
【０２２２】
図１について、１つの単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、２つのルンゲ−クッタ半工程の実行において連続して用いられる。移動時間ＴＴ Ｉｎ／Ｏｕｔは、移動時間外部メモリー（５４）からマルチプレクサ（５８）に送られる。マルチプレクサ（５８）はまた、第２の半工程から移動時間を受け取る。マルチプレクサ（５８）の出力ＴＴ（Ｘ）（Ｙ＋２）は、単一サイクルのルンゲ−クッタ移動時間発生器（６０）へ送られる。緩慢データＳｌｏｗｎｅｓｓは、緩慢外部メモリー（４４）からライン格納器（６６）および緩慢補間器（６８）へ送られる。
【０２２３】
緩慢補間器（６８）から、緩慢データＳｌｏｗｎｅｓｓは、２つのライン遅延（７０）およびマルチプレクサ（７２）に送られる。マルチプレクサから、緩慢データは、単一サイクルのルンゲ−クッタ移動時間発生器（６０）に入力される。単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、また第２の半工程の間に第１の半工程からの古い移動時間データ０ｌｄＴＴ（Ｘ）（Ｙ）を受け取る。
【０２２４】
第１の半工程で、単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、図３に示されるように、および、図４−９に示される工程にわたって、入力データＴＴ（Ｘ）（Ｙ＋２）およびＳｌｏｗｎｅｓｓを、出力ＴＴ２（Ｘ）（Ｙ）およびＤｅｌａｙｅｄＴＴに変換する。出力ＴＴ２（Ｘ）（Ｙ）はライン格納器（６４）に格納される。
【０２２５】
第２の工程で、単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、入力データ、ＴＴ Ｉｎ−第２の半工程のみ（マルチプレクサ（５８）をＴＴ（Ｘ）（Ｙ＋２）と組み合わせた)、０ｌｄＴＴ（Ｘ）（Ｙ）およびＳｌｏｗｎｅｓｓを、移動時間の外部メモリー（５４）にライトバックされている出力ＴＴ２（Ｘ）（Ｙ）に変換する。ＯｌｄＴＴ（Ｘ）（Ｙ）の入力が、単に単一サイクルのルンゲ−クッタ移動時間発生器（６０）内の適切な数のライン格納器によって遅延されたオリジナルの入力データＴＴ（Ｘ）（Ｙ＋２）であること、およびそのＴＴ Ｉｎ−第２の工程のみの入力は、第１の半工程からの出力であることに注目されるべきである。
【０２２６】
図１に示されるように、シーケンシャルモードにおいて、移動時間出力ＴＴ２（Ｘ）（Ｙ）は、マルチプレクサ（５８）の入力へフィードバックされて、単一のライン格納器（６４）に保持されることが注目されるべきである。従って、第１の半工程は、全平面にわたってではなく、単一のライン（ＸおよびＹにわたるループの代わりに、一定のＹでＸにわたるループ)にわたって行なわれる。その後、第２の半工程は、次のＹの値に関する第１の半工程に進む前に同じライン上で行なわれる。
【０２２７】
図２は、パラレルに２つのルンゲ−クッタ半工程を行うための上記のコアの２つを使用する実施形態における図式である。第１の単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、第１の移動時間外部メモリー（５５）から古い移動時間データＯｌｄＴＴ（Ｘ）（Ｙ）および移動時間入力ＴＴ（Ｘ）（Ｙ＋２）を受け取る。それぞれ、第１および第２の緩慢外部メモリー（４４）、（４５）からの、現在の緩慢平面および次の緩慢平面からの緩慢データＣｕｒｒｅｎｔ Ｓｌｏｗｎｅｓｓ ＰｌａｎｅおよびＮｅｘｔ Ｓｌｏｗｎｅｓｓ Ｐｌａｎｅは、緩慢補間器（6８）に入力される。
【０２２８】
緩慢補間器（６８）から、緩慢データＳｌｏｗｎｅｓｓは、単一サイクルのルンゲ−クッタ移動時間発生器（６０）と、２ライン遅延（７０）へ送られる。単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、遅延した移動時間Ｄｅｌｙｅｄ ＴＴおよびＴＴ２（Ｘ）（Ｙ）を出力し、これらは、２ライン遅延（７０）からの遅延した緩慢Ｓｌｏｗｎｅｓｓを持つ入力として、第２の単一サイクルのルンゲ−クッタ移動時間発生器（６１）へと送られる。
【０２２９】
第２のサイクルのルンゲ−クッタ移動時間発生器（６１）、その後、遅延した移動時間Ｄｅｌａｙｅｄ ＴＴおよびＴＴ２（Ｘ）（Ｙ）を出力し、これは、第２の移動時間外部メモリー（５４）へ送られる。
【０２３０】
ハードウエアへとインプリメントされた数値積分は、多数の適用のためのデータを処理するために使用され得、本明細書において論じられた例に限定されない。
【０２３１】
従って、本明細書に記載された発明の実施形態は、本発明の原理の適用の単に例示であることは理解されるべきである。例示された実施形態の詳細への本明細書における言及は、請求項の範囲を制限するようことは意図されず、それら自身は、本発明にとって不可欠であると見なされたそれらの特徴について述べるものである。
【技術分野】
【０００１】
本出願は、２００９年３月１０日に出願の、米国仮出願第６１／１５，８３９号（発明の名称「数値積分のハードウエアおよび方法（HARDWARE AND METHOD OF NUMERICAL INTEGRATION）」）に開示された１以上の発明を請求するものである。
米国仮特許出願のアメリカ合衆国法典第３５巻第１１９条第（ｅ）項の利益は、本明細書によって請求され、前述の出願は、引用によって本明細書に組み込まれる。
【背景技術】
【０００２】
本発明は、コンピュータシステムおよびデータを処理する方法の分野に関する。特に、本発明は、移動時間の処理を加速するために、アプリケーション特有の集積回路（ＡＳＩＣ）またはフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）コプロセッサの形でハードウエア加速を使用するコンピュータシステムに関する。
【０００３】
科学的な計算での多くの応用は微分方程式の解法を含んでおり、重要な決定を下すために使用される結果を生む。例えば、地球科学では、光線トレーシングの技術は、微分方程式のシステムのための初期値問題の数値解法になる。これらの光線方程式は、アイコナール方程式の特徴的な線を記載する。当該解法は、移動時間の数値の格子を生じ、地震波トレースとあいまってアルゴリズム（例えば、キルヒホッフ・マイグレーション）への入力として用いられ、地球の表面画像を生成する。これらの画像は、石油及びガス産業における調査と掘削の決定に重要な役割を果たす。
【０００４】
地球の地表下の土壌の多数のトレースは、どこに炭化水素が存在するか、および炭化水素が存在するか否かを、正確に決定するために要求される。現在、多数のトレースはデータで得られ、コンピュータに送信され、コンピュータは地球の表面下の画像を生成するために、音波の移動時間に近似させる。数値微分方程式の解法の計算上集約的な本質が、これらの決定手順の多くをバッチ処理に変える。従って、微分方程式解法のスピードアップが多くの決定手順を可能にし、集約的な方向に向かい、多くの「仮定」のシナリオの試みを利用する。したがって、これらの計算の加速は、大きな経済的価値を有する。
【０００５】
本発明は、データを変換し、計算のためにハードウエアでの直接的実行を提供することによってデータについての計算を加速する手段を提供し、それにより、中央処理装置（ＣＰＵ）上の計算上の負荷を軽減すると共にデータの変換を等価のソフトウェアより著しく速く行なう。
【発明の概要】
【課題を解決するための手段】
【０００６】
移動時間データ容量から、Ｘ軸、Ｙ軸およびＺ軸に沿ってＸ、ＹおよびＺの値によって定められた平面上の単一の点のルンゲ−クッタ積分を介したデータ変換のためのシステム、方法及びチップ。前記システムは少なくとも１つのメモリーバンクおよび少なくとも1つの代替のメモリーバンク並びに前記メモリーバンクと通信する少なくとも１つの単一サイクルのルンゲ−クッタ移動時間発生器を含む。単一サイクルのルンゲ−クッタ移動時間発生器は、前記少なくとも１つのメモリーバンクからデータを読み出し、移動時間データ容量及び緩慢データにおけるＸ軸、Ｙ軸およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められた平面の点でルンゲ−クッタ積分を行なうことにより、データを変換し、積分によって半工程だけ進めて数値の他の平面を発生させ、前記少なくとも１つの代替のメモリーバンクにデータをライトバックする。
【図面の簡単な説明】
【０００７】
【図１】図１は、ルンゲ−クッタ積分の第２オーダーの各半工程が連続的に実行されるダイアグラムを示す。
【図２】図２は、ルンゲ−クッタ積分の第２オーダーの各半工程が同時に実行されるダイアグラムを示す。
【図３】図３は、図１および２から単一サイクルのルンゲ−クッタ移動時間発生器の詳細を示す。
【図４】図４は、第１実施形態の図１〜３での移動時間発生器によって行なわれた移動時間発生の工程のフローダイアグラムを示す。
【図５】図５は、各Ｚに対するＸ−Ｙ平面を算出するための工程を示す。
【図６】図６は、移動時間容量全体でのＸ軸とＺ軸とのスワップのための工程を示す。
【図７】図７は、各Ｘに対するＺ−Ｙ平面を算出するための工程を示す。
【図８】図８は、移動時間容量全体でのＺ軸とＸ軸とのスワップのための工程を示す。
【図９】図９は、各Ｙに対するＸ−Ｚ平面を算出するための工程を示す。
【図１０】図１０は、第２実施形態の図１〜３での移動時間発生器によって行なわれた移動時間発生の工程のフローダイアグラムを示す。
【図１１】図１１は、各Ｙに対するＸ−Ｚ平面を算出して、Ｚ−Ｘ平面としてメモリーにライトバックするための工程を示す。
【図１２】図１２は、各Ｙに対するＺ−Ｘ平面を算出して、Ｘ−Ｚ平面としてメモリーにライトバックするための工程を示す。
【図１３】図１３は、ルンゲ−クッタ移動時間発生器に対するメモリーインターフェースの概要を示す。
【発明を実施するための形態】
【０００８】
本発明は、ルンゲ−クッタ積分の第２オーダーを用いる方法を実行して、ソース・トレースデータおよび速度モデルから移動時間を発生するシステムである。好ましくは、前記方法は、専用の集積回路（「チップ」）などの特殊目的のハードウエアで実行される。
【０００９】
ルンゲ−クッタ積分は、オリジナルのソフトウェアのハードウエア内の実行からＸｉｌｉｎｘからＶｉｒｔｅｘ−ＩＩＰｒｏまたはＶｉｒｔｅｘ−５ＦＰＧＡデバイスなどのフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）に元々移植されたが、これが高い容量のアプリケーションのために特定用途の集積回路（ＡＳＩＣ）を含む他のハードウエア構成への取り込みにも適していることが理解されるだろう。ＦＰＧＡは、仕様が更新され得るという利点、または同じハードウエアが他のアプリケーションを実行するために構成され得るという利点を有している。しかしながら、ＡＳＩＣは、高性能を示し、大きな生産量に対して、低コストを示し得る。
【００１０】
上述されたハードウエアで実行されるルンゲ−クッタ（数値）積分は、多くのアプリケーション用のデータを処理するために使用され得る。一実施形態において、ハードウエアで実行される数値積分は、地球の地表下の地震のデータに関係する移動時間の値を処理するために使用される。
【００１１】
図３は、ルンゲ−クッタコアの構造を示す。コアは、トレースデータのソースと速度モデルから移動時間の値の平面上で、ルンゲ−クッタ積分を実行し、図４〜１２に記載されたとおり半工程だけ前に進められた積分（すなわち、深さを増加させて下向き）による値の別の平面を発生させる。したがって、これらのコアのいずれか２つは、図２に示されるような１工程だけ積分を進めることが要求されるか、又は２つのコアが図１に示されるのと同じコアを通過する。これは、ハードウエアコストと速度の間で何らかのトレードオフができる。言いかえれば、ルンゲ−クッタ積分は、次の１Ｄベクトルに移る前にデータの１Ｄベクトル上での両方の半工程で行なわれる。第２オーダー近似が３つのデータポイントを必要とするので、各々のベクトルはパイプライン構造で保持される各方向に、その２つの至近の隣接対を有している必要がある。したがって、５つのベクトルへの同時アクセスが必要である。
【００１２】
単一サイクルのルンゲ−クッタ移動時間発生器（６０）、（６１）はメモリーインターフェース（８２）と相互作用する。当該メモリーインターフェース（８２）は中央コントローラ（８０）を含んでいて、図１３に示されるように、移動時間外部メモリー（５４）、（５５）と、緩慢外部メモリー（４４）、（４５）とを制御する。中央コントローラ（８０）は、中央処理装置（ＣＰＵ）（８３）と相互作用するメモリーインターフェース（８２）によって制御される。中央処理装置（８３）は、中央コントローラ（８０）によって制御されるレジスタに書き込んだり、レジスタから読み出したりすることができる。図３の単一サイクルのルンゲ−クッタ移動時間発生器ブロック（６０）は、移動時間外部メモリー（５４）、（５５）に存在する現在の平面から移動時間の入力を受け取り、緩慢外部メモリー（４４）、（４５）に存在する速度モデルから局所的緩慢値を受け取る。
【００１３】
移動時間外部メモリー（５４）、（５５）は、好ましくはＳＳＲＡＭなどの高速アクセスメモリーである。ＳＳＲＡＭなどのスタティックメモリーはそのメモリー空間内の任意のアドレスに高速アクセスを提供する。しかしながら、スタティックメモリー容量は制限されており、本明細書では一例として１００万ワードと仮定した。高速ランダムアクセスメモリーは、インデクサ（８４）と、中央コントローラ（８０）によって制御されるレジスタマップを有している。高速ランダムアクセスメモリーは、Ｘ−Ｙ平面を算出するためにＸに対して、Ｙに対するＸ−Ｚ平面を算出する際のＺに対して、およびＺ−Ｙ平面を算出する際のＺに対して１のユニットを算入する（counts in units）。高速ランダムアクセスメモリーは、各Ｚに対するＸ−Ｙ平面を算出する際のＹに対して、および各Ｙに対するＸ−Ｚ平面を算出する際にＺに対してＸサイズのユニットを算入する。高速ランダムアクセスメモリーは、データの移動時間容量におけるＸ軸及びＹ軸またはＺ軸及びＸ軸をスワップするために、１及びＸサイズ又はＺサイズのユニットを算入する。移動時間データ全体におけるＸ軸及びＺ軸はスワップされ得るか、又はデータの一部がアプリケーションに応じてスワップされ得る。
【００１４】
緩慢外部メモリー（４４）、（４５）は、好ましくはＤＤＲＡＭなどの大容量メモリーである。バルクストレージは、典型的な配置で、１０億ワードを提供する。それは、一連の列および行として内部に配列される。また、このメモリの位置へのアクセスは３段階の手順であり、潜在的に非常に遅い。まず、列がアクセスに開かれる。ついで、その列内の任意の位置またはカラムへのアクセス（「カラムアクセス」）が行なわれる。この段階で、一連のカラムアクセスは高速で行なわれることがあり、すべてのデータの提供は同じ列内にある。最後に、列は「プレチャージ」動作を行なうことにより閉じられる。少数の列（典型的に４つの列）が一度に開かれることを可能にする拡張がある。しかし、これは明らかに、一般的な場合に任意の記憶場所への高速アクセスを許さない。したがって、大容量メモリーは、リニアアクセス、例えば内部ループでのＸ上の反復など、高度に局所的なアクセスパターンに適する。大容量メモリーは外部ループまたはＹ軸及びＺ軸に対して同じアクセス時間を有している。
【００１５】
大容量メモリーは、内側の方向においてアドレスをインクリメントせず、Ｙ軸に対して単独に又はＺ軸に対してＹサイズずつのいずれかで列アドレスをインデックスする（indexes）。大容量メモリーは、算出と書き込みを同時にすることができる。
【００１６】
移動時間外部メモリー（５４）、（５５）が「代替のメモリーバンク」と等価であり、また、緩慢外部メモリー（４４）、（４５）が、図４乃至１２に関連して記述された「メモリーバンク」と等価であることは注目されるべきである。ルンゲ−クッタ移動時間発生器（６０）、（６１）は、半工程だけ進められた積分によって移動時間を生成する。各クロックサイクルにおいて、完全な積分は１つの移動時間点上で行なわれる。
【００１７】
図３を参照すると、現在の平面に対するＴＴ（Ｘ）（Ｙ＋２）の移動時間データ（２）は、移動時間外部メモリー（５４）、（５５）から単一サイクルのルンゲ−クッタ移動時間発生器（６０）へ送られる。ＴＴ（Ｘ）（Ｙ＋２）の移動時間データ（２）は、移動時間データの現在の平面の到着ベクトルであり、追加の４つのベクトルは、Ｙ軸計算のためのライン格納器（４）、（６）、（８）、（１０）内に格納される。同様に、Ｘ軸計算に対してＴＴ（Ｘ＋２）（Ｙ）のライン格納器（６）から移動時間データの現在の平面から到着するベクトルは、レジスタ（２８）、（３０）、（３２）及び（３４）における４つの他のベクトルと共に格納される。ライン格納器又はレジスタのいずれか内に格納された利用可能な到着するベクトルおよび４つの他のベクトルをもつことによって、５つのベクトルへの同時アクセスは、利用可能な第１及び第２オーダーの近似である。
【００１８】
ルンゲ−クッタ移動時間発生器（６０）内では、移動時間データＴＴ（Ｘ）（Ｙ＋２）は直接入力としてライン格納器（４）と微分ブロック（１２）へ送られる。ライン格納器（４）はループカウンターおよびアドレス発生器（４６）からＸ アドレス Ａｄｄｒ Ｘを受け取る。ライン格納器（４）からＴＴ（Ｘ）（Ｙ＋1）の直接出力は、直接入力としてライン格納器（６）へ送られ、および微分ブロック（１２）と微分ブロック（１４）へ送られる。ライン格納器（６）はＸ書き込みアドレス Ａｄｄｒ Ｘ Ｗ Ａｄｄｒを受け取り、そしてＸ＋２は読み出しアドレスＡｄｄｒ Ｘ＋２ Ｒｄ Ａｄｄｒを受け取る。ライン格納器（６）に送られたＸ＋２読み出しアドレスは、ＴＴ（Ｘ＋２）（Ｙ）のライン格納器（６）に格納されたベクトルがライン格納器の他のベクトルの少なくとも２サイクル前に読まれることを可能にし、Ｘ軸計算のために使用されるレジスタ（２８）に送られた出力を生成する。ループカウンターおよびアドレス発生器（４６）からライン格納器（６）への別々の書き込みアドレスＷ ａｄｄｒと読み出しアドレスＲｄ Ａｄｄｒ入力を有することによって、書き込みアドレスは、読み出しアドレスに影響を及ぼすことなく、読み出しアドレスから別々に計算することができる。
【００１９】
ライン格納器（６）の直接出力ＴＴ（Ｘ＋２）（Ｙ）は、レジスタ（２８）およびＹブロック（３６）に関する
【００２０】
【化１】
【００２１】
に送られる。レジスタ（２８）からのＴＴ（Ｘ＋１）（Ｙ）の出力は、Ｙブロック（３６）に関する
【００２２】
【化２】
【００２３】
と、パイプラインにおける次のレジスタ（３０）に送られる。レジスタ（３０）からのＴＴ（Ｘ）（Ｙ）の出力は、Ｙブロック（３６）に関する
【００２４】
【化３】
【００２５】
と、パイプラインの次のレジスタ（３２）に送られる。レジスタ（３２）からのＴＴ（Ｘ−１）（Ｙ）の出力は、Ｙブロック（３６）に関する
【００２６】
【化４】
【００２７】
と、パイプラインの次のレジスタ（３４）に送られる。ＴＴ（Ｘ−２）（Ｙ）の出力はレジスタ（３４）からＹブロック（３６）に関する
【００２８】
【化５】
【００２９】
に送られる。図３には示されていないが、レジスタ（２８）、（３０）、（３２）および（３４）からの出力が、Ｙ軸計算のために図３に示された微分ブロック（１２）、（１４）、（１６）、（１８）、（２０）、（２２）および（２４）に類似した微分ブロック（示されず）を用いて微分されていることを留意されたい。Ｙブロック（３６）に関する
【００３０】
【化６】
【００３１】
は、数値の現在の平面内のＸ軸に等しく間隔をあけられた５つの微分計算された移動時間の値の配列を分析し、当該値の導関数を比較し、中心点で波頭伝達の方向を推定する。Ｙブロック（３６）に関する
【００３２】
【化７】
【００３３】
は、ハミルトニアン（および緩慢補間）ブロック（３８）に送られる。
【００３４】
レジスタ（３０）からＴＴ（Ｘ）（Ｙ）の出力もまた、直接入力として、ライン格納器（８）及び微分ブロック（１４）及び（１６）に送られる。ライン格納器（８）はループカウンター及びアドレス発生器（４６）からＸアドレス、ＡｄｄｒＸを受け取る。ライン格納器（８）の直接出力は、微分ブロック（１６）および（１８）に送られ、かつライン格納器（１０）の直接入力として送られる。ライン格納器（１０）は、ループカウンターおよびアドレス発生器（４６）からＸアドレス、ＡｄｄｒＸを受け取る。ライン格納器（１０）の直接出力は、ＴＴ（Ｘ）（Ｙ−２）およびＤｅｌａｙｅｄＴＴである。ＤｅｌａｙｅｄＴＴは、一連のライン格納器（４）、（６）、（８）及び（１０）において遅延した、入力された移動時間ＴＴ（Ｘ）（Ｙ＋２）である。ＤｅｌａｙｅｄＴＴは、ルンゲ−クッタ移動時間発生器（６０）ブロックから出力され、ＴＴ（Ｘ）（Ｙ−２）は微分ブロック（１８）に送られる。
【００３５】
微分ブロック（１２）の出力ｄＴＴ／ｄＹ（２）は、微分ブロック（２０）およびＥＮＯ決定論理ブロック（２６）に送られる。微分ブロック（１４）からの出力ｄＴＴ／ｄＹ（１）は、微分ブロック（２０）および（２２）、ならびにＥＮＯ決定論理ブロック（２６）に送られる。微分ブロック（１６）からの出力ｄＴＴ／ｄＹ（０）は、微分ブロック（２２）および（２４）、ならびにＥＮＯ決定論理ブロック（２６）に送られる。微分ブロック（１８）からの出力ｄＴＴ／ｄＹ（−１）は、微分ブロック（２４）およびＥＮＯ決定論理ブロック（２６）に送られる。代わりに、微分ブロック（２０）、（２２）及び（２４）からのｄ２ＴＴ（１）ｄＹ2、ｄ2ＴＴ（０）ｄＹ2及びｄ2ＴＴ（０）ｄＹ2の出力は、それぞれ、すべてＥＮＯ決定論理ブロック（２６）に送られる。ＥＮＯ決定論理ブロック（３６）は、数値の現在の平面内のＹ軸に等しく間隔をあけられた、５つの微分計算された移動時間の値の配列を分析し、当該値の導関数を比較し、中心点で波頭伝達の方向を推定する。
【００３６】
ＥＮＯ決定論理ブロック（２６）の出力
【００３７】
【化８】
【００３８】
は、ハミルトニアン（及び緩慢補間）ブロック（３８）に送られる。ハミルトニアン（及び緩慢補間）ブロック（３８）はまた、緩慢外部メモリー（４４）に格納される速度モデルから緩慢データ（４４）を受け取る。ハミルトニアン（及び緩慢補間）ブロック（３８）は、ＥＮＯ決定論理ブロック（２６）の出力
【００３９】
【化９】
【００４０】
から次の平面、および時間＝距離／速度の関係を使用して緩慢外部メモリー（４４）に格納される速度モデルから緩慢データ（４４）に達するために、波頭に要する時間を計算する。ハミルトニアン（及び緩慢補間）ブロック（３８）の出力Ｈａｍ（Ｘ、Ｙ）は、ルンゲ−クッタ半工程ブロック（４０）に送られ、ＴＴ２（Ｘ、Ｙ）（５２）の出力は、計算されているトレースのためのメモリに送られ、書き込まれる。緩慢データが、積分が行なわれる移動時間容量内のすべての点のために格納されないことを留意されたい。したがって、緩慢の局所値は、隣接点での緩慢値間のブロック（３８）の緩慢補間部分によって計算される。
【００４１】
２つの単一サイクルのルンゲ−クッタ移動時間発生器（６０）、（６１）が、半工程を計算するために各々使用されているのであれば、古い移動時間データ、ＯｌｄＴＴ（Ｘ、Ｙ）は、図２に示されるように、他の半工程移動時間データを出力するためにルンゲ−クッタ半工程ブロック（４０）に入力されるだろう。第２のルンゲ−クッタ移動時間発生器（６１）は、第１のルンゲ−クッタ移動時間発生器（６０）と同じであることが好ましい。
【００４２】
一方の半工程における現在の（過去の）平面、他方の半工程における次の平面、およびそれらの間の補間を読み出すことによって、始めるためのデータがないかもしれないことを留意されたい。もし１つの緩慢外部メモリーだけが存在し、それにより、１つの緩慢データ値だけが一度に読み出されることがあると、２つの値が必要とされるので、補間は起こり得ない。通常、第２の値は、ライン格納器または移動時間外部メモリーのような他のメモリーから供給されるが、移動時間発生の開始時では、あらかじめ格納されている値はないことがある。その場合、補間は、前半工程に必要ではなく、平面境界上にある必要もない（the first half step and needs to be on a plane boundary to that no interpolation is necessary）(例えば、単一の値は直接読み出され得る)。半工程を使用することによって、インクリメンタルな移動時間発生がどこで開始し得るかに制限ができる。言いかえれば、移動時間のインクリメントは、速度モデルのグリッド境界上で開始しなければならない。
【００４３】
本願における用語
【００４４】
【化１０】
【００４５】
は、Ｘ軸またはＹ軸いずれかに沿った距離の予想値、およびそれによる波頭方向の水平成分を表す。この予想値は、伝播波の方向のＺと比較した、ＸまたはＹにおける導関数であり得る。
【００４６】
図４乃至１２は、現在の平面からの移動時間、および速度モデルからの第１実施形態および第２実施形態において実行される半工程進められた移動時間までの局所的緩慢値の変換を示す。
【００４７】
下方積分だけでは、全データ容量にわたって十分に正確ではない。(初期のショット（initial shot）の位置からの水平移動が比較的大きい)データ容量の外側領域における精度には、各水平軸に沿った積分を必要とし;この積分のパスは「サイドスウィープ（sidesweep）」として言及されるであろう。
【００４８】
単一サイクルのルンゲ−クッタ移動時間発生器（６０）、（６１）はサイドスウィープに使用される。サイドスウィープを使用することにより、移動時間容量の周辺領域における精度が向上する。しかしながら、上述されるインデクシングは、（＋）Ｚ方向の計算を進めるために，計算がＸ−Ｙ平面に沿って生じることを示唆する。サイドスウィープは、（＋及び−）Ｙ方向に進むためのＸ−Ｚ平面、及び（＋及び−）Ｘ方向に進むためのＹ−Ｚ平面を交互に算出する、このプロセスに従うことを必要とする。−Ｚ方向(上向きのスウィープ)に進むことが、移動時間の正確な積分を提供するためには必要ではないことを留意されたい。サイドスウィープは、図４乃至１２に、より詳細に記載される。
【００４９】
大容量メモリーのこのアクセスパターンの制限は、（Ｘ上の反復に続いてＹ上を反復し、その後Ｚ上の最も外側を反復する）下向きのサイドスウィープが、（Ｘ上の反復に続いてＺ上を反復し、その後（＋及び−）Ｙ上を反復する）Ｙ軸のサイドスウィープの次に直接来ることが可能であるが、Ｘ軸のサイドスウィープが同じ方法では達し得ないことを意味する。これは、Ｘ軸が主軸であることを、Ｘ軸のサイドスウィープが要求するからであり、高性能順次アクセスに必要なように、それが短軸ではあり得ない。引用により本明細書に組み込まれる、２００１年５月２２日に公表の、米国特許第６，２３７，０２１号（発明の名称「データ集約型アプリケーションの能率的に処理するための方法および装置（METHOD AND APPARATUS FOR THE EFFICIENT PROCESSING OF DATA-INTENSIVE APPLICATIONS）」）の単一サイクルの構造を使用することにより、（ＺまたはＹいずれかの）反復の主軸は、大容量のダイナミックメモリーを利用することができる一方で、反復の残りの(短)軸は、高速アクセスのスタティックメモリーを利用する。
【００５０】
本発明の１つの実施形態において、大容量メモリーに関係するアクセスパターンの制限を克服するために、データの移動時間容量（および緩慢データの関連するセクション）は、コピーされ、Ｘ軸のスウィープの前に、そのプロセスにおいて軸をスワップし;（容量全体にわたるセカンドパスが一般的に精度を必要とするために)その後、プロセスを逆行させる。したがって、Ｙ軸は、Ｘ軸のサイドスウィープのための短軸になる。このスワップが可能なのは、全Ｘ−Ｙ平面がスタティックメモリーに格納されることができ、一方の軸に沿った高速アクセスが可能であるからである。各平面は全体的に、その短軸としてＸ軸を備える、スタティックメモリーに順番に読み込まれる。それは、その後、その短軸としてＹ軸を備える大容量(ダイナミック)メモリーにライトバックされる。この軸スワップを他の処理と組み合わせることは可能であり、軸スワップには、更なる時間を消費する必要はない。この技術が、任意の３つの軸を、その軸におけるデータへの高速アクセスのための短軸に変換させる、または任意の３つの軸が、アルゴリズム考察のための主軸となることを可能にするように拡張され得ることを留意されたい。しかしながら、現在の埋め込みは、ＸおよびＹ軸が主軸として３つのすべての軸をカバーする短軸として扱われることを必要とするのみである。これらの工程は、以下に詳細に記載される。
【００５１】
図４
総体的な方法記述−第１の実施形態
【００５２】
（１０４）．各Ｚに対するＸ−Ｙ平面を算出し、メモリーにライトバックする。
【００５３】
移動時間は、メモリーバンク、好ましくはＤＤＲメモリーのような大容量メモリーから代替のメモリーバンクに、またはＳＳＲＡＭメモリーのような高速アクセスメモリーであることが好ましい、図１および図２に示された移動時間外部メモリー（５４）、（５５）にコピーされる。代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるため、移動時間容量全体を包含することができない。したがって、各Ｘ−Ｙ平面が工程（１０４）で各Ｚに対して算出された後、データはメモリーバンクまたは大容量メモリーにコピーバックされる。メモリーバンクのデータは、次のＺ平面を発生させるための始点として使用される。したがって、移動時間容量全体は、大容量メモリーに蓄積され、１つの平面は代替のメモリーバンクに格納される。
【００５４】
新しい移動時間容量の第１のスウィープの第１の平面に関して、メモリーバンクからロードするデータはない。代わりに、ＣＰＵは、関連する値を、直接代替のメモリーバンクに初期化する。
【００５５】
代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるため、移動時間容量全体を包含することができない。したがって、各Ｘ−Ｙ平面が工程（１０４）で各Ｚに対して算出された後、データはメモリーバンクまたは大容量メモリーにコピーバックされる。
【００５６】
（１０６）．その後、移動時間容量のＸ軸およびＺ軸はスワップされる。
【００５７】
工程（１０４）で計算され、メモリーバンクにコピーバックされた移動時間容量は、代替のメモリーバンクにロードされ、その後、メモリーバンクの異なる部分にライトバックされ、Ｘ軸およびＺ軸をスワップする。
【００５８】
（１０８）． 各Ｘに対するＺ−Ｙ平面は、いずれかのＸ方向において算出され、メモリーにライトバックされる。
【００５９】
用語「いずれかのＸ方向」は、2つの方向、増加するＸ座標、または減少するＸ座標を指す。代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるため、移動時間容量全体を包含することができない。したがって、各Ｚ−Ｙ平面が工程（１０８）で各Ｘに対して算出された後、データはメモリーバンクまたは大容量メモリーにコピーバックされる。
【００６０】
（１１０）．その後、移動時間容量のＺ軸およびＸ軸はスワップされる。
【００６１】
工程（１０８）で計算され、メモリーバンクにコピーバックされた移動時間容量は、代替のメモリーバンクにロードされ、その後、メモリーバンクの異なる部分にライトバックされ、Ｚ軸およびＸ軸をスワップする。
【００６２】
（１１２）．次に、いずれかの方向における各Ｙに対するＸ−Ｚ平面は、算出され、メモリーにライトバックされる。
【００６３】
用語「いずれかのＹ方向」は、2つの方向、増加するＹ座標、または減少するＹ座標を指す。
【００６４】
（１１６）．メモリーまたはＣＰＵに完全な移動時間を送る。
【００６５】
他の半工程がまだ完了していなければ、工程（１１２）からのデータは、別のパスのために工程（１０４）に送り返される。全工程が完了していれば、その後、移動時間データは外部メモリーまたはＣＰＵへ送信される。
【００６６】
図５乃至９
図４におけるブロック１０４乃至１１２の詳細。
【００６７】
図５− ブロック１０４の詳細
各Ｚに対するＸ−Ｙ平面を算出し、メモリーにライトバックするための工程。
【００６８】
（１２０）． 第１の工程において、データは初期化される。
【００６９】
第１のＺ平面ループ：
【００７０】
（１２１）．その後、第１のＺ平面で開始し、
【００７１】
（１２２）．各Ｙに対するＸデータを読み出し、代替のメモリーバンクにコピーする。
【００７２】
（１２３）．ＹサイズずつＺをインクリメントする（１２３）。
【００７３】
（１２４）．各Ｙに対するすべてのＸデータが読み出されたか否かを決定する（１２４）。各Ｙに対するＸデータの読み出しが終了していなければ、工程（１２２）に戻る。
各Ｙに対するＸデータの読み出しが終了していれば、先に進む。
【００７４】
現在のＺ平面ループ：
【００７５】
読み出しループ：
【００７６】
（１２５）現在のＺ平面に対するＸ緩慢データを読み出す。
【００７７】
（１２６）．次のＺ平面に対するＸ緩慢データを読み出す。
【００７８】
（１２７）．１ずつＹをインクリメントする。
【００７９】
（１２８）．（１２８）が終了していなければ、工程（１２５）に戻る。（１２８）が終了していれば、先に進む。
【００８０】
書き込みループ：
【００８１】
（１２９）．次のＺに対するＸデータを代替のメモリーバンクに読み込む。
【００８２】
（１３０）．最小値を算出する。
【００８３】
算出された最小値は、以前の格納されたデータ、および平面内の各ポイントに対する現在の平面のその新しく計算されたデータの間の最小値である。最小値のデータは、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーに格納される。最小値のデータは、新しい平面の開始として使用され、メモリーバンク、好ましくは、ＤＤＲAMのような大容量メモリーにライトバックもされる。
【００８４】
（１３１）．メモリーバンクにデータまたは最小値を書き込み、代替のメモリーバンクにデータのコピーを保存する。
【００８５】
最小値は、代替のメモリーバンク、好ましくは、ＳＳＲAMのような高速アクセスメモリー、およびメモリーバンク、好ましくは、ＤＤＲAMのような大容量メモリーの両方に書き込まれる。最小値のデータは、新しい平面の開始として使用される。
【００８６】
（１３２）．ＹサイズずつＺをインクリメントする（１３２）。
【００８７】
（１３３）．すべてのＹのインクリメントが終了していなければ、工程（１３４）において現在のおよび代替のメモリーバンクをスワップし、工程（１２５）に戻る。
【００８８】
（１３３）．終了していれば、移動時間容量全体においてＸ軸およびＺ軸をスワップする工程（１０６）（図６）に進む。
【００８９】
（１３４）．現在のおよび代替のメモリーバンクをスワップする。
【００９０】
図６−ブロック（１０６）の詳細
移動時間容量全体においてＸ軸およびＺ軸をスワップするための工程
【００９１】
（１３５）．第１の工程において、Ｙ、Ｘを初期化する。
【００９２】
読み出しＸ移動時間ループ：
【００９３】
（１３６）．Ｚに対するＸ移動時間データを読み出し、代替のメモリーバンクにコピーする。
【００９４】
（１３７）．ＹサイズずつＺをインクリメントする（１３７）。
【００９５】
工程（１４１）からのＸのインクリメントが、工程（１３７）におけるＺのインクリメントと異なるならば、データは、メモリーバンク内の別々のエントリーに書き込まれる。
【００９６】
（１３８）．Ｚに対するすべての移動時間データが読み出されたか否かを決定する。各Ｚに対するＸデータの読み出しが終了していなければ、工程（１３６）に戻る。各Ｚに対するＸデータの読み出しが終了していれば、先に進む。
【００９７】
書き込みＺ移動時間ループ：
【００９８】
（１３９）．ＹおよびＸを初期化する。
【００９９】
（１４０）．Ｘに対するＺ移動時間データをメモリーバンクに書き込む。
【０１００】
（１４１）．その後、ＹサイズずつＸをインクリメントする（１４１）。
【０１０１】
工程（１４１）からのＸのインクリメントが、工程（１３７）におけるＺのインクリメントと異なるならば、データは、メモリーバンク内の別々のエントリーに書き込まれる。
【０１０２】
（１４２）．Ｘに対するすべてのＺ移動時間データがメモリーに書き込まれたかどうかを決定する。各Ｘに対するＺ移動時間データの書き込みが終了していなければ、工程（１４０）に戻る。各Ｘに対するＺ移動時間の書き込みが終了していれば、いずれかのＸ方向において各Ｘに対するＺ−Ｙ平面を算出する工程（１０８）（図７）に進む。
【０１０３】
図７−ブロック（１０８）の詳細
いずれかのＸ方向において各Ｘに対するＺ−Ｙ平面を算出し、メモリーにライトバックするための工程
【０１０４】
（１４３）．第１の工程において、データは初期化される。
【０１０５】
第１のＸ平面ループ：
【０１０６】
（１４４）．その後、第１のＸ平面で開始し、
【０１０７】
（１４５）．各Ｙに対するＺデータを読み出し、代替のメモリーバンクにコピーする。
【０１０８】
（１４６）．＋／−ＹサイズずつＸをインクリメントする（１２３）。
【０１０９】
用語「＋／−」は、直後の（immediately after）変数の増加または減少のいずれかとして定義される。
【０１１０】
（１４７）．各Ｙに対するすべてのＺデータが読み出されたかどうかを決定する。
各Ｙに対するＺデータの読み出しが終了していなければ、工程（１４４）に戻る。各Ｙに対するＺデータの読み出しが終了していれば、先に進む。
【０１１１】
現在のＸ平面ループ：
【０１１２】
読み出しループ：
【０１１３】
（１４８）．現在のＸ平面に対するＺ緩慢データを読み出す。
【０１１４】
（１４９）．次のＸ平面に対するＺ緩慢データを読み出す。
【０１１５】
（１５０）．＋／−１ずつＹをインクリメントする。
【０１１６】
用語「＋／−」は、直後の変数の増加または減少のいずれかとして定義される。
【０１１７】
（１５１）．終了していなければ、工程（１４８）に戻る。終了していれば、先に進む。
【０１１８】
書き込みープ：
【０１１９】
（１５２）．次のＸに対するＺデータを代替のメモリーバンクに読み込む。
【０１２０】
（１５３）．最小値を算出する。
【０１２１】
算出された最小値は、以前の格納されたデータ、および平面内の各ポイントに対する現在の平面のその新しく計算されたデータの間の最小値である。最小値のデータは、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーに格納される。最小値のデータは、新しい平面の開始として使用され、メモリーバンク、好ましくは、ＤＤＲAMのような大容量メモリーにライトバックもされる。
【０１２２】
（１５４）．メモリーバンクにデータまたは最小値を書き込み、代替のメモリーバンクにデータのコピーを保存する。
【０１２３】
最小値は、代替のメモリーバンク、好ましくは、ＳＳＲAMのような高速アクセスメモリー、およびメモリーバンク、好ましくは、ＤＤＲAMのような大容量メモリーの両方に書き込まれる。最小値のデータは、新しい平面の開始として使用される。
【０１２４】
（１５５）．＋／−ＹサイズずつＸをインクリメントする。
【０１２５】
用語「＋／−」は、直後の変数の増加または減少のいずれかとして定義される。
【０１２６】
（１５６）．すべてのYインクリメントが終了していなければ、工程（１５７）において現在のおよび代替のメモリーバンクをスワップし、工程（１４８）に戻る。終了していれば、移動時間容量全体においてＺ軸およびＸ軸をスワップする工程(１１０)（図８）に進む。
【０１２７】
（１５７）．現在のおよび代替のメモリーバンクをスワップする。
【０１２８】
図８− ブロック（１１０）の詳細
移動時間容量全体においてＺ軸およびＸ軸をスワップするための工程（１１０）。
【０１２９】
（１５８）．第１の工程において、Ｙ、Ｘを初期化する。
【０１３０】
読み出しＺ移動時間ループ：
【０１３１】
（１５９）．Ｘに対するＺ移動時間データを読み出し、代替のメモリーのバンクにコピーする。
【０１３２】
（１６０）．ＹサイズずつＸをインクリメントする。
【０１３３】
（１６１）．Ｘに対するすべてのＺ移動時間データが読み出されたかどうかを決定する。各Ｘに対するＺデータの読み出しが終了していなければ、工程（１５９）に戻る。各Ｘに対するＺデータの読み出しが終了していれば、先に進む。
【０１３４】
書き込みＸ移動時間ループ：
【０１３５】
（１６２）．ＹおよびＺを初期化する。
【０１３６】
（１６３）．Ｚに対するＸ移動時間データをメモリーバンクに書き込む。
【０１３７】
（１６４）．その後、ＹサイズずつＺをインクリメントする。
【０１３８】
（１６５）．Ｚに対するすべてのＸ移動時間データがメモリーに書き込まれたかどうかを決定する。各Ｚに対するＸ移動時間の書き込みが終了していなければ、工程（１６３）に戻る。各Ｚに対するＸ移動時間の書き込みが終了していれば、いずれかのＹ方向において各Ｙに対するＸ−Ｚ平面を算出する工程（１１２）（図９）に進む。
【０１３９】
図９−ブロック（１１２）の詳細
いずれかのＹ方向において各Ｙに対するＸ−Ｚ平面を算出し、メモリーへライトバックするための工程
【０１４０】
（１６６）．第１の工程において、データは初期化される。
【０１４１】
第１のＺ平面ループ:
【０１４２】
（１６７）．その後、第１のＹ平面で始める。
【０１４３】
（１６８）．各Ｚに対するＸのデータを読み出し、代替のメモリーバンクへとコピーする。
【０１４４】
（１６９）．＋／−１ずつＺをインクリメントする。
【０１４５】
用語「＋／−」は、その後すぐ変数を増加させるか、または減少させるかのいずれかとして定義される。
【０１４６】
（１７０）．各Ｚに対する全てのＸデータが読み出されたか否かを判断する。各Ｚに対するＸのデータの読み出しが終了していないならば、工程（１６８）に戻る。各Ｚに対するＸのデータの読み出しが終了しているならば、先へ進む。
【０１４７】
現在のＺ平面ループ：
【０１４８】
読み出しループ：
【０１４９】
（１７１）．現在のＹ平面に対するＸ緩慢データを読み出す。
【０１５０】
（１７２）．次のＹ平面に対するＸ緩慢データを読み出す。
【０１５１】
（１７３）．＋／−１ずつＹをインクリメントする。
【０１５２】
用語「＋／−」は、その後すぐ変数を増加させるか、または減少させるかのいずれかとして定義される。
【０１５３】
（１７４）．終了していなければ、工程（１７１）に戻る。終了しているならば、先に進む。
【０１５４】
書き込みループ：
【０１５５】
（１７５）．代替のメモリーバンクに次のＹに対するＸデータを読み出す。
【０１５６】
（１７６）．最小値を算出する。
【０１５７】
算出された最小値は、以前に格納されたデータと、平面内の各点に対する現在の平面の新しく算出されたデータとの間の最小値である。最小値は、代替のメモリーバンク、好ましくはＳＳＲＡＭのような高速アクセスメモリーに格納される。最小値は、新しい平面のスタートとして使用され、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーにもライトバックされる。
【０１５８】
（１７７）．データまたは最小値をメモリーバンクへ書き込み、代替のメモリーバンクにコピーを保存する。
【０１５９】
最小値は、代替のメモリーバンク、好ましくはＳＲＡＭのような高速アクセスメモリーバンクと、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーの両方に書き込まれる。最小値のデータは、新しい平面のスタートとして使用される。
【０１６０】
（１７８）．＋／−ＹサイズずつＺをインクリメントする。
【０１６１】
用語「＋／−」は、その後すぐ変数を増加させるか、または減少させるかのいずれかとして定義される。
【０１６２】
（１７９）．すべてのＺインクリメントが終了していないならば、工程（１８０）における現在および代替のメモリーバンクをスワップして、工程（１７１）に戻る。終了していれば、データを介するセカンドパスが必要か否かを決定する工程（１１４）（図４）へ進む。
【０１６３】
（１８０）．現在および代替のメモリーバンクをスワップする。
【０１６４】
図１０−全体の方法の記載−第２の実施形態
代替的に、第２の実施形態では、軸スワップは処理時間を減らすためにＹ軸算出と組み合わされる。
【０１６５】
（１０４）．Ｘ−Ｙ平面が各Ｚに対して算出され、メモリーにライトバックされる。
【０１６６】
移動時間はメモリーバンク、好ましくはＤＤＲメモリーのような大容量メモリーから、代替のメモリーバンクまたは図１および２に示される移動時間外部メモリー（５４）、（５５）、（これは、好ましくは、ＳＳＲＡＭメモリーのような高速アクセスメモリーである）へコピーされる。代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるので、それは移動時間容量全体を包含することができない。従って、工程（１０４）において各Ｘ−Ｙ平面が各Ｚに対して算出された後、データは、メモリーバンクまたは大容量メモリーにコピーされる。メモリーバンクのデータは、次のＺ平面を作り出すための始点として使用される。その後、全体の移動時間容量が大容量メモリーに構築され、１つの平面が代替のメモリーバンクに格納される。
【０１６７】
新しい移動時間容量の第１のスワップの第１の平面に対して、メモリーバンクからロードするデータはない。その代わり、ＣＰＵは、代替のメモリーバンクへ関連する値を直接初期化する。
【０１６８】
代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるので、それは移動時間容量全体を包含することができない。従って、工程（１０４）において、各Ｚに対して各Ｘ−Ｙ平面が算出された後、データはメモリーバンクまたは大容量メモリーにコピーされる。
【０１６９】
（１１８）．１つのＹ方向における各ＹのＸ−Ｚ平面を算出して、メモリーをＺ−Ｘ平面としてライトバックする。
【０１７０】
（１０８）．各Ｘに対するＺ−Ｙ平面がいずれかのＸ方向において算出され、メモリーにライトバックされる。
【０１７１】
用語「いずれかのＸ方向」は、２つの方向、Ｘ座標を増加させること、または、Ｘ座標を減少させること、を指す。代替のメモリーバンクは、比較的小さな高速アクセスメモリーバンクであるので、それは移動時間容量全体を包含することができない。従って、工程（１０８）において各Ｘに対して各Ｚ−Ｙ平面が算出された後、データはメモリーバンクまたは大容量メモリーにコピーされる。
【０１７２】
（１２０）．他方のＹ方向における各Ｙに対するＺ−Ｘ平面を算出して、Ｘ−Ｚ平面としてメモリーにライトバックする。
【０１７３】
（１１６）．メモリーまたはＣＰＵに完全な移動時間を送る。
【０１７４】
別の半工程がまだ完了していないならば、工程（１１２）からのデータは別のパスのために工程（１０４）に送られる。全工程が完了しているならば、移動時間データは外部メモリーまたはＣＰＵへ送られる。
【０１７５】
ブロック（１０４）、（１０８）および（１１６）の詳細は上論され、これによって参照によってここで繰り返される。ブロック（１１８）および（１２０）の詳細を以下に示す。
【０１７６】
図１１−ブロック（１１８）の詳細
１方のＹ方向において各Ｙに対するＸ−Ｚ平面を算出し、Ｚ−Ｘ平面としてメモリーに書き込むための工程
【０１７７】
（１８１）．第１の工程で、データは初期化される。
【０１７８】
第１のＹ平面ループ：
【０１７９】
（１８２）．その後、第１のＸ平面から始めて、
【０１８０】
（１８３）．各Ｚに対するＸのデータを読み出し、代替のメモリーバンクにコピーする。
【０１８１】
（１８４）．＋あるいは−ＹサイズずつＺをインクリメントする（１２３）。
【０１８２】
（１８５）．各Ｚに対する全てのＸデータが読み出されたか否かを判断する。各Ｚに対するＸのデータの読み出しが終了していないならば、工程（１８３）に戻る。各Ｚに対するＸのデータの読み出しが終了しているならば、先に進む。
【０１８３】
現在のＹ平面ループ：
【０１８４】
読み出しループ：
【０１８５】
（１８６）．現在のＹ平面に対するＸ緩慢データを読み出す。
【０１８６】
（１８７）．次のＹ平面に対するＸ緩慢データを読み出す。
【０１８７】
（１８８）．＋／−１ずつＺをインクリメントする。
【０１８８】
用語「＋／−」は、その後すぐ変数を増加させるか、または減少させるかのいずれかとして定義される。
【０１８９】
（１８９）．終了していないならば、工程（１８６）に戻る。終了しているならば、先へ進む。
【０１９０】
書き込みループ：
【０１９１】
（１９０）．次のＹのためのＸデータを代替のメモリーバンクに読み込む。
【０１９２】
（１９１）．最小値を算出する。
【０１９３】
算出された最小値は、以前に格納されたデータと、平面内の各点に対する現在の平面の新しく算出されたデータとの間の最小値である。最小値のデータは、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーに格納される。最小値のデータは、新しい平面のスタートとして使用され、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーにもライトバックされる。
【０１９４】
（１９２）．データをＺ−Ｘオーダーにおける次のＹへまたはメモリーバンクへの最小値にライトバックし、代替のメモリーバンクにコピーを保存する。
【０１９５】
最小値は、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーと、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーの両方に書き込まれる。最小値のデータは、新しい平面のスタートとして使用される。
【０１９６】
（１９３）．＋あるいは−ＹサイズずつＺをインクリメントする。
【０１９７】
（１９４）．すべてのＺのインクリメントが終了していないならば、工程（１９５）で現在および代替のメモリーバンクをスワップして、工程（１８６）に戻る。終了しているならば、いずれかのＹ方向における各Ｙに対するＺ−Ｘ平面を算出し、Ｘ−Ｚ平面としてメモリーにライトバックする工程（１１６）（図１１）へ進む。
【０１９８】
（１９５）．現在および代替のメモリーバンクをスワップする。
【０１９９】
図１２−ブロック（１２０）の詳細
他方のＹ方向における各ＹのＺ−Ｘ平面を算出し、Ｘ−Ｚ平面としてメモリーにライトバックするための工程
【０２００】
（１９６）．第１の工程において、データは初期化される。
【０２０１】
第１のＹ平面ループ：
【０２０２】
（１９７）．その後、第１のＹ平面で始めて、
【０２０３】
（１９８）．各Ｘに対するＺデータを読み出し、代替のメモリーバンクにコピーする。
【０２０４】
（１９９）．他方の＋又は−YサイズずつＺをインクリメントする（１２３）。
【０２０５】
（２００）．各Ｘに対する全てのＺデータが読み出されたか否かを判断する。各Ｘに対するＺデータの読み出しが終了していないならば、工程（１９８）に戻る。各Ｘに対するＺデータの読み出しが終了しているならば、先へ進む。
【０２０６】
現在のＹ平面ループ：
【０２０７】
読み出しループ：
【０２０８】
（２０１）．現在のＹ平面に対するＺ緩慢データを読み出す。
【０２０９】
（２０２）．次のＹ平面に対するＺ緩慢データを読み出す。
【０２１０】
（２０３）．＋/−１ずつＺをインクリメントする。
【０２１１】
用語「＋／−」は、その後すぐ変数を増加させるか、または減少させるかのいずれかとして定義される。
【０２１２】
（２０４）．終了していないならば、工程（２０１）に戻る。終了しているならば、先へ進む。
【０２１３】
書き込みループ：
【０２１４】
（２０５）．次のＹに対するＺデータを代替のメモリーバンクに読み込む。
【０２１５】
（２０６）．最小値を算出する。
【０２１６】
算出された最小値は、前に格納されたデータと、平面内の各点に対する現在の平面の新しく計算されたデータとの間の最小値である。最小値のデータは、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーに格納される。最小値のデータは、新しい平面のスタートとして使用され、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーにもライトバックされる。
【０２１７】
（２０７）．データを、Ｘ−Ｚオーダーの次のＹへまたはメモリーバンクへの最小値へライトバックし、代替のメモリーバンクにコピーを保存する。
最小値は、代替のメモリーバンク、好ましくは、ＳＳＲＡＭのような高速アクセスメモリーと、メモリーバンク、好ましくはＤＤＲＡＭのような大容量メモリーの両方に書き込まれる。最小値のデータは、新しい平面のスタートとして使用される。
【０２１８】
（２０８）．他の＋または−ＹサイズずつＺをインクリメントする。
【０２１９】
（２０９）．すべてのＺのインクリメントが終了していないならば、工程（２１０）において現在および代替のメモリーバンクをスワップし、工程（２０１）に戻る。終了しているならば、図２に示されるような別の単一サイクルのルンゲ−クッタ移動時間発生器、または図１に示されるようなライン格納器（６４）およびマルチプレクサ（６２）に、データを送る工程（１１８）へ進む。
【０２２０】
（２１０）．現在および代替のメモリーバンクをスワップする。
【０２２１】
図１−３のハードウエア実行の詳細な記載
図３の単一サイクル移動時間発生器を使用する２つの方法が、図１および２に例証される。図１は、２つのルンゲ−クッタの半工程を連続的に実行するための、上記のコアの１つを使用する実行の図式を示す。図２は、パラレルに２つのルンゲ−クッタの半工程を実行するために、上記のコアの２つを使用する実行の図式を示す。
【０２２２】
図１について、１つの単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、２つのルンゲ−クッタ半工程の実行において連続して用いられる。移動時間ＴＴ Ｉｎ／Ｏｕｔは、移動時間外部メモリー（５４）からマルチプレクサ（５８）に送られる。マルチプレクサ（５８）はまた、第２の半工程から移動時間を受け取る。マルチプレクサ（５８）の出力ＴＴ（Ｘ）（Ｙ＋２）は、単一サイクルのルンゲ−クッタ移動時間発生器（６０）へ送られる。緩慢データＳｌｏｗｎｅｓｓは、緩慢外部メモリー（４４）からライン格納器（６６）および緩慢補間器（６８）へ送られる。
【０２２３】
緩慢補間器（６８）から、緩慢データＳｌｏｗｎｅｓｓは、２つのライン遅延（７０）およびマルチプレクサ（７２）に送られる。マルチプレクサから、緩慢データは、単一サイクルのルンゲ−クッタ移動時間発生器（６０）に入力される。単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、また第２の半工程の間に第１の半工程からの古い移動時間データ０ｌｄＴＴ（Ｘ）（Ｙ）を受け取る。
【０２２４】
第１の半工程で、単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、図３に示されるように、および、図４−９に示される工程にわたって、入力データＴＴ（Ｘ）（Ｙ＋２）およびＳｌｏｗｎｅｓｓを、出力ＴＴ２（Ｘ）（Ｙ）およびＤｅｌａｙｅｄＴＴに変換する。出力ＴＴ２（Ｘ）（Ｙ）はライン格納器（６４）に格納される。
【０２２５】
第２の工程で、単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、入力データ、ＴＴ Ｉｎ−第２の半工程のみ（マルチプレクサ（５８）をＴＴ（Ｘ）（Ｙ＋２）と組み合わせた)、０ｌｄＴＴ（Ｘ）（Ｙ）およびＳｌｏｗｎｅｓｓを、移動時間の外部メモリー（５４）にライトバックされている出力ＴＴ２（Ｘ）（Ｙ）に変換する。ＯｌｄＴＴ（Ｘ）（Ｙ）の入力が、単に単一サイクルのルンゲ−クッタ移動時間発生器（６０）内の適切な数のライン格納器によって遅延されたオリジナルの入力データＴＴ（Ｘ）（Ｙ＋２）であること、およびそのＴＴ Ｉｎ−第２の工程のみの入力は、第１の半工程からの出力であることに注目されるべきである。
【０２２６】
図１に示されるように、シーケンシャルモードにおいて、移動時間出力ＴＴ２（Ｘ）（Ｙ）は、マルチプレクサ（５８）の入力へフィードバックされて、単一のライン格納器（６４）に保持されることが注目されるべきである。従って、第１の半工程は、全平面にわたってではなく、単一のライン（ＸおよびＹにわたるループの代わりに、一定のＹでＸにわたるループ)にわたって行なわれる。その後、第２の半工程は、次のＹの値に関する第１の半工程に進む前に同じライン上で行なわれる。
【０２２７】
図２は、パラレルに２つのルンゲ−クッタ半工程を行うための上記のコアの２つを使用する実施形態における図式である。第１の単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、第１の移動時間外部メモリー（５５）から古い移動時間データＯｌｄＴＴ（Ｘ）（Ｙ）および移動時間入力ＴＴ（Ｘ）（Ｙ＋２）を受け取る。それぞれ、第１および第２の緩慢外部メモリー（４４）、（４５）からの、現在の緩慢平面および次の緩慢平面からの緩慢データＣｕｒｒｅｎｔ Ｓｌｏｗｎｅｓｓ ＰｌａｎｅおよびＮｅｘｔ Ｓｌｏｗｎｅｓｓ Ｐｌａｎｅは、緩慢補間器（6８）に入力される。
【０２２８】
緩慢補間器（６８）から、緩慢データＳｌｏｗｎｅｓｓは、単一サイクルのルンゲ−クッタ移動時間発生器（６０）と、２ライン遅延（７０）へ送られる。単一サイクルのルンゲ−クッタ移動時間発生器（６０）は、遅延した移動時間Ｄｅｌｙｅｄ ＴＴおよびＴＴ２（Ｘ）（Ｙ）を出力し、これらは、２ライン遅延（７０）からの遅延した緩慢Ｓｌｏｗｎｅｓｓを持つ入力として、第２の単一サイクルのルンゲ−クッタ移動時間発生器（６１）へと送られる。
【０２２９】
第２のサイクルのルンゲ−クッタ移動時間発生器（６１）、その後、遅延した移動時間Ｄｅｌａｙｅｄ ＴＴおよびＴＴ２（Ｘ）（Ｙ）を出力し、これは、第２の移動時間外部メモリー（５４）へ送られる。
【０２３０】
ハードウエアへとインプリメントされた数値積分は、多数の適用のためのデータを処理するために使用され得、本明細書において論じられた例に限定されない。
【０２３１】
従って、本明細書に記載された発明の実施形態は、本発明の原理の適用の単に例示であることは理解されるべきである。例示された実施形態の詳細への本明細書における言及は、請求項の範囲を制限するようことは意図されず、それら自身は、本発明にとって不可欠であると見なされたそれらの特徴について述べるものである。
【特許請求の範囲】
【請求項１】
少なくとも１つのメモリーバンクと、少なくとも１つの代替のメモリーバンクと、および前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクと相互作用する少なくとも１つの決定ブロックを含む、移動時間データにおけるＸ軸、Ｙ軸およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められる単一の点に関する移動時間の半工程を生み出すためのルンゲ−クッタ積分を実行する方法であって、該方法は、以下：
前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対してＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
前記移動時間データ容量のＸ軸およびＺ軸をスワップする工程、
前記移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、Ｚ−Ｙ平面を、いずれかのＸ方向における各Ｘに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
前記移動時間データ容量におけるＺ軸とＸ軸をスワップする工程、
前記移動時間データ容量のＸ−Ｚ平面上の一連の点に対していずれかのＹ方向における各Ｙに対してＸ−Ｚ平面を算出し、Ｘ−Ｚ平面を、いずれかのＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
単一の点に対する第２の半工程が算出されないならば、前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出するために戻り、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
単一の点に対する第２の半工程が算出されたならば、前記移動時間データ容量を、前記少なくとも１つのメモリーバンクに送る工程、
を含むことを特徴とする方法。
【請求項２】
前記代替のメモリーバンクが、高速アクセスの、スタティックメモリーであり、前記メモリーバンクが、大容量ダイナミックメモリーであることを特徴とする請求項１に記載の方法。
【請求項３】
前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｙに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｙに対する前記Ｘデータをコピーする工程、
ＹサイズずつＺをインクリメントする工程、
現在のＺ−平面に対するＸ緩慢データを読み出し、次のＺ−平面に対するＸ緩慢データを読み出す工程、
１ずつＹをインクリメントする工程、
前記代替のメモリーバンクへ次のＺに対するＸデータを読み出す工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへ書き込み、前記移動データまたは最小値のコピーを、前記代替メモリーバンクに保存する工程、および
ＹサイズずつＺをインクリメントする工程、
各Ｚに対するＸ−Ｙ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｙに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｙに対する前記Ｘデータをコピーする工程、
を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、Ｚ−Ｙ平面を、いずれかのＸ方向における各Ｘに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｙに対するＺデータを読み出し、メモリーの代替のバンクへ各Ｙに対するＺデータをコピーする工程、
＋／−ＹサイズずつＸをインクリメントする工程、
現在のＸ平面に対するＺ緩慢データを読み出し、次のＸ平面に対する前記Ｚ緩慢データを読み出す工程、
＋／−１ずつＹをインクリメントする工程、
前記代替のメモリーバンクへ次のＸに対するＺデータを読み出す工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへ書き込み、前記移動データまたは最小値のコピーを前記代替のメモリーバンクに保存する工程、および
＋／−ＹサイズずつＸをインクリメントする工程、
各Ｘに対するＺ−Ｙ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｙに対するＺデータを読み出し、メモリーの代替のバンクへ各Ｙに対する前記Ｚデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記移動時間データ容量のＸ−Ｚ平面上の一連の点に対するいずれかのＹ方向における各Ｙに対してＸ−Ｚ平面を算出し、Ｘ−Ｚ平面をいずれかのＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｚに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｚに対するＸデータをコピーする工程、
＋／−ＹサイズずつＺをインクリメントする工程、
現在のＹ−平面に対するＸ緩慢データを読み出し、次のＹ−平面に対する前記Ｘ緩慢データを読み出す工程、
１ずつＹをインクリメントする工程、
前記代替のメモリーバンクへ次のＹに対するＸデータを読み出す工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへ書き込み、前記移動データまたは最小値のコピーを前記代替のメモリーバンクに保存する工程、および
＋／−ＹサイズずつＺをインクリメントする工程、
各Ｙに対するＸ−Ｚ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｚに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｚに対する前記Ｘデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記移動時間データ容量における軸をスワップする工程は、移動時間データ容量全体にわたることを特徴とする請求項１に記載の方法。
【請求項７】
前記移動時間データ容量における軸をスワップする工程は、移動時間データ容量の一部にわたることを特徴とする請求項１に記載の方法。
【請求項８】
少なくとも１つのメモリーバンクと、少なくとも１つの代替のメモリーバンクと、および前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクと相互作用する少なくとも１つの決定ブロックを含む、移動時間データ容量におけるＸ軸、Ｙ軸およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められる単一の点に関する移動時間の半工程を生み出すためのルンゲ−クッタ積分を実行する方法であって、該方法は、以下：
前記移動時間データ容量のＸ−Ｙ平面上の一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対してＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
前記移動時間データ容量のＸ−Ｚ平面上の一連の点に対して一方のＹ方向における各Ｙに対してＸ−Ｚ平面を算出し、Ｘ−Ｚ平面をいずれかのＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへ書き込む工程、
前記移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、各Ｚに対してＺ−Ｙ平面を、いずれかのＸの方向において、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
前記移動時間データ容量のＺ−Ｘ平面上の一連の点に対して他方のＹ方向における各Ｙに対してＺ−Ｘ平面を算出し、Ｘ−Ｚ平面を他方のＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
単一の点に対する第２の半工程が算出されないならば、前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程に戻る工程、
単一の点に対する第２の半工程を算出されたならば、前記移動時間データ容量を、前記少なくとも１つのメモリーバンクに送る工程、
を含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記代替のメモリーバンクが、高速アクセスの、スタティックメモリーであり、前記メモリーバンクが、大容量ダイナミックメモリーであることを特徴とする請求項８に記載の方法。
【請求項１０】
前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｙに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｙに対する前記Ｘデータをコピーする工程、
ＹサイズずつＺをインクリメントする工程、
現在のＺ−平面に対するＸ緩慢データを読み出し、次のＺ−平面に対するＸ緩慢データを読み出す工程、
１ずつＹをインクリメントする工程、
前記代替のメモリーバンクへ次のＺに対するＸデータを読み込む工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへライトバックし、前記移動データまたは最小値のコピーを、前記代替メモリーバンクに保存する工程、および
ＹサイズずつＺをインクリメントする工程、
各Ｚに対するＸ−Ｙ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｙに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｙに対する前記Ｘデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項８に記載の方法。
【請求項１１】
前記移動時間データ容量のＸ−Ｚ平面上の一連の点に対する一方のＹ方向における各Ｙに対するＸ−Ｚ平面を算出し、Ｚ−Ｘ平面をいずれかのＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへ書き込む工程が、以下：
各Ｚに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｚに対するＸデータをコピーする工程、
＋／−ＹサイズずつＺをインクリメントする工程、
現在のＹ−平面に対するＸ緩慢データを読み出し、次のＹ−平面に対する前記Ｘ緩慢データを読み出す工程、
＋／−１ずつＺをインクリメントする工程、
前記代替のメモリーバンクへ次のＹに対するＸデータを読み出す工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへ書き込み、前記移動データまたは最小値のコピーを前記代替のメモリーバンクに保存する工程、および
＋／−ＹサイズずつＺをインクリメントする工程、
各Ｘに対するＺ−Ｙ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｙに対するＺデータを読み込み、メモリーの代替のバンクへ各Ｚに対する前記Ｘデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項８に記載の方法。
【請求項１２】
前記移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、各Ｘに対してＺ−Ｙ平面を、いずれかのＸの方向において、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｙに対するＺデータを読み出し、メモリーの代替のバンクへ各Ｙに対するＺデータをコピーする工程、
＋／−ＹサイズずつＸをインクリメントする工程、
現在のＸ−平面に対するＺ緩慢データを読み出し、次のＸ−平面に対する前記Ｚ緩慢データを読み出す工程、
＋／−１ずつＹをインクリメントする工程、
前記代替のメモリーバンクへ次のＸに対するＺデータを読み込む工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへ書き込み、前記移動データまたは最小値のコピーを前記代替のメモリーバンクに保存する工程、および
＋／−ＹサイズずつＸをインクリメントする工程、
各Ｘに対するＺ−Ｙ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｙに対するＺデータを読み込み、メモリーの代替のバンクへ各Ｙに対する前記Ｚデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項８に記載の方法。
【請求項１３】
前記移動時間データ容量のＺ−Ｘ平面上の一連の点に対する他方のＹ方向における各Ｙに対してＺ−Ｘ平面を算出し、Ｘ−Ｚ平面を他方のＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｘに対するＺデータを読み出し、メモリーの前記バンクへ各Xに対するＺデータをコピーする工程、
他の＋または−ＹサイズずつＺをインクリメントする工程、
現在のＹ−平面に対するＸ緩慢データを読み出し、次のＹ−平面に対する前記Ｘ緩慢データを読み出す工程、
＋／−１ずつＺをインクリメントする工程、
前記代替のメモリーバンクへ次のＹに対するＺデータを読み込む工程、
最小値を算出する工程、
前記メモリーバンクへ移動時間または最小値をライトバックし、前記移動時間又は最小値のコピーを、前記代替のメモリーバンクに保存する工程、および
他の＋／−ＹサイズずつＺをインクリメントする工程、
各Ｙに対するＺ−Ｘ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｚに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｚに対する前記Ｘデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項８に記載の方法。
【請求項１４】
移動時間データ容量からのＸ軸、Ｙ軸、およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められる単一の点のルンゲ−クッタ積分を介したデータの変換のためのシステムであって、該システムは、以下：
少なくとも１つのメモリーバンクおよび少なくとも１つの代替のメモリーバンク、
前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクと連絡する少なくとも１つの単一サイクルのルンゲ−クッタ移動時間発生器、
を含み、
ここで、前記少なくとも１つの単一サイクルのルンゲ−クッタ移動時間発生器は、少なくとも１つのメモリーバンクからデータを読み出し、半工程によって前に進められる積分による値の別の平面を作り出すために、移動時間データ容量および緩慢データにおけるＸ軸、Ｙ軸およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められる平面の点上でルンゲ−クッタ積分を行うことによってデータを変換し、および前記少なくとも１つの代替のメモリーバンクへ前記データをライトバックする、
ことを特徴とするシステム。
【請求項１５】
前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクに結合されるＣＰＵをさらに含むことを特徴とする請求項１４に記載のシステム。
【請求項１６】
前記データが、２つのルンゲ−クッタ移動時間発生器によって連続的に変換されることを特徴とする請求項１４に記載のシステム。
【請求項１７】
前記データが、２つのルンゲ−クッタ移動時間発生器によってパラレルになされて変換されることを特徴とする請求項１４に記載のシステム。
【請求項１８】
ルンゲ−クッタ移動時間発生器による前記データの変換が、以下、
移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対する前記Ｘ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
前記移動時間データ容量におけるＸ軸およびＺ軸をスワップする工程、
前記移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、いずれかのＸ方向における各Ｘに対する前記Ｚ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
前記移動時間データ容量におけるＺ軸およびＸ軸をスワップする工程、
前記移動時間データ容量のＸ−Ｚ平面上の一連の点に対するいずれかのＹ方向における各Ｙに対するＸ−Ｚ平面を算出し、いずれかのＹ方向における各Ｙに対するＸ−Ｚ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
単一の点に対する第２の半工程が算出されないならば、前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対してＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程に戻る工程、
単一の点に対する第２の半工程が算出されたならば、前記移動時間データ容量を、前記少なくとも１つのメモリーバンクに送る工程、
を含むことを特徴とする請求項１４に記載のシステム。
【請求項１９】
前記ルンゲ−クッタ移動時間発生器によるデータの変換が、以下：
前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
前記移動時間データ容量のＸ−Ｚ平面における一連の点に対するいずれかのＹ方向における各Ｙに対するＸ−Ｚ平面を算出し、いずれかのＹ方向における各Ｙに対するＸ−Ｚ平面として、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクへ書き込む工程、
前記移動時間データ容量のＺ−Ｙ平面における一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、いずれかのＸ方向における各Ｘに対する前記Ｚ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
前記移動時間データ容量のＺ−Ｘ平面における一連の点に対する他方のＹ方向における各Ｙに対するＺ−Ｘ平面を算出し、他方のＹ方向における各Ｙに対する前記Ｘ−Ｚ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
単一の点に対する第２の半工程が算出されていないならば、前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対してＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクへライトバックする工程に戻る工程、
単一の点に対する第２の半工程が算出されたならば、前記移動時間データ容量を、前記少なくとも１つのメモリーバンクに送る工程、
を含むことを特徴とする請求項１４に記載のシステム。
【請求項２０】
現在の平面に対する移動時間データの入力を受け入れるための第１のポート、
速度モデルからの緩慢データの入力を受け入れるポート、
ルンゲ−クッタ積分を介して入力を変換する工程、
半工程及び遅延した移動時間データによって進められる積分による移動時間データの平面を出力する工程、
を含むルンゲ−クッタ積分を実行するためのチップであって、
前記平面を出力する工程は、
前記移動時間データのＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出する工程、
移動時間データ容量におけるＸ軸およびＺ軸をスワップする工程、
移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出する工程、
移動時間データ容量におけるＺ軸およびＸ軸をスワップする工程、
移動時間データ容量のＸ−Ｚ平面上の一連の点に対するいずれかのＹ方向における各Ｙに対するＸ−Ｚ平面を算出する工程、
単一の点に対する第２の半工程が算出されないならば、移動時間データ容量の前記Ｘ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出する工程に戻る工程、
を含むことを特徴とするチップ。
【請求項２１】
第１の半工程によって進められる積分による移動時間データの平面の出力の入力をさらに含むことを特徴とする請求項１９に記載のチップ。
【請求項１】
少なくとも１つのメモリーバンクと、少なくとも１つの代替のメモリーバンクと、および前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクと相互作用する少なくとも１つの決定ブロックを含む、移動時間データにおけるＸ軸、Ｙ軸およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められる単一の点に関する移動時間の半工程を生み出すためのルンゲ−クッタ積分を実行する方法であって、該方法は、以下：
前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対してＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
前記移動時間データ容量のＸ軸およびＺ軸をスワップする工程、
前記移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、Ｚ−Ｙ平面を、いずれかのＸ方向における各Ｘに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
前記移動時間データ容量におけるＺ軸とＸ軸をスワップする工程、
前記移動時間データ容量のＸ−Ｚ平面上の一連の点に対していずれかのＹ方向における各Ｙに対してＸ−Ｚ平面を算出し、Ｘ−Ｚ平面を、いずれかのＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
単一の点に対する第２の半工程が算出されないならば、前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出するために戻り、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
単一の点に対する第２の半工程が算出されたならば、前記移動時間データ容量を、前記少なくとも１つのメモリーバンクに送る工程、
を含むことを特徴とする方法。
【請求項２】
前記代替のメモリーバンクが、高速アクセスの、スタティックメモリーであり、前記メモリーバンクが、大容量ダイナミックメモリーであることを特徴とする請求項１に記載の方法。
【請求項３】
前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｙに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｙに対する前記Ｘデータをコピーする工程、
ＹサイズずつＺをインクリメントする工程、
現在のＺ−平面に対するＸ緩慢データを読み出し、次のＺ−平面に対するＸ緩慢データを読み出す工程、
１ずつＹをインクリメントする工程、
前記代替のメモリーバンクへ次のＺに対するＸデータを読み出す工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへ書き込み、前記移動データまたは最小値のコピーを、前記代替メモリーバンクに保存する工程、および
ＹサイズずつＺをインクリメントする工程、
各Ｚに対するＸ−Ｙ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｙに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｙに対する前記Ｘデータをコピーする工程、
を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、Ｚ−Ｙ平面を、いずれかのＸ方向における各Ｘに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｙに対するＺデータを読み出し、メモリーの代替のバンクへ各Ｙに対するＺデータをコピーする工程、
＋／−ＹサイズずつＸをインクリメントする工程、
現在のＸ平面に対するＺ緩慢データを読み出し、次のＸ平面に対する前記Ｚ緩慢データを読み出す工程、
＋／−１ずつＹをインクリメントする工程、
前記代替のメモリーバンクへ次のＸに対するＺデータを読み出す工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへ書き込み、前記移動データまたは最小値のコピーを前記代替のメモリーバンクに保存する工程、および
＋／−ＹサイズずつＸをインクリメントする工程、
各Ｘに対するＺ−Ｙ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｙに対するＺデータを読み出し、メモリーの代替のバンクへ各Ｙに対する前記Ｚデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記移動時間データ容量のＸ−Ｚ平面上の一連の点に対するいずれかのＹ方向における各Ｙに対してＸ−Ｚ平面を算出し、Ｘ−Ｚ平面をいずれかのＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｚに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｚに対するＸデータをコピーする工程、
＋／−ＹサイズずつＺをインクリメントする工程、
現在のＹ−平面に対するＸ緩慢データを読み出し、次のＹ−平面に対する前記Ｘ緩慢データを読み出す工程、
１ずつＹをインクリメントする工程、
前記代替のメモリーバンクへ次のＹに対するＸデータを読み出す工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへ書き込み、前記移動データまたは最小値のコピーを前記代替のメモリーバンクに保存する工程、および
＋／−ＹサイズずつＺをインクリメントする工程、
各Ｙに対するＸ−Ｚ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｚに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｚに対する前記Ｘデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記移動時間データ容量における軸をスワップする工程は、移動時間データ容量全体にわたることを特徴とする請求項１に記載の方法。
【請求項７】
前記移動時間データ容量における軸をスワップする工程は、移動時間データ容量の一部にわたることを特徴とする請求項１に記載の方法。
【請求項８】
少なくとも１つのメモリーバンクと、少なくとも１つの代替のメモリーバンクと、および前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクと相互作用する少なくとも１つの決定ブロックを含む、移動時間データ容量におけるＸ軸、Ｙ軸およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められる単一の点に関する移動時間の半工程を生み出すためのルンゲ−クッタ積分を実行する方法であって、該方法は、以下：
前記移動時間データ容量のＸ−Ｙ平面上の一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対してＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
前記移動時間データ容量のＸ−Ｚ平面上の一連の点に対して一方のＹ方向における各Ｙに対してＸ−Ｚ平面を算出し、Ｘ−Ｚ平面をいずれかのＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへ書き込む工程、
前記移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、各Ｚに対してＺ−Ｙ平面を、いずれかのＸの方向において、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
前記移動時間データ容量のＺ−Ｘ平面上の一連の点に対して他方のＹ方向における各Ｙに対してＺ−Ｘ平面を算出し、Ｘ−Ｚ平面を他方のＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程、
単一の点に対する第２の半工程が算出されないならば、前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程に戻る工程、
単一の点に対する第２の半工程を算出されたならば、前記移動時間データ容量を、前記少なくとも１つのメモリーバンクに送る工程、
を含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記代替のメモリーバンクが、高速アクセスの、スタティックメモリーであり、前記メモリーバンクが、大容量ダイナミックメモリーであることを特徴とする請求項８に記載の方法。
【請求項１０】
前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｙに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｙに対する前記Ｘデータをコピーする工程、
ＹサイズずつＺをインクリメントする工程、
現在のＺ−平面に対するＸ緩慢データを読み出し、次のＺ−平面に対するＸ緩慢データを読み出す工程、
１ずつＹをインクリメントする工程、
前記代替のメモリーバンクへ次のＺに対するＸデータを読み込む工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへライトバックし、前記移動データまたは最小値のコピーを、前記代替メモリーバンクに保存する工程、および
ＹサイズずつＺをインクリメントする工程、
各Ｚに対するＸ−Ｙ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｙに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｙに対する前記Ｘデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項８に記載の方法。
【請求項１１】
前記移動時間データ容量のＸ−Ｚ平面上の一連の点に対する一方のＹ方向における各Ｙに対するＸ−Ｚ平面を算出し、Ｚ−Ｘ平面をいずれかのＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへ書き込む工程が、以下：
各Ｚに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｚに対するＸデータをコピーする工程、
＋／−ＹサイズずつＺをインクリメントする工程、
現在のＹ−平面に対するＸ緩慢データを読み出し、次のＹ−平面に対する前記Ｘ緩慢データを読み出す工程、
＋／−１ずつＺをインクリメントする工程、
前記代替のメモリーバンクへ次のＹに対するＸデータを読み出す工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへ書き込み、前記移動データまたは最小値のコピーを前記代替のメモリーバンクに保存する工程、および
＋／−ＹサイズずつＺをインクリメントする工程、
各Ｘに対するＺ−Ｙ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｙに対するＺデータを読み込み、メモリーの代替のバンクへ各Ｚに対する前記Ｘデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項８に記載の方法。
【請求項１２】
前記移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、各Ｘに対してＺ−Ｙ平面を、いずれかのＸの方向において、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｙに対するＺデータを読み出し、メモリーの代替のバンクへ各Ｙに対するＺデータをコピーする工程、
＋／−ＹサイズずつＸをインクリメントする工程、
現在のＸ−平面に対するＺ緩慢データを読み出し、次のＸ−平面に対する前記Ｚ緩慢データを読み出す工程、
＋／−１ずつＹをインクリメントする工程、
前記代替のメモリーバンクへ次のＸに対するＺデータを読み込む工程、
最小値を算出する工程、
移動データまたは最小値を前記メモリーバンクへ書き込み、前記移動データまたは最小値のコピーを前記代替のメモリーバンクに保存する工程、および
＋／−ＹサイズずつＸをインクリメントする工程、
各Ｘに対するＺ−Ｙ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｙに対するＺデータを読み込み、メモリーの代替のバンクへ各Ｙに対する前記Ｚデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項８に記載の方法。
【請求項１３】
前記移動時間データ容量のＺ−Ｘ平面上の一連の点に対する他方のＹ方向における各Ｙに対してＺ−Ｘ平面を算出し、Ｘ−Ｚ平面を他方のＹ方向における各Ｙに対して、前記少なくとも１つのメモリーバンクと前記少なくとも１つの代替のメモリーバンクへライトバックする工程が、以下：
各Ｘに対するＺデータを読み出し、メモリーの前記バンクへ各Xに対するＺデータをコピーする工程、
他の＋または−ＹサイズずつＺをインクリメントする工程、
現在のＹ−平面に対するＸ緩慢データを読み出し、次のＹ−平面に対する前記Ｘ緩慢データを読み出す工程、
＋／−１ずつＺをインクリメントする工程、
前記代替のメモリーバンクへ次のＹに対するＺデータを読み込む工程、
最小値を算出する工程、
前記メモリーバンクへ移動時間または最小値をライトバックし、前記移動時間又は最小値のコピーを、前記代替のメモリーバンクに保存する工程、および
他の＋／−ＹサイズずつＺをインクリメントする工程、
各Ｙに対するＺ−Ｘ平面が算出されないならば、前記メモリーバンクと前記代替のメモリーバンクをスワップし、各Ｚに対するＸデータを読み出し、メモリーの代替のバンクへ各Ｚに対する前記Ｘデータをコピーする工程に戻る工程、
を含むことを特徴とする請求項８に記載の方法。
【請求項１４】
移動時間データ容量からのＸ軸、Ｙ軸、およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められる単一の点のルンゲ−クッタ積分を介したデータの変換のためのシステムであって、該システムは、以下：
少なくとも１つのメモリーバンクおよび少なくとも１つの代替のメモリーバンク、
前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクと連絡する少なくとも１つの単一サイクルのルンゲ−クッタ移動時間発生器、
を含み、
ここで、前記少なくとも１つの単一サイクルのルンゲ−クッタ移動時間発生器は、少なくとも１つのメモリーバンクからデータを読み出し、半工程によって前に進められる積分による値の別の平面を作り出すために、移動時間データ容量および緩慢データにおけるＸ軸、Ｙ軸およびＺ軸に沿ったＸ、ＹおよびＺの値によって定められる平面の点上でルンゲ−クッタ積分を行うことによってデータを変換し、および前記少なくとも１つの代替のメモリーバンクへ前記データをライトバックする、
ことを特徴とするシステム。
【請求項１５】
前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクに結合されるＣＰＵをさらに含むことを特徴とする請求項１４に記載のシステム。
【請求項１６】
前記データが、２つのルンゲ−クッタ移動時間発生器によって連続的に変換されることを特徴とする請求項１４に記載のシステム。
【請求項１７】
前記データが、２つのルンゲ−クッタ移動時間発生器によってパラレルになされて変換されることを特徴とする請求項１４に記載のシステム。
【請求項１８】
ルンゲ−クッタ移動時間発生器による前記データの変換が、以下、
移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対する前記Ｘ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
前記移動時間データ容量におけるＸ軸およびＺ軸をスワップする工程、
前記移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、いずれかのＸ方向における各Ｘに対する前記Ｚ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
前記移動時間データ容量におけるＺ軸およびＸ軸をスワップする工程、
前記移動時間データ容量のＸ−Ｚ平面上の一連の点に対するいずれかのＹ方向における各Ｙに対するＸ−Ｚ平面を算出し、いずれかのＹ方向における各Ｙに対するＸ−Ｚ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
単一の点に対する第２の半工程が算出されないならば、前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対してＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程に戻る工程、
単一の点に対する第２の半工程が算出されたならば、前記移動時間データ容量を、前記少なくとも１つのメモリーバンクに送る工程、
を含むことを特徴とする請求項１４に記載のシステム。
【請求項１９】
前記ルンゲ−クッタ移動時間発生器によるデータの変換が、以下：
前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
前記移動時間データ容量のＸ−Ｚ平面における一連の点に対するいずれかのＹ方向における各Ｙに対するＸ−Ｚ平面を算出し、いずれかのＹ方向における各Ｙに対するＸ−Ｚ平面として、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクへ書き込む工程、
前記移動時間データ容量のＺ−Ｙ平面における一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出し、いずれかのＸ方向における各Ｘに対する前記Ｚ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
前記移動時間データ容量のＺ−Ｘ平面における一連の点に対する他方のＹ方向における各Ｙに対するＺ−Ｘ平面を算出し、他方のＹ方向における各Ｙに対する前記Ｘ−Ｚ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクにライトバックする工程、
単一の点に対する第２の半工程が算出されていないならば、前記移動時間データ容量のＸ−Ｙ平面における一連の点に対する各Ｚに対してＸ−Ｙ平面を算出し、各Ｚに対するＸ−Ｙ平面を、前記少なくとも１つのメモリーバンクおよび前記少なくとも１つの代替のメモリーバンクへライトバックする工程に戻る工程、
単一の点に対する第２の半工程が算出されたならば、前記移動時間データ容量を、前記少なくとも１つのメモリーバンクに送る工程、
を含むことを特徴とする請求項１４に記載のシステム。
【請求項２０】
現在の平面に対する移動時間データの入力を受け入れるための第１のポート、
速度モデルからの緩慢データの入力を受け入れるポート、
ルンゲ−クッタ積分を介して入力を変換する工程、
半工程及び遅延した移動時間データによって進められる積分による移動時間データの平面を出力する工程、
を含むルンゲ−クッタ積分を実行するためのチップであって、
前記平面を出力する工程は、
前記移動時間データのＸ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出する工程、
移動時間データ容量におけるＸ軸およびＺ軸をスワップする工程、
移動時間データ容量のＺ−Ｙ平面上の一連の点に対するいずれかのＸ方向における各Ｘに対するＺ−Ｙ平面を算出する工程、
移動時間データ容量におけるＺ軸およびＸ軸をスワップする工程、
移動時間データ容量のＸ−Ｚ平面上の一連の点に対するいずれかのＹ方向における各Ｙに対するＸ−Ｚ平面を算出する工程、
単一の点に対する第２の半工程が算出されないならば、移動時間データ容量の前記Ｘ−Ｙ平面における一連の点に対する各Ｚに対するＸ−Ｙ平面を算出する工程に戻る工程、
を含むことを特徴とするチップ。
【請求項２１】
第１の半工程によって進められる積分による移動時間データの平面の出力の入力をさらに含むことを特徴とする請求項１９に記載のチップ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公表番号】特表２０１２−５２０５１２（Ｐ２０１２−５２０５１２Ａ）
【公表日】平成２４年９月６日（２０１２．９．６）
【国際特許分類】
【出願番号】特願２０１１−５５４１３６（Ｐ２０１１−５５４１３６）
【出願日】平成２２年３月１０日（２０１０．３．１０）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０２６７７２
【国際公開番号】ＷＯ２０１０／１０４９１６
【国際公開日】平成２２年９月１６日（２０１０．９．１６）
【出願人】（５１１２１７６５８）コンプレックス データ テクノロジーズ (1)
【Ｆターム（参考）】
【公表日】平成２４年９月６日（２０１２．９．６）
【国際特許分類】
【出願日】平成２２年３月１０日（２０１０．３．１０）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０２６７７２
【国際公開番号】ＷＯ２０１０／１０４９１６
【国際公開日】平成２２年９月１６日（２０１０．９．１６）
【出願人】（５１１２１７６５８）コンプレックス データ テクノロジーズ (1)
【Ｆターム（参考）】
[ Back to top ]