JP2010271755A - シミュレーション・システム、方法及びプログラム - Google Patents

Abstract

【課題】 マルチコアまたはマルチプロセッサ・システムにおいて、処理ループを投機的パイプライニングで高速化する際に、予測の誤差をシステム的に計算することによって、誤差の累積を減らすこと。
【解決手段】
マルチコアまたはマルチプロセッサ・システムの環境において、制御ブロックのループの個々の処理が、投機的パイプライニングの技法で、好適には個別のスレッドとして個別のコアまたはプロセッサに割り当てられる。この予測入力に基づく出力に対して、当該スレットの予測変数値を用いて、補正値が計算される。この補正値の計算は、予測変数値の一次微分係数の近似値としての勾配値として与えられる。シミュレーション・システムの場合一般的に、変数値は複数あるので、一次微分係数は、ヤコビ行列としてあらわされる。そこで、本発明では、その各々の成分が一次偏微分係数の近似値としての勾配値である行列をヤコビ行列と呼ぶことにする。すると、本発明において、補正値の計算は、このようにして定義されたヤコビ行列によって行なわれる。
【選択図】 図１１

Description

この発明は、マルチコアまたはマルチプロセッサ・システムにおいて、シミュレーションを実行する技法に関する。

近年、科学技術計算、シミュレーションなどの分野で、複数のプロセッサをもつ、いわゆるマルチプロセッサ・システムが使用されている。そのようなシステムでは、アプリケーション・プログラムは、複数のプロセスを生成して、個別のプロセッサに、プロセスを割り当てる。それらのプロセッサは、例えば、例えば、MPI (Message-Passing Interface)のようなプロセス間のメッセージ交換を利用したり、共有のメモリ空間を利用したりして互いに通信しながら、処理を進める。

最近になって特に盛んに開発されるようになってきたシミュレーションの分野として、ロボット、自動車、飛行機などのメトカトロニクスのプラントのシミュレーション用ソフトウェアがある。電子部品とソフトウェア技術の発展の恩恵により、ロボット、自動車、飛行機などでは、神経のように張り巡らされたワイヤ結線や無線ＬＡＮなどを利用して、大部分の制御が電子的に行われる。

それらは、本来的には機械的装置であるのに、大量の制御ソフトウェアをも内蔵している。そのため、製品の開発に当たっては、制御プログラムの開発とそのテストに、長い時間と、膨大な費用と、多数の人員を費やす必要が出てきた。

このようなテストのために従来行われている技法として、ＨＩＬＳ(Hardware In the Loop Simulation)がある。特に、自動車全体の電子制御ユニット（ＥＣＵ）をテストする環境は、フルビークルＨＩＬＳと呼ばれる。フルビークルＨＩＬＳにおいては、実験室内で、本物のＥＣＵが、エンジン、トランスミッション機構などをエミュレーションする専用のハードウェア装置に接続され、所定のシナリオに従って、テストが行われる。ＥＣＵからの出力は、監視用のコンピュータに入力され、さらにはディスプレイに表示されて、テスト担当者がディスプレイを眺めながら、異常動作がないかどうか、チェックする。

しかし、ＨＩＬＳは、専用のハードウェア装置を使い、それと本物のＥＣＵの間を物理的に配線しなくてはならないので、準備が大変である。また、別のＥＣＵに取り替えてのテストも、物理的に接続し直さなくてはならないので、手間がかかる。さらに、本物のＥＣＵを用いたテストであるため、テストに実時間を要する。従って、多くのシナリオをテストすると、膨大な時間がかかる。また、ＨＩＬＳのエミュレーション用のハードウェア装置は、一般に、非常に高価である。

そこで近年、高価なエミュレーション用ハードウェア装置を使うことなく、ソフトウェアで構成する手法が提案されている。この手法は、ＳＩＬＳ(Software In the Loop Simulation)と呼ばれ、ＥＣＵに搭載されるマイクロコンピュータ、入出力回路、制御のシナリオ、エンジンやトランスミッションなどのプラントを全て、ソフトウェア・シミュレータで構成する技法である。これによれば、ＥＣＵのハードウェアが存在しなくても、テストを実行可能である。

このようなＳＩＬＳの構築を支援するシステムとして例えば、MathWorks社が開発したシミュレーション・モデリング・システムである、MATLAB(R)/Simulink(R)がある。MATLAB(R)/Simulink(R)を使用すると、図１に示すように、画面上にグラフィカル・インターフェースによって、機能ブロックA,B,...,Gを配置し、矢印のようにその処理の流れを指定することによって、シミュレーション・プログラムを作成することができる。一般に、MATLAB(R)/Simulink(R)におけるブロック線図は、シミュレーション対象となるシステムの１タイムステップの挙動を記述したもので、これを規定時間分繰り返し計算することで、システムの時系列での挙動を得る。

特に、制御系システムのシミュレーションにおいては、フィードバック制御が多く用いられるため、モデルにループを含む場合が多い。図１の機能ブロックにおいては、ブロックGからブロックAに至るフローがループをあらわしており、１タイムステップ前の系の出力が、次のタイムステップにおける系の入力となっている。

シミュレーションをマルチコアまたはマルチプロセッサ・システム上で実現する場合、並列実行させるために、好適には１つの処理単位が、１つのコアまたはプロセッサに割り当てられる。一般的には、モデル中の独立に処理可能な部分を抽出して並列化を行うこととなる。図１の例では、処理Aの終了後、B、C->E、 D->Fの処理は独立に処理可能なため、例えば、Bの処理に一つ、A->C->E->Gの処理に一つ、D->Fの処理に一つといった形でコアまたはプロセッサが割り当てられる。この割り当てによって繰り返し計算を行う例を図２に示す。

図２のように、系全体がループに含まれるモデルの繰り返し処理では、１タイムステップの全処理の結果が次のタイムステップの処理の入力となるため、モデルのクリティカルパスが、そのまま繰り返し処理のクリティカルパスとなる。図２の例では、ブロック群２０２の処理の終了後、その結果が次のブロック群２０４に渡されて実行されるという直列的な処理になる。ブロック群２０２、２０４、２０６の中で最も時間を要するパス（A->C->E->G）の処理の直列的な並びがクリティカル・パスになってしまうのである。

そこで、本願発明者らは、図３に示すように、複数のタイムステップ分の処理を複数コアまたはプロセッサを用いて投機的に並列実行する方法に想到した。理論的には、図２に示す処理におけるクリティカルパスによる限界を超えて高速化することができる。ブロック群３０２、３０４、３０６の個々のパス（B, A->C->E->G, D->F）が個別のプロセッサに割り当てられて、並列実行される。図２では３Ｔかかっていた処理が、図３ではＴに短縮されていることが見て取れる。このような処理は、本出願人に係る特願２００８−２７４６８６号明細書に記述されている。

ただし、図３に示す並列処理においては、前の時刻の処理の終了を待たないで並列的に処理を進めるために、入力の予測を行う。そのため、予測が大きく外れている場合、そのまま処理を継続するとシミュレーションの結果が正しい結果から大きくそれてしまう可能性がある。

そこで、予測が誤っている場合には、正しい結果を入力として再度計算を行うロールバック処理を行い、正しい結果から大きくそれてしまう問題を回避する。ただし、通常、厳密な値の予測は難しいので、ある閾値を設定し、予測誤差がその範囲内であるならば、ロールバックは行わない。予測値と後から判明する本来の値が厳密に一致していない全ての場合にロールバックを行ってしまえば、通常、予測に基づいて並列的に実行された処理のほぼ全てが再度やり直されることとなり、並列性が失われる。そのため、この方法によってシミュレーションを高速化することはできない。

