JPH1091597A - マルチプロセッサ装置におけるトークンにもとづく命令の直列化 - Google Patents

Abstract

(57)【要約】 【課題】 マルチプロセッサ装置で直列処理される命令
を、トークンを使用して直列化するプロセスを提供す
る。 【解決手段】 トークンは要求に応じてプロセッサの１
つに割当てることができ、その後、プロセッサはコマン
ドを実行する権利を有する。コマンドが、分散したタス
クで構成される場合、コマンドに属する最後の依存タス
クも実行されるまでトークンはブロックされたままであ
る。そのときにのみトークンを他の命令に割当てること
ができる。また、このトークンを管理する装置は３つの
状態を特徴とする。第１の状態ではトークンを利用で
き、第２の状態ではトークンがプロセッサの１つに割当
てられ、第３の状態では、依存タスクがまだ実行されて
いるのでトークンはブロックされる。ここで述べている
トークンの原理を同様に実現できる回路についても説明
してある。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、マルチプロセッサ
装置の命令を、トークンを使用して直列化するプロセス
と、トークンを管理する装置に関し、特に、全てのプロ
セッサに共通のリソースを変更するＩＰＴＥ（ページ・
テーブル・エントリ無効化）、ＳＳＫＥ（記憶キー拡張
セット）等のコマンドに関する。

【０００２】

【従来の技術】マルチプロセッサ装置では、各々のプロ
セッサが、オペレーティング・システムによって各々の
プロセッサに割当てられた命令の流れを処理する。たと
えば、第１のプロセッサは、メモリ内の指定されたペー
ジに保存されたプログラムを処理し、第２のプロセッサ
は、他のページに保存されたオペレーティング・システ
ムのプログラムを実行する。実行側プロセッサへの個々
のプログラムの割当ては、この例では、オペレーティン
グ・システムの特別なルーチンによって行われる。プロ
セッサが、プロセッサに割当てられているプログラムの
処理を終えると、オペレーティング・システムは、再び
使用できるようになったプロセッサに割当てる新しいプ
ログラムを明示する。

【０００３】２つのプロセッサが、それぞれプログラム
を実行中に同じメモリ・アドレスにアクセスすると、衝
突が生じる。最初、実際にはプロセッサのそれぞれの専
用レベル１（Ｌ１）キャッシュだけが変更される。ただ
しその後、データの保全性を保証するために、Ｌ１キャ
ッシュに保存された２つの権限レベルのどちらが有効か
判断できなければならない。

【０００４】マルチプロセッサ装置のプロセッサの１つ
が、全てのプロセッサに共通のリソースを変更するとき
には、データの保全性に関して、より重要な問題が生じ
る。

【０００５】その場合、リソースの変更によって、他の
プロセッサで今実行されている命令に関してリソースの
ステータスが未定義のままにならないようにしなければ
ならない。そうでなければデータの保全性に対する違反
が生じる。

【０００６】全てのプロセッサに共通のリソースを変更
するコマンドを実行するときには、他の全てのプロセッ
サが、実行されている変更を記憶しなければならないこ
とがある。たとえば、共同リソースのローカル・コピー
を更新しなければならないため等である。従って、共同
リソースを変更するコマンドにより、他の全てのプロセ
ッサで実行する必要のある一連のドーター・プロセス
（daughter process）が起動することがあり得る。

【０００７】これらの全てのプロセスの実行で重要なこ
とは、データの保全性を維持することに関連した正しい
スケジューリングである。

【０００８】この種の命令の例は、仮想アドレシングに
よりメモリをアドレスするマルチプロセッサ装置の分野
に見られる。普通、仮想アドレスから実アドレスへの変
換は、メモリに保存され、互いに関係のあるいくつかの
テーブルを使用して行われる。図１にこれらのテーブル
の構造を示す。変換に必要な第１のテーブル、セグメン
ト・テーブルの初期アドレスは、ＣＰＵの制御レジスタ
に保存される。このようにして指定されたセグメント・
テーブルを起点として、変換を進めるのに必要なページ
・テーブルの初期アドレスを含む、セグメント・テーブ
ル内のエントリに達するために、セグメント索引（仮想
アドレスのビット１乃至１１によって形成される）を使
用することができる。

【０００９】図２はセグメント・テーブルのエントリを
示す。各エントリは、参照が行われたページ・テーブル
の初期アドレス（ページ・テーブル起点）だけでなく、
その長さも示す。アドレス変換のためにページ・テーブ
ルの使用が予想されなくなると、ページ・テーブルは有
効でなくなったと認識されなければならない。これは、
ページ・テーブルの無効ビットをセットすることによっ
て行われる。ページ・テーブル無効ビットがセットされ
ていない、従って０に等しいページ・テーブルのみアド
レス変換に使用することができる。

【００１０】次に、アドレス変換の次の段階で、途中で
見つかっているページ・テーブルを利用して、必要なペ
ージ・フレームの初期アドレスが決定される。図１はこ
の方法を示している。ページ・テーブルの関連エントリ
に達する上での索引の目的は、仮想アドレスの中間領
域、ページ索引（仮想アドレスのビット１２乃至１９）
によって達成される。このようにして見つかったページ
・テーブル・エントリは、所要ページが保存されたペー
ジ・フレームの初期アドレスを参照する。この例のペー
ジ・フレームは、ページを収容できるメモリ内アドレス
領域である。

【００１１】図３はページ・テーブル・エントリを示
す。これはページ・フレームの初期アドレスを含む。ま
たページ無効ビットがあり、指定されたページのデータ
が有効かどうかを示す。ページ・テーブル・エントリ
は、このページ無効ビットがセットされていない、従っ
て０に等しい場合はアドレス変換にのみ使用できる。

【００１２】アクセスされる実アドレスを決定するため
に、図１に示すように、仮想アドレスのバイト索引（ビ
ット２０乃至３１）を、ページ・フレームの初期アドレ
スに追加する必要がある。そのために、バイト索引はペ
ージ・フレームのランプ・アドレスに付加される。この
ようにして得られるアドレスは実アドレスである。この
実アドレスをもとに絶対アドレスを得るには、いわゆる
プレフィクスを実アドレスに追加しなければならないこ
とがある。メモリは、このようにして得られた絶対アド
レスにより、直接アクセスすることができる。

【００１３】ここまでに述べた仮想アドレスから実アド
レスへの多段階変換は非常に時間がかかる。テーブルの
階層全体を検索しなければならないためである。１つの
アドレスの変換に約５０のプロセッサ・サイクルが必要
である。

【００１４】この理由のために、セグメント・テーブル
とページ・テーブルによって詳細な変換を回避する形
で、ページ・フレームの実初期アドレスを高速に検索で
きるよう、アドレス変換キャッシュ（または変換索引バ
ッファ：ＴＬＢ）が用いられている。そのため、ページ
に関係するアドレス変換キャッシュ・エントリで、仮想
アドレスの上位部（すなわちセグメント索引とページ索
引）が、ページ・フレームの実初期アドレスとの関係か
らセットされる。このエントリは、ページが最初にアド
レスされた場合に作成され、その後、ページがアドレス
される全ての場合に用いられる。アドレス変換キャッシ
ュのルックアップにはわずか数プロセッサ・サイクルし
か要しないので、メモリに保存されるセグメント・テー
ブルとページ・テーブルによる明示的変換に比べて、速
度の点で大きな利点がある。

【００１５】各プロセッサに、割当てられた専用のアド
レス変換キャッシュがある。キャッシュは、シーケンス
に従ってプロセッサによって実行されたアドレス変換結
果を保存する。仮想アドレスを、割当てられた実アドレ
スに変換する場合、プロセッサは最初、そのアドレス変
換キャッシュのこのページに関するエントリを保存して
いるかどうかチェックする。そうでない場合にのみ、プ
ロセッサは、メモリ内のテーブルを利用して仮想アドレ
スを変換する。

【００１６】仮想アドレス処理によって開かれたアドレ
ス領域は、使用可能なメモリのサイズよりも何倍も大き
い。そのため、ある指定された時点では、実質的にアド
レス可能なページの一部しかメモリ内に存在しない。他
のページは外部記憶媒体にある。

【００１７】プロセッサが、メモリに存在しないページ
にアクセスした場合、別のページをメモリから外部記憶
媒体に転送する必要がある。プロセッサがアクセスしよ
うとする新しいページは、メモリにそのように作成した
空き位置に保存することができる。ページの動的な保存
と転送のこのプロセスは"スワッピング"と呼ばれる。

【００１８】ページがメモリから外部記憶媒体に転送さ
れるとき、このページに関係するページ・テーブルのエ
ントリも無効にしなければならない。このエントリは実
際に、メモリのページの実初期アドレスを参照していた
からである。これは、関連ページ・テーブル・エントリ
のページ無効ビットをセットすることによって行われ
る。図３はページ・テーブル・エントリの構造を示す。
ページ無効ビットはこの例ではビット２１である。ペー
ジ無効ビットがセットされているページ・テーブル・エ
ントリは、アドレス変換には使われなくなることがあ
る。

【００１９】ページを外部記憶媒体に転送し、関連ペー
ジ・テーブル・エントリを無効にすることで、メモリ
に、他のページを保存できる空き位置が作成される。

【００２０】プロセッサが、まだメモリに存在しないペ
ージをアドレスするとき、当のページは外部記憶媒体か
らメモリに入力しなければならない（デマンド・ページ
ング）。この新しいページはそこで、古いページを無効
にして別の記憶域に転送することによって作成されてい
る空き位置を占める。この新しいページについて、新し
いページ・テーブル・エントリが作成される。全く異な
る仮想アドレス領域が、この新しいページ・テーブル・
エントリによって、古いページに占められていたメモリ
の絶対アドレスの同じ領域にマップされる。

【００２１】ここまで、ページがメモリの記憶域に入力
されるとき、またはそこから外部記憶域に転送されると
きに、ページ・テーブルのエントリに変更が必要なこと
について述べてきたが、エントリは、途中で外部記憶域
に転送されているページを参照する個々のプロセッサに
割当てられたアドレス変換キャッシュにも存在する。ペ
ージ・テーブルのエントリと共に、ＴＬＢのこれらのエ
ントリも、アドレス変換キャッシュに割当てられたプロ
セッサがこれらのエントリを使用できないように、従っ
て、メモリからすでに転送されており、メモリ内の位置
が他のページによって占められているページをアドレス
しようとしてもできないように、"無効"と宣言しなけれ
ばならない。転送されたページを参照するＴＬＢエント
リが、ＴＬＢに存在し続けるものなら、割当てられたプ
ロセッサは、目的のページとは全く異なるページをアド
レスする。

【００２２】ここで、メモリから転送されるページを無
効にする目的からは、ページ・テーブルの対応エントリ
を無効にする必要がある一方で、個々のプロセッサに割
当てられた全てのアドレス変換キャッシュのページに関
係した全てのエントリも無効にする必要がある。

【００２３】その結果は、ページ・テーブルの１つのエ
ントリを無効にするためには、一方で、ページ・テーブ
ル・エントリ自体（及び開始側プロセッサに割当てられ
たＴＬＢで転送されるページに関係するエントリ）を、
無効化を開始するプロセッサによって無効にする必要が
あり、他方、他の全てのプロセッサに割当てられたアド
レス変換キャッシュで転送されるページに関係するエン
トリを無効にするためには、これらのプロセッサで依存
するタスクを起動する必要もある。

【００２４】その場合、変更される共通のリソースは、
メモリの関連ページ・テーブルであり、これはもちろん
全てのプロセッサによってアクセスされる。アドレス変
換キャッシュの対応エントリは、共通リソースのローカ
ル・コピーを表す。共通リソースを変更する場合は、ロ
ーカル・コピーも更新しなければならない。

