(57)【要約】  データ処理回路は、書込みポートを有するレジスタ・ファイル（１７）および命令処理ステージ（１０ａ〜１０ｄ）のパイプラインを備える。タイミング回路（１４）は互いに異なる時点でのステージ間の命令依存情報の転送のタイミングを調節するように構成されているので、それぞれのステージでの連続する命令の処理が部分的にオーバラップしている。第１および第２ステージ（１０ｃ、１０ｄ）はパイプライン内で連続している。ステージの第１および第２ステージはそれぞれ、関係するステージ（１０ｃ、１０ｄ）内の命令依存情報が書込みを要求する場合、結果を書込みポートに書き込むための結果出力を有する。書込みシーケンシング回路（１４４）はステージ（１０ｃ、１０ｄ）の第１および第２ステージ内の命令依存情報の書込みテストを交互に行なう。書込みシーケンシング回路（１４４）はステージ（１０ｃ、１０ｄ）の特定のステージの書込みテストを行なう場合、ステージ（１０ｃ、１０ｄ）の特定のステージ内の命令依存情報が結果の書込みを要求するかどうかテストする。要求する場合は、書込みポートが書き込むことを次にコミットするすべての結果の前にその結果を書き込むことを書込みポートがコミットしてしまうまでに、書込みシーケンシング回路（１４４）は、パイプライン（ｌ０ａ〜１０ｄ）を通してステージ（１０ｃ、１０ｄ）に新しい命令依存情報を転送することを遅延させる。
2007535060.tif 000002
【特許請求の範囲】
【請求項１】
パイプライン式非同期命令プロセッサを備えるデータ処理回路であって、
書込みポートを有するレジスタ・ファイルと、
命令処理ステージのパイプラインであって、前記パイプライン内で連続している前記ステージのうちの第１および第２ステージそれぞれは、該ステージ内の命令依存情報が書込みを要求した場合に、前記書込みポートに結果を書き込むための結果出力を有する命令処理ステージのパイプラインと、
それぞれのステージの連続する命令の処理が部分的にオーバラップするように、互いに異なる時点でのステージ間の命令依存情報の転送のタイミングを調節するように構成されたタイミング回路と、
前記ステージのうちの前記第１および第２ステージで命令依存情報の書込みテストを交互に行なうように構成された書込みシーケンシング回路であって、前記ステージのうちの特定のステージに関する書込みテストを行なうときに、前記ステージのうちの該特定のステージ内の命令依存情報が結果の書込みを要求するかどうかテストし、要求する場合は、前記パイプラインを通しての新しい命令依存情報の前記ステージのうちの前記特定のステージへの転送を、前記書込みポートが次に書き込むことをコミットすることができる結果の前に、前記書込みポートが前記結果を書き込むことをコミットしてしまうまで、遅延させる書込みシーケンシング回路と、
を備えるデータ処理回路。
【請求項２】
前記シーケンシング回路は、前記ステージのうちの該特定のステージから命令依存情報を転送することを求める要求信号に応じて、前記ステージのうちの各特定のステージで書込みテストを開始させると共に、結果の書込みが開始されて、かつ、命令依存情報が前記ステージのうちの前記特定のステージから転送されてしまうまで、前記新しい命令依存情報を前記ステージのうちの前記特定のステージに転送することを求める要求信号を遅延させるように構成される、請求項１に記載のデータ処理回路。
【請求項３】
前記タイミング回路は、命令依存情報の連続する転送の繰り返しサイクルを開始させ、各サイクル内の前記転送が前記パイプラインに沿って、より上流で連続している前記ステージのシリーズに関して、後に連続してそのタイミングが調節されるように構成され、前記タイミング回路が前記シリーズの上流の端で前のサイクルからの転送に応じて前記シリーズの下流の端で各サイクルを開始させる、請求項２に記載のデータ処理回路。
【請求項４】
前記タイミング回路が、
タイミング信号転送回路のチェーンであって、該チェーンを通してタイミング信号を伝播し、伝播タイミング信号を連続して受け取る前記チェーン内のタイミング信号転送回路はその後、命令依存情報の転送を制御する出力をそれぞれ前記シリーズ内の連続してさらに上流にあるステージに結合させる、タイミング信号転送回路のチェーンと、
それぞれ前記ステージのうちの前記第１および第２ステージへの命令依存情報の転送を制御する出力を有するタイミング信号転送回路にタイミング信号を伝播するための実用的に前記チェーン内にある条件付き遅延素子であって、第１および第２タイミング信号パスを備え、前記対応するステージ内の命令依存情報がそれぞれ結果の書込みを要求するかしないかに依存している前記第１パスまたは前記第２パスを通して前記タイミング信号をルーティングして、前記第１パスが、前記書込みポートが結果の書込みをコミットすることができるかどうかに依存する、前記タイミング信号の伝播を可能にするように構成されたイネーブル回路を備える条件付き遅延素子と
を備える、請求項３に記載のデータ処理回路。
【請求項５】
前記ステージのうちの前記第１ステージが少なくとも第１タイプの命令に応じて複数の結果を出力するように構成されたデータ処理回路であって、各書込みテストが、前記ステージのうちの前記特定のステージ内の前記命令依存情報が複数の結果の書込みを要求するかどうかをテストし、要求する場合、前記パイプラインを通して前記ステージのうちの前記特定のステージに新しい命令依存情報を転送することを、前記書込みポートが複数の結果を全てその次の結果の前に書き込むことをコミットされるまで遅延させることを含む、請求項１に記載のデータ処理回路。
【請求項６】
前記ステージのうちの前記第１ステージが、前記命令によって指定されたオペランドを使用して命令選択算術演算を行なうように構成された実行ステージであり、前記ステージのうちの前記第２ステージが、前記命令によって指定されたアドレスを使用してメモリにアクセスするように構成された記憶ステージであるデータ処理回路であって、前記ステージのうちの前記第１および第２ステージがそれぞれ算術命令およびメモリ・アクセス命令を実行したときに結果を前記レジスタ・ファイルに書き込むように構成される、請求項１に記載のデータ処理回路。
【請求項７】
前記実行ステージが、第１タイプのメモリ・アクセス命令を実行したときに前記第１タイプのメモリ・アクセス命令によって指定されたメモリ・アクセスを更新し、前記更新から生じた更新されたアドレスを結果として前記レジスタ・ファイルの前記書込みポートに書き込むように構成される、請求項１に記載のデータ処理回路。
【請求項８】
前記データ処理回路が実行するように構成された前記命令組が第１および第２タイプの命令を含み、前記実行ステージのうちの前記第１および第２ステージがそれぞれ前記第１および第２タイプの命令に応じて結果を書き込むように構成される、請求項１に記載のデータ処理回路。
【請求項９】
前記第１タイプの前記命令が第１および第２サブセットを含み、
前記第１サブセットの各命令が前記第１、第２両方のタイプのものであり、前記第２サブセットからの命令が前記ステージのうちの前記第２ステージが結果を書き込むように構成されるようにさせない、請求項８に記載のデータ処理回路。
【請求項１０】
前記書込みシーケンシング回路が、前記結果の書込みが要求されるかどうか判定するために前記ステージのうちの前記特定のステージ内の命令依存情報をテストすることによって前記書込みテストを行なうように構成される、請求項１に記載のデータ処理回路。
【請求項１１】
書込みポートを有するレジスタ・ファイルおよび命令処理ステージのパイプラインを備えたパイプライン式非同期命令プロセッサを用いて、パイプライン式非同期命令プロセッサを使用して、命令のプログラムを実行する方法であって、前記ステージのうちの第１および第２ステージそれぞれは、該ステージ内の命令依存情報が書込みを要求する場合、前記書込みポートに結果を書き込むための結果出力を有し、
それぞれのステージでの連続する命令の処理が部分的にオーバラップするように、それぞれのステージごとに異なるパイプラインを通しての命令依存情報の転送のタイミングを調節してパイプライン方式で命令を実行すること、
前記ステージのうちの前記第１および第２ステージで命令依存情報の書込みテストを交互に行ない、前記ステージのうちの特定のステージ内の命令依存情報が結果の書込みを要求するかどうかテストすることを含む書込みテストを行なうこと、
要求する場合は、前記パイプラインを通して前記ステージのうちの前記特定のステージに新しい命令依存情報を転送することを、前記書込みポートが次に書き込むことをコミットすることができる結果の前に、前記書込みポートが前記結果を書き込むことをコミットしてしまうまで遅延させること
を含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パイプライン式非同期命令プロセッサを有するデータ処理回路に関する。
【背景技術】
【０００２】
命令実行パイプラインニングは、命令処理のそれぞれのステップを実行するための複数のステージを備えた命令プロセッサを使用することを必要とする従来のコンピュータ技術である。典型的なステップ（steps）は、命令フェッチング・ステップ、命令デコーディング／オペランド・フェッチング・ステップ、実行（計算）ステップ、および結果ライト・バック・ステップを含む。これらのステージ（stages）は、前のステージが前の命令のために生成した一部分の結果を使用して、次のステージが前の命令のためのフォローオン・ステップを実行している間に前のステージが第１命令のための１つのステップを実行するように、アセンブリ・ライン原理に従って並行して動作する。今日の命令プロセッサの大多数は、同期回路、すなわち全ステージが同一の中心クロック（central clock）の制御下で動作し、全ての命令が１クロック・サイクルの終りに１ステージ下流に一緒に移動する回路で実装されている。
【０００３】
米国特許出願第２００２／０１５６９９５号は、パイプライン式非同期命令プロセッサを開示している。このプロセッサにはセントラル・クロックは使用されていない。その代わり、隣接するステージは、第１ステージが次のステージに供給される情報を更新しなければならない場合にのみ互いに同期する。アセンブリ・ラインの類推から、命令を全てのステージから次のステージへ同時に移動させる１本のコンベヤ・ベルトを使用する代わりに、各ステージは、そのステージが命令を終了し次のステージが命令を自由に受け取ることができるそれ自身の時間を選択する。典型的には、ハンドシェーク信号は、第１ステージが利用可能な情報を有し次のステージが新情報を受け取る準備ができていることを示すために交換される。
【０００４】
非同期ステージを順次に使用することに加えて、米国特許出願第２００２／０１５６９９５号はまた、同じパイプラインステージの代替物として、いくつかの異なる実行ステージを並行して使用し、そうすることで、ある命令のための実行ステップの実行を、前の命令の実行ステップがまだ完了していなくても、開始することを可能にする。
【０００５】
しかし、命令のプログラムは、一般に、命令の結果が命令の出現順にレジスタ・ファイルに書き込まれることを前提としている。これは、通常、命令が順次的に通り抜け、結果をレジスタ・ファイルに書き込むパイプライン内にライト・バックステージを設けることによって保証される。米国特許出願第２００２／０１５６９９５号はこの技法を非同期パイプラインに適用している。実際の結果は、場合によっては順序不同に、様々なステージからレジスタ・ファイルに供給されてよいが、ライト・バックステージは、結果がレジスタ・ファイルに書き込まれる順序を決定する。このために、ライト・バックステージは、命令を続けて受け取り、出力するキュー回路を使用する。ライト・バックステージは、命令をキューから読み出し、１つの命令を読み出すと、その結果がレジスタ・ファイルに書き込まれるようにし、その後で次の命令に着手する。
【０００６】
同様の技法は、２０００年９月１７〜２０日に「２０００年ＩＥＥＥコンピュータ設計国際会議：コンピュータおよびアンプのＶＬＳＩ；プロセッサ（ＩＣＣＤ ’００）［2000 IEEE International Conference on Computer Design: VLSI in Computers & amp; processors (ICCD ’00)］に発表された、エス・ビー・フーバ（S. B. Furber）、ディ・エー・エドワーズ（D. A. Edwards）およびジェイ・ディ・ガーサイド（J. D. Garside）による論文、「アムレット３：１００ミップス非同期埋込みプロセッサ（Amulet 3: a 100 MIPS Asynchronous Embedded Processor）」に記載されている。この論文は、２つのタイプの命令、すなわち、メモリ・アクセス命令、およびメモリへのアクセスを必要としないプロセッサ内部命令を有するプログラムを実行するプロセッサについて考察している。パイプラインのあるステージでは、メモリ・アクセス命令が「内部」命令と並行して実行される。その結果、ロード命令の結果は、内部命令の結果に関して順序不同に生成される可能性がある。この論文はまた、順序付けられたライト・バックを提供している。このライト・バック機能は、リオーダ・バッファを使用して実行される。命令デコーダは、各命令にリオーダ・バッファ内にそれ自体の位置を割り当てる。結果が生成された後は、その結果はその命令に割り当てられた位置に書き込まれる。プロセスは、命令順に順次各結果を待ち受け、その結果をレジスタ・ファイルにコピー・バックする。
【０００７】
したがって、これらのプロセッサは、結果が適切な順序でレジスタ・ファイルに書き込まれることを保証するが、その代償としてかなり大きなオーバーヘッドがかかる。すなわち、全命令およびそれらの結果の利用可能性を監視するライト・バックステージが提供される必要がある。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
とりわけ、本発明の目的は、結果をレジスタ・ファイルに書き込む予め決められた順序が、リオーダ・バッファを使用しなくても保証されるパイプライン式非同期命令プロセッサを備えた回路を提供することである。
【課題を解決するための手段】
【０００９】
本発明による回路は請求項１に説明されている。この回路には、結果を同じ書込みポートを通してレジスタ・ファイルに書き込むために、パイプラインの少なくとも２つの連続するステージが設けられる。書込みシーケンシング回路は、パイプラインのこれらの連続するステージがそれぞれ結果を書き込む機会を得ることを、そのステージの命令がこれを必要とする場合は、保証する。
【００１０】
書込みシーケンシング回路は、結果を書き込む機能を有する各ステージが、別のステージが次のシーケンスで次の命令に応じて書き込むための次の機会を得る前に、各シーケンスでその現在の命令に応じて順次書き込む機会を得るように、機会が予め決められた無期限に繰り返される順序で与えられることを保証する。これは、書込みの順序がプログラム内の命令の順序に対応することを保証する。非同期ステージのタイミングの自由によって、予知できない書込み順序が生じることはない。あるステージでの命令がそのステージに書き込むように要求する場合、書込みシーケンシング回路は、書込み回路が後でコミット（commit―かかわり合うこと・関係すること―）する結果の前に結果が書き込まれるように書込みポートが結果を書き込むことをコミットするまで、新しい命令のそのステージへの移動を防止する。（本明細書中で使用されるコミットすることとは、実際にレジスタ・ファイルに書き込むこと、または結果がローディング順にレジスタ・ファイルにそれを通して書き込まれるパイプライン、あるいは様々な結果がコミットされる順に結果を書き込むことを保証されている他のあらゆる機構に結果をロードすることを含んでよい。）これは、多かれ少なかれクロック内のエスケープメント機構として機能し、別の書込みステージが進んでしまうまで、あるいはその逆の場合まで、１つの書込みステージでのパイプラインを通しての進行を防止する。
【００１１】
書込みシーケンシング回路は、パイプラインを通して命令情報を転送するタイミングを調節するための様々な異なる非同期タイミング回路と組み合わされることができる。一実施形態では、逆方向シーケンシング回路が使用され、この場合、転送の波動（wave）が生じ、各波動はパイプラインに沿って連続してさらに上流にあるステージへの転送を必要とし、各波動はパイプラインの始点またはパイプラインの一部分で前の波動の到着によって開始される。この実施形態では、書込みシーケンシング回路は、ステージ内の命令が書込みを要求し、書込みポートが結果を受け入れる準備ができていない場合、条件付きで波の伝播を遅延させることによって、パイプラインを通しての命令情報の転送のタイミングを調節するためのタイミング回路の一部分として組み込まれることができる。
【００１２】
他の実施形態においては、タイミング回路は、下流のステージが次の命令のための準備ができていて、上流ステージが利用可能な命令を持っている場合に転送を開始するために、連続するステージ間のハンドシェーク−インターフェースを備える。この実施形態および前の実施形態では、クロック内でエスケープメントとして動作する別個の書込みシーケンシング回路が使用されてもよい。
【００１３】
さらに他の実施形態では、書込みをする特定のステージのための機会のタイミングは、命令情報のその特定のステージからパイプライン内の次のステージへの転送のタイミングにリンクされる。新しい命令情報の特定のステージへの転送は、命令情報が次のステージに転送されてしまい、かつ結果の書込みが開始されるまで保留される。
【００１４】
他の実施形態においては、同じステージから複数の結果を書き込むことを要求する命令もあり得る。この場合、書込みシーケンシング回路は、機会が次のステージに順に与えられる前に全ての結果の書込みが少なくとも開始されていることを保証することが好ましい。
【００１５】
一実施形態においては、各ステージから書き込まれる結果の数は、そのステージによって実行される命令のタイプに依存する。あるステージに結果を書き込むように要求する命令もあるが、別のステージに書き込むように要求する命令もある。たとえば、算術ステージは算術命令に応じて書き込み、記憶ステージはメモリ・ロード命令に応じて書き込こんでよい。さらに、命令がそれぞれ複数のステージにある場合の様々な時点でそれらのステージに書き込むように要求する命令もある。たとえば、算術ステージ内のアドレス・レジスタ・インクリメンテーションを有するロード命令は、算術ステージからレジスタ・ファイルへのインクリメントされたアドレス値の書込みと、記憶ステージからロード結果の書込みとを必要とすることがある。さらに、１つのステージから複数の結果を書き込むことを要求する命令もある。たとえば、複雑な算術演算は結果の実数部分と虚数部分をレジスタ・ファイル内の様々なレジスタに書き込むことを必要とする。
【００１６】
一実施形態では、それぞれが順次に書き込む機会を得るように、レジスタ・ファイルに書き込むことができる、まさに２つの連続するステージが使用される。しかし、本発明は２つの書込みステージ、すなわち直接隣接するステージに限定されない。
【発明を実施するための最良の形態】
【００１７】
本発明のこれらおよび他の目的および有利な態様は、添付の図を使用して、限定しない例として説明される。
【００１８】
図１は、いくつかの処理ステージ１０ａ〜１０ｅ、レジスタ１２ａ〜１２ｄ、タイミング回路１４、書込みマルチプレクサ１６、レジスタ・ファイル１７および命令メモリ１８を備えた命令処理回路を示す。処理ステージ１０ａ〜１０ｄはレジスタ１２ａ〜１２ｄを介してパイプラインに接続される。第１ステージ１０ａを除いて各ステージ１０ｂ〜１０ｅは、先行パイプライン・レジスタ１２ａ〜１２ｄに結合された１つまたは複数の命令情報入力を有し、最後のステージ１０ｅを除いて各ステージ１０ａ〜１０ｄは、これらに続くパイプライン・レジスタ１２ａ〜１２ｄに結合された命令情報出力を有する。２つの処理ステージ１０ｃ、１０ｄは、結果および随伴するレジスタ・アドレスをマルチプレクサ１６に出力する別の結果出力を有する。これらの処理ステージ１０ｃ、１０ｄはまた、タイミング回路１４に結合された検証出力１９ａ、１９ｂを有する。あるステージの検証出力は、そのステージからレジスタ・ファイルに書き込むことが必要かどうかを示すのに役立つ。
【００１９】
処理ステージは、たとえば、命令フェッチングステージ１０ａ、デコーダ／オペランド・フェッチングステージ１０ｂ、実行ステージ１０ｃ、メモリ・アクセスステージ１０ｄおよび最終ステージ１０ｅである。命令フェッチングステージ１０ａは、命令メモリ１８に結合された命令アドレス出力および命令入力を有する。命令メモリ１８は、簡単なメモリでもよく、あるいはキャッシュなどを備えた複雑なメモリ・システムでもよい。オペランド・フェッチングステージ１０ｂは、レジスタ・ファイル１７の読出しポートに結合されたレジスタ・アドレス出力を有する。レジスタ・ファイル１７は、実行ステージ１０ｃに先行するパイプライン・レジスタ１２ｂに結合された読出しデータ出力を有する。実行ステージ１０ｃおよび記憶ステージ１０ｄの結果出力は、レジスタ・ファイル１７の書込みポートに結合されたデータ／アドレス出力を有するマルチプレクサ１６に結合される。
【００２０】
この図の実施形態では、タイミング回路１４は、サイクル・ジェネレータ１４２、シーケンシング回路１４０ａ〜１４０ｅ、および書込みハンドシェーク回路１４４を備え、レジスタ１２ａ〜１２ｄ、命令フェッチステージ１０ａおよび書込みマルチプレクサ１６に結合された出力を有する。命令フェッチステージへの出力は、プログラム・カウンタの更新を制御する。マルチプレクサ１６への出力は、レジスタ・ファイル１７への書込みを制御する。レジスタ１２ａ〜１２ｄへの出力は、連続するステージ１０ａ〜１０ｅ間の情報のコピーイングのタイミングを制御する。事実上、各シーケンシング回路１４０ａ〜１４０ｅはそれぞれステージ１０ｂ〜１０ｅに対応し、ステージ１０ｂ〜１０ｅの入力は、シーケンシング回路１４０ｂ〜１４０ｅが結合されているレジスタ１２ａ〜１２ｄに結合される。サイクル・ジェネレータ１４２およびシーケンシング回路１４０ａ〜１４０ｅは、ループ状に接続されていて、最終ステージ１０ｅのためのシーケンシング回路１４０ｅと記憶ステージ１０ｄのためのシーケンシング回路１４０ｄとの間の接続は、書込みハンドシェーク回路１４４を介して接続される。同様に、記憶ステージ１０ｄのためのシーケンシング回路１４０ｄと実行ステージ１０ｃのためのシーケンシング回路１４０ｃとの間のループ内の接続は、書込みハンドシェーク回路１４４を介して接続される。書込みハンドシェーク回路１４４はまた、実行ステージ１０ｃおよび記憶ステージ１０ｄからの検証出力１９ａ、１９ｂに結合される。
【００２１】
動作中、フェッチステージ１０ａは、連続する命令をフェッチし、これらの命令をデコーダステージ１０ｂのレジスタ１２ａに適用する。デコーダステージ１０ｂは、そのレジスタ１２ａから各命令を読み出し、その命令からデコードされた情報を生成する。デコーダステージ１０ｂはまた、その命令からオペランド・レジスタ・アドレスを抽出し、それらをレジスタ・ファイル１７に適用する。それに応じて、レジスタ・ファイル１７はアドレス指定されたレジスタの内容を生成する。実行ステージ１０ｃのレジスタ１２ｂは、デコードされた情報およびアドレス指定されたレジスタの内容を格納する。
【００２２】
実行ステージ１０ｃは、デコードされた情報に従って動作を実行し、命令情報を記憶ステージ１０ｄのレジスタ１２ｃに供給する。命令情報は、デコーダステージ１０ｂからの命令情報のコピーを含んでもよいが、さらに、記憶ステージ１０ｄによって使用されるメモリ・アドレスなど、実行ステージによって生成された情報を含んでもよい。第１および第２タイプの命令（たとえば、加算命令、またはインデックス・レジスタがそこで更新されるメモリ・アクセス命令）では、実行ステージ１０ｃは、実行ステージ１０ｃが命令情報からのレジスタ・アドレスと共にマルチプレクサ１６に供給する結果を生成する。このタイプの命令に応じて、実行ステージ１０ｃは、検証出力１９ａで検証信号を生成する。第３および第４タイプの命令（たとえば、インデックス更新が生じないメモリ・アクセス命令）よって、有効な結果およびレジスタ・アドレスは生じない。このタイプの命令に応じて、実行ステージ１０ｃは、検証出力１９ａで検証信号を生成しない。
【００２３】
続いて記憶ステージ１０ｄは、命令情報によって要求された場合、実行ステージ１０ｃおよびアクセス・データ・メモリによって生成された命令情報を受け取る。第１および第３タイプの命令（たとえばメモリ読出し命令）では、記憶ステージ１０ｄは、記憶ステージ１０ｄが命令情報からのレジスタ・アドレスと共にマルチプレクサ１６に供給する結果を生成する。このタイプの命令に応じて、記憶ステージ１０ｄは、検証出力１９ｂで検証信号を生成する。第２および第４タイプの命令（たとえば加算命令）よって、記憶ステージ１０ｄからの有効結果およびレジスタ・アドレスは生じない。このタイプの命令に応じて、記憶ステージ１０ｄは、検証出力１９ｂで検証信号を生成しない。
【００２４】
タイミング回路１４は、処理のタイミングを制御し、詳細にはレジスタ１２ａ〜１２ｄがステージ１０ａ〜１０ｄ間で情報を引き継ぐ時点を制御する。一実施形態では、逆方向シーケンシング機構が使用され、レジスタ１２ａ〜１２ｄは、それぞれ次のレジスタ１２ａ〜１２ｄが下流で情報を取り込んだ後でデータを取り込む。したがって、連続してより上流にある（最初のステージ１０ａにより近い）レジスタ１２ａ〜１２ｄが連続して情報を取り込む。この実施形態では、サイクル・ジェネレータ１４２が、最も下流のレジスタ１２ｄから始めて次のサイクルを開始し、続いて、連続してより上流のレジスタ１２ａ〜１２ｃを更新し、プログラム・カウンタが更新された後は、次の命令のフェッチを開始する。
【００２５】
さらに、タイミング回路１４は、実行ステージ１０ｃまたは記憶ステージ１０ｄが、現在の命令がそれを要求することを示す場合、レジスタ・ファイル１７への書込み動作を開始する。これらの書込み動作の時点は、タイミング回路がレジスタ１２ａ〜１２ｅにデータを取り込ませる時点にリンクされる。タイミング回路１４がレジスタ１２ｃ、１２ｄにステージ１０ｃ、１０ｄからデータを取り込ませるとき、タイミング回路１４はまた、ステージ１０ｃ、１０ｄが、そのステージ１０ｃ、１０ｄ内の命令が書込みを要求し、レジスタ・ファイル１７が新しい書込みを受け入れる準備ができている（前の書込みから十分に遠く進められている）ことを示す場合、レジスタ・ファイルにそのステージからのアドレスおよび結果に関する書込み動作を開始させる。続いて、タイミング回路１４は、次の上流のレジスタ１２ａ〜１２ｅにデータを取り込むように信号を送る。
【００２６】
命令が書込みを要求しない場合は、タイミング回路１４は、次の上流のレジスタにデータを取り込むように直ちに信号を送る。書込みが必要であるがレジスタ・ファイル１７が用意できていない場合は、タイミング回路１４は、レジスタ・ファイル１７が書込みを受け入れる用意ができるまで待ち、それが生じると、タイミング回路がレジスタ・ファイル１７に書込みを開始させ、続いて、タイミング回路１４が次の上流レジスタ１２ａ〜１２ｅにデータを取り込むように信号を送る。
【００２７】
レジスタ・ファイル１７の様々な実施形態は、レジスタ・ファイル１７への結果の書込みをサポートすることができる。最も簡単な実施形態では、結果は直接マルチプレクサ１６からレジスタ・ファイル１７に書き込まれる。しかし、さらに進んだ実施形態では、結果をバッファするために１つまたは複数のレジスタ、あるいはさらにＦＩＦＯバッファが提供されてもよい。そのような実施形態では、レジスタ・ファイル１７は、前の結果の書込みが依然として進行中であっても、バッファ・スペースが後の書込みの結果を格納するために利用可能な場合は、次の結果のための用意ができていると言われることができる。他の諸実施形態では、レジスタ・ファイル１７は、レジスタ・ファイル１７の読出しポートでの読出しアドレスをまだ完了されていない書込みアクションの書込みアドレスと比較し、読出しポート上の読出し結果を最も新しいそのような完了していない書込み動作からの結果で置き換えるバイパス機構を含んでもよい。
【００２８】
擬似コードに関して、回路は次のように記述されることができる。パイプラインの全体の動作は次のように記述される。
ｆｏｒｅｖｅｒ  ｄｏ
ｓｔａｇｅ＿ｎ（）；ｓｔａｇｅ＿ｎ−ｌ（）；ｓｔａｇｅ＿ｎ−２（）；ｓｔａｇｅ＿１（）
ｏｄ
ここで「；」は順次的に実行されるアクティビティを分離する。「ｓｔａｇｅ＿ｉ」で示される第ｉステージ（ｉ＝１．．ｎ）のアクティビティは、少なくとも、第ｉステージの生成されたデータ（「ｄａｔａｌ＿ｉ」）をそのステージの終りで次のステージの前にステージレジスタに取り込むことを含む。
ｓｔａｇｅ＿ｒｅｇｉｓｔｅｒ＿ｉ：＝ｄａｔａ１＿ｉ
（このタイプの擬似コードは、それ自体よく知られているタングラム言語を使用して、タイミング回路に自動的に変換されることができることに留意されたい。）２つの連続するステージでは、ステージアクティビティはまた、データをレジスタ・ファイルに書き込むことを含む。
ｓｔａｇｅ＿ｒｅｇｉｓｔｅｒ＿ｉ：＝ｄａｔａｌ＿ｉ‖
ｉｆ（ｖｌｄ＿ｉ）ｒｆ＿ａｃｔｉｖａｔｅ！＜＜ｄａｔａ２＿ｉ，ｄｓｔ＿ｉ＞＞
ここで、‖は並行（必ずしも順次的ではない）アクティビティを示し、「！」は、「！」の右の情報を「！」の左に識別されたチャネルに書き込むことを示す。すなわち、あるステージの検証信号ｖｌｄ＿ｉが、そのステージによって処理された命令がレジスタ・ファイルに書き込むことを要求することを示す場合、そのステージからｄａｔａ２＿ｉおよびそのステージからレジスタ・アドレスｄｓｔ＿ｉを書き込むことである。「ｒｆ＿ａｃｔｉｖａｔｅ」は、両方のステージが書き込むことができるレジスタ・ファイルに結合された共用のチャネルを示す。レジスタ・ファイルのアクティビティは、次の擬似コードで表されることができる。
ｆｏｒｅｖｅｒ  ｄｏ
ｒｆ＿ａｃｔｉｖａｔｅ？＜＜ｄａｔａ，ｄｓｔ＞＞；
ｒｆ＿ｗｒｉｔｅ（ｄａｔａ，ｄｓｔ）；
ｏｄ
【００２９】
すなわち、レジスタ・ファイルはｒｆ＿ａｃｔｉｖａｔｅチャネルを「聴き」、新しいデータを聴く前に、データが受け取られた場合、アドレス指定されたレジスタでレジスタ・ファイルにデータを書き込む。他の実施形態では、レジスタ・ファイルはまた、バイパスを制御するためにライト・バックステージと通信する。
【００３０】
図２は、書込みタイミング回路１４４の実施を概略的に示している。この実施は２つのブランチを含み、各ブランチはシーケンシング回路２０ａ、２０ｂ、および条件付きハンドシェーク転送回路２２ａ、２２ｂを有する。さらに、この実施は、ハンドシェーク組合せ回路２４およびレジスタ・ファイル・タイミング回路２６を含む。各ブランチ内のシーケンシング回路２０ａ、２０ｂは、タイミング回路の対応するシーケンシング回路１４０ｄ、１４０ｅ（図示されず）に結合されたパッシブ端子と、ブランチの転送回路２２ａ、２２ｂに結合された順次的に第１のアクティブ端子と、ブランチの対応するシーケンシング回路の上流にあるタイミング回路のシーケンシング回路１４０ｃ、１４０ｄ（図示されていない）の１つに結合された順次的に第２のアクティブ端子とを有する。すなわち、第２ブランチのシーケンシング回路２０ｂの順次的に第２の端子は、場合によってはステージのタイミングを制御する他の回路を介して、第１ブランチのシーケンシング回路２０ａのパッシブ端子に結合される。順に、第１ブランチのシーケンシング回路２０ａの順次的に第２の端子は、ステージのタイミングを制御する他の回路を介して第２ブランチのシーケンシング回路２０ｂのパッシブ端子に結合される。転送回路２２ａ、２２ｂは、検証出力１９ａ、１９ｂに結合された条件入力を有する。転送回路２２ａ、２２ｂは、組合せ回路２４に結合されたアクティブ端子を有し、組合せ回路２４は、順に、レジスタ・ファイル・タイミング回路２６に結合されたアクティブ端子、および、どのマルチプレクサ入力からデータが通されるか制御するためのマルチプレクサ１６（図示されず）に結合された選択出力２８を有する。各シーケンシング回路２０ａ、２０ｂは最初にその順次的に第１のアクティブ端子で要求を生成し、その要求の確認応答を待ち、続いて順次的に第２のアクティブ端子で要求を生成することによって、そのパッシブ端子で要求信号に応答するように構成される。シーケンシング回路２０ａ、２０ｂの実施は、使用されるハンドシェークのタイプに依存するが、簡単な実施では、パッシブ端子の要求信号伝導体は順次的に第１のアクティブ端子の要求信号伝導体に結合され、順次的に第１のアクティブ端子の確認応答信号伝導体は順次的に第２のアクティブ端子の要求信号伝導体に結合される。
【００３１】
各転送回路２２ａ、２２ｂは、検証信号が検証出力１９ａ、１９ｂにない場合、直ちにそのパッシブ端子から要求を確認応答するか、あるいは、検証信号がある場合は、要求を組合せ回路２４に転送し、その回路から確認応答を返すように構成される。転送回路２２ａ、２２ｂの実行は、使用されるハンドシェークのタイプに依存するが、簡単な実施形態では、検証信号によって制御され、入ってくる要求を、シーケンシング回路２０ａ、２０ｂの順次的に第１のアクティブ・ポートの確認応答信号伝導体に戻して結合するか、あるいは、組合せ回路２４に結合するマルチプレクシング回路が使用される。ハンドシェーク回路の実行のより一般的な例は、それ自体、エイ・ピータース（A. Peters）による論文「単一レール・ハンドシェーク回路（Single Rail Handshake circuits）」ＩＳＢＮ９０−７４４４５−２８−４に見出される。
【００３２】
組合せ回路２４は、レジスタ・ファイル・タイミング回路２６へのそのアクティブ端子に保留中の要求がない場合は、要求を転送回路２２ａ、２２ｂからレジスタ・ファイル・タイミング回路２６に転送するように構成される。組合せ回路２４は、要求を転送するとき、関連する転送回路２２ａ、２２ｂの要求を確認応答し、マルチプレクサ１６（図示されていない）にどのステージ１０ｃ、１０ｄを求める要求を受け取ったかを通知する信号を送る。一般に、この信号はまた、レジスタ・ファイル１７への書込みを可能にするのに有用である。組合せ回路２４は、レジスタ・ファイル・タイミング回路２６が保留中の場合は、保留要求が確認応答されるまで待ち、その後で転送回路２２ａ、２２ｂから新しい要求を転送し、その要求を確認応答する。
【００３３】
組合せ回路２４の実施は使用されるハンドシェークのタイプに依存するが、簡単な実施形態では、１対のフリップ−フロップがそれぞれ転送回路２２ａ、２２ｂのそれぞれの１つごとに使用される。各フリップ−フロップはその転送回路２２ａ、２２ｂからの要求によって設定され、レジスタ・ファイル・タイミング回路２６からの確認応答によってリセットされる。設定されたフリップ−フロップの出力信号は、もう１つのフリップ−フロップの設定を不可能にし、関連する転送回路２２ａ、２２ｂへの確認応答信号を生じさせ、レジスタ・ファイル・タイミング回路２６への要求信号を生じさせ、何れのステージ１０ｃ、１０ｄがレジスタ・ファイル１７に結合されなければならないかを、マルチプレクサ１６に示している。レジスタ・ファイル・タイミング回路２６は、レジスタ・ファイル１７が関連するステージから結果を書き込む時間を持ったとき、要求を確認応答する。組合せレジスタ・ファイル・タイミング回路２６の実施は、使用されるハンドシェークのタイプに依存するが、簡単な実施形態では、レジスタ・ファイル１７に結果を書き込むのに十分な遅延の後で要求を確認応答する遅延回路が使用されてもよい。
【００３４】
ハンドシェークを生成し受け入れるための様々な種類を有する適切な非同期タイミング回路が当技術から知られていることを強調しておく。説明されてきた実施は簡単な例として役立つだけである。したがって、本発明はこれらの実施に限定されない。
【００３５】
本発明は図１に示された実施形態に限定されないことを理解されたい。たとえば、特定の逆方向シーケンシング回路の代わりに、他のいかなるタイプのパイプラインタイミング回路が使用されてもよい。さらに、レジスタ・ファイル書込み動作をパイプライン・レジスタ１２ａ〜１２ｄへの情報の送信にリンクする代わりに、結果を生成する可能性のあるステージ１０ｃ、１０ｄが代替的に結果を書き込む機会を得ることを保証するために、シーケンシング回路が使用されてもよい。これはさらに詳しく議論される。
【００３６】
この例では、逆方向シーケンシング回路は、パイプライン内の並行性を利用する有利にも簡単な機構を提供する。パイプライン・レジスタの新しいシリーズの開始が、パイプラインの始めに前のシリーズが到着した後でアクションの開始を取り込むので、複雑なハンドシェーキングは何も必要がない。したがって、各ステージにその現在の命令を処理する時間を与えるため、パイプラインを通して後方に伝播する必要がある遅延が使用される。本質的に、この場合、シーケンシング回路１４０ａ〜１４０ｄは、次の上流のパイプライン・レジスタに取り込みを始める前に、パイプライン・レジスタ１２ａ〜１２ｄにデータを取り込むのに十分な時間を保証する遅延回路であればよい。
【００３７】
非常に長いパイプラインの場合、シーケンシング回路１４０ａ〜１４０ｅは、複数のサブループに分割されてよく、各サブループでは、次の下流のサブループからタイミング信号が（あればそれが）到着した場合、タイミング信号の新しいシリーズが、前のタイミング信号がサブループの上流の端に到着することによって、サブループの下流の端で始動される。短いループの場合、ステージがその動作を完了していないうちに新しいタイミング信号が到着するリスクがある可能性がある。この場合、下にあるステージ１０a〜１０dが前の命令を処理してしまったことを示すまで、１つのシーケンシング回路１４０ａ〜１４０ｄから次の上流のものにタイミング信号を転送するのを遅延させるために、追加の回路が提供されてもよい。
【００３８】
代替形態として、完全にブローされた非同期パイプライン、すなわち、パイプラインの端からのタイミング信号の生成が、前のタイミング信号がループの上流の端に到着するのを待たないパイプライン、が使用されてもよい。この場合、たとえば、次のステージ１０ａ〜１０ｄがもうその現在の情報を必要とせず要求ステージから情報をコピーしてしまったときに、ステージが用意できていてタイミング回路が要求を確認応答する場合、タイミング回路１４がステージ１０ａ〜１０ｄの端を求める要求を生成するように構成される転送タイミング機構が使用されてもよい。
【００３９】
このタイプの代替形態では、本発明は、ステージ１０ａ〜１０ｄから結果を書き込む機会を（機会が検証信号の生成に応じて使用されてもされなくても）、ステージ１０ａ〜１０ｄから下流のパイプライン・レジスタ１２ａ〜１２ｄに書き込むことにリンクする書込みタイミング回路によって、図１の場合と同じ方法で実施されてもよい。書込みを要求する機会は、次のステージ１０ａ〜１０ｄの入力でパイプライン・レジスタ１２ａ〜１２ｄに情報を取り込むことが許可されている場合にのみ与えられる。この時に、この次のステージが結果をレジスタ・ファイル１７に書き込む機会を持っていることが保証される。次の上流のステージ１０ａ〜１０ｄへの確認応答は、情報がパイプライン・レジスタ１２ａ〜１２ｄに取り込まれ、かつ書き込む機会が与えられた場合にのみ許可される。これが生じる順序は関連性がない。すなわち、最初に情報がパイプライン・レジスタ１２ａ〜１２ｄに取り込まれてもよく、最初に結果を書き込む機会が与えられてもよく、あるいは、両方が並行して行なわれてもよい。
【００４０】
図３は、独立書込みタイミング・ハンドシェーク回路３０が使用される実施形態を示している。この実施形態では、ステージ１０ａ〜１０ｂは、必要な場合は互いに同期するためにハンドシェーク接続を有する（明瞭のために、これらの接続は、この目的のためにハンドシェーク処理回路を含むと考えられるパイプライン・レジスタ１２ａ〜１２ｄに接続するように示されている）。さらに、ステージ１０ｃ、１０ｄは、書込みタイミング・ハンドシェーク回路３０とハンドシェーク信号を交換するように構成される。結果を書き込むことを必要とする可能性のある各ステージ１０ｃ、１０ｄは、十分用意ができた場合、検証／無検証信号を生成し、その後、書込みタイミング・ハンドシェーク回路３０とハンドシェークを交換する。たとえば、書込みタイミング・ハンドシェーク回路３０は、第１ステージおよび第２ステージ１０ｃ、１０ｄに対して交互に要求を生成してよく、ステージ１０ｃ、１０ｄは用意ができたときにこれらの要求を確認応答してよい。同様に、ステージ１０ｃ、１０ｄは要求を生成してよく、ハンドシェーク回路はこれらの要求を交互に確認応答する。
【００４１】
図４は、書込みタイミング・ハンドシェーク回路３０が、追加されたリピータ回路４０およびシーケンシング回路４２と共に、図２のそれと同様に実装される実施形態を示していす。アクティブ端子４４、４６は、ステージ１０ｃ、１０ｄとハンドシェークを交換するために提供される。しかし、他の多くの実施が、たとえば、確認応答の代わりにステージ１０ｃ、１０ｄからの要求を使用して、あるいは、そのクロック期間が引き延ばされるなどする可能性のあるレジスタ・ファイル書込みクロック回路を使用して、可能であることを理解されたい。
【００４２】
これまでのところ、本発明によれば、パイプライン内の複数のステージ１０ｃ、１０ｄは、同じ書込みポートを介してレジスタ・ファイル１７に結果を書き込むことができることを理解されたい。ステージが書込みをするかどうは、ステージによって処理される命令によって決まる。タイミング回路は、諸ステージが書込みを開始する機会を交互に得ることを保証する。このようにして、プログラムへの書込みの予め決められた順序が保持されることが保証される。たとえば、プログラムが連続する命令
Ｌｏａｄ  ＋＋Ｒ１，Ｒ２
Ａｄｄ  Ｒ３，Ｒ４，Ｒ５
を含むと仮定する（Ｌｏａｄは、レジスタＲ１の値をインクリメントし、データをレジスタＲ２にフェッチするためのアドレスとして値を使用する。Ａｄｄは、レジスタＲ３およびＲ４からの値を加算しＲ５に書き込む。Ｒ２およびＲ５は同じレジスタでよく、その場合、書込み順は命令の順序に対応すべきである）。次に、Ｒ１の内容がロードされて、実行ステージ１０ｃは最初この値をインクリメントする。実行ステージ１０ｃは、インクリメンテーションの結果をレジスタ・ファイル１７内のレジスタＲ１に書き込む。実行ステージ１０ｃは、次に命令およびインクリメントされたアドレスを記憶ステージ１０ｄに渡す。次に、記憶ステージ１０ｄは、この結果に従ってアドレスと共に記憶位置からデータをフェッチし、実行ステージ１０ｃはＲ３およびＲ４の内容を加算する。実行ステージ１０ｃは加算の結果をＲ５に書き込み、記憶ステージ１０ｄはフェッチの結果をＲ２に書き込む。タイミング回路１４は、最初にフェッチの結果が書き込まれ、次に加算の結果が書き込まれることを保証する。
【００４３】
本発明は、レジスタ・ファイル１７に書き込まれるのと同じ結果を記憶ステージ１０ｄにも書き込むことに限定されないことが理解されるであろう。たとえば「ポスト−インクリメント」命令（Ｒ１＋＋）の場合、レジスタＲ１の内容が記憶ステージ１０ｄに渡されて、インクリメントされた値はレジスタ・ファイル１７に書き戻される。同様の例では、Ｒ１のインクリメンテーションはロード命令には必要がない。
Ｌｏａｄ  ＲＩ，Ｒ２
Ａｄｄ  Ｒ３，Ｒ４，Ｒ５
【００４４】
この場合、実行ステージ１０ｃはまた加算の結果をＲ５に書き込み、記憶ステージ１０ｄはフェッチの結果をＲ２に書き込む。タイミング回路１４は、書込みが様々なステージから生じ、したがって均一でない待ち時間を有していたとしても最初にフェッチの結果が書き込まれ、次に加算の結果が書き込まれることを保証する。
【００４５】
もちろん、レジスタの読出しが、保留中の書込みが存在するレジスタ・ファイル１７のレジスタから生じることが起こる可能性もある。この場合、一実施形態では、レジスタの書込み動作が保留中の場合、そのレジスタの古い内容が使用されてよい。より進んだ実施形態では、レジスタ読出しアクションの結果内の保留中の書込みアクションの結果を置換するためにどんなバイパス機構が使用されてもよい。この実施形態では、不確定な読出しの問題は、理論上、深いパイプラインが使用されていて、結果書込み動作のタイミングが読出し動作に同期されていない場合に生じる。この問題は、前の波がパイプラインの上流の端までまだ進んでいない限り、レジスタ取込みの新しい波がパイプラインの下流の端を形成することを防ぐ図１の逆方向シーケンシング機構によって防止される。完全に非同期のパイプラインでは、この問題を回避するために、書込みステージ１０ａ、１０ｃのシーケンシング構成にレジスタ・ファイル１７から読み出すステージを含むことが必要である可能性がある。これは、パイプライン・レジスタ１２ａ〜１２ｄでの新しい取込みの各サイクルおよび結果のレジスタ・ファイル１７への書込みが、レジスタ読出しステージでのそれぞれの取込みの後に書込みステージで生じることを保証するために行なわれる。しかし、通常、このタイプのシーケンシングは不必要である。
【００４６】
これらの例では、各ステージ１０ａ〜１０ｄは、１つの命令に応じて、せいぜい１つの結果をレジスタに書き込むことを必要とするだけである。しかし、他の実施形態では、本発明から逸脱することなく、その同じ命令に応じて、１つまたは複数のステージ１０ａ〜１０ｄが複数の結果を書き込むように構成されてもよい。たとえば、実行ステージ１０ｃは、２つのオペランドの合計と差の両方をレジスタ・ファイル１７の様々なレジスタに書き戻すように構成されることができるであろう。
【００４７】
図５は、ステージの１つ１０ｃが複数の結果を書き込むように構成されたパイプライン・プロセッサの一部分を示している。この実施形態では、アドレス／結果出力、検証出力およびハンドシェーク端子が、各結果に提供される。３入力マルチプレクサ１６が使用される。図１または図４で使用されたものと同様でよい書込みタイミング回路３０／１４４は、ステージ１０ｃ、１０ｄが順に各結果を書き込む機会を得ることを保証している。これは、たとえば、結果の書込みをパイプライン・レジスタ１２ｃ、１２ｄへの情報の書込みにリンクすることによって実現されることができる。あるいは、これらのステージが順次書き込む機会を得ることを保証するために、独立シーケンシング機構が使用されてもよく、２つの結果を書き込むことができるステージ１０ｃは順次２つの機会を得る。明らかに、これはどんな数の結果にも拡張されることができる。
【００４８】
図５は単に１つの実施形態を示すだけであることが理解されるであろう。たとえば、他の実施形態では、同じアドレス／結果出力が複数の結果のために使用されてもよい。この実施形態では、ステージ１０ｃは、交代したことを確認応答する前に、全ての結果が１つのアドレス／結果出力に適用されることを保証する。他の代替形態では、書込みタイミング回路は、複数の全ての結果が、たとえば、ステージ１０ｃが複数の有効結果が入手可能であることを示す時に移る前に、レジスタ・ファイル１７に複数の要求を出すことによって書き込まれることを保証する。
【００４９】
他の実施形態では、レジスタ・ファイルは複数の書込みポートを有してよく、少なくとも１つのポートは、上記で単一ポートに関して説明されたように、共用され、他の１つまたは複数のポートは、たとえば、他のステージから、あるいは同様に共用されたポートに書き込むステージから、他の結果が並行して書き込まれることができるようにする。他の１つまたは複数のポートも共用されてよい。本発明は、レジスタ・ファイル１７に書き込むことを可能にする検証信号が命令に依存する実施形態に関して説明されてきたが、検証信号はまた、（たとえば、命令で指定されたガード・レジスタの内容に依存する）命令に付随するガード・ビットの値などの要素に依存することを理解されたい。
【００５０】
書込み機能を有する２つの直接隣接するパイプラインステージ１０ｃ、１０ｄが一例として示されているが、本発明はこの例に限定されないことが理解されるであろう。たとえば、より大きな数の連続するパイプラインステージが１つまたは複数の結果をレジスタ・ファイル１７に書き込む機能を有してもよい。この場合、そのようなステージのそれぞれが、ステージが別の機会を得る前に、好ましくは最も下流にあるステージから始めて、予め決められた順序で順に書き込む機会を得るようにシーケンシング回路が含まれることが好ましい。他の例においては、書き込むための機能を有するステージは、直接隣接している必要はない。
【図面の簡単な説明】
【００５１】
【図１】パイプライン式命令処理回路を示す図である。
【図２】書込みタイミング回路を示す図である。
【図３】代替パイプライン式命令処理回路を示す図である。
【図４】代替書込みタイミング回路を示す図である。
【図５】パイプライン式命令処理回路の一部分を示す図である。
【図１】
2007535060.tif 000003
【図２】
2007535060.tif 000004
【図３】
2007535060.tif 000005
【図４】
2007535060.tif 000006
【図５】
2007535060.tif 000007
【国際調査報告】
2007535060.tif 000008
2007535060.tif 000009
2007535060.tif 000010