したがって、予測によって並列性を確保するためには、予測誤差をある程度許容することが必須となる。ただし、予測誤差を許容することにより、図４に示すように、処理の進行とともに誤差が蓄積していく。よって、あまり許容誤差を大きくしすぎれば、大きな並列性が得られる一方、計算結果が実際の正しいと思われる値から次第にずれて行き、ついにはシミュレーションの結果が許容できないものになってしまう恐れがある。図３に示す並列処理においては、許容誤差量と、並列化による実行速度にはトレードオフの関係があり、より少ない蓄積誤差と実行速度を両立する方法が必要である。

特開平２−２２６１８６号公報は、シミュレーション対象の時間的な変化を表す複数の変数群からなる連立微分方程式系を、時間の所定間隔で積分演算し、その変数群の値を用いて順次積分演算を繰り返し、対象の変化をシミュレーションする方法において、変数群のうちの一部の変数について、積分演算後の変数と、その微係数を用いて修正子を算出し、その修正子を用いて各変数値を修正することを開示する。

Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme Ottoni, David I. August, “Speculative Decoupled Software Pipelining”, In proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, 2007は、マルチコア環境で、処理のループを、スレッドに分解して、ソフトウェア・パイプライニングとして投機的に実行させる技法を開示する。

特開平２−２２６１８６号公報

[1] Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme Ottoni, David I. August, "Speculative Decoupled Software Pipelining", In proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, 2007

特許文献１は、シミュレーションにおいて、結果の変数の値を修正する一般的な技法を与える。一方、非特許文献１は、処理ループに対する投機的パイプライニングを開示する。しかし、特許文献１は、マルチコア環境におけるパイプライニングに関する適用について、示唆するものではない。

非特許文献１は、投機的パイプライニングの一般的なスキーム、及び制御ブロック間の内部状態の伝播に関する技法は提供するが、高速化のために誤差を許容した場合に蓄積していく誤差を解消するための技法については、特に示唆するものではない。

従って、この発明の目的は、マルチコアまたはマルチプロセッサ・システムにおいて、複数時刻の処理を投機的に並列化することによって高速化する際に、予測の誤差に基づく出力誤差を計算・補正することによって、誤差の累積の減少と、より大きな高速化性能を両立できる技法を提供することにある。

この発明によれば、マルチコアまたはマルチプロセッサ・システムの環境において、先ず、MATLAB(R)/Simulink(R)などで記述された制御ブロックの各時刻の処理が、投機的パイプライニングの技法で、好適には個別のスレッドまたはプロセスとして個別のコアまたはプロセッサに割り当てられる。

パイプライニングの性質により、次の時刻の処理を担うコアまたはプロセッサが実行中のスレッドまたはプロセスに対する入力は、前段の処理の出力を予測した値が入力として与えられる。この予測入力は、線形補間、ラグランジュ補間、最小二次法補間など、既存の任意の補間関数を用いることができる。

この補間入力に基づく出力に対して、当該スレッドの予測入力値と前の時刻の出力値の差分（予測誤差）と、シミュレーションモデルの予測入力周りの一次勾配の近似値を用いて、補正値が計算される。

特に、一般的なシミュレーションモデルの場合、変数値は複数あるので、一次勾配は、ヤコビ行列としてあらわされる。そこで、本発明では、その各々の成分が一次偏微分係数の近似値としての勾配値である行列をヤコビ行列と呼ぶことにする。すると、本発明において、補正値の計算は、このようにして定義されたヤコビ行列によって行なわれる。

本発明の１つの好適な特徴によれば、ヤコビ行列の計算は、シミュレーション本体の計算とは別のスレッドまたはプロセスとして、別個のコアまたはプロセッサに割り当てられ、シミュレーション本体の実行時間をほとんど増加させない。

この発明によれば、投機的パイプライニングによって実行されるシミュレーション・システムにおいて、一次勾配の近似値としてのヤコビ行列を計算して出力値を補正することにより、シミュレーションの精度を向上させ、また、ロールバックの頻度を減らすので、シミュレーションの速度を向上させる、という効果が得られる。

ループを含む機能ブロックの例を示す図である。 図１の機能ブロックを並列化した例を示す図である。 図１の機能ブロックを投機的パイプライン化した例を示す図である。 シミュレーションの実行による、予測値と実際値のずれの累積を示す図である。 本発明を実施するためのハードウェア構成の例を示すブロック図である。 ループを含む機能ブロックの例を示す図である。 図６の機能ブロックを投機的パイプライン化した例を示す図である。 機能ブロックのループを、関数の形で示したブロックを示す図である。 図８のブロックを投機的パイプライン化した例を示す図である。 予測値、計算値、及び実際の値の関係を示す図である。 ヤコビ行列の計算を伴って投機的パイプライニングで実行する処理の機能ブロック図である。 ヤコビ行列の計算を伴って投機的パイプライニングで実行する処理のフローチャートを示す図である。 ヤコビ行列の計算処理のフローチャートを示す図である。 トーラス状のアーキテクチャをもつシステムにおいて、本発明を実施する構成を示す図である。 並列論理プロセスを示す図である。 図１４の構成における、マスター・プロセスの処理のフローチャートを示す図である。 図１４の構成における、メイン・プロセスの処理のフローチャートを示す図である。 図１４の構成における、ヤコビ・スレッドの処理のフローチャートを示す図である。

以下、図面を参照して、本発明の一実施例の構成及び処理を説明する。以下の記述では、特に断わらない限り、図面に亘って、同一の要素は同一の符号で参照されるものとする。なお、ここで説明する構成と処理は、一実施例として説明するものであり、本発明の技術的範囲をこの実施例に限定して解釈する意図はないことを理解されたい。

図５を参照して、本発明を実施するために使用されるコンピュータのハードウェアについて説明する。図５において、ホスト・バス５０２には、複数のＣＰＵ１ ５０４ａ、ＣＰＵ２ ５０４ｂ、ＣＰＵ３ ５０４ｃ、・・・ＣＰＵｎ ５０４ｎが接続されている。ホスト・バス５０２にはさらに、ＣＰＵ１ ５０４ａ、ＣＰＵ２ ５０４ｂ、ＣＰＵ３ ５０４ｃ、・・・ＣＰＵｎ ５０４ｎの演算処理のためのメイン・メモリ５０６が接続されている。このような構成の典型的な例は、対称型マルチプロセッシング （ＳＭＰ）アーキテクチャである。

一方、Ｉ／Ｏバス５０８には、キーボード５１０、マウス５１２、ディスプレイ５１４及びハードティスク・ドライブ５１６が接続されている。Ｉ／Ｏバス５０８は、Ｉ／Ｏブリッジ５１８を介して、ホスト・バス５０２に接続されている。キーボード５１０及びマウス５１２は、オペレータが、コマンドを打ち込んだり、メニューをクリックするなどして、操作するために使用される。ディスプレイ５１４は、必要に応じて、後述する本発明に係るプログラムをＧＵＩで操作するためのメニューを表示するために使用される。

この目的のために使用される好適なコンピュータ・システムのハードウェアとして、ＩＢＭ（Ｒ）Ｓｙｓｔｅｍ Ｘがある。その際、ＣＰＵ１ ５０４ａ、ＣＰＵ２ ５０４ｂ、ＣＰＵ３ ５０４ｃ、・・・ＣＰＵｎ ５０４ｎは、例えば、インテル（Ｒ）Ｘｅｏｎ（Ｒ）であり、オペレーティング・システムは、Ｗｉｎｄｏｗｓ（商標）Ｓｅｒｖｅｒ ２００３である。オペレーティング・システムは、ハードティスク・ドライブ５１６に格納され、コンピュータ・システムの起動時に、ハードティスク・ドライブ５１６からメイン・メモリ５０６に読み込まれる。