【００２５】重要なことは、開始側プロセッサで初期タ
スクを実行し、開始側プロセッサに依存するタスクの、
他のプロセッサ（レスポンダ）での実行時に、アドレス
変換に関してデータの保全性を保護することである。ど
のプロセッサでも、そこで実行される命令は、どの１つ
のプロセッサでも、その実行時に必要とするアドレス変
換を一貫して行えなければならない。また更に、これ
は、アドレス変換がメモリのテーブル階層を使用した長
いパスを経由して行われるか、アドレス変換キャッシュ
を使用した短いパスを経由して行われるかどうかとは無
関係でなければならない。

【００２６】ここで、初期タスク（開始側プロセッサで
実行される）と、それに依存するタスク（他のプロセッ
サで実行される）は、適切な形で、それぞれのプロセッ
サで実行される他の命令と直列化しなければならない。

【００２７】マルチプロセッサ装置にはコンピュータ・
コマンドの列全体があり、これは、これまで示してきた
方式に従って発生し、全てのプロセッサに共通のリソー
スは、従って初期タスクによって変更されると同時に、
初期タスクに依存するタスクによって更新される共通リ
ソースのローカル・コピーが利用できる。ここで述べた
ページ・テーブル・エントリの無効化（ＩＰＴＥ）は、
この種のコマンドの１つの例である。

【００２８】この種のコンピュータ・コマンドの他の例
は、全てのページに割当てられ、このページへのアクセ
ス権を決定するキー情報の変更に関係する。キー情報
は、所要記憶域に保存される一方、アドレス変換キャッ
シュのエントリにも保存される。ページに割当てられた
キー情報を変更するには、中央のリソース、所要記憶域
を変更する必要がある一方、個々のプロセッサのアドレ
ス変換キャッシュ内のキー情報のローカル・コピーを更
新する必要もある。

【００２９】ここでも、共通リソースを変更するために
初期タスクが、またローカル・コピーを更新するための
この初期タスクに依存するタスクが実行される。

【００３０】これらのコマンドの場合でも、データの保
全性の保護が保証されなければならない。命令実行中
に、この命令によってアドレスされるページのキーの変
更は防ぐ必要がある。そのためには、初期タスクと、依
存タスクの適切なスケジューリングが必要である。

【００３１】この問題の解決方法は、図３に示してい
る、いわゆる"静止"方式で表される。この方式の場
合、"ＩＰＴＥ"コマンド（ページ・テーブル・エントリ
無効化）を実行しようとするプロセッサは、"静止要求"
を他の全てのプロセッサに送る。これらのプロセッサは
ただ、"静止要求"の前に開始された命令を実行している
（３０１）。これらの命令の１つが完全に実行されると
（３０２）、関連するプロセッサは、最後のプロセッサ
も、まだ保留中であるその命令の実行を完了する（３０
３）まで待機時間を挿入する（３０４）。この時点から
以降、全てのプロセッサが"静止モード"になる（３０
５）。ＰＵ０はここで、対応するページ・テーブル・エ
ントリ及び、外部記憶域に転送されるページに関係した
それ自身のＴＬＢのエントリを無効化できる。他のプロ
セッサは、これらに割当てられたＴＬＢのこのページに
関係するエントリを削除するよう促される。

【００３２】ＩＰＴＥコマンドが完全に終了した後、開
始側ＰＵは他の全てのプロセッサに"静止リセット"を送
る（３０８）。次に後者のプロセッサは、命令フローの
次の命令の処理に進む（３０９）。ＰＵ０も、"静止リ
セット"を送った後、後の命令の処理に進む。

【００３３】この方式の欠点は、依存タスクを実行して
いるプロセッサ側で待機時間が長く、その間、これらの
プロセッサは次の命令を実行できないことである。各プ
ロセッサで、待機時間は、各例につき、開始側プロセッ
サがその"静止要求"を送ったとき実行されたばかりのそ
の命令の完了時（３０２）に始まり、最後のプロセッサ
も、"静止要求"の時点で保留されていたコマンドの実行
を終えた時点に終了する（３０３）。開始側プロセッサ
がページ・テーブル・エントリを無効にしている間、他
のプロセッサ側はまた待機時間に入り（３０７）、この
状態は依存タスクを実行する要求が届くまで続く。レス
ポンダＰＵ側に生じるこれら待機時間は無視できるもの
ではなく、達成可能なパフォーマンスを損う。

【００３４】レスポンダＰＵに生じるこれらの待機時間
を避ける方法は、Padegsらによる米国特許番号３９４７
８２３号に述べられている。ここで提起している解決方
法の目的は、任意のプロセッサで保留されている命令の
それぞれに用いられるメモリ・アドレス（及びその内
容）を、それら命令に対して命令の完了まで維持するこ
とである。これは、命令によってアクセスされるメモリ
・アドレスと内容に対して特別なバッファ・メモリを取
り入れることにより行われる。その結果、命令は実メモ
リ・ページ、アドレス、及び内容に依存しなくなる。こ
れらへのアクセスは、命令の実行中には行われなくなる
からである。従って、ページ・テーブルのエントリとア
ドレス変換キャッシュの無効化、及び外部Ｉ／Ｏ装置へ
のページの転送は、まだ実行されている命令を考慮せず
に、これらの命令が、外部記憶域に転送されるページの
アドレスにアクセスする場合でも、実行することができ
る。この方法の場合、結果的に、データの保全性に関し
て、正しいスケジューリングに注意する必要はない。そ
のため、依存タスクの実行に関係する待機時間は、この
方法を利用することにより回避することができる。

【００３５】ただし、この方法の欠点は、ちょうど実行
されている命令に必要な全てのアドレス及びアドレス内
容を一時的に保存するために、高価なハードウェアを追
加しなければならないことにある。

【００３６】IBM Technical Disclosure Bulletin、Vo
l．33、No．6B、November、1990、P428-433に発表され
た"Low-Synchronization Translation Lookaside Buffe
r Consistency Algorithm（低同期化ＴＬＢ一貫性アル
ゴリズム）"で、B．S．Rosenburgは、ページ・テーブル
・エントリを無効にするプロセスを示している。ここで
はレスポンダ・プロセッサの待機時間が回避される。そ
のために、開始側プロセッサはまず、対応するページ・
テーブル・エントリを無効化し、変更されたページ・テ
ーブルを識別する。次にレスポンダ・プロセッサに割込
みが送られ、これに応答して、命令フローの割込み可能
点で、アクティブなページ・テーブルの変更を探す。ペ
ージ・テーブル・エントリが無効化されている場合、レ
スポンダ・プロセッサは、存在する場合には対応するロ
ーカルＴＬＢエントリを無効化する。次にレスポンダ・
プロセッサは、命令フローの次の命令の処理に進む。

【００３７】この方法の欠点は、全てのレスポンダＰＵ
が、全てのページ・テーブルを調べてフラグを探し、エ
ントリを無効化しなければならないことである。このよ
うな処理にはかなりの時間がかかる。もう１つの欠点と
して、変更されたページ・テーブルにアクセスする命令
に関係したデータの保全性については何も言及されてい
ない。分散タスクから構成されるコマンドの直列化に関
係した技術的な解決方法では、データの保全性という側
面を無視することはできない。

【００３８】

【発明が解決しようとする課題】本発明の目的は、マル
チプロセッサ装置において命令の直列化方法を提供する
ことである。この場合、指定されたコマンドの直列化の
必要性は、これらのコマンドにより、全てのプロセッサ
に共通のリソースが変更されるという事実から来てい
る。

【００３９】本発明の他の目的は、開始側プロセッサで
実行される１つの初期タスクと、この初期タスクに依存
し、他のプロセッサで実行されるタスクとで構成される
コマンドを実行するために、適切な直列化の方法を提供
することである。共同リソースのローカル・コピーを更
新しなければならない場合には、依存タスクの実行が必
要になることがある。

【００４０】本発明の他の目的は、高いパフォーマンス
を保証するために、さまざまなタスクの実行時に生じる
待機時間を最少にすることである。

【００４１】また、分散タスクを構成するコマンドの実
行時にデータの保全性を保証することも重要である。

【００４２】本発明の他の目的は、ページ・テーブル・
エントリを無効化するコマンド、ＩＰＴＥ、及びページ
に関係するキー情報を変更するコマンド、ＳＳＫＥを対
象にした、改良された実行形態を提起することである。

【００４３】本発明の他の目的は、ここで提供する直列
化処理を行うためのトークンを管理する装置を開示する
ことである。

【００４４】本発明の他の目的は、この装置を、ハード
ウェアにあまりコストをかけずに実現することである。

【００４５】

【課題を解決するための手段】本発明に従って、マルチ
プロセッサ装置で直列処理される命令の直列化のための
トークンを管理する装置によってタスクが実行される。
プロセッサは、トークンを保有している場合にのみ、直
列処理される命令を実行することができ、トークンを管
理する装置は次の状態を特徴とする。第１の状態では、
どのプロセッサにもトークンは割当てられず、トークン
は、トークンを要求したプロセッサには割当てることが
できる。第２の状態では、プロセッサの１つにトークン
が割当てられ、トークンを要求したプロセッサには割当
てられない。第３の状態では、どのプロセッサにもトー
クンは割当てられず、トークンを要求したプロセッサに
も割当てられない。

【００４６】従って、直列化される命令の直列化は、ト
ークンの割当てによって規定される。この場合、第３の
状態については別に、トークンがブロックされる機構が
追加される。これにより直列化される命令の実行を外部
条件と連結することができる。外部条件により、トーク
ンをブロックし、従って直列化される命令の実行を防ぐ
ことができる。

【００４７】ｎ個のプロセッサで構成されるマルチプロ
セッサ装置でトークンを管理する装置は、本発明に従っ
て、プロセッサｉがトークンを保有している場合にセッ
トされる１つの信号Ａｉの、各プロセッサｉに対する可
用性、各プロセッサｉに対して、まだ完全に実行されて
いないタスク（このタスクは直列処理される命令の１つ
の実行で直列化され、そのためにトークンを要求したプ
ロセッサに前記トークンを割当てることができなくな
る）がプロセッサｉで保留されているときにセットされ
る１つの信号Ｂｉの可用性、及び、マルチプロセッサ装
置全体に共通な信号Ｃの可用性、によって実現される。
信号Ｃは、先に列挙された全てのプロセッサの信号Ａ
１、．．．Ａｎ、Ｂ１、．．．ＢｎのORチェインによっ
て生じ、要求側プロセッサにトークンを割当てられない
場合にセットされる。ここでトークンを管理する装置の
第１の状態は、信号Ａ１、．．．Ａｎ、Ｂ１、．．．Ｂ
ｎのいずれもセットされないことを特徴とする。トーク
ンを管理する装置の第２の状態は、信号Ａ１、．．．Ａ
ｎの１つがセットされることを特徴とする。トークンを
管理する装置の第３の状態は、信号Ａ１、．．．Ａｎは
いずれもセットされないが、Ｂ１、．．．Ｂｎ信号の少
なくとも１つはセットされることを特徴とする。

【００４８】この実施形態の利点は、トークンを管理す
る装置の状態が、非常に簡素な形で表されることであ
る。その結果、必要なハードウェアのコストは低く抑え
られる。命令の直列化に必要な基本回路は、信号Ａ
１、．．．Ａｎ、Ｂ１、．．．ＢｎのORチェインに限定
される。

