(57)【特許請求の範囲】
【請求項１】
分岐命令に対する分岐先を予測し該予測された分岐先の命令の投機的実行を行った後に該分岐予測が外れていたことが判明した場合に回復処理を行う予測外れ回復機構を備えた計算機であって、
計算機の論理動作の誤りを検出する誤り検出機構と、
前記誤り検出機構によって誤りが検出された場合に、該予測外れ回復機構を使用して誤り発生前の計算機の状態を復元し、誤りが検出された命令を含む命令列を再実行することにより、間欠故障による誤りを訂正する命令再実行機構と、
を具備するとともに、命令を一つずつ実行する動作モードを備え、前記命令再実行機構は、前記誤り検出機構によって誤りが検出された場合に該動作モードを選択して再実行を行う計算機。
【請求項２】
命令の実行に誤りが無いことが前記誤り検出機構によって確認されたことを条件として命令を完結させる、請求項１に記載の計算機。
【請求項３】
前記命令再実行機構による再実行時にも前記誤り検出機構によって誤りが検出された場合には、固定故障とみなして実行を中止する、請求項１に記載の計算機。
【請求項４】
請求項１から請求項３までのいずれか１項に記載の計算機を二重化して、それらの出力を比較し、不一致が検出された場合には、内部動作の誤りが検出された計算機を切り離し、誤りが検出されていない他方の計算機で実行を継続させる計算機システム。
【請求項５】
いずれか一方の計算機において内部動作の誤りが検出された場合には、該切り離し後に両方の計算機による二重化構成状態の復元を行なうことを可能とするため、両方の計算機ともに再実行が行われる、請求項４に記載の計算機システム。
【請求項６】
分岐命令に対する分岐先を予測し該予測された分岐先の命令の投機的実行を行った後に該分岐予測が外れていたことが判明した場合に回復処理を行う予測外れ回復機構を備えた計算機における誤り回復方法であって、
誤り検出機構が、計算機の論理動作の誤りを検出するステップと、
該誤り検出機構によって誤りが検出された場合に、命令再実行機構が、該予測外れ回復機構を使用して誤り発生前の計算機の状態を復元し、誤りが検出された命令を含む命令列を再実行することにより、間欠故障による誤りを訂正するステップと、
を具備し、前記訂正ステップは、命令を一つずつ実行する動作モードを選択して再実行を行う方法。
【請求項７】
該誤り検出機構によって命令の実行に誤りが無いことが確認されたことを条件として制御及び実行ユニットが命令を完結させるステップを更に具備する、請求項６に記載の方法。
【請求項８】
該命令再実行機構による再実行時にも誤りが検出された場合に制御及び実行ユニットが固定故障とみなして実行を中止するステップを更に具備する、請求項６に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、計算機(computer)及びその誤り回復方法(error recovery method) に関する。
【０００２】
【従来の技術】
近年、半導体の進歩を背景として計算機の高速化が進んでいる。しかしながら、かかる半導体の進歩によって、演算や記憶に使用されるＭＯＳトランジスタ等の素子が小さくなる結果、放射線や内部又は外部からの電気雑音に対する耐性が減少し、誤りが起こる確率が大きくなっている。
【０００３】
誤りが発生した場合に備えるべく、従来より各種の誤り訂正方法が知られている。例えば、メモリにおいては、その他の部分に比較して誤りの確率が大きいため、ＥＣＣ(Error Correction Code) コードが使用され、安定した動作の保証が図られている。しかし、メモリ以外の部分では、コストや性能の観点からＥＣＣコードはあまり使用されていない。
【０００４】
従来、高信頼度を要求されるメインフレーム計算機において、メモリ以外の部分に発生した誤りを訂正する方法は、命令実行の完了時に、誤りが無ければ次の命令の処理を進める一方、誤りを検出した場合にはその命令を再実行する、というものである。この方法では、誤りチェックを待たないと次の命令処理を開始することができず、命令実行の並列度を高くすることができないという問題があった。
【０００５】
また、より並列度の高い命令実行を行う計算機では、動作中の状態を記憶装置に格納しておき、誤りが検出された場合には、この記憶装置から以前の状態を復元し、その時点に戻って再実行を行うようにしている。この方式では、本来の命令実行には必要の無い、動作中の状態を格納する記憶装置を必要とするため、コストアップになるという問題があった。
【０００６】
誤りの原因は、外部からの雑音や放射線等、間欠性(intermittent)（一過性）のものである場合が多いので、上記いずれの方式においても、再実行時には誤りが発生せず、正しく実行される可能性が高い。したがって、論理動作の誤りが検出された場合に、どのようにすれば、命令実行の並列度を低下させることなく、かつ、ハードウェア量を増大させることなく、誤り訂正を行うことができるか、が課題となっている。
【０００７】
一方、最近の高性能計算機では、投機的実行(speculative execution) と呼ばれる命令実行方法を行うものが多い。計算機の命令実行において、条件分岐命令の実行効率が性能を大きく左右する。この条件分岐命令を通常のパイプライン計算機で実行すると、条件分岐命令であることを認識し、条件の成立を判定し、それから分岐先の命令を読み出す(fetch) 、という最低３つのステップを経て、次の命令が実行可能となるので、次の命令実行までに時間がかかる。
【０００８】
投機的実行方式では、条件分岐命令であることを認識すると同時に、分岐予測機構を利用して、分岐方向を予測(predict) し、その命令の読み出し(fetch) を行うことにより、２ステップで次の命令が実行可能になる。最近の分岐予測機構は９０％以上の場合に正しい分岐方向を予測しており、大部分の場合、効率的な実行が可能である。
【０００９】
しかし、予測が外れる場合もあり、その場合に備えて、計算機の状態を記憶装置に格納することが行われる。そして、後に予測が外れたことが判明すると、記憶装置から分岐直前の状態を復元し、分岐方向を修正して実行を進める。
【００１０】
【発明が解決しようとする課題】
本発明は、上述した背景に鑑みてなされたものであり、その目的は、かかる投機的実行の予測外れに対応するための状態記憶装置を、計算機の論理動作の誤りが検出された際にも使用することにより、電気的雑音や放射線に起因する誤りの発生時にその誤りを訂正することができる経済的な計算機及びその誤り訂正方法を提供することにある。
【００１１】
【課題を解決するための手段】
上記目的を達成すべく、本発明によれば、分岐命令に対する分岐先を予測し該予測された分岐先の命令の投機的実行を行った後に該分岐予測が外れていたことが判明した場合に回復処理を行う予測外れ回復機構を備えた計算機であって、計算機の論理動作の誤りを検出する誤り検出機構と、前記誤り検出機構によって誤りが検出された場合に、該予測外れ回復機構を使用して誤り発生前の計算機の状態を復元し、誤りが検出された命令から命令列を再実行することにより、間欠故障による誤りを訂正する命令再実行機構と、を具備する計算機が提供される。
【００１２】
また、本発明によれば、分岐命令に対する分岐先を予測し該予測された分岐先の命令の投機的実行を行った後に該分岐予測が外れていたことが判明した場合に回復処理を行う予測外れ回復機構を備えた計算機における誤り回復方法であって、計算機の論理動作の誤りを検出するステップと、誤りが検出された場合に、該予測外れ回復機構を使用して誤り発生前の計算機の状態を復元し、誤りが検出された命令を含む命令列を再実行することにより、間欠故障による誤りを訂正するステップと、を具備する方法が提供される。
【００１３】
【発明の実施の形態】
図１は、本発明の説明に必要な部分を中心に、命令の投機的実行と論理動作の誤り訂正とを行う計算機の構造を示すブロック図である。計算機の論理動作の誤りを検出する方式として、パリティーチェックによる方式、二重化してその結果を比較する方式、あるいは、乗算器ではモジュロ(modulo)３の剰余をチェックする方式などが知られている。このような方式の何れか、あるいは、これらを適当に組みあわせることにより、誤りを検出することが出来る。
【００１４】
本発明は、投機的実行を行う計算機において、上記の誤り検出機構により誤りが検出された場合に、分岐予測外れと同様に、状態記憶装置から以前の状態を復元して再実行を行うことにより、間欠誤りを訂正する。これを可能にするために、通常の投機的実行方式に以下の変更を加える必要がある。
【００１５】
投機的実行を行う計算機では、命令の完了(complete)と命令の完結(commit)という概念がある。命令の完了は、その命令が実行され、演算結果などが得られた状態である。しかし、命令は投機的な予測に基づいて実行されている場合があり、その結果により計算機の状態を変化させてしまうと、予測外れの場合は復元ができなくなる。従って、命令の完結という段階があり、これは命令の実行(execute) が完了し、かつ、予測外れがないことが確認された時点で行われる。以上のように、完了段階の命令は取り消しが可能であるが、完結した命令は取り消すことができない。
【００１６】
誤りを生じた命令が完結してしまうと取り消しが出来ず、従って、訂正もできなくなるので、本発明を実施するためには、それぞれの命令の通常の完結条件に加えて、誤りが発生しなかったことも確認して完結させる構造とする。
【００１７】
そして、誤りが検出された場合には、分岐予測外れと同様に、状態記憶装置から、誤り無く完結した命令だけを含み、誤った命令の結果を含まない最近の状態を読み出して復元し、その時点から再実行を行う。この機構としては、もともとの予測外れに対応するための機構を大部分流用することができる。主要な違いは、分岐方向を修正して異なる命令列を実行するのではなく、同じ命令列を再実行する点にある。
【００１８】
以下、図１を用いて具体的に説明する。プロセッサ状態部(processor states)２０と記したブロックは、プログラムカウンタ、レジスタ等の、命令の実行に必要な状態を集めて模式的に記したものであり、実際の計算機の実装では、幾つかの部分に分かれて実装されるのが普通である。プロセッサ状態部２０に保持された状態に基づいて計算機１０全体が制御され、命令が実行されていく。
【００１９】
投機的実行では予測により命令の実行を開始するので、予測が外れた場合には、以前の正しかった状態まで戻って実行を再開する必要がある。この状態を格納するのがチェックポイントアレイ(check point array)１２である。コミットポインタ(commit pointer)１４は、最後の、正しく命令を完結(commit)した状態を格納しているエントリを指している。また、カレントポインタ(current pointer)１６は、次に予測を行うに際して、その直前の状態を格納するエントリを指している。
【００２０】
バックアップ制御部(backup control)１８は、予測外れや誤動作が起こった場合にコミットポインタ１４で指された状態をチェックポイントアレイ１２から取出しプロセッサ状態部２０に格納することにより、その状態から実行を再開させる制御を行う部分である。
【００２１】
分岐ユニット(branch unit)２２と記した部分は、分岐命令を取り扱う部分であり、分岐先を予測して投機的実行を行い、かつ、後に予測が外れたことが判明した時に通知を行う。また、この部分は、命令の完結を監視し、予測した部分まで命令が完結したことを検出し通知する機能を有している。
【００２２】
誤り検出回路(error detection circuits)２４は、計算機１０の論理動作を監視する部分であり、実際には分散して実装される。誤動作の検出にはパリティーチェックやレジジュー(residue) チェック、あるいは二重化比較などが用いられる。制御及び実行ユニット(control and execution unit)２６は、計算機の残りの部分である。
【００２３】
分岐ユニット２２は、分岐先が決定する前に、方向を予測して投機的実行を行うために、その分岐命令の実行直前の状態（プロセッサ状態部２０の内容）をカレントポインタ１６が指すチェックポイントアレイ１２のエントリに格納する。そして、予測した分岐先の命令実行を開始する。そして、分岐ユニット２２は、予測を行いチェックポイントアレイ１２のエントリを消費したので、カレントポインタ１６を一つ進める。また、分岐ユニット２２は、命令の完結を監視し、コミットポインタ１４の指すエントリの次のエントリまで命令が完結すると、コミットポインタ１４を進め、コミットポインタ１４が常に最後の命令完結状態を指すように制御する。
【００２４】
分岐方向の予測が間違っていたことが判明すると、分岐ユニット２２は、そのことをバックアップ制御部１８に通知する。バックアップ制御部１８は、コミットポインタ１４に従ってチェックポイントアレイ１２から正しく完結した最後のエントリを読み出し、プロセッサ状態部２０の状態を復元する。これにより、計算機１０は、その状態（実行する命令の番地を含む）から命令実行を再開する。このバックアップにより、その後の予測もキャンセルとなるので、カレントポインタ１６の値はコミットポインタ１４によって指されるエントリの次のエントリを指すように変更される。
【００２５】
本発明による、誤動作からの回復は、この予測外れの回復機構を殆どそのまま利用する。ハードウェアの誤動作を検出する誤り検出回路２４からバックアップ制御部１８へ誤動作の検出が通知されると、バックアップ制御部１８は、予測外れと同様に、コミットポインタ１４で指される、正しく実行を完結した状態を取出し、プロセッサ状態部２０を復元する。計算機１０は、この状態から実行を再開するので、誤動作を起こした命令も再度実行されることになる。誤動作の原因が、放射線や外部雑音のような繰り返し発生しないものであれば、再実行時には誤りが発生せず、正しく実行を完了する。また、内部動作に起因する雑音の場合でも、再実行にともない実行の状態が変化し、雑音の発生量が異なることが多い。従って、再実行時には誤動作を引き起こさない場合が多い。
【００２６】
図２は、命令完結の手順を示すフローチャートである。なお、フローチャート中の分岐予測、誤り検出及び命令完結は、命令シリアル番号ごとに並列に実行される。ステップ１０２では、命令シリアル番号を取得(fetch) し、命令を発行(issue) する。次いで、ステップ１０４では、命令を実行(execute) し、シリアル番号を付して実行結果を送出する。次いで、ステップ１０６では、分岐予測が外れたか的中したかを判定し、外れた場合には前述のバックアップ処理に移行する一方、的中した場合にはステップ１０８に進む。
【００２７】
ステップ１０８では、誤りが検出されたか否かを判定し、誤りが検出された場合には誤り回復処理に移行する一方、誤りが検出されなかった場合にはステップ１１０に進む。ステップ１１０では、当該命令よりも古い命令が全て完結するまで待機した後、命令完結状態となる。このように、本発明においては、誤りが検出されなかったことが命令完結の条件に加わっている。
【００２８】
図３は、誤り検出後の処理の手順を示すフローチャートである。内部発生雑音のレベルは動作状態によって変化し、一般に複数の命令を同時実行し計算機全体の動作率が高い場合には雑音レベルも高くなる。従って、上記の再実行に際して、複数の命令を並列実行するモードではなく、命令を一つづつ実行するようなモードで実行することにより、内部雑音を減少させ、再実行の成功確率を高めることが出来る。そこで、図３の処理では、通常の実行より内部雑音が少なくなる動作モードを備え、誤りが検出された場合にこのモードを選択して再実行を行うようにしている。
【００２９】
このような方法により、かなりの間欠故障に起因する誤りを訂正することが出来るが、再実行で回復することができない固定故障が発生した場合や、間欠故障でも、状態記憶自体や復元機構などに誤りが発生した場合には、訂正をすることができない。図３の処理では、再実行の結果においても誤りが検出された場合には、固定故障とみなして実行を中止するようにしている。
【００３０】
具体的には、誤り検出後、まず、ステップ２０２で、誤りが検出された命令を指すプログラムカウンタ（ＰＣ）値をＥＰＣとして記憶する。次いで、ステップ２０４では、命令発行のモードをシングルイシューモードに変更する。通常イシューモードでは、複数の命令がスーパスカラ(superscalar) 方式で並列に発行されるのに対し、シングルイシューモードでは、ノイズを減らすため、命令が一つずつ発行される。
【００３１】
次いで、ステップ２０６では、バックアップ処理として、コミットポインタ１４によって指されるエントリから状態が復元される。そして、ステップ２０８では、その次の命令から実行が再開される。ステップ２１０では、命令を実行し、プログラムカウンタＰＣを更新する。ステップ２１２では、ＰＣがＥＰＣに一致しているか否かが判定され、一致しないときにはステップ２１０に戻る一方、一致するときにはステップ２１４に進む。
【００３２】
ステップ２１４では、誤りが検出されたか否かが判定される。誤りが検出された場合には、固定故障であるとみなして、割り込みを発生させる。一方、誤りが検出されなかった場合には、ステップ２１６に進み、通常イシューモードに復帰し、命令実行を継続する。
【００３３】
さらに高信頼度が必要とされる場合には、図４に示されるように、上記の構成の計算機を二重化し、相互の出力を比較する機構を付け加える。すなわち、第１の計算機１０Ａの出力と第２の計算機１０Ｂの出力とは、一致回路３０によって常に比較される。そして、第２の計算機１０Ｂ内で誤りが検出された場合、又は出力の不一致が検出された場合には、第１の計算機１０Ａの出力が選択されて、共通キャッシュメモリ３２に格納される。換言すれば、第２の計算機１０Ｂ内で誤りが検出されておらず、かつ、出力が一致している場合には、第２の計算機１０Ｂの出力が選択されて、共通キャッシュメモリ３２に格納される。また、第１の計算機１０Ａの出力が選択される場合で、かつ、第１の計算機１０Ａ内で誤りが検出された場合には、回復不能誤り信号が出力される。
【００３４】
このように、両計算機の出力が異なる場合には、内部で誤りが検出された計算機を切り離し、誤りが検出されていない計算機を使って実行を継続することにより、正しい実行を継続して維持することができる。但し、これだけでは一方の計算機に間欠故障が起こった場合には、一方だけが状態復元を行うことにより出力に不一致が生じてしまうので、誤りが検出された場合には、両方の計算機で状態復元を同時に行うように構成する必要がある。
【００３５】
図４のシステムでの誤り訂正処理を具体的に説明するためのフローチャートが図５に示される。この図に示されるように、第１の計算機１０Ａ内で誤りが検出された場合、第１の計算機１０Ａは、ステップ３０２において第２の計算機１０Ｂに誤りの発生を通知する。そして、ステップ３０４及び３０６に示されるように、両計算機において、図３に示される誤り検出後処理が実行される。その結果、両計算機の状態は、同一の状態に維持される。第２の計算機１０Ｂ内で誤りが検出された場合も同様である。
【００３６】
誤りが検出された一方の計算機を切り離している状態では信頼性が低下しているので、運用を中断することができる適当な時点で診断を行い、固定故障が発生している場合にはハードウェア部品の交換を行う。また、固定故障が検出されず、回復することができない間欠故障であったと考えられる場合は、両方の計算機をもとの二重化比較構成に戻して運用を再開する。
【００３７】
パリティーチェックで保護されたキャッシュメモリなどの場合には、誤動作が検出されると、そのときにアクセスしたエントリをハードウェアで無効化してから再実行を行う。このように制御を行うことにより、再実行時には無効化されたエントリがアクセスされる結果、下位のキャッシュメモリや主記憶から正しい内容が読み出されて誤りが回復される。このように単純に再実行を行うのではなく、エントリの無効化のような処理と合わせて回復を図るようにしてもよい。
【００３８】
ＥＣＣで保護されたキャッシュメモリでは、ＥＣＣにより正しいデータが供給されるので、この正しいデータで実行を続け、割り込みによって訂正可能誤りの発生をＯＳ(operating system)に通知して回復を依頼することもでき、必ずしも、本発明を適用する計算機においては、検出された全ての誤動作を再実行によって回復を図らなければならないということではない。ＥＣＣのような他の誤動作修正メカニズムと本発明の方式を併用してよい。
【００３９】
以上、本発明を特にその好ましい実施の形態を参照して詳細に説明した。本発明の容易な理解のため、本発明の具体的な形態を以下に付記する。
【００４０】
（付記１）  分岐命令に対する分岐先を予測し該予測された分岐先の命令の投機的実行を行った後に該分岐予測が外れていたことが判明した場合に回復処理を行う予測外れ回復機構を備えた計算機であって、
計算機の論理動作の誤りを検出する誤り検出機構と、
前記誤り検出機構によって誤りが検出された場合に、該予測外れ回復機構を使用して誤り発生前の計算機の状態を復元し、誤りが検出された命令を含む命令列を再実行することにより、間欠故障による誤りを訂正する命令再実行機構と、
を具備する計算機。（１）
【００４１】
（付記２）  前記誤り検出機構は、パリティーチェックを行うものである、付記１に記載の計算機。
【００４２】
（付記３）  前記誤り検出機構は、二重化比較を行うものである、付記１に記載の計算機。
【００４３】
（付記４）  命令の実行に誤りが無いことが前記誤り検出機構によって確認されたことを条件として命令を完結させる、付記１に記載の計算機。（２）
【００４４】
（付記５）  通常の実行より内部雑音が少なくなる動作モードを備え、前記命令再実行機構は、前記誤り検出機構によって誤りが検出された場合に該動作モードを選択して再実行を行う、付記１に記載の計算機。（３）
【００４５】
（付記６）  前記命令再実行機構による再実行時にも前記誤り検出機構によって誤りが検出された場合には、固定故障とみなして実行を中止する、付記１に記載の計算機。（４）
【００４６】
（付記７）  付記１から付記６までのいずれか１項に記載の計算機を二重化して、それらの出力を比較し、不一致が検出された場合には、内部動作の誤りが検出された計算機を切り離し、誤りが検出されていない他方の計算機で実行を継続させる計算機システム。（５）
【００４７】
（付記８）  いずれか一方の計算機において内部動作の誤りが検出された場合には、両方の計算機ともに再実行が行われる、付記７に記載の計算機システム。（６）
【００４８】
（付記９）  分岐命令に対する分岐先を予測し該予測された分岐先の命令の投機的実行を行った後に該分岐予測が外れていたことが判明した場合に回復処理を行う予測外れ回復機構を備えた計算機における誤り回復方法であって、
計算機の論理動作の誤りを検出するステップと、
誤りが検出された場合に、該予測外れ回復機構を使用して誤り発生前の計算機の状態を復元し、誤りが検出された命令を含む命令列を再実行することにより、間欠故障による誤りを訂正するステップと、
を具備する方法。（７）
【００４９】
（付記１０）  誤りの検出が、パリティーチェックによって行われる、付記９に記載の方法。
【００５０】
（付記１１）  誤りの検出が、二重化比較によって行われる、付記９に記載の方法。
【００５１】
（付記１２）  命令の実行に誤りが無いことが確認されたことを条件として命令を完結させるステップを更に具備する、付記９に記載の方法。（８）
【００５２】
（付記１３）  前記訂正ステップは、通常の実行より内部雑音が少なくなる動作モードを選択して再実行を行う、付記９に記載の方法。（９）
【００５３】
（付記１４）  再実行時にも誤りが検出された場合に固定故障とみなして実行を中止するステップを更に具備する、付記９に記載の方法。（１０）
【００５４】
【発明の効果】
以上、説明したように、本発明によれば、投機的実行の予測外れに対応するための状態記憶装置を、計算機の論理動作の誤りが検出された際にも使用することにより、電気的雑音や放射線に起因する誤りの発生時にその誤りを訂正することができることとなる。
【図面の簡単な説明】
【図１】本発明の説明に必要な部分を中心に、命令の投機的実行と論理動作の誤り訂正とを行う計算機の構造を示すブロック図である。
【図２】命令完結(commit)の手順を示すフローチャートである。
【図３】誤り検出後の処理の手順を示すフローチャートである。
【図４】計算機を２重化したシステムでの本発明の応用例について説明するためのブロック図である。
【図５】図４のシステムでの誤り訂正処理を説明するためのフローチャートである。
【符号の説明】
１０…計算機
１２…チェックポイントアレイ(check point array)
１４…コミットポインタ(commit pointer)
１６…カレントポインタ(current pointer)
１８…バックアップ制御部(backup control)
２０…プロセッサ状態部(processor states)
２２…分岐ユニット(branch unit)
２４…誤り検出回路(error detection circuits)
２６…制御及び実行ユニット(control and execution unit)
１０Ａ…第１の計算機
１０Ｂ…第２の計算機
３０…一致回路
３２…共通キャッシュメモリ
【図１】
0004603185.tif 000002
【図２】
0004603185.tif 000003
【図３】
0004603185.tif 000004
【図４】
0004603185.tif 000005
【図５】
0004603185.tif 000006