本発明を実施するためには、マルチプロセッサ・システムを用いることが必要である。ここでマルチプロセッサ・システムとは、一般に、独立に演算処理し得るプロセッサ機能のコアを複数もつプロセッサを用いるシステムを意図しており、従って、マルチコア・シングルプロセッサ・システム、シングルコア・マルチプロセッサ・システム、及びマルチコア・マルチプロセッサ・システムのどれかでよいことを理解されたい。

なお、本発明を実施するために使用可能なコンピュータ・システムのハードウェアは、ＩＢＭ（Ｒ）Ｓｙｓｔｅｍ Ｘに限定されず、本発明のシミュレーション・プログラムを走らせることができるものであれば、任意のコンピュータ・システムを使用することができる。オペレーティング・システムも、Ｗｉｎｄｏｗｓ（Ｒ）に限定されず、Ｌｉｎｕｘ（Ｒ）、Ｍａｃ ＯＳ（Ｒ）など、任意のオペレーティング・システムを使用することができる。さらに、シミュレーション・プログラムを高速で動作させるために、ＰＯＷＥＲ（商標）６ベースで、オペレーティング・システムがＡＩＸ（商標）のＩＢＭ（Ｒ）Ｓｙｓｔｅｍ Ｐなどのコンピュータ・システムを使用してもよい。

さらに、本発明を有利に実施するために使用可能なコンピュータ・システムのハードウェアとして、インターナショナル・ビジネス・マシーンズ社から入手可能な、Blue Gene(R) Solutionがある。

ハードティスク・ドライブ５１６にはさらに、MATLAB(R)/Simulink(R)、Ｃコンパイラまたは、Ｃ＋＋コンパイラ、後述する本発明に係る解析、平坦化、クラスタリング、展開のためのモジュール、ＣＰＵ割り当て用コード生成モジュール、処理ブロックの期待される実行時間を測定するためのモジュールなどが格納されており、オペレータのキーボードやマウス操作に応答して、メイン・メモリ５０６にロードされて実行される。

なお、使用可能なシミュレーション・モデリング・ツールは、MATLAB(R)/Simulink(R)に限定されず、オープンソースのScilab/Scicosなど任意のシミュレーション・モデリング・ツールを使用することが可能である。

あるいは、場合によっては、シミュレーション・モデリング・ツールを使わず、直接、Ｃ、Ｃ＋＋などでシミュレーション・システムのソース・コードを書くことも可能であり、その場合にも、個々の機能が、互いに依存関係にある個別の機能ブロックとして記述できるなら、本発明は適用可能である。

図６及び図７は、本発明の１つの背景技術としての、非特許文献１によって開示される投機的パイプライニングの技術を説明する図である。

図６は、機能ブロックＡ、Ｂ、Ｃ及びＤからなる、例示的なSimulink(R)のループを示す図である。

この機能ブロックＡ、Ｂ、Ｃ及びＤのループが、図７に示すように、投機的パイプライニングの技術によって、ＣＰＵ１、ＣＰＵ２及びＣＰＵ３に割り当てられる。すなわち、ＣＰＵ１が、１つのスレッドで機能ブロックＡ_k-1、Ｂ_k-1、Ｃ_k-1及びＤ_k-1を順次実行し、ＣＰＵ２が、別のスレッドで機能ブロックＡ_k、Ｂ_k、Ｃ_k及びＤ_kを順次実行し、ＣＰＵ３が、さらに別のスレッドで機能ブロックＡ_k+1、Ｂ_k+1、Ｃ_k+1及びＤ_k+1を順次実行する。

ＣＰＵ２は、ＣＰＵ１がＤ_k-1を完了するのを待つことなく、予測入力によって投機的に処理を開始する。ＣＰＵ３は、ＣＰＵ２がＤ_kを完了するのを待つことなく、予測入力によって投機的に処理を開始する。このような投機的パイプライニングの処理によって、全体の処理速度が向上される。

特に非特許文献１が開示するのは、ＣＰＵ１からＣＰＵ２に、また、ＣＰＵ２からＣＰＵ３に、機能ブロックの内部状態が伝播されることである。通常、Simulink(R)などによるシミュレーションモデルにおいては、機能ブロックが内部状態を持つことがある。この内部状態は、ある時刻の処理によって更新され、その値が次の時刻の処理によって使用される。したがって、複数の時刻の処理を投機的に並列化して実行する場合には、この内部状態に対しても予測が必要となるが、非特許文献１にあるように、これらの内部状態をパイプライン的に受け渡すことで、その予測が不要となる。例えば、ＣＰＵ１で実行されたＡ_k-1の内部状態x_A(t_k)が、機能ブロックＡ_kを実行するＣＰＵ２に伝播され、ＣＰＵ２で利用される。これによって、この投機的パイプライニングの技術では、内部状態の予測は不要である。

図８は、図６に示すような機能ブロックのループを関数表記であらわした図である。すなわち、u_kを入力して、u_k+1 = F(u_k)という処理の結果として得られたu_k+1が出力される。

なお、u_k+1 = F(u_k)において、F(u_k)という解析的にあらわされる関数が存在するとは限らないことに留意されたい。要するに、u_kという入力で以って機能ブロックを実行すると、その処理の結果、u_k+1が出力される、ということである。

またu_kも、F(u_k)も、実際はベクトルであって、
u_k = (u₁(t_k), ... ,u_n(t_k))^T
F(u_k) = (f₁(u_k), ... ,f_n(u_k))^T
のように表記される。

図９は、図８のループを、投機的パイプライニング処理する場合の図である。図９において、その一段目は、１つのＣＰＵで、u_k-1 = F(u_k-2)という処理が出力されるが、その二段目では、別のＣＰＵで、u^* _k = F(u^_k-1)という結果が計算出力される。ここで、二段目には、一段目の処理の結果u_k-1ではなく、予測された入力u^_k-1が入力されることに留意されたい。すなわち、一段目の処理が終わるのを待つと遅くなるので、前段から予測された入力u^_k-1を用意して二段目に入力することによって、処理を並列化し、高速化させる。

同様に、三段目には、二段目の計算処理の結果の^*u_kではなく、予測された入力u^_kが入力され、結果的に、u^* _k+1 = F(u^_k)が計算されて出力される。
なお、以下では、u^という表記を、

と同一視することに留意されたい。

予測が成功した場合は、このような投機的パイプライニングによって、シミュレーションの動作速度は向上できるが、予測入力u^_kと、実際の入力u_kに誤差がある場合、正しい入力値を用いて再度計算を行うロールバック処理が行われるため、動作速度が向上しない。通常、予測入力を実際の入力に厳密に一致させることは難しいため、予測誤差がある閾値以下である場合、予測は成功したものと見なして、計算結果をそのまま採用することで、多くのシミュレーションモデルに対して高速化を実現する。その場合、許容した誤差が次第に蓄積していくという問題が発生する。そのことは、図１０に典型的に示される。

すなわち、図１０に示すように、u^_k-1からu^* _kが計算されるが、このu^* _kは次の段の計算に使われることなく、次の段は、新たな予測入力u^_kで始まり、この計算結果は、
u^* _k+1となる。

そこで、予測値と実際の値の差をε_k = u^_k - u_kとし、
計算値と実際の値の差をε^* _k = u^* _k - u_kとすると、図１０から見て取れるように、時間の経過とともに、誤差ε^* _kは、誤差ε_kよりもさらに拡大する可能性がある。

このように誤差が累積していくと、シミュレーションの結果が許容できないものとなってしまう可能性がある。