【００４９】本発明の他の利点として、各プロセッサｉ
に対して、信号ＡｉとＢｉのORチェインによって生じる
１つの信号Ｃｉの可用性が考慮されている。また、マル
チプロセッサ全体に共通であり、全てのプロセッサの信
号Ｃ１、．．．ＣｎのORチェインによって生じる信号Ｃ
の可用性も考慮されている。

【００５０】信号Ｃは、マルチプロセッサ装置全体に共
通な信号なので、これは、回路設計の観点から、各プロ
セッサに置かれるORゲートにより、各プロセッサｉに割
当てられる信号Ａｉ及びＢｉが最初に連接され、１つの
信号Ｃｉを形成する場合は利点になる。その際、１つの
信号、つまり信号Ｃｉ、を各プロセッサから中央のORゲ
ートに供給するだけでよいからである。

【００５１】本発明の他の利点として、直列処理される
命令は、開始側プロセッサで実行される第１のタスク
と、レスポンダ・プロセッサで実行される依存タスクと
で構成される。ここでトークンは、開始側プロセッサに
割当てなければならないので、開始側プロセッサは第１
のタスクを実行することができる。トークンは、全ての
依存タスクが完了するまで、トークンを要求するプロセ
ッサには割当てられない。

【００５２】本発明により、本発明に従ってトークンが
取り得る第３の状態でどのような利点が得られるか明ら
かになる。命令が、異なるプロセッサで実行される分散
タスクで構成される場合、開始側プロセッサは、命令の
実行を開始するためには、トークンを保有していなけれ
ばならない。しかし、まだ保留されているタスクが実行
過程にある限り、トークンはブロックされたままであ
る。ただし開始側プロセッサは、そのタスクをすでに終
えており、トークンを返している可能性はある。こうし
て依存タスクにより、直列処理される新しいコマンドの
実行を開始することはできなくなる。

【００５３】本発明の他の利点として、命令バッファが
マルチプロセッサ装置の各プロセッサに割当てられ、こ
こで最初のプロセッサは、最初のタスクの実行時にコマ
ンドやアドレスをレスポンダ・プロセッサの命令バッフ
ァに書込む。これらのコマンドやアドレスは、レスポン
ダ・プロセッサで実行される依存タスクを指定する。

【００５４】このようにして、最初のタスクは、レスポ
ンダ・プロセッサに割込む必要なく、必要な依存タスク
を開始することができる。レスポンダ・プロセッサが、
依存タスクを実行できる点に達したときにのみ、命令バ
ッファに書込まれた情報が考慮される。

【００５５】本発明の他の利点として、レスポンダＰＵ
の命令バッファへの書込みは、ブロードキャスト強制操
作によって行われる。

【００５６】更に、信号Ｂｉ（"コマンド保留"）を、レ
スポンダ・プロセッサｉの命令バッファへのコマンドま
たはアドレスの書込みと一緒にセットすることも利点に
なる。

【００５７】これと共に、レスポンダ・プロセッサｉの
それぞれの依存タスクの終了時に信号Ｂｉをリセットす
ることも利点になる。

【００５８】また本発明では、依存タスクは、レスポン
ダ・プロセッサの命令フローの中、割込み可能な点に挿
入され実行される。

【００５９】これによりレスポンダ・プロセッサの待機
時間が回避され、パフォーマンスは大幅に向上する。

【００６０】リマインダをもとにした解決方法で特に大
きな利点のあるコマンドは、ＳＳＫＥ（記憶キー拡張セ
ット）コマンドである。

【００６１】マルチプロセッサ装置はメモリで構成され
るが、メモリをアドレスするためには、仮想アドレスか
ら実アドレスへの変換を、アドレス変換テーブルを利用
して行うことができる。すでに行われたアドレス変換の
結果は、アドレス変換キャッシュに保存される。アドレ
ス変換キャッシュはそれぞれプロセッサの１つに割当て
られる。ページに対する個々のプロセッサのアクセス権
を決定するためのキー情報は、メモリの一部分、つまり
キー記憶域に保存される。直列処理される命令は、キー
情報を変更するための命令（ＳＳＫＥ）である。開始側
プロセッサは、最初のタスクの実行時にキー記憶域にあ
るキー情報を変更する。そして、依存タスクの実行時、
他のプロセッサは、他のプロセッサに割当てられたアド
レス変換キャッシュのキー情報を変更する。

【００６２】プロセッサは各々、キー記憶域のキーの変
更によって影響を受ける。ＳＳＫＥの場合にデータの保
全性の観点からコマンドの直列化が必要である。依存タ
スクの実行時には他のコマンドへのトークンの割当ても
防止しなければならない。

【００６３】リマインダをもとにした解決方法が特に都
合がよい１つのコマンドは、ページ・テーブルのエント
リを無効化するコマンド、ＩＰＴＥ（ページ・テーブル
・エントリ無効化）である。その場合、マルチプロセッ
サ装置はメモリで構成されるが、メモリをアドレスする
ために、仮想アドレスから実アドレスへの変換を、アド
レス変換テーブルを利用して行うことができる。すでに
行われたアドレス変換の結果は、アドレス変換キャッシ
ュに保存される。アドレス変換キャッシュはそれぞれプ
ロセッサの１つに割当てられる。直列処理される命令
は、ページ・テーブル・エントリを無効化する命令（Ｉ
ＰＴＥ）である。開始側プロセッサは、最初のタスクの
実行時にページ・テーブル・エントリを無効化する。そ
して、依存タスクの実行時、他のプロセッサは、他のプ
ロセッサに割当てられたアドレス変換キャッシュの対応
するエントリを無効化する。

【００６４】直列化は、特に、ページ・テーブル・エン
トリを無効化する場合にデータの保全性の観点から重要
である。プロセッサは全て、アドレス変換のためにメモ
リのテーブルにアクセスするので、当然、ページ・テー
ブル・エントリの無効化は全てのプロセッサに影響を与
える。また、まだ依存タスクの実行時に新しいＩＰＴＥ
を開始することも不可能である。依存タスクは、ＩＰＴ
Ｅの場合には、ＴＬＢエントリを無効化する。特にこの
ために、返された後でもトークンをブロック状態にする
ことができるトークン管理装置が有利である。

【００６５】本発明の利点として、特に、ページ・テー
ブル・エントリの無効化に関係して、ｎ次関連アドレス
変換キャッシュの導入がある。この場合、ｎ回を超える
アドレス変換を要する命令は、ページ・テーブル・エン
トリを無効化する命令（ＩＰＴＥ）で直列化される。

【００６６】ＩＰＴＥは、次の手段により、ｎ回を超え
るアドレス変換を要するこの種のコマンドで有利に直列
化することができる。トークンは、プロセッサｉに割当
てなければならない。これによりプロセッサｉは、ｎ回
を超えるアドレス変換を要する命令を実行することがで
きる。

【００６７】このような手段によりデータの保全性の保
護を保証できる。ｎタプル関連アドレス変換キャッシュ
により、ｎ回より少ないまたは等しいアドレス変換を要
するコマンドでＩＰＴＥを直列化する必要がない。これ
で時間とコストが節約される。

【００６８】マルチプロセッサ装置で直列処理される命
令を直列化するため、本発明に従ったプロセスについて
述べる。直列処理される命令の１つの実行は、開始側プ
ロセッサでの第１のタスクの実行から構成され、開始側
プロセッサは、トークンを保有している場合にのみ第１
のタスクを実行することができ、トークンは、使用可能
な場合、プロセッサの１つにのみ割当てることができ
る。このプロセスは次のステップで構成される。（１）
開始側プロセッサにトークンを要求するステップ、
（２）トークンが使用可能な場合に開始側プロセッサに
トークンを割当てるステップ、（３）直列処理される命
令を実行するステップ、（４）直列処理される命令の最
初のタスクが完了した後にトークンを返すステップ（そ
の結果、トークンは、必ずしも他のプロセッサから使用
できるようにする必要がない）、（５）直列処理される
命令の実行が完了した後にトークンの可用性を確立する
ステップ。

【００６９】このプロセスの場合、最初のタスクのパフ
ォーマンスは、トークンを保有した実行側プロセッサに
依存する。このプロセッサはまた、最初のタスクの実行
を完了したときにトークンを返す。

【００７０】本発明に従った利点は、それにもかかわら
ず、コマンドに属し、他のプロセッサで実行されるタス
クが、すでに完全に完了したかどうかを考慮できるとい
う点にある。他のプロセッサのタスクを含めて、コマン
ド全体が完了したときにのみ、直列処理される新しいコ
マンドを実行することができる。本発明に従って、その
時点までトークンの可用性が再確立されることはない。

【００７１】

【発明の実施の形態】図５及び図６は、開始側プロセッ
サで実行される最初のタスクのシーケンスを示す。例に
示すように、ページ・テーブル・エントリの無効化が考
慮されているが、それでもコマンドを実行する基本シー
ケンスは、最初のタスク、及びこの最初のタスクに依存
するタスクで構成された全てのコマンドで同じである。
ＩＰＴＥ（ページ・テーブル・エントリ無効化）の例を
続けるが、最初のタスクが実行されているとき、ページ
無効ビットをセットすることによって、ページ・テーブ
ルのページに関係するエントリを最初に無効化しなけれ
ばならない。次のステップでは、開始側ＰＵのＴＬＢの
ページに関係するエントリを無効化しなければならな
い。更に、開始側プロセッサは他のプロセッサ、レスポ
ンダＰＵに、他のプロセッサにも割当てられたＴＬＢの
ページに関係するエントリを無効化するよう要求しなけ
ればならない。

【００７２】メモリに保存されたアドレス変換テーブル
にアクセスするコマンドが妥当な直列化レベルに達する
には、無効化を行うプロセッサは、トークンを要求し、
トークンを割当てられなければならない。トークンを保
有したプロセッサだけが、アドレス変換テーブルに対す
る修正アクセスを行うことができる。更に、１度にトー
クンを保有できるのは１次のプロセッサだけである。リ
レー・バトンにたとえることのできるトークンを利用す
ることで、共通リソースに対するプロセッサのアクセス
権が規定される。

【００７３】あるページが、あるプロセッサによって無
効化されるとき、プロセッサは、最初のステップ（４０
０）で、無効化トークンが使用可能か（"トークン使用
可能"）どうか確認する。トークンが使用できない場
合、最初のタスクの実行は延期される。トークンが使用
できる場合、次のステップ（４０１）で開始側プロセッ
サがトークンを要求できる。次に、無効化トークンを要
求側プロセッサに割当てることができた（"トークン受
信"）かどうかの問い合わせがなされる（４０２）。そ
うでなければ、途中でトークンの可用性に変化があった
ことになる。そのため、処理はシーケンスの先頭へ返る
（４００）。トークンを割当てることができた（"トー
クン受信"）場合、開始側プロセッサは最初のタスクの
実行を開始することができる。

【００７４】初めに、外部記憶域に転送されるページに
関係したページ・テーブル・エントリが無効化される
（４０３）。次のステップ（４０４）で、開始側ＰＵ
は、依存タスクを実行するコマンドを全てのレスポンダ
ＰＵに送る。これは、いわゆるブロードキャスト強制操
作によって行われる。つまり、このページに関係したＴ
ＬＢエントリを、無効化対象のページのアドレスと共に
無効化するコマンドが、全てのレスポンダＰＵに送ら
れ、レスポンダＰＵのそれぞれの無効化バッファに書込
まれる。従って開始側ＰＵは、全てのレスポンダＰＵ
に、処理すべき内容を通知している。ページに関係した
ＴＬＢエントリの無効化がそれぞれいつ行われるかは、
レスポンダＰＵの問題になる。しかし、レスポンダＰＵ
がそのＴＬＢを変更するのに必要とする情報は全て、無
効化バッファに保存されている。レスポンダＰＵのステ
ータスはここで"コマンド保留"になる。つまり別の依存
タスクが保留されている。

【００７５】ブロードキャスト強制操作が実行される
と、初期タスクの終わりに達し、初期タスクは従って、
ステップ（４０５）で無効化トークンを返すことができ
る。その結果、開始側ＰＵはトークンを保有しなくなる
が、トークンはそれでも、トークンを要求する他のどの
ＰＵにも割当てることはできない。依存タスクはまだレ
スポンダＰＵ側で保留されているからである。

【００７６】ステップ（４０６）は、レスポンダＰＵの
無効化バッファに保存されたコマンドがレスポンダＰＵ
によってどのように処理されるかを示す。そのため、依
存タスク（ページ・テーブルの無効化では、対応するＴ
ＬＢエントリを削除するはずのタスク）は、対応するレ
スポンダＰＵの命令フローで割込み可能点においてルー
プをなし、実行される。レスポンダＰＵの"コマンド保
留"ステータスは、依存タスクの実行が完全に終了する
と消失する。まだ保留されている最後の依存タスクがそ
のプロセッサによって完全に実行されたとき、要求側プ
ロセッサに対するトークンの可用性が再確立される（４
０７）。トークンは再び"使用可能"になる。つまり、要
求側プロセッサにトークンを割当てることができ、従っ
て、ページ・テーブル・エントリの無効化を行う立場に
置くことができる。ステップ（４０７）では、開始側Ｐ
Ｕの開始側タスクが完了し、開始側ＰＵはそこで命令フ
ローの次の命令を処理できる（４０８）。

【００７７】ステップ（４００）で、開始側プロセッサ
は、無効化トークンが使用可能かどうかチェックする。
使用できない場合、つまり、"トークン使用可能"ステー
タスが存在しない場合、開始側プロセッサ、ここでは、
開始側タスクを実行を妨げられているプロセッサは、ス
テップ（４１０）で、他のＰＵからの依存タスクが命令
バッファに保存されているかどうかチェックする。ＩＰ
ＴＥの例では、これはＴＬＢエントリを無効化するコマ
ンドである。この種の依存タスクが実行されるのを待っ
ていない場合、プロセッサは最初の問い合わせに返る
（４００）。最初の問い合わせでトークンの可用性が再
びチェックされる。しかし、他のＰＵからの依存タスク
が命令バッファに保存されていると、この依存タスクは
ステップ（４１１）で実行される。従ってＩＰＴＥの場
合、外部記憶域に転送されるページに対応したＴＬＢエ
ントリが無効化される。無効化に必要なデータは命令バ
ッファに保存される。依存タスクが完了すると、"コマ
ンド保留"信号がステップ（４１２）でリセットされ
る。次に、プロセッサは、無効化トークンが途中で使用
可能になったかどうか再確認するために問い合わせに返
る（４００）。

【００７８】レスポンダＰＵの観点から見た対応する方
式を図７に示す。レスポンダＰＵが、実行されたばかり
の命令の処理を終えると、問い合わせステップ（５０
０）が実行される。ここでは、他のＰＵが、ＴＬＢエン
トリを無効化するコマンドを当該レスポンダＰＵの無効
化バッファにブロードキャスト強制操作によって書込ん
だかどうかチェックされる。書込んでいない場合、レス
ポンダＰＵは命令フローの次の命令の実行に進む（５０
３）。しかし依存タスクが保留されている場合、従って
レスポンダＰＵは"コマンド保留"ステータスにあり、依
存タスクは、ステップ（５０１）で命令バッファに保存
されたコマンドに従って実行される。ページ・テーブル
・エントリの無効化の場合、外部記憶域に転送されるペ
ージに関係したＴＬＢエントリが無効化される。その
後、ステップ（５０２）で、当該レスポンダＰＵで保留
されている依存タスクはなくなったことを示すために"
コマンド保留"信号がリセットされる。次にステップ
（５０３）で命令フローの次の命令が処理される。

【００７９】図８に、直列化に用いられるトークンが取
り得るさまざまな状態の表現を示す。複数のプロセッサ
（６０１）を有するコンピュータ装置（６００）が示し
てある。

【００８０】装置の第１の状態（６０６）で、トークン
（６０３）はどのプロセッサにも割当てられていない
が、使用はできる。つまりプロセッサの１つから要求が
あれば、そのプロセッサに割当てることができる。

【００８１】その場合には、装置は第２の状態（６０
７）にシフトする。ここでトークンはプロセッサの１
つ、この例ではプロセッサ２（６０４）に割当てられ
る。プロセッサ２はこうして、直列処理される特別な命
令を実行する許可を受ける。これらの命令には、開始側
タスクが全てのプロセッサに共通のリソースを変更し、
他のプロセッサで依存タスクを起動する全ての命令が含
まれる。他のプロセッサは、共通リソースのローカル・
コピーを変更する。ＰＵ２の場合、トークンを保有する
ことは、この種の命令の開始側タスクを実行できる権利
を意味する。

【００８２】開始側タスクが完全に実行されると、ＰＵ
２はトークンを返す。これは図５のステップ（４０５）
に対応する。しかし、まだ完全に実行されていない依存
タスクがレスポンダＰＵで保留されている場合は、トー
クンは、返されたときにまだ他のプロセッサから使用で
きない。従ってトークンを管理する装置は第３の状態
（６０８）にシフトする。トークン（６０５）がどのＰ
Ｕ（６０１）にも割当てられていないとき、それでもト
ークンはまだ"トークン使用可能"ステータスにはない。
ＰＵ（６０１）の少なくとも１つはまだその"コマンド
保留"信号をリセットしていないからである。これが生
じるとき、つまり、全てのレスポンダＰＵがそれらに割
当てられた依存タスクを終了しているとき、トークンは
再び開放され、また第１の状態（６０６）に達する。こ
れは図５のステップ（４０７）に対応する。ＰＵ（６０
１）の１つからの要求によりトークン（６０３）をその
ＰＵに割当てることができる。

【００８３】状態１（６０６）、状態２（６０７）、状
態３（６０８）を順次に実行する代わりに、第２の状態
から第１の状態への切り替え（６０９）も可能である。
つまりプロセッサの１つに割当てられているトークン
（６０４）は、返されたとき再び直接使用できるように
なる。このような処理は、１つのタスクでのみ構成され
るコマンドには理にかなっており、従って処理の実行は
依存タスクの処理で構成されない。これらのコマンド
は、ここに示した形で、開始側タスクと依存タスクで構
成される、すでに述べたコマンドで直列化できる。この
手順は、データの保全性を守るためには必要になること
がある。

【００８４】図９は、トークンを管理するための基本回
路を示す。ここで、どのプロセッサｉについても、プロ
セッサｉがトークンを保有している（"トークン受信"）
かどうかを示す信号Ａｉ（７０１）を使用できる。ま
た、どのプロセッサｉについても、まだ完全に実行され
ていない依存タスクがプロセッサｉで実行を保留されて
いる（"コマンド保留"）かどうかを示す信号Ｂｉ（７０
２）を使用できる。これらの信号は全て、ORチェイン
（７００）によって信号Ｃ（７０３）になるよう処理さ
れる。信号Ａｉのいずれか１つがセットされる（つま
り、プロセッサｉがトークンを保有した状態になる）
か、信号Ｂｉの少なくとも１つがセットされる（つま
り、まだ完全に実行されていない依存タスクが保留され
ている）と、信号Ｃ（７０３）もセットされる。この信
号Ｃの意味は"トークン使用不可"である。このようにト
ークンは、信号Ｃがセットされていない場合、つまりト
ークンが"使用可能"な場合にのみ、要求側プロセッサに
割当てることができる。

【００８５】次に、一方ではラインＡ１からＡｎ（７０
１）、ＢｉからＢｎ（７０２）、及びＣ（７０３）の状
態間で、他方では図８に示した状態間で、接続の確立が
試行される。トークンを管理する装置が第１の状態（６
０６）にある場合、これはつまり一方でトークン（６０
３）はどのプロセッサにも割当てられていないことを意
味する。そのため、信号Ａ１からＡｎ（７０１）はどれ
もセットされない。他方、どのプロセッサも"コマンド
保留"ステータスにはならない。トークン（６０３）は
そのとき使用できないからである。よって、ラインＢｉ
からＢｎ（７０２）のどれもまたセットされない。従っ
て、信号Ｃ（７０３）もセットされない。トークン（６
０３）は従って"トークン使用可能"ステータスにある。

【００８６】プロセッサの１つからの要求に応答して、
トークンがこのプロセッサに割当てられた場合は、信号
Ａ１からＡｎ（７０１）の１つがセットされなければな
らない。これは"トークン受信"ステータスに相当する。
従って、信号ラインＢｉからＢｎ（７０２）のステータ
スとは無関係に、信号Ｃ、"トークン使用不可"がセット
される。プロセッサに割当てられたトークン（６０４）
は、他のどのプロセッサにも割当てられなくなる。信号
のこのステータスは装置の第２の状態（６０７）に対応
する。

【００８７】ここで、トークンを保有していたプロセッ
サがトークンを返したが、依存タスクはまだ完全に実行
されていない場合、装置は第３の状態（６０８）にシフ
トする。この時点までセットされていた対応する信号ラ
インＡｉ（"トークン受信"）は、トークンが返るとリセ
ットされる。しかしまだ処理されていない依存タスクが
レスポンダＰＵ側で実行を保留されているので、信号Ｂ
１からＢｎ（"コマンド保留"）のうち少なくとも１つは
セットされ、そのため、信号Ｃ（７０３）もセットされ
る。つまりすでに返されたトークン（６０５）は第３の
状態でまだ"トークン使用不可"ステータスにある。

【００８８】全ての依存タスクが完全に処理されたとき
だけ、Ｂ１からＢｎの全てのライン（"コマンド保留"）
もリセットされる。次に信号Ｃもリセットされ、装置は
再び第１の状態（６０６）に戻り、トークン（６０３）
は再び"使用可能"になる。

【００８９】図１０は、実現の容易さという点では有利
な図９に示した回路の変更例を示す。この例で、プロセ
ッサｉに関係した信号Ａｉ（７０８、"トークン受信"）
とＢｉ（７０９、"コマンド保留"）は、ORゲート（７１
０）によって処理され、全てのプロセッサでＣｉ信号
（７１１）が形成される。前記信号Ｃｉは次に中央のOR
ゲート（７１２）の入力に印加される。この中央ORゲー
トの出力は信号Ｃ（７１３）で、これは"トークン使用
不可"の意味を有する。図９の大きなORゲート（７０
０）をｎ個の小さいORゲート（７１０）と１つの中央OR
ゲート（７１２）に分ける利点は、２つのライン（Ａｉ
とＢｉ）を使用する必要はなくなり、各プロセッサから
中央のORゲート（７１２）に１つ（Ｃｉ）だけでよいこ
とである。他の部分の回路は同じである。

【００９０】図１１は、信号Ａ１乃至Ａｎ、Ｂ１乃至Ｂ
ｎ、及びＣの時系列と共に、初期タスク及び依存タスク
の時系列を表す試みである。更に、この時系列を、図８
に示している装置に可能な状態とリンクする試みもなさ
れている。