本発明は、このように累積する誤差を小さいレベルに抑えることを目的とするものであり、図８及び図９の構成から得られる出力に、所定の計算によって得られる補正を加えることによって、そのような誤差を解消するものである。以下、そのアルゴリズムを説明する。

先ず、ベクトル関数F(u_k)のテイラー展開は、次のようになる。
F(u_k) = F(u^_k) - J_f(u^_k)ε_k + R(|ε_k|²)

ここで、J_f(u^_k)は、ヤコビ行列で、次のような式であらわされる。

また、R(|ε_k|²)はテイラー展開の二次以上の項を表す。
ε_kは、予測精度が高い場合、そのすべての成分が小さい実数であるベクトルとなる。ε_kが小さい場合、テイラー展開の二次以上の項も小さくなるため、R(|ε_k|²)は無視することができる。ε_kが大きい場合には、R(|ε_k|²)が無視できず、補正計算は実行できない。その場合には、前の時刻の出力結果を入力として再度計算を行うロールバック処理を行う。このとき、ε_kが十分に小さいかどうかは、予め与えられる閾値によって判定する。

ε^* _k+1 = F(u^_k) - F(u_k)であるから、これは、R(|ε_k|²)を無視できるとすると、
J_f(u^_k)ε_kにほぼ等しい。

ここで、ε_k = u^_k - u_kであることと、ε^* _k = u^* _k - u_kであることを用いると、
ε^* _k+1は、J_f(u^_k)(u^_k - u_k)で近似できることになる。

ところが、F(u_k) = (f₁(u_k), ... ,f_n(u_k))^Tは、
u_k = (u₁(t_k), ... ,u_n(t_k))^Tに対して、解析的に偏微分可能とは限らず、よって、上記のヤコビ行列を解析的に求めることが可能とは限らない。

そこで、本発明では、下記のような差分の式により、ヤコビ行列を近似計算する。

ここで、H_i = (0...0 h_i 0...0)^Tで、すなわち、左からi番目の要素かh_iで、その他が0の行列である。また、h_iは、適当な小さいスカラー値である。

このようにして定義されたヤコビ行列を近似式J^_f(u^_k)を以って置き換えることにより、
ε^* _k+1 = J^_f(u^_k)(u^_k - u_k)と計算され、
さらに、このε^* _k+1を使ってu_k+1 = u^* _k+1 - ε^* _k+1によって、補正された値u_k+1が得られる。
このような計算により、誤差の累積を減少させるのが、この発明の骨子である。

次に、図１１を参照して、本発明に従い、投機的パイプライニングにおいて、上述した誤差補正機能を行うシステムの構成について説明する。

まず、ＣＰＵ１に割り当てられたブロック１１０２には、u_k-2が入力され、ブロック１１０２は、u_k-1 = F(u_k-2)を出力する。

これと並行して、ＣＰＵ２に割り当てられたブロック１１０４には、予測された値u^_k-1が入力され、ブロック１１０４は、u^* _k = F(u_k-1)を出力する。

なお、予測された値の計算は例えば、以下に示すような方法で、ブロック１１０６で行われる。
その１つの方法は、線形補間であり、下記のような式であらわされる。
u^_i(t_k+m+j) = m・u_i(t_k+j+1) - (m-1)・u_i(t_k+j)

別の方法として、ラグランジュ補間があり、下記のような式であらわされる。

予測された値の計算手法は、これには限定されず、例えば最小二乗法補間など、任意の補間方法を使用することができる。ブロック１１０６で行われる処理は、ＣＰＵの数に余裕がある場合、別のスレッドとして、ブロック１１０４が割り当てられているＣＰＵとは別のＣＰＵに個別に割り当ててもよい。あるいは、ブロック１１０４が割り当てられているＣＰＵで処理するようにしてもよい。

この実施例で特徴的なのは、ヤコビ行列の成分を計算する補助スレッド１１０４_１〜１１０４_ｎが別途起動されることである。すなわち、補助スレッド１１０４_１では、
F(u^_k-1+H₁)/h₁が計算され、補助スレッド１１０４_ｎでは、
F(u^_k-1+H_n)/h_nが計算される。このような補助スレッド１１０４_１〜１１０４_ｎは、ＣＰＵの数に余裕がある場合、ブロック１１０４が割り当てられているＣＰＵとは別のＣＰＵに個別に割り当てられて、本来の計算を遅延させることなく実行することができる。

なお、もしＣＰＵの数に余裕がない場合、補助スレッド１１０４_１〜１１０４_ｎは、ブロック１１０４が割り当てられているＣＰＵと同一のＣＰＵに割り当てることもできる。

ブロック１１１２では、ブロック１１０２からのu_k-1と、ブロック１１０４からの
u^* _kと、補助スレッド１１０４_１〜１１０４_ｎからの、
F(u^_k-1+H₁)/h₁、F(u^_k-1+H₂)/h₂、・・・、F(u^_k-1+H_n)/h_nすなわち、
J^_f(u^_k-1)とを用いて、
u_k = u^* _k - J^_f(u^_k-1)(u^_k-1 - u_k-1)
という式により、u_kが計算される。

これと並行して、ＣＰＵ３に割り当てられたブロック１１０８には、ブロック１１０６と同様のアルゴリズムで、ブロック１１１０から予測された値u^_kが入力され、ブロック１１０８は、u^* _k+1 = F(u_k)を出力する。ブロック１１１０で行われる処理は、ＣＰＵの数に余裕がある場合、別のスレッドとして、ブロック１１０８が割り当てられているＣＰＵとは別のＣＰＵに個別に割り当ててもよい。あるいは、ブロック１１０８が割り当てられているＣＰＵで処理するようにしてもよい。

ブロック１１０８にも、ブロック１１０４の場合と同様に、ヤコビ行列の成分を計算する補助スレッド１１０８_１〜１１０８_ｎが別途起動されて、関連付けられる。以降の処理は、ブロック１１０４及び補助スレッド１１０４_１〜１１０４_ｎの場合と同様であるので、説明は繰り返さないが、補正値ε^* _k+1を計算するために、ブロック１１１４は、ブロック１１１２から、u_kを受け取ることを理解されたい。

ブロック１１１４や、それ以降の補正も同様に計算される。

図１２は、この実施例のシミュレーション本体の処理を実行するスレッド（メインスレッド）の動作を示すフローチャートである。

最初のステップ１２０２では、そのスレッドでの処理に用いられる各変数の初期化を行う。まず、iにスレッドＩＤがセットされる。ここでは、パイプライニングの最初の段のスレッドのスレッドＩＤが0で、次の段のスレッドのスレッドＩＤが１となる、というように増分されるものとする。ｍにはメインスレッドの数がセットされる。ここでメインスレッドとは、パイプライニングの各段の処理を実行するスレッドを指す。ｎには、ロジックの数がセットされる。ここで、ロジックとは、シミュレーション・モデルの処理全体をいくつかの塊に分割した一つの塊を指し、これを順次化して並べたものがメインスレッドで繰り返し実行する１タイムステップ分の処理となる。図６の例では、A,B,C,Dのそれぞれが、各々一つのロジックである。

nextという変数には、(i+1)%m、すなわち、(i+1)をmで割った余りが格納される。これは、i番目のメインスレッドの次の時刻の処理を担当するスレッドのIDとなる。
また、tiにはiがセットされる。tiは、i番目のスレッドが実行すべき処理の時刻を表し、ステップ１２０２の段階においては、i番目のスレッドは時刻iから処理を開始することとなる。

更に、rollbackiおよびrb_initiatorにはFALSEがセットされる。これらの変数は、予測誤差が大きすぎて補正が実行できない場合のロールバック処理を、複数のメインスレッドにまたがって実行するための変数である。