【００９１】まず、トークン（８００）は第１の状態
（６０６）にある、つまりトークンは要求に応じてＰＵ
に割当てることができる（"トークン使用可能"）。従っ
て、信号Ａ１乃至Ａｎ、Ｂ１乃至Ｂｎ、またはＣのいず
れもセットされない。プロセッサｉは、ページ・テーブ
ル・エントリの無効化を開始しようとした場合、最初に
トークンを要求しなければならない。トークンは使用で
きるので、プロセッサの要求に応じてプロセッサに割当
てることができる。（８０１）。トークンを受信したＰ
Ｕｉは信号Ａｉ（８０４、"トークン受信"）をセットす
る。

【００９２】ＰＵｉはトークンを保有したので、共通リ
ソースを変更する命令の初期タスク（８０２）を実行す
る権利を有する。トークンはここでＰＵｉに割当てられ
るので、トークン（８０５）を要求する他のＰＵからは
使用できなくなる。この点、で、信号Ｃ（８１１、"ト
ークン使用不可"）も、ＰＵｉがトークンを受け取った
時点からセットされなければならない。初期タスク（８
０２）の実行中に、開始側ＰＵｉは他のＰＵ、すなわち
レスポンダに要求（８０３）を送り、初期タスクに属す
る依存タスク（８０８、８０９）の実行を求める。レス
ポンダＰＵで実行される依存タスクのより詳しい仕様に
関するコマンド及びデータも、開始側ＰＵによってレス
ポンダの命令バッファに書込まれる。ブロードキャスト
強制操作によってレスポンダＰＵの命令バッファにコマ
ンド及びデータが書込まれる瞬間、各レスポンダＰＵ
の"コマンド保留"信号がセットされる。ＰＵｉによって
開始されたブロードキャスト強制操作の結果、信号Ｂｉ
を除く信号Ｂ１乃至Ｂｎ（８１０）が全てセットされ
る。

【００９３】開始側タスク（８０２）が終了すると、開
始側ＰＵはトークンを返す（８０６）。同時に、プロセ
ッサｉによるトークンの保有を示す信号Ａｉがリセット
される（８０４）。しかし、この返却が生じるとき、ト
ークンは、トークンを要求する他のＰＵから使用できる
ようにはならない。依存タスクがまだレスポンダＰＵ側
で保留されているからである（８１０）。装置はここで
第３の状態（６０８）、つまりどのＰＵもトークンを保
有していない状態（８０７）になる。そのためラインＡ
１乃至Ａｎはどれもセットされない。信号Ｃは"トーク
ン使用不可"ステータスのままである（８１１）。レス
ポンダＰＵがその命令フローの割込み可能点に達する
と、実行を保留されている各依存タスク（８０８、８０
９）を挿入し実行できる。レスポンダＰＵの１つ、たと
えばＰＵ１、での依存タスクの実行が終了すると、この
レスポンダに関係する"コマンド保留"信号、この場合は
Ｂ１がリセットされる（８１０）。

【００９４】開始側ＰＵによって開始された最後の依存
タスク（８０９）が完了すると、まだセットされている
最後の"コマンド保留"信号がリセットされる。すでに返
却されているトークンはここで再び使用可能になる。装
置は状態３から状態１（８１２）に変わり、信号Ｃのス
テータスは"トークン使用可能"になる（８１１）。トー
クンはまた、トークンを要求するＰＵに割当てることが
できる。ここで達した状態は、また初期状態（８００）
に対応する。

【００９５】信号Ａ１乃至Ａｎ、Ｂ１乃至Ｂｎ、及びＣ
のステータスの時間に関係した変化を考慮すると、信号
Ｃ（８１１）は実際には、図９及び図１０に描いたよう
に、信号Ａ１乃至Ａｎ及びＢ１乃至ＢｎのORチェイン処
理として表せることが明確になる。

【００９６】図１２は、トークンを管理するための具体
的な回路を示す。ＰＵｉがトークンを要求するとき、信
号ライン（９０１）は"HIGH"にセットされる。信号ライ
ン（９０２）が同時に"HIGH"になると、つまりトークン
が使用可能であれば、両方の入力、従ってANDゲート
（９００）の出力も"HIGH"になる。ANDゲートの出力は
一時的にラッチ（９０３）に保存される。信号ラインＡ
ｉ（９０４）の"HIGH"信号は、トークンが要求の時点で
使用可能だったので要求側ＰＵｉに割当てられたことを
意味する。従って信号Ａｉは、プロセッサｉがトークン
を保有している（この場合は信号がセットされる）かど
うかを示す。

【００９７】信号ラインＡｉ（９０４）及び信号ライン
Ｂｉ（９０５、"コマンド保留"）は、ORゲート（９０
６）の入力を成す。これは図１０のORゲート（７１０）
に対応する。ここで、このORゲート（９０６）の出力は
信号Ｃｉであり、これは一時的にラッチ（９０７）に保
存される。中央ORゲート（９１１）との接続（９０９）
は、図１０の中央ORゲート（７１２）に相当するドライ
バ・モジュール（９０６）を介して確立される。他のプ
ロセッサも全て、それぞれの信号ライン（９０９）に対
応した接続（９１０）を介して中央ORゲート（９１１）
の入力に接続される。中央ORゲート（９１１）の入力
（９０９、９１０）は、ここでは図１０の信号Ｃ１乃至
Ｃｎ（７１１）に相当する。よって、ORゲート（９１
１）の出力は、信号Ａｉ（"トークン受信"）か、でなけ
れば信号Ｂｉ（"コマンド保留"）がいずれかのＰＵでセ
ットされているかどうかを示す。

【００９８】中央ORゲート（９１１）の出力（９１２）
は、図１０の信号ラインＣ（７１３）に相当する。この
信号ラインＣが"HIGH"にセットされた場合、これは、ま
だ完全に実行されていない依存タスクがプロセッサの１
つで保留されている（信号Ｂｉ、"コマンド保留"の１つ
がセットされている）ので、プロセッサのいずれか１つ
がトークンを保有している（信号Ａｉ、"トークン受信"
の１つがセットされている）か、そうでなければトーク
ンはまだブロックされていることを意味する。ここで、
信号ラインＣの"HIGH"ステータスは、トークンを要求す
るＰＵにトークンを割当てられないこと、従ってトーク
ンは使用不可（"トークン使用不可"）であることを意味
する。よってトークンは、信号ラインＣが"ＬＯＷ"にな
ったときだけＰＵに割当てられる。信号Ｃは中央ORゲー
ト（９０１）からプロセッサのそれぞれに位置するレシ
ーバ（９１３）に供給される（９１２）。従って各プロ
セッサ上には信号ラインＣ（９１４、"トークン使用不
可"）が存在し、Ｃのステータスは各ラッチ（９１５）
から測定できる。

【００９９】信号Ｃ（９１４）は、インバータ（９１
６）を介して信号（９０２）に変換され、信号（９０
２）はトークンが使用できる（"トークン使用可能"）そ
のときに"HIGH"になる。信号（９０２）は、トークン
が"トークン使用可能"ステータス（９０２）にあるとき
だけプロセッサｉに割当てられるように、ANDゲート
（９００）の第２の入力に供給される。

【０１００】信号Ｂｉ（９０５、"コマンド保留"）は、
依存タスクがプロセッサｉで保留されているときにセッ
トされる。依存タスクを指定するコマンドは、それを実
行するために必要なデータと共に、ライン（９１７）を
介してブロードキャスト強制操作によって無効化バッフ
ァ（９１８）に書込まれる。ラッチ（９２０）もライン
（９１７）を介してセットされる。このラッチの出力、
信号ラインＢｉ（９０５、"コマンド保留"）は次に"HIG
H"になる。この信号（９０５）は、ＰＵｉが依存タスク
を完全に実行したときにリセットされる。これは、リセ
ット入力に存在する"トークン・ロック解除"信号（９１
９）によってリセットされたラッチ（９２０）によって
行われる。その結果、信号Ｂｉ（９０５、"コマンド保
留"）も再び"LOW"にリセットされる。

【０１０１】初期タスクには、ページ・テーブルのエン
トリを無効化する目的があるが、依存タスクは、このペ
ージに関係するレスポンダＰＵの各ＴＬＢエントリを削
除する役割がある。ＴＬＢエントリを無効化するコマン
ドが無効化バッファ（９１８）に書込まれる場合、"Ｔ
ＬＢエントリ無効化"信号が同時にセットされる。信号
Ｂｉ（９０５）も"HIGH"なので、ＴＬＢエントリが無効
化されるのであればANDゲート（９２２）の出力もセッ
トされる。ＴＬＢエントリの削除は、無効化バッファに
保存されたコマンドに従って行われる。

【０１０２】図１３は、アドレス変換キャッシュの構造
及び機能モードを示す。アドレス変換が正常に行われた
場合、ページの実初期アドレスへの仮想アドレスのセグ
メント索引及びページ索引の割当てが、セグメント・テ
ーブルとページ・テーブルのエントリを使用してメモリ
で確立される。しかし、この変換に必要なプロセッサ・
サイクル数はかなりの値になる。ただし、メモリにある
ページをアドレスするのに必要なアドレス変換が１度行
われていると、仮想アドレスのセグメント索引とページ
索引の、ページの実初期アドレスとの接続をテーブルの
エントリに記録することが可能になる。アドレス変換キ
ャッシュは、この種のテーブルを表し、仮想アドレスの
高次の要素をページの実初期アドレスに割当てるための
ものである。プロセッサがページを初めてアドレスする
場合、アドレス変換は、セグメント・テーブルとページ
・テーブルを使用して行う必要がある。そのため、対応
するエントリがＴＬＢに作成される。これにより仮想ア
ドレスの高次の要素がページの実初期アドレスに割当て
られる。プロセッサは、２回目にこのページにアクセス
しようとすると、最初に、プロセッサに割当てられたＴ
ＬＢを調べ、このページに関係したエントリを探す。こ
の種のエントリをＴＬＢで見つけた場合、明示的アドレ
ス変換の実行は不要になり、かなりの時間が節約され
る。セグメント・テーブルとページ・テーブルを利用し
た明示的アドレス変換は、プロセッサが、プロセッサに
割当てられたＴＬＢのページに関係したエントリを見つ
けなかったときにのみ行われる。

【０１０３】ＴＬＢはアレイ（１００６、１００７、１
００８、１００９）で構成される。ページの実初期アド
レスへの仮想アドレスの高次要素の割当てはＴＬＢのタ
スクである。ＴＬＢの列（１００６）の１２８エントリ
の１つをアドレスするのに、仮想アドレスの高次要素の
ビット１３乃至１９（１００１）が用いられる。各エン
トリは、仮想アドレスに関係し、仮想アドレスのビット
１乃至１２が保存される要素（１０１１）及びページの
実初期アドレス（１０１２）で構成される。

【０１０４】仮想アドレス（１０００）を基準に、仮想
アドレスによって指定されたページに関係したＴＬＢエ
ントリの検索を行う場合、まず、ＴＬＢの１２８のエン
トリの１つが、仮想アドレスのビット１３乃至１９（１
００１）を使用してアドレスされる。このようにして見
つけられたエントリは、仮想アドレスのビット１３乃至
１９と、検索されている仮想アドレスの対応ビットとの
間に一致があり、最近行われたアドレス変換の１つに関
係する。しかし、エントリが実際に検索されたページを
表すかどうかを確認するには、エントリに保存された仮
想アドレスのビット１乃至１２（１０１１）と、検索さ
れている仮想アドレスのビット１乃至１２（１００２）
との比較が必要である。この比較は比較器（１０１５）
で行われる。比較器の出力信号（１０１６）は、比較さ
れたビットが一致するときセットされる。この場合、エ
ントリに保存されたアドレス・ビット１乃至１９（１０
１２）は、検索されているページの実初期アドレスの高
次要素を表す。比較器の出力（１０１６）がセットされ
ると、実アドレスの高次要素（１０１２）は、ANDゲー
ト（１０１７）を介してアドレス・バス（１０２２）に
切り替えることができる。