ステップ１２０４では、iが0であるかどうか、すなわち、当該スレッドが最初（0番目）のスレッドであるかをチェックする。当該スレッドが最初のスレッドである場合には、初期入力を入力として処理を開始するために、１２０６において
関数set_ps(P, 0, initial_input)を呼び出す。ここで、initial_inputはシミュレーションモデルの初期入力（ベクトル）を指す。また、Pは未来の時刻の入力の予測に利用する過去の時刻の入力点（時刻と入力ベクトルの組）を保持しておくためのバッファである。関数set_ps(P, t, input)は、Pに、時刻tの入力としてinputを記録するという動作を行うものであって、すなわち、set_ps(P, 0, initial_input)によって、Pに、時刻0と初期入力の組がセットされる。ここに記録された値が、後に当該スレッドで実行される最初のロジックへの入力となる。また、j = 0とセットされる。

次に、ステップ１２０８、１２１０では、0番目のスレッドが時刻0の処理を実行するのに必要となる各ロジックの（初期）内部状態を当該スレッドが使用できるようにしている。

ステップ１２１０においては、関数set_state(S₀, 0, j, intial_state_j)が呼び出される。ここで、S₀は0番目(S_iであればi番目）のスレッドの各ロジックが使用する内部状態を保持しておくためのバッファであり、時刻と、ロジックIDを示す数値の組に、１つの内部状態を表すデータが対応する形で内部状態が記録される。
set_state(S₀, 0, j, intial_state_j)の呼び出しによって、S₀に、ロジックID jと、時刻0の組（j, 0)に対して、（初期）内部状態intial_statejが記録されることとなる。ここで記録された（初期）内部状態は、後に0番目のスレッドが各ロジックを実行する段階で利用される。

jが1増分されることと、ステップ１２０８での判断により、ステップ１２１０は、jがnに達するまで繰り返される。jがnに達すると、ステップ１２０８での判断により、ステップ１２１２に移る。

iが0でない場合は、最初のスレッドではないため、ステップ１２０２の時点では時刻t_iにおける入力値（すなわち時刻t_i-1の処理の出力値）が得られていない。そこで直接ステップ１２１２に移る。

ステップ１２１２では、predict(P, t_i)という関数が呼ばれて、その結果がinputに代入される。predict(P, t_i)は、時刻tiの処理の入力ベクトルを予測し、予測された入力ベクトルを返す。

この際の予測アルゴリズムとしては、前述のように、Pに蓄積されたベクトルデータを用いて、線形補間や、ラグランジュ補間などが適用される。ただし、P中に、時刻t_iに対するベクトルデータが既に記録されている場合には、そのベクトルデータが返される。図１１の実施例では、ブロック１１０６、１１１０などによって実行される。なお、開始直後は、予測を実行するのに十分な点（時刻と入力ベクトルの組）がPに保持されていない場合があり、その場合には、必要な点がPに与えられるまで待つ。すなわち、前の時刻を担当しているスレッドが処理を終えるまで待つこととなる。
こうして、predict(P, t_i)の呼び出しによって得られたベクトルデータは、
predicted_inputという変数に格納される。

次に同ステップでは、当該スレッドが使用するヤコブ行列を計算するスレッドをスタートさせるために、start(JACOBI_THREADSi, input, t_i)が呼ばれる。ここでスタートされるヤコブ行列計算用のスレッドの処理は、図１３に示し、内容は後述する。

次のステップ１２１４、１２１６、１２１８では、ロジックを順次実行していき、全ロジックが実行し終わった段階で、次のステップ１２２０に移る処理を行う。すなわち、ステップ１２１４では、jが0にセットされ、ステップ１２１６では、jがnより小さいかどうかが判断される。そして、ステップ１２１６での判断により、jがnに達するまでステップ１２１８が実行される。

ステップ１２１８では、一つロジックが実行される。そこでは、まず
get_state(S_i, t_i, j)が呼ばれる。この関数は、S_i中に、(t_i, j)の組に対応付けられて記録されているベクトルデータ（内部状態データ）を返す。ただし、そのようなデータがない場合、あるいは（t_i, j)の組に対応付けられているデータにフラグがセットされている場合は、Siに(t_i, j)の組に対するデータが記録されるかまたは、フラグが解除されるまで待つ。
get_state(S_i, t_i, j)から返された結果は、変数stateに格納される。

次に同ステップでは、exec_b_j(input, state)が呼ばれる。この関数は、j番目のロジックをb_jとしたとき、b_jへの入力をinput, b_jへの内部状態をstateとして、その処理を実行する。その結果として、次の時刻の内部状態（updated)と、bjの出力（output）の組を返す。

こうして返されたupdatedは、次のset_state(S_next, t_i+1, j, updated)の呼び出しの引数に使われる。この呼び出しによって、S_next中に、(t_i+1, j)の組にupdatedが対応付られた形で内部状態が記録される。その際、(t_i+1, j)の組に対応するベクトルデータが既に存在する場合は、それがupdatedで上書きされ、セットされているフラグが解除される。この処理によって、next番目のスレッドが各ロジックを実行する際に、必要な内部状態を参照して使用することができるようになる。

次に同ステップでは、outputがinputに代入される。これはb_j+1への入力となる。そしてjが1増分されてステップ１２１６に戻る。こうして、jがnに達するまでステップ１２１８が繰り返されて、jがnに等しくなると、次のステップ１２２０に移る。

ステップ１２２０以降では、予測入力に基づき計算された値を補正する段階であるが、前述の通り、予測誤差があまりに大きい場合は、ロールバック処理が行われる。
ステップ１２２０では、rb_initiatorがTRUEであるかどうかの判断が行われる。
rb_initiatorがTRUEである場合は、当該スレッドが、以前にロールバック処理を発動させ、ロールバック処理中であることを表している。一方、rb_initiatorがFALSEである場合は、当該スレッドは、ロールバック処理を発動しておらず、ロールバック処理中でもないことを表している。通常の補正を実行する流れではrb_initiatorはFALSEとなっている。
当該ステップにおいて、rb_initiatorがFALSEであると判断されると、ステップ１２２２に移る。

ステップ１２２２では、rollback_iの値がTRUEであるかが判断される。rollback_iの値がTRUEである場合、当該スレッドより前のスレッドによってロールバック処理が発動され、当該スレッドがロールバックに必要な処理を実行しなければならないことを表している。一方、rollback_iの値がFALSEである場合には、当該スレッドはロールバックに必要な処理を実行する必要がないことを表している。通常の補正を実行する流れではrollback_iはFALSEとなっている。当該ステップにおいて、rollback_iがFALSEであると判断されると、ステップ１２２４に移る。

ステップ１２２４では、get_io(I_i, t_i-1)が呼ばれる。ここで、I_iは、i番目のスレッドが使用する先頭のロジックの入力を保持しておくためのバッファである。
このバッファには、時刻と入力ベクトルの組が一つだけ記録される。get_io(I_i, t_i-1)では、I_iに記録されている入力ベクトルが返されるが、与えられた時刻（t_i-1）が、入力ベクトルと組になって記録されているいる時刻と一致しない、あるいはデータが存在しない場合には、NULLを返す。

続いて、ステップ１２２６では、t_iが0であるかどうかが判断される。
これは、t_iが0の場合には、それより前の時刻の出力というものが存在せず、ステップ１２２８において必ずactual_inputがNULLとなるため、補正計算のために前の時刻の出力結果が得られるまで待つための判断であるステップ１２２８で無限ループに陥るのを避けるためのステップである。

t_iが0である場合は、補正計算などのステップは行わず、直接ステップ１２３６に移る。t_iが0でない場合は、ステップ１２２８へ移る。