【０１０５】しかしそれでも、２つの仮想アドレスは、
ビット１３乃至１９が一致し、ビット１乃至１２は異な
る可能性はある。アレイのアドレスはビット１３乃至１
９を介して行われるので、後で変換されたアドレスのエ
ントリは、先に変換されたアドレスを上書きし、その場
合には１つの列（１００６）しか使用できない。従っ
て、ビット１３乃至１９が一致し、ビット１乃至１２は
異なる仮想アドレスのＴＬＢに、共存するエントリを作
成する可能性を得るためには、最初の列に並列な列を追
加する必要がある。図１３は４つの列を示す。ここで
は、"４重関連アドレス変換キャッシュ"という用語を用
いる。最初の列に類似した追加列（１００７、１００
８、１００９）はそれぞれ、仮想アドレスのビット１乃
至１２を比較するための比較器（１０１８）を有する。
仮想アドレスが一致する場合、この比較器の出力信号
（１０１９）は、ANDゲート（１０２０）を介して、ペ
ージの実初期アドレス（１０１４）をアドレス・バス
（１０２２）に切り替える。図１３に示した４重関連Ｔ
ＬＢで、ビット１３乃至１９が一致する仮想アドレスに
関係した４つまでの異なるエントリが、４つの列（１０
０６、１００７、１００８、１００９）に並んで存在す
ることができる。

【０１０６】これら４つの仮想アドレスの１つがＴＬＢ
を使用して変換されるとき、４つの列に関係する４つの
エントリが、仮想アドレスのビット１３乃至１９によっ
て最初に選択される。変換される仮想アドレスに実際に
対応する４つのエントリが、仮想アドレスのビット１乃
至１２と、エントリ内の対応ビットとの比較器により行
われる比較で確認される。比較器によってビットが一致
することが示された列のエントリが、当該エントリのは
ずである。このエントリに保存された実初期アドレスが
ここでANDゲートを介してアドレス・バス（１０２２）
に切り替えられる。

【０１０７】全ての列に共通の共通無効ビットをアドレ
スするのに仮想アドレスのビット１３乃至１９（１００
１）も用いられる。そのため、１２８のラッチで構成さ
れるアレイ（１０１０）に工夫がされる。ＴＬＢエント
リを無効化するため、このエントリに関係した共通無効
ビット（１０２１）がセットされる。しかしセットされ
た共通無効ビットは４つの列全てに関係する。

【０１０８】ｎタプル関連ＴＬＢにより、互いに完全に
独立した最大ｎ回のアドレス変換の結果を同時に保存す
ることができる。従って、途中でアドレス変換がｎ回ま
でしか必要ない命令が実行されるとき、必要なアドレス
変換は全て命令の始めに行うことができる。これは図１
４に示してある。命令（１１００）を実行するために必
要なアドレス変換は全て、命令の始めに実行される（１
１０１）。これらのアドレス変換を実行するために、命
令は、メモリのアドレス変換テーブル、つまりセグメン
ト・テーブルとページ・テーブルにアクセスできなけれ
ばならない。しかしアドレス変換が完了すればこれは必
要なくなる。実行されている全てのアドレス変換につい
て、対応するエントリが、プロセッサに属するＴＬＢで
作成されているからである。従って、命令（１１００）
は、その実行中に指定されたアドレスにアクセスしよう
とした場合、対応するＴＬＢエントリを使用してアクセ
スを実行できる。ある命令に必要なアドレス変換の回数
が、使用可能なＴＬＢの列の個数を超えない場合、必要
なアドレス変換は、実行される命令の始めに行うことが
でき、その後にページ・テーブルにアクセスする必要は
なくなる。これはつまり、この種の命令は、ページ・テ
ーブル・エントリを無効化して直列化する必要がないこ
とを意味する。命令はそのローカルＴＬＢにアクセス
し、後で、ページ・テーブルを使用して変換を行う必要
はないからである。

【０１０９】ある命令の実行中にｎ回を超えるアドレス
変換を行う必要があり、使用可能なＴＬＢの列がｎ個し
かないときは事情は異なる。この例は図１５に示してあ
る。命令の始め（１１０３）には、命令に必要な全ての
アドレス変換を実行することはできない。そのために必
要になるエントリがＴＬＢで使用できないからである。
つまり、再びページ・テーブルにアクセスする後続の変
換（１１０４）は、命令が実行される次の段階で行う必
要があるからである。ページ・テーブルが、命令の実行
時に、第１と第２のアドレス変換の間に変更されるので
あれば、データの保全性の問題が生じる可能性がある。
そのため、ｎ回を超えるアドレス変換を要するこの種の
命令は、ページ・テーブルを変更するコマンド（たとえ
ばページ・テーブル・エントリ無効化）で直列化しなけ
ればならない。

【０１１０】本発明に従って、この直列化は、ｎ回を超
えるアドレス変換を要するコマンドが、実行されるため
にトークンを保有しなければならないという形で達成さ
れる。対応するシーケンスが図１６に示してある。最
初、トークンは第１の状態（１２００）にある。プロセ
ッサｉは、ｎ回を超えるアドレス変換を要するコマンド
を実行する必要がある場合、トークンを要求しなければ
ならない。トークンが"使用可能"なら、プロセッサｉに
割当てることができる（１２０１）。従ってプロセッサ
ｉはコマンド（１２０２）を完全に実行する許可を得
る。プロセッサｉはトークンを保有しているので、信号
Ａｉ（１２０３、"トークン受信"）もセットされる。装
置は"トークン使用不可"ステータス（１２０４）にある
ので、トークンを要求する他のプロセッサにトークンを
割当てることはできない。ＰＵｉで実行されたタスクが
終了すると（１２０２）、コマンドの実行は中断する。
依存タスクは実行されないからである。トークンが、返
されたとき（１２０６）にすぐに再使用できるようにな
る（１２０７）のはそのためである。従って装置は、第
２の状態（６０７）から第１の状態（６０６）に直接シ
フトする。これは図８の矢印（６０９）に対応する。こ
れはまた、図１６の信号図からも読取れる。ＰＵｉで実
行されたタスクが終了すると（１２０２）、信号Ａｉ
（１２０３）もリセットされる。依存タスクは実行され
ないので、信号Ｂ１乃至Ｂｎはいずれもセットされな
い。そのため信号Ｃ（１２０４）、"トークン使用不可"
は、タスクの終了時にすぐにリセットされ、トークンは
再使用できるようになる。

【０１１１】まとめとして、本発明の構成に関して以下
の事項を開示する。