ステップ１２２８では、actual_inputがNULLであるかどうかが判断される。
actual_inputがNULLである場合、前の時刻の処理の出力がまだ得られていないことを表す。これは前述のように、補正計算のために必要となる前の時刻の処理の出力結果が得られるまで待つための判断であり、必要な出力が得られていない場合には、ステップ１２２２に戻る。必要な出力が得られている場合には、actual_inputがNULLとなっていないため、ステップ１２３０へ移る。

ステップ１２３０では、correctable(predicted_input, actual_input)が呼び出される。この関数は、それぞれが同じ要素数のベクトルであるpredicted_inputとactual_inputのユークリッドノルムが所定の閾値を超えた場合にFALSE、そうでない場合にTRUEを返す。correctable(predicted_input, actual_input)がFALSEを返す場合は、予測誤差が大きすぎて、補正処理が行えないことを表し、TRUEである場合には、補正が可能であることを表す。補正が可能な場合、ステップ１２３４へ進む。

ステップ１２３４では、まず、get_jm(J_i, t_i)が呼ばれる。ここで、J_iは、i番目のスレッドが使用するヤコブ行列を保持しておくためのバッファで、ヤコブ行列の各列ベクトルが時刻の値と組となって形で記録されている。
get_jm(J_i, t_i)は、J_i中に記録されているヤコブ行列を返す関数であるが、ヤコブ行列の各列ベクトルに組となって記録されている全時刻データが、与えられた引数t_iと等しくなるまで待ってからヤコブ行列を返す。

こうして得られたヤコブ行列を変数jacobian_matrixとし、次にcorrect_output(predicted_input, actual_input, jacobian_matrix, output)を呼び出す。この関数は、要するに、図１１のブロック１１１２またはブロック１１１４で実行される計算に対応する。

ブロック１１１４を例に取れば、predicted_inputがu^_kに対応し、actual_inputがukに対応し、jacobian_matrixがJ^f(u^_k)に対応し、outputが、u^* _k+1に対応する。この関数の戻り値はu_k+1となる。当該ステップでは、correct_output(predicted_input, actual_input, jacobian_matrix, output)の結果得られた補正された出力を、outputに格納する。

その後、ステップ１２３６へ進み、まずset_io(I_next, t_i, output)が呼び出される。この関数は、I_nextに、時刻t_iとoutputの組で、既にI_nextに記録されているデータを上書きする。これはnext番目のスレッドによってそのスレッドの予測誤差の計算や、出力補正のために用いられる。

次に、同ステップでは、set_ps(P, t_i+1, output)が呼び出される。これにより、Pに時刻t_i+1の入力データとして、outputが記録される。次に、t_iがmだけ増加され、処理はステップ１２３８の判断に進む。

ステップ１２３８では、t_i > Tかどうかが判定される。ここでTは、実行しているシミュレーションが出力するシステムの挙動の時系列の長さを表す値である。

t_iがTを超えている場合には、それ以上の先の時刻のシステムの挙動は不要であるため、そのスレッドの処理を終了する。t_iがTを超えていない場合には、ステップ１２１２に戻り、当該スレッドが次に実行すべき時刻の処理を実行する。

ステップ１２３０で、correctable(predicted_input, actual_input)が、FALSEを返す場合、ステップ１２３２へ進み、ロールバックを行うための準備が行われる。
ステップ１２３２では、inputにactual_inputが設定され、rollback_nextにTRUEがセットされ、rb_initiatorがTRUEとされ、rb_state(S_next, t_i+1)が呼び出される。
rollback_nextがTRUEにセットされることで、next番目のスレッドにおいても、現在実行している時刻の処理を再度やり直さねばならないことを伝達することができる。
関数rb_state(S_next, t_i+1)では、Snext中に（t_i+1, k)に対応付けて記録されているベクトルデータに、それが無効であることを示すフラグをセットする。ただし、ここでk=0, ..., n-1である。

これは、各ロジックによって計算された内部状態が無効であることを示すもので、このようにフラグがセットされた内部状態はnext番目のメインスレッド上のロジックによって使用されなくなる。これにより、そのメインスレッド上のロジックは、計算の実行を、ロールバックが完了して正しい内部状態がS_nextに与えられるまで待たされることとなり、間違った値に基づいて計算が進行してしまうのを防ぐ。
その後、ステップ１２１４に戻ることで、前の時刻の処理結果であるベクトルデータを入力として使用して、同じ時刻の処理を再度やり直すこととなる。

ステップ１２１４、ステップ１２１６、ステップ１２１８を経て、同じ時刻の処理がやり直された場合、ステップ１２２０へ進むと、必ずrb_initiatorがTRUEと判定される。
この場合には、ステップ１２４０へ進み、set_io(I_next, t_i, output)を呼び出すことで、再計算された出力を、next番目のスレッドに伝達し、set_ps(P, t_i+1, output)が呼び出されて、予測に用いるデータを更新する。

その後、ステップ１２４２へ進む。ステップ１２４２では、rollback_iがTRUEになるまで待ち続けることになる。この変数rollback_iは、当該スレッドの一つ前のスレッドが、次のように振舞うことによりFALSEへと変更され、このループから抜けることができる。

まず、当該スレッドにおいて、ステップ１２３２でrollback_nextをTRUEにしたことにより、next番目のスレッドのステップ１２２２において、処理が１２４４へと分岐することになる。

そのスレッドのステップ１２４４では、rb_state(S_next, t_i+1)が呼び出され、前述のような内部状態の無効化が行われた後、rollback_iをFALSEにし、rollback_nextをTRUEにする。これによって更に次のスレッドに同様のやり直し処理（ロールバック）を伝播させていくことができる。これを順繰りにおこなうことにより、最後はロールバック処理を発動したスレッドのロールバックフラグ（rollback_i）がTRUEとなる。
これによってそのスレッドは、ステップ１２４２のループから抜け出し、ステップ１２４６へと進む。

ここでrollbackiをFALSEにし、ロールバック処理を発動したスレッドであることを示すフラグrb_initiatorをFALSEにして、通常の予測に基づくロジックの処理１２１２へと移行する。

ここで、図１２のステップ１２０８におけるstart(JACOBI_THREADS_i,input,t_i)によって実行される処理を詳細説明する。
JACOBI_THREADS_iは、複数のスレッドを表しており、そのk番目のスレッドの処理を表すフローチャートを図１３に示す。

ステップ１３０２では、mod_input = input + fruc_vector_kという演算が行われる。ここで、fruc_vector_kは、ベクトルサイズがモデルの先頭ロジックの入力ベクトルの要素数に等しく、k番目の要素がh_k、それ以外は全て0であるような列ベクトルデータである。これは、図１１に関連して、H_i = (0...0 h_i 0...0)Tとして説明したものの、iをkと読み替えたものと同一である。この処理では、ヤコブ行列を計算するために、入力ベクトルの１成分のみを微小にずらした入力値を作成している。

ステップ１３０４では、jが一旦0にセットされ、以下、判断ステップ１３０６により、jがnに達するまで、ステップ１３０８が繰り返される。ここでnとは、図１２のステップ
１２０６でセットしたモデルに含まれるロジックの数であり、単にmod_inputを入力として、ロジック全体を実行することを意味している。

ステップ１３０８ではまず、get_state(S_i,t_i,j)が呼ばれる。get_state(S_i,t_i,j)は、図１２で呼ばれる同名の関数と同じ処理である。その結果は変数stateにセットされる。

ステップ１３０８では次に、exec_b_j(mod_input,state)が呼ばれる。exec_bj(mod_input,state)は、図１２で呼ばれる同名の関数と同じ処理であり、一つのロジックの処理を実行している。