【０１１２】（１）マルチプロセッサ装置で直列処理さ
れる命令の直列化のためのトークンを管理する装置であ
って、プロセッサは、トークンを保有している場合に
は、直列処理される命令の１つのみを実行することがで
き、前記トークンを管理する装置は、前記トークンがい
ずれのプロセッサにも割当てられず、前記トークンを要
求したプロセッサに前記トークンを割当てることができ
る第１の状態と、前記トークンがプロセッサの１つに割
当てられ、前記トークンを要求したプロセッサには前記
トークンを割当てることができない第２の状態と、前記
トークンがいずれのプロセッサにも割当てられず、前記
トークンを要求したプロセッサに前記トークンを割当て
ることができる第３の状態と、を有する、装置。 （２）前記マルチプロセッサ装置はｎ個（ｎは１以上の
整数）のプロセッサで構成され、各プロセッサｉについ
て、プロセッサｉが前記トークンを保有しているときに
セットされる信号Ａｉが使用でき、各プロセッサｉにつ
いて、信号Ｂｉが各プロセッサｉに使用でき、前記信号
Ｂｉは、まだ完全に実行されていないタスクがプロセッ
サｉで保留されているときにセットされ、前記タスク
は、直列処理される命令の１つの実行で直列化されなけ
ればならず、そのために、前記トークンを要求したプロ
セッサに前記トークンを割当てることができず、また、
信号Ｃが使用でき、前記信号Ｃは、マルチプロセッサ装
置全体に共通であり、すでに列挙されている全てのプロ
セッサの信号Ａ１、．．．Ａｎ、Ｂ１、．．．ＢｎのOR
チェインによって生じ、前記トークンを要求側プロセッ
サに割当てることができないときにセットされ、前記ト
ークンを管理する装置の第１の状態は、信号Ａ
１、．．．Ａｎ、Ｂ１、．．．Ｂｎのいずれもセットさ
れず、前記トークンを管理する装置の第２の状態は、信
号Ａ１、．．．Ａｎの１つがセットされ、前記トークン
を管理する装置の第３の状態は、信号Ａ１、．．．Ａｎ
のいずれもセットされず、信号Ｂ１、．．．Ｂｎのうち
少なくとも１つはセットされる、前記（１）記載のトー
クン管理装置。 （３）各プロセッサｉについて、信号Ａｉ、ＢｉのORチ
ェインにより生じる１つの信号Ｃｉが使用でき、前記マ
ルチプロセッサ装置全体に共通な信号Ｃが、全てのプロ
セッサの信号Ｃ１、．．．ＣｎのORチェインにより生じ
る、前記（２）記載のトークン管理装置。 （４）各プロセッサｉについて、プロセッサｉが前記ト
ークンを要求したときにセットされる１つの信号が使用
でき、前記１つの信号は、出力が信号ＡｉであるANDゲ
ートの入力側に、反転した信号Ｃと共に存在する、前記
（２）記載のトークン管理装置。 （５）直列処理される前記命令は、開始側プロセッサで
実行される第１のタスクと、レスポンダ・プロセッサで
実行される依存タスクとで構成され、前記トークンは、
前記開始側プロセッサが前記第１のタスクを実行できる
ように前記開始側プロセッサに割当てなければならず、
前記トークンは、全ての依存タスクが完了するまでは前
記トークンを要求するプロセッサに割当てられない、前
記（１）記載のトークン管理装置。 （６）前記マルチプロセッサ装置の全てのプロセッサに
命令バッファが割当てられ、前記第１のタスクの実行時
に、前記レスポンダ・プロセッサで実行される依存タス
クを指定するコマンドやアドレスを、前記開始側プロセ
ッサが前記レスポンダ・プロセッサの前記命令バッファ
に書込む、前記（５）記載のトークン管理装置。 （７）第１のタスクの実行中に、前記開始側プロセッサ
は、前記レスポンダ・プロセッサで実行される依存タス
クを指定するコマンドやアドレスを、前記レスポンダ・
プロセッサの命令バッファに、ブロードキャスト強制操
作により書込む、前記（５）記載のトークン管理装置。 （８）前記第１のタスクの実行時に、前記開始側プロセ
ッサは、前記レスポンダ・プロセッサの命令バッファに
コマンドやアドレスを書込み、レスポンダ・プロセッサ
ｉの前記命令バッファへの書込みで前記信号Ｂｉもセッ
トされる、前記（５）記載のトークン管理装置。 （９）レスポンダ・プロセッサｉで保留されている前記
依存タスクが完了したとき、前記信号Ｂｉはリセットさ
れる、前記（８）記載のトークン管理装置。 （１０）前記依存タスクが、前記レスポンダ・プロセッ
サの命令フローの割込み可能点で挿入され実行される、
前記（５）記載のトークン管理装置。 （１１）前記マルチプロセッサ装置はメモリを含み、前
記メモリをアドレスするために、仮想アドレスから実ア
ドレスへの変換がアドレス変換テーブルを利用して実行
でき、すでに実行されているアドレス変換の結果は、ア
ドレス変換キャッシュの１つに保存され、前記アドレス
変換キャッシュはそれぞれ前記プロセッサの１つに割当
てられ、直列処理される命令は、ページ・テーブル・エ
ントリを無効化する命令（ＩＰＴＥ）であり、前記開始
側プロセッサは、前記第１のタスクの実行時に前記ペー
ジ・テーブル・エントリを無効化し、前記依存タスクの
実行時に、他のプロセッサは、前記他のプロセッサに割
当てられたアドレス変換キャッシュ内の対応するエント
リを無効化する、前記（５）記載のトークン管理装置。 （１２）前記マルチプロセッサ装置はメモリを含み、前
記メモリをアドレスするために、仮想アドレスから実ア
ドレスへの変換がアドレス変換テーブルを利用して実行
でき、すでに実行されているアドレス変換の結果は、ア
ドレス変換キャッシュに保存され、前記アドレス変換キ
ャッシュはそれぞれ前記プロセッサの１つに割当てら
れ、ページに対する個々のプロセッサのアクセス権を明
示するキー情報が、前記メモリの一部、すなわちキー記
憶域に保存され、直列処理される命令は、前記キー情報
を変更する命令（ＳＳＫＥ）であり、前記開始側プロセ
ッサは、前記第１のタスクの実行時に前記キー記憶域の
前記キー情報を変更し、前記依存タスクの実行時に、前
記他のプロセッサに割当てられたアドレス変換キャッシ
ュの前記キー情報を前記他のプロセッサが変更する、前
記（５）記載のトークン管理装置。 （１３）マルチプロセッサ装置で直列処理される命令を
直列化するプロセスであって、直列処理される命令の１
つの実行は、開始側プロセッサでの第１のタスクの実行
で構成され、前記開始側プロセッサは、トークンを保有
している場合にのみ前記第１のタスクを実行でき、前記
トークンは、使用できる場合にはプロセッサの１つにの
み割当てることができ、前記開始側プロセッサによって
前記トークンが要求されるステップと、前記トークンが
使用できる場合は、前記開始側プロセッサに前記トーク
ンが割当てられるステップと、直列処理される命令が実
行されるステップと、直列処理される命令の第１のタス
クが完了した後に前記トークンが返されることにより、
前記トークンは必ずしも他のプロセッサが使用できるよ
うにする必要のないステップと、直列処理される命令が
完了した後に、前記トークンの可用性が確立されるステ
ップと、を含む、プロセス。 （１４）直列処理される命令を直列化するプロセスであ
って、各プロセッサｉで１つの信号Ａｉが使用でき、前
記トークンが開始側プロセッサｉに割当てられたとき、
信号Ａｉ（トークン受信）がセットされ、前記第１のタ
スクが完了した後に前記トークンが返されてから信号Ａ
ｉがリセットされる、前記（１３）記載のプロセス。 （１５）直列処理される命令を直列化するプロセスであ
って、直列処理される命令の実行は、開始側プロセッサ
での第１のタスクの実行と、レスポンダ・プロセッサで
の依存タスクの実行とで構成され、全ての依存タスクが
終了したとき前記トークンの可用性が確立される、前記
（１３）記載のプロセス。 （１６）直列処理される命令を直列化するプロセスであ
って、各プロセッサｉに１つの信号Ｂｉを使用でき、前
記信号Ｂｉは、依存タスクの実行がプロセッサｉで保留
されている場合にセットされ、前記信号Ｂｉは、前記依
存タスクの実行が完了したときリセットされる、前記
（１５）記載のプロセス。 （１７）直列処理される命令を直列化するプロセスであ
って、前記依存タスクは、前記レスポンダ・プロセッサ
の命令フローの割込み可能点で挿入され実行される、前
記（１５）記載のプロセス。 （１８）直列処理される命令を直列化するプロセスであ
って、前記マルチプロセッサ装置の各プロセッサに命令
バッファが割当てられ、前記第１のタスクの実行時に、
前記レスポンダ・プロセッサで実行される前記依存タス
クを指定するコマンドやアドレスを、前記開始側プロセ
ッサが前記レスポンダ・プロセッサの命令バッファに書
込む、前記（１５）記載のプロセス。 （１９）直列処理される命令を直列化するプロセスであ
って、前記第１のタスクの実行時に、前記レスポンダ・
プロセッサで実行される前記依存タスクを指定するコマ
ンドやアドレスを、前記開始側プロセッサがブロードキ
ャスト強制操作によって前記レスポンダ・プロセッサの
命令バッファに書込む、前記（１５）記載のプロセス。 （２０）直列処理される命令を直列化するプロセスであ
って、前記信号Ｂｉは、前記レスポンダ・プロセッサｉ
の命令バッファへの書込みによってもセットされる、前
記（１８）記載のプロセス。 （２１）直列処理される命令を直列化するプロセスであ
って、前記マルチプロセッサ装置はメモリを含み、前記
メモリをアドレスするために、仮想アドレスから実アド
レスへの変換が、アドレス変換テーブルを利用して実行
でき、すでに実行されているアドレス変換の結果は、ア
ドレス変換キャッシュに保存され、前記アドレス変換キ
ャッシュはそれぞれ前記プロセッサの１つに割当てら
れ、直列処理される命令は、ページ・テーブル・エント
リを無効化する命令（ＩＰＴＥ）であり、前記開始側プ
ロセッサは、前記第１のタスクの実行時に前記ページ・
テーブル・エントリを無効化し、前記依存タスクの実行
時に、他のプロセッサは、前記他のプロセッサに割当て
られたアドレス変換キャッシュ内の対応するエントリを
無効化する、前記（１５）記載のプロセス。 （２２）直列処理される命令を直列化するプロセスであ
って、前記マルチプロセッサ装置はメモリを含み、前記
メモリをアドレスするために、仮想アドレスから実アド
レスへの変換がアドレス変換テーブルを利用して実行で
き、すでに実行されているアドレス変換の結果は、アド
レス変換キャッシュに保存され、前記アドレス変換キャ
ッシュはそれぞれ前記プロセッサの１つに割当てられ、
ページに対する個々のプロセッサのアクセス権を明示す
るキー情報が、前記メモリの一部、すなわちキー記憶域
に保存され、直列処理される命令は、前記キー情報を変
更する命令（ＳＳＫＥ）であり、前記開始側プロセッサ
は、前記第１のタスクの実行時に前記キー記憶域の前記
キー情報を変更し、前記依存タスクの実行時には、前記
他のプロセッサに割当てられたアドレス変換キャッシュ
の前記キー情報を前記他のプロセッサが変更する、前記
（１５）記載のプロセス。 （２３）直列処理される命令を直列化するプロセスであ
って、前記アドレス変換キャッシュはｎ次関連性であ
り、ｎ回を超えるアドレス変換を要する命令は、ページ
・テーブル・エントリを無効化する命令（ＩＰＴＥ）で
直列化される、前記（２１）記載のプロセス。 （２４）直列処理される命令を直列化するプロセスであ
って、プロセッサｉが、ｎ回を超えるアドレス変換を要
する命令を実行するためには、前記トークンをプロセッ
サｉに割当てなければならない、前記（２３）記載のプ
ロセス。

【図面の簡単な説明】

【図１】セグメント・テーブル及びページ・テーブルに
よって仮想アドレスを実アドレスに変換する方法を示す
図である。

【図２】セグメント・テーブル・エントリの構造を示す
図である。

【図３】ページ・テーブル・エントリの構造を示す図で
ある。

【図４】最新技術で実現さるように、マルチプロセッサ
装置のページ・テーブル・エントリを無効化するコマン
ドの時系列を示す図である（静止方法）。

【図５】ページ・テーブル・エントリの無効化の例を使
用して、最初のタスクと依存タスクで構成されるコマン
ドの最初のタスクを実行する、本発明に従ったステップ
のフローチャートを示す図である。

【図６】ページ・テーブル・エントリの無効化の例を使
用して、最初のタスクと依存タスクで構成されるコマン
ドの最初のタスクを実行する、本発明に従ったステップ
のフローチャートを示す図である。

【図７】ページ・テーブル・エントリの無効化の例を使
用して、最初のタスクと依存タスクで構成されるコマン
ドの依存タスクを実行する、本発明に従ったステップの
フローチャートを示す図である。

【図８】本発明に従ってトークンが取り得る３つの状態
を示す図である。

【図９】トークンを管理する基本回路の図である。

【図１０】トークンを管理するのに必要な基本回路を実
現するもう１つの可能性を示す図である。

【図１１】トークンの現在状態に応じた回路の信号のス
テータスを示す図である。

【図１２】トークンを管理する具体的な回路の図であ
る。

【図１３】４重関連アドレス変換キャッシュの動作方法
を示す図である。

【図１４】ｎタプル関連アドレス変換キャッシュを有す
るプロセッサでｎ回より少ないアドレス変換を要する命
令の実行時に守るべき制限を示す図である。

【図１５】ｎ回より多いアドレス変換を要する命令の実
行時に守るべき制限を示す図である。

【図１６】最初の１つのタスクだけで構成された命令の
場合に、トークンの状態に応じた信号のステータスを示
す図である。

【符号の説明】

６００ コンピュータ装置 ６０１ プロセッサ ７００、７１０、７１２、９０６、９１１ ORゲート ８０２ 初期タスク ８０３ 要求 ８０８、８０９ 依存タスク ９００、９２２、１０１７、１０２０ ANDゲート ９０３、９０７、９１５、９２０ ラッチ ９１３ レシーバ ９１６ インバータ ９１８ 無効化バッファ １０００ 仮想アドレス １００６、１００７、１００８、１００９、１０１０
アレイ １０１２、１０１４ 実初期アドレス １０１５、１０１８ 比較器 １０１６、１０１９ 出力信号 １０２１ 共通無効ビット １０２２ アドレス・バス １１００ 命令

───────────────────────────────────────────────────── フロントページの続き (72)発明者 クラウス・ヨルグ・ゲッツラフ ドイツ、ディ−71101 シェーンアイク、 フライゼンヴェグ 26 (72)発明者 アーヴィン・プェッファー ドイツ、ディ−71088 ホルツゲルリンゲ ン、テックストラッセ 12 (72)発明者 ハンス−ヴェルナー・タスト ドイツ、ディ−71093 バイル・イン・シ ョーエンバッハ、ハルトマンストラッセ 66

Claims (24)

【特許請求の範囲】
1. 【請求項１】マルチプロセッサ装置で直列処理される命
   令の直列化のためのトークンを管理する装置であって、 プロセッサは、トークンを保有している場合には、直列
   処理される命令の１つのみを実行することができ、 前記トークンを管理する装置は、 前記トークンがいずれのプロセッサにも割当てられず、
   前記トークンを要求したプロセッサに前記トークンを割
   当てることができる第１の状態と、 前記トークンがプロセッサの１つに割当てられ、前記ト
   ークンを要求したプロセッサには前記トークンを割当て
   ることができない第２の状態と、 前記トークンがいずれのプロセッサにも割当てられず、
   前記トークンを要求したプロセッサに前記トークンを割
   当てることができる第３の状態と、 を有する、装置。