ステップ１３０８では次に、exec_b_j(mod_input,state)の実行の結果得られたoutputが、mod_inoutにセットされ、jが1だけ増分されて、ステップ１３０６に戻る。これによって次のロジックへと処理が移る。

こうして、ステップ１３０８の繰り返しによりj = nになると、全ロジックの処理が終了するので、ステップ１３１０に行き、そこで、set_jm(J_i,t_i,k,mod_input/h_k)が呼ばれる。

set_jm(J_i,t_i,k,mod_input/h_k)は、J_iに、ヤコブ行列のk列目のベクトル要素として、
mod_input/h_kを、時刻t_iと関連付けて記録する。このとき、既に記録されているデータは、上書きされる。

ステップ１３１０の後は、図１３のフローチャートで示す処理は終了する。
k=0, ..., n-1の全てのスレッドが終了すると、時刻tiに対応したヤコブ行列が完成する。

図１４は、トーラス的に立体的にノード間接続されたアーキテクチャをもつコンピュータ・システムで本発明を実施する様子を示す図である。このようなアーキテクチャをもつコンピュータ・システムとして、これには限定されないが、インターナショナル・ビジネス・マシーンズ社から入手可能な、Blue Gene(R) Solutionがある。

図１４において、ノード１４０２には、全体の演算処理を管理するマスタープロセスが割り当てられる。ノード１４０２には、ノード１４０４＿１、１４０４＿２、・・・、１４０４＿ｐが関連付けられ、それぞれには、メインプロセス＃１、＃２・・・＃ｐが割り当てられる。メインプロセス＃１、＃２・・・＃ｐに割り当てられる処理は、図１１で、ブロック１１０２、１１０４及び１１０８で示されている処理と、論理的に等価である。

また、ノード１４０４＿１には、一連のノード１４０４＿１＿１、ノード１４０４＿１＿２、・・・ノード１４０４＿１＿ｑが関連づけられる。そうして、ノード１４０４＿１＿１、ノード１４０４＿１＿２、・・・ノード１４０４＿１＿ｑには、ヤコビ・スレッド＃１−１、＃１−２、・・・、＃１−ｑが割り当てられる。ヤコビ・スレッド＃１−１、＃１−２、・・・、＃１−ｑに割り当てられる処理は、図１１で、ブロック１１０４＿１〜１１０４＿ｎで示されている処理と、論理的に等価である。

ノード１４０４＿２には、一連のノード１４０４＿２＿１、ノード１４０４＿２＿２、・・・ノード１４０４＿２＿ｑが関連づけられる。そうして、ノード１４０４＿２＿１、ノード１４０４＿２＿２、・・・ノード１４０４＿２＿ｑには、ヤコビ・スレッド＃２−１、＃２−２、・・・、＃２−ｑが割り当てられる。

同様に、ノード１４０４＿ｐには、一連のノード１４０４＿ｐ＿１、ノード１４０４＿ｐ＿２、・・・ノード１４０４＿ｐ＿ｑが関連づけられる。そうして、ノード１４０４＿ｐ＿１、ノード１４０４＿ｐ＿２、・・・ノード１４０４＿ｐ＿ｑには、ヤコビ・スレッド＃ｐ−１、＃ｐ−２、・・・、＃ｐ−ｑが割り当てられる。

図１５は、図１４のシステム上で実行されるプロセスを模式的に示す図である。パイプライニング・プロセス１５０２＿１、１５０２＿２、・・・、１５０２＿ｐは、それぞれ、ノード１４０４＿１、１４０４＿２、・・・、１４０４＿ｐに割り当てられた処理であり、その各々が、ロジックＡ、Ｂ、・・・、Ｚからなっている。ロジックＡ、Ｂ、・・・、Ｚは、図６において、ブロックＡ、Ｂ、Ｃ及びＤで示されているような機能ブロックと同等のものである。なお、図１５では、補助スレッドである一連のヤコビ・スレッドは、図示を省略されている。

図１５で、制御ロジック（外部ロジック）１５０４とあるのは、シミュレーション・システムにおける、その他の処理を総称的に示すものである。例えば、Simulinkが、外部プログラムと連携して動作する場合があるが、その外部プログラムなどを指す。

図１６は、図１４のシステムにおける、マスター・プロセス１４０２のフローチャートである。図１６において、ステップ１６０２では、kに、ある初期値k_INIが与えられる。

図１６において、pは、プロセッサ数であり、図１４のpと同一である。図１６の処理では、p台のメイン・プロセスが、timestamp = k ... k+(p-1) の範囲を並列的に計算する。

マスター・プロセスは、ステップ１６０４で、次のタイムスタンプ（k+p）のための入力を予測して、その担当メイン・プロセスに、ステップ１６０６で、その入力を非同期で送る。ここでの担当メイン・プロセスは、実際には、今timestamp=kを実行しているプロセスになる。なお、その入力の予測には、前述した、線形補間、ラグランジュ補間などが使用される。

次に、マスター・プロセスは、ステップ１６０８で、真っ先に処理が終わるはずのtimestamp=k 担当のプロセッサの出力を待って受信する。マスター・プロセスが、同期のために待つのはここだけである。

ステップ１６１０では、マスター・プロセスは、投機的パイプライニング処理とは直接関係ない外部ロジック１５０４（図１５）を実行する。

ステップ１６１２では、マスター・プロセスは、k>=k_FINであるかどうか判断し、もしそうなら、マスター・プロセスの処理は完了する。

k>=k_FINでなければ、マスター・プロセスは、ステップ１６１４で、timestamp=k の外部ロジックからの出力を、timestamp=k+1 担当のプロセッサへ非同期送信する。

尚、timestamp=k 担当のプロセスは、その時刻の処理が終了すると、次は
timestamp=k+p 担当になる。このとき既に、予測入力が届いているので、休むことなく、すぐに処理を開始することになる。

これが、p個のプロセスを同時並行的に待たせることなく動作させる方法で、そのために、予測入力は、先行して処理される。図１６では、timestamp=k の出力を受信する前に timestamp=k+p の入力を予測しているが、上記の並行処理の状況を典型的に説明するためである。

図１７は、各タイムスタンプ(Timestamp=k, k+1, ・・・,k+p)でのメイン・プロセス（図１４）の処理を示すフローチャートである。

ステップ１７０２では、メイン・プロセスは、マスター・プロセスから予測入力を受信する。ステップ１７０４では、メイン・プロセスは、ステップ１８０２で受信した予測入力を、そのまま勾配プロセスに非同期伝播送信する。

ステップ１７０６では、メイン・プロセスは、次のロジックがあるかどうか判断する。ここで、ロジックとは、図１６でロジックＡ、ロジックＢ、・・・ロジックＺなどとして示されているものである。

メイン・プロセスが、次のロジックがあると判断すると、ステップ１７０８に進み、そこで、一つ前の時刻を担当しているメインプロセスから、当該メインプロセスで使用する内部状態を受信する。ステップ１７１０では、受信した内部状態をそのまま勾配プロセスに非同期送信する。

ステップ１７１２では、メイン・プロセスは、所定のロジックの処理を実行する。そうして、ステップ１７１４で、メイン・プロセスは、ロジックの実行の結果更新された内部状態を、次の時刻の処理を担当するメイン・プロセスへ非同期送信する。

ステップ１７０６で、メイン・プロセスが、次のロジックがないと判断した場合、ステップ１７１６に進み、最後尾の勾配スレッドから、勾配出力を受信する。

ステップ１７１８では、メイン・プロセスは、修正入力を受信する。修正入力とは、図１１を例にとると、例えばブロック１１１２から出力される、補正後の前の時刻の出力u_kである。

ステップ１７２０では、メイン・プロセスは、修正入力u_kと、勾配出力J^_f(u^_k)によって、ロジックの最終的な出力値を補正すし、さらにステップ１７２２で、そのようにして補正した出力を非同期通信により、マスタースレッドに送り、ステップ１７０２に戻る。

図１８は、図１４に示すヤコビ・スレッドの処理を示すフローチャートである。ステップ１８０２では、ヤコビ・スレッドは、予測入力を受信する。これは、図１１で、例えば、ヤコビ・スレッド１１０４＿１、１１０４＿２、・・・、１１０４＿ｎが、ブロック１１０６から、予測入力を受信することに相当する。

図１４に示す構成の場合、１つのメイン・プロセスに対するヤコビ・スレッド群は、シリアルに接続されているので、ステップ１８０４では、次のプロセスであるヤコビ・スレッドに、出力が非同期伝播送信される。

ステップ１８０６では、ヤコビ・スレッドは、次のロジックがあるかどうか判断する。ヤコビ・スレッドの処理は、実際には入力値を微小に変化させて、シミュレーションモデルそのものの処理を実行する処理であり、ここで言うロジックも、これまでのロジックと同義である。

ステップ１８０６で、次のロジックがあると判断されると、ステップ１８０８では、最初のヤコビ・スレッドはメイン・スレッドから、以降のヤコビ・スレッドは一つ前のヤコビスレッドから内部状態を受信し、ステップ１８１０では、その内部状態を次のヤコビ・スレッドに非同期送信して、ステップ１８１２では、所定のロジックを実行する。

ステップ１８０６で、次のロジックがないと判断されると、出力は、次のヤコビ・スレッドに非同期送信される。ただし、最後のヤコビスレッドは、メイン・スレッドに非同期送信を行う。このとき、当該ヤコビ・スレッドは、それより前のヤコビ・スレッドから受け取っている出力も同時に次のヤコビ・スレッドに送信する。したがって最後のヤコビスレッドは、全てのヤコビ・スレッドの出力結果をメイン・スレッドに非同期送信することとなる。その後、再びステップ１８０２に戻る。

以上、この発明をＳＭＰ、トーラス状構成などの実施例に基づき説明してきたが、この発明は、この特定の実施例に限定されず、この技術分野の当業者が自明に思いつく様々な変形、置換などの構成、技法適用可能であることを理解されたい。例えば、特定のプロセッサのアーキテクチャ、オペレーティング・システムなどに限定されない。また、本発明は、マルチプロセス、マルチスレッド、あるいは、それらのハイブリッド並列化のいずれのシステムにも適用できることも、この技術分野の当業者なら理解するであろう。

さらに、上記実施例は、主として、自動車のＳＩＬＳのシミュレーション・システムにおける並列化に関連するものであったが、このような例には限定されず、航空機、ロボットその他の物理システムのシミュレーション・システムに広く適用可能であることも、この技術分野の当業者には明らかであろう。

５０４ａ、５０４ｂ、５０４ｃ・・・ＣＰＵ
１１０２、１１０４・・・パイプライニング処理
１１０４＿１、１１０４＿２・・・ヤコビ・スレッド

Claims (16)

1. マルチコアまたはマルチプロセッサ環境で、複数の機能ブロックからなるループ処理を、複数段のパイプライン化して実行するためのシステムであって、
   前記処理をパイプライン化して、個々のプロセッサまたはコアに割り当てる手段と、
   前記パイプラインの予測値を用いて計算された値から一次勾配項を計算する手段と、
   前記一次勾配項の値によって、前記パイプラインの出力値を補正する手段を有する、
   パイプライン実行システム。
2. パイプラインの処理の内部状態の値を、当該パイプラインの処理を担当したプロセッサまたはコアから、次段のパイプラインの処理を担当するプロセッサまたはコアに引き渡すための手段を有する、
   請求項１に記載のパイプライン実行システム。
3. 前記機能ブロックが複数の入力変数をもち、前記一次勾配項が、該複数の入力変数に関するヤコビ行列の近似式であらわされる、請求項１に記載のパイプライン実行システム。
4. 前記ヤコビ行列の近似式を計算するための処理が、個別のスレッドとして処理され、該スレッドは、前記ループ処理を割り当てられる前記プロセッサまたはコアとは別のプロセッサまたはコアに割り当てられる、請求項３に記載のパイプライン実行システム。
5. 前記予測値が、前段のパイプラインの値の線形補間またはラグランジュ補間によって計算される、請求項１に記載のパイプライン実行システム。
6. 前記システムが、トーラス的に立体的にノード間接続されたアーキテクチャをもち、前記ヤコビ行列の近似式を計算するためのスレッドが、１つの次元に沿った個別のノード上に割り当てられる、請求項４に記載のパイプライン実行システム。
7. マルチコアまたはマルチプロセッサ環境で、複数の機能ブロックからなるループ処理を、複数段のパイプライン化して実行するための方法であって、
   前記処理をパイプライン化して、個々のプロセッサまたはコアに割り当てるステップと、
   前記パイプラインの予測値を用いて計算された値から一次勾配項を計算するステップと、
   前記一次勾配項の値によって、前記パイプラインの出力値を補正するステップを有する、
   パイプライン実行方法。
8. パイプラインの処理の内部状態の値を、当該パイプラインの処理を担当したプロセッサまたはコアから、次段のパイプラインの処理を担当するプロセッサまたはコアに引き渡すためのステップを有する、
   請求項７に記載のパイプライン実行方法。
9. 前記機能ブロックが複数の入力変数をもち、前記一次勾配項が、該複数の入力変数に関するヤコビ行列の近似式であらわされる、請求項７に記載のパイプライン実行方法。
10. 前記ヤコビ行列の近似式を計算するための処理が、個別のスレッドとして処理され、該スレッドは、前記ループ処理を割り当てられる前記プロセッサまたはコアとは別のプロセッサまたはコアに割り当てられる、請求項９に記載のパイプライン実行方法。
11. 前記予測値が、前段のパイプラインの値の線形補間またはラグランジュ補間によって計算される、請求項７に記載のパイプライン実行方法。
12. マルチコアまたはマルチプロセッサを有するコンピュータ・システムにおいて、複数の機能ブロックからなるループ処理を、複数段のパイプライン化して実行するためのプログラムであって、
    前記コンピュータ・システムに、
    前記処理をパイプライン化して、個々のプロセッサまたはコアに割り当てるステップと、
    前記パイプラインの予測値を用いて計算された値から一次勾配項を計算するステップと、
    前記一次勾配項の値によって、前記パイプラインの出力値を補正するステップを実行させる、
    パイプライン実行プログラム。
13. パイプラインの処理の内部状態の値を、当該パイプラインの処理を担当したプロセッサまたはコアから、次段のパイプラインの処理を担当するプロセッサまたはコアに引き渡すためのステップを有する、
    請求項１２に記載のパイプライン実行プログラム。
14. 前記機能ブロックが複数の入力変数をもち、前記一次勾配項が、該複数の入力変数に関するヤコビ行列の近似式であらわされる、請求項１２に記載のパイプライン実行プログラム。
15. 前記ヤコビ行列の近似式を計算するための処理が、個別のスレッドとして処理され、該スレッドは、前記ループ処理を割り当てられる前記プロセッサまたはコアとは別のプロセッサまたはコアに割り当てられる、請求項１４に記載のパイプライン実行プログラム。
16. 前記予測値が、前段のパイプラインの値の線形補間またはラグランジュ補間によって計算される、請求項１２に記載のパイプライン実行プログラム。

Images