2. 【請求項２】前記マルチプロセッサ装置はｎ個（ｎは１
   以上の整数）のプロセッサで構成され、 各プロセッサｉについて、プロセッサｉが前記トークン
   を保有しているときにセットされる信号Ａｉが使用で
   き、 各プロセッサｉについて、信号Ｂｉが各プロセッサｉに
   使用でき、前記信号Ｂｉは、まだ完全に実行されていな
   いタスクがプロセッサｉで保留されているときにセット
   され、 前記タスクは、直列処理される命令の１つの実行で直列
   化されなければならず、そのために、前記トークンを要
   求したプロセッサに前記トークンを割当てることができ
   ず、 また、信号Ｃが使用でき、前記信号Ｃは、マルチプロセ
   ッサ装置全体に共通であり、すでに列挙されている全て
   のプロセッサの信号Ａ１、．．．Ａｎ、Ｂ１、．．．Ｂ
   ｎのORチェインによって生じ、前記トークンを要求側プ
   ロセッサに割当てることができないときにセットされ、 前記トークンを管理する装置の第１の状態は、信号Ａ
   １、．．．Ａｎ、Ｂ１、．．．Ｂｎのいずれもセットさ
   れず、 前記トークンを管理する装置の第２の状態は、信号Ａ
   １、．．．Ａｎの１つがセットされ、 前記トークンを管理する装置の第３の状態は、信号Ａ
   １、．．．Ａｎのいずれもセットされず、信号Ｂ
   １、．．．Ｂｎのうち少なくとも１つはセットされる、 請求項１記載のトークン管理装置。
3. 【請求項３】各プロセッサｉについて、信号Ａｉ、Ｂｉ
   のORチェインにより生じる１つの信号Ｃｉが使用でき、 前記マルチプロセッサ装置全体に共通な信号Ｃが、全て
   のプロセッサの信号Ｃ１、．．．ＣｎのORチェインによ
   り生じる、 請求項２記載のトークン管理装置。
4. 【請求項４】各プロセッサｉについて、プロセッサｉが
   前記トークンを要求したときにセットされる１つの信号
   が使用でき、 前記１つの信号は、出力が信号ＡｉであるANDゲートの
   入力側に、反転した信号Ｃと共に存在する、 請求項２記載のトークン管理装置。
5. 【請求項５】直列処理される前記命令は、開始側プロセ
   ッサで実行される第１のタスクと、レスポンダ・プロセ
   ッサで実行される依存タスクとで構成され、 前記トークンは、前記開始側プロセッサが前記第１のタ
   スクを実行できるように前記開始側プロセッサに割当て
   なければならず、 前記トークンは、全ての依存タスクが完了するまでは前
   記トークンを要求するプロセッサに割当てられない、 請求項１記載のトークン管理装置。
6. 【請求項６】前記マルチプロセッサ装置の全てのプロセ
   ッサに命令バッファが割当てられ、 前記第１のタスクの実行時に、前記レスポンダ・プロセ
   ッサで実行される依存タスクを指定するコマンドやアド
   レスを、前記開始側プロセッサが前記レスポンダ・プロ
   セッサの前記命令バッファに書込む、 請求項５記載のトークン管理装置。
7. 【請求項７】第１のタスクの実行中に、前記開始側プロ
   セッサは、前記レスポンダ・プロセッサで実行される依
   存タスクを指定するコマンドやアドレスを、前記レスポ
   ンダ・プロセッサの命令バッファに、ブロードキャスト
   強制操作により書込む、 請求項５記載のトークン管理装置。
8. 【請求項８】前記第１のタスクの実行時に、前記開始側
   プロセッサは、前記レスポンダ・プロセッサの命令バッ
   ファにコマンドやアドレスを書込み、 レスポンダ・プロセッサｉの前記命令バッファへの書込
   みで前記信号Ｂｉもセットされる、 請求項５記載のトークン管理装置。
9. 【請求項９】レスポンダ・プロセッサｉで保留されてい
   る前記依存タスクが完了したとき、前記信号Ｂｉはリセ
   ットされる、請求項８記載のトークン管理装置。
10. 【請求項１０】前記依存タスクが、前記レスポンダ・プ
    ロセッサの命令フローの割込み可能点で挿入され実行さ
    れる、請求項５記載のトークン管理装置。
11. 【請求項１１】前記マルチプロセッサ装置はメモリを含
    み、 前記メモリをアドレスするために、仮想アドレスから実
    アドレスへの変換がアドレス変換テーブルを利用して実
    行でき、 すでに実行されているアドレス変換の結果は、アドレス
    変換キャッシュの１つに保存され、前記アドレス変換キ
    ャッシュはそれぞれ前記プロセッサの１つに割当てら
    れ、 直列処理される命令は、ページ・テーブル・エントリを
    無効化する命令（ＩＰＴＥ）であり、 前記開始側プロセッサは、前記第１のタスクの実行時に
    前記ページ・テーブル・エントリを無効化し、 前記依存タスクの実行時に、他のプロセッサは、前記他
    のプロセッサに割当てられたアドレス変換キャッシュ内
    の対応するエントリを無効化する、 請求項５記載のトークン管理装置。
12. 【請求項１２】前記マルチプロセッサ装置はメモリを含
    み、 前記メモリをアドレスするために、仮想アドレスから実
    アドレスへの変換がアドレス変換テーブルを利用して実
    行でき、 すでに実行されているアドレス変換の結果は、アドレス
    変換キャッシュに保存され、前記アドレス変換キャッシ
    ュはそれぞれ前記プロセッサの１つに割当てられ、 ページに対する個々のプロセッサのアクセス権を明示す
    るキー情報が、前記メモリの一部、すなわちキー記憶域
    に保存され、 直列処理される命令は、前記キー情報を変更する命令
    （ＳＳＫＥ）であり、 前記開始側プロセッサは、前記第１のタスクの実行時に
    前記キー記憶域の前記キー情報を変更し、前記依存タス
    クの実行時に、前記他のプロセッサに割当てられたアド
    レス変換キャッシュの前記キー情報を前記他のプロセッ
    サが変更する、 請求項５記載のトークン管理装置。
13. 【請求項１３】マルチプロセッサ装置で直列処理される
    命令を直列化するプロセスであって、 直列処理される命令の１つの実行は、開始側プロセッサ
    での第１のタスクの実行で構成され、 前記開始側プロセッサは、トークンを保有している場合
    にのみ前記第１のタスクを実行でき、 前記トークンは、使用できる場合にはプロセッサの１つ
    にのみ割当てることができ、 前記開始側プロセッサによって前記トークンが要求され
    るステップと、 前記トークンが使用できる場合は、前記開始側プロセッ
    サに前記トークンが割当てられるステップと、 直列処理される命令が実行されるステップと、 直列処理される命令の第１のタスクが完了した後に前記
    トークンが返されることにより、前記トークンは必ずし
    も他のプロセッサが使用できるようにする必要のないス
    テップと、 直列処理される命令が完了した後に、前記トークンの可
    用性が確立されるステップと、 を含む、プロセス。
14. 【請求項１４】直列処理される命令を直列化するプロセ
    スであって、各プロセッサｉで１つの信号Ａｉが使用で
    き、 前記トークンが開始側プロセッサｉに割当てられたと
    き、信号Ａｉ（トークン受信）がセットされ、 前記第１のタスクが完了した後に前記トークンが返され
    てから信号Ａｉがリセットされる、 請求項１３記載のプロセス。
15. 【請求項１５】直列処理される命令を直列化するプロセ
    スであって、 直列処理される命令の実行は、開始側プロセッサでの第
    １のタスクの実行と、レスポンダ・プロセッサでの依存
    タスクの実行とで構成され、 全ての依存タスクが終了したとき前記トークンの可用性
    が確立される、 請求項１３記載のプロセス。
16. 【請求項１６】直列処理される命令を直列化するプロセ
    スであって、 各プロセッサｉに１つの信号Ｂｉを使用でき、 前記信号Ｂｉは、依存タスクの実行がプロセッサｉで保
    留されている場合にセットされ、 前記信号Ｂｉは、前記依存タスクの実行が完了したとき
    リセットされる、 請求項１５記載のプロセス。
17. 【請求項１７】直列処理される命令を直列化するプロセ
    スであって、 前記依存タスクは、前記レスポンダ・プロセッサの命令
    フローの割込み可能点で挿入され実行される、請求項１
    ５記載のプロセス。
18. 【請求項１８】直列処理される命令を直列化するプロセ
    スであって、 前記マルチプロセッサ装置の各プロセッサに命令バッフ
    ァが割当てられ、 前記第１のタスクの実行時に、前記レスポンダ・プロセ
    ッサで実行される前記依存タスクを指定するコマンドや
    アドレスを、前記開始側プロセッサが前記レスポンダ・
    プロセッサの命令バッファに書込む、請求項１５記載の
    プロセス。
19. 【請求項１９】直列処理される命令を直列化するプロセ
    スであって、 前記第１のタスクの実行時に、前記レスポンダ・プロセ
    ッサで実行される前記依存タスクを指定するコマンドや
    アドレスを、前記開始側プロセッサがブロードキャスト
    強制操作によって前記レスポンダ・プロセッサの命令バ
    ッファに書込む、請求項１５記載のプロセス。
20. 【請求項２０】直列処理される命令を直列化するプロセ
    スであって、 前記信号Ｂｉは、前記レスポンダ・プロセッサｉの命令
    バッファへの書込みによってもセットされる、請求項１
    ８記載のプロセス。
21. 【請求項２１】直列処理される命令を直列化するプロセ
    スであって、 前記マルチプロセッサ装置はメモリを含み、 前記メモリをアドレスするために、仮想アドレスから実
    アドレスへの変換が、アドレス変換テーブルを利用して
    実行でき、 すでに実行されているアドレス変換の結果は、アドレス
    変換キャッシュに保存され、前記アドレス変換キャッシ
    ュはそれぞれ前記プロセッサの１つに割当てられ、 直列処理される命令は、ページ・テーブル・エントリを
    無効化する命令（ＩＰＴＥ）であり、 前記開始側プロセッサは、前記第１のタスクの実行時に
    前記ページ・テーブル・エントリを無効化し、 前記依存タスクの実行時に、他のプロセッサは、前記他
    のプロセッサに割当てられたアドレス変換キャッシュ内
    の対応するエントリを無効化する、 請求項１５記載のプロセス。
22. 【請求項２２】直列処理される命令を直列化するプロセ
    スであって、 前記マルチプロセッサ装置はメモリを含み、 前記メモリをアドレスするために、仮想アドレスから実
    アドレスへの変換がアドレス変換テーブルを利用して実
    行でき、 すでに実行されているアドレス変換の結果は、アドレス
    変換キャッシュに保存され、前記アドレス変換キャッシ
    ュはそれぞれ前記プロセッサの１つに割当てられ、 ページに対する個々のプロセッサのアクセス権を明示す
    るキー情報が、前記メモリの一部、すなわちキー記憶域
    に保存され、 直列処理される命令は、前記キー情報を変更する命令
    （ＳＳＫＥ）であり、 前記開始側プロセッサは、前記第１のタスクの実行時に
    前記キー記憶域の前記キー情報を変更し、 前記依存タスクの実行時には、前記他のプロセッサに割
    当てられたアドレス変換キャッシュの前記キー情報を前
    記他のプロセッサが変更する、 請求項１５記載のプロセス。
23. 【請求項２３】直列処理される命令を直列化するプロセ
    スであって、 前記アドレス変換キャッシュはｎ次関連性であり、 ｎ回を超えるアドレス変換を要する命令は、ページ・テ
    ーブル・エントリを無効化する命令（ＩＰＴＥ）で直列
    化される、 請求項２１記載のプロセス。
24. 【請求項２４】直列処理される命令を直列化するプロセ
    スであって、 プロセッサｉが、ｎ回を超えるアドレス変換を要する命
    令を実行するためには、前記トークンをプロセッサｉに
    割当てなければならない、請求項２３記載のプロセス。