JP2000513854A - タグビットのスタック・キャッシュを用いて厳密なガーベッジ・コレクションを支援するための装置及びその方法 - Google Patents

Abstract

(57)【要約】 プログラム・スタック内で参照とプリミティブ値を本質的に区別しないコンピュータ・システムにおいて、厳密なガーベッジ・コレクションを支援するための方法及びその装置はプログラム・スタックと関連して動作するスタック・タグ・キャッシュを使用してプロセス・スタックの全てのエントリにタグ項目を供給する。タグ項目の値は、スタック・エントリが別のメモリ・ロケーションへの参照か又はプリミティブ値か、即ち整数か又は浮動小数点数かを表わす。タグ項目の構成と値はプログラム・スタックの変化に相関する。スタック・タグ・キャッシュはトラップ又はコンテクスト・スイッチの発生時にキャッシュ内容を入れ換えるための装備、並びに意図した命令オペランドの種類でタグ値を冗長検査するための手段を含む。

Description

【発明の詳細な説明】 タグビットのスタック・キャッシュを用いて 厳密なガーベッジ・コレクションを支援するための 装置及びその方法 関連出願への相互参照 本出願は、本出願日と同日に出願され共に譲渡された３件の特許出願の内の１ 件であり、その３件の残りの２件は、発明者Ole Agesen及びDavid Ungarによる 「プログラム・データスタックのライブポインタ・マスクをデルタ符号化するた めの方法及び装置」と題する米国特許出願第ＸＸ／ＸＸＸ,ＸＸＸ号(訳注：出願 番号未送達のため)、及び、発明者Guy L．Steele，Jr.による「スタック内容を サブスタックに分離することで厳密（exact）なガーベッジ・コレクションを支 援するための装置及びその方法」と題する米国特許出願第ＸＸ／ＸＸＸ,ＸＸＸ 号（訳注：出願番号未送達のため）である。上記同時出願中の特許出願の内容は 参照により本願発明に含まれる。 発明の分野 本願発明はデータ処理システムに関し、更に詳しくは、メモリ管理を支援する ための装置及ひその方法に関する。 発明の背景 データ処理システム内で最も重要な資源の１つが実行中のタスクでの利用に直 接使用可能なメモリ量である。そのためメモリの効率的利用とメモリ管理ストラ テジには多くの関心が向けられて来た。メモリ管理で重要な概念は、メモリをタ スクに割り当て、割り当て解 除し、しかるのち再請求する方法である。 メモリの割り当て解除と再請求は実行プログラムによって明示されて制御され るか、未使用のメモリを検索して再請求する別の特殊用途プログラムによって実 行されるが、明示的に割り当て解除されることはなかった。「ガーベッジ・コレ クション(garbage collection)」は、記憶管理とくに自動メモリ再請求を実行す るために使用されるアルゴリズムのクラスを表わすために技術文献や関連技術分 野で用いられる用語である。参照カウント、マーク−スイープ、世代ガーベッジ ・コレクション・アルゴリズムを含め多くの周知のガーベッジ・コレクション・ アルゴリズムが存在する。これらの技術とその他のガーベッジ・コレクション技 術はRichard Jones及びRaphael Lins著「Garbage Collection，Algorithms For Automatic Dynamic Memory Management」John Wiley & Sons出版社、1996年 に詳細に説明されている。残念なことに、ガーベッジ・コレクションについて記 述された技術の多くが、以下に説明するように実装上の問題を惹起する特有の条 件を有している。 本明細書の目的のために「オブジェクト」という言葉は計算機システム（comp uting system）のメモリの中に表現されるデータ構造を表わす。オブジェクトと いう言葉の用法は、「オブジェクト指向」システムでの「オブジェクト」という 言葉の用法とは明らかに違い、オブジェクト指向システムではオブジェクトには 関連「メソッド」、即ち関連するコード部分があり、このコードがオブジェクトの 参照を介して呼び出される。しかし、本願発明はこうしたオブジェクト指向シス テムに応用できるものである。 オブジェクトは「参照」により、又は、データ構造にアクセスするために使用 できる少量の情報によって検索できる。参照を実現す る１つの方法としては、「ポインタ」又は多数ビットの情報を使用する「マシン ・アドレス」を用いるが、他の実現方法も可能である。汎用プログラミング言語 及びその他プログラムされたシステムでは参照を使用してオブジェクトを特定し アクセスすることが多い。こうしたオブジェクトはそれ自体にデータ、例えば整 数又は浮動小数点数への参照、及び、更に別のオブジェクトへの参照を含む。こ のようにして、各々の参照がオブジェクトをポイントし、そのオブジェクトが更 に別のオブジェクトをポイントするといった参照の連鎖が作成できる。 ガーベッジ・コレクション技術は、直接的手段又はポインタ連鎖経由のどちら かで実行プログラムからデータ構造に到達できなくなる時点を決定する。データ 構造に到達できないようになったときに、データ構造が占有しているメモリを再 請求しプログラムから明示的に割り当て解除されていなかったとしても再使用で きる。有効なものにするには、ガーベッジ・コレクション技術は、第１に実行プ ログラムへ直接アクセス可能な参照を認識し、第２に、オブジェクトへの参照が 与えられたらそのオブジェクト内部に含まれる参照を認識してガーベッジ・コレ クタが参照連鎖を一時的にトレースできるようにしなければならない。 「再配置」ガーベッジ・コレクタとして知られているガーベッジ・コレクタの サブクラスは実行プログラムによって未だ到達できるデータ構造を再配置する。 データ構造の再配置はデータ構造のコピーをメモリの別の領域に作り、次にオリ ジナルのデータ構造へ到達可能な参照全部を新しいコピーへの参照に置換する。 オリジナルのデータ構造によって占有されていたメモリが再請求され再使用され る。再配置ガーベッジ・コレクタは実行プログラムによって使用されたメ モリを圧縮することでメモリ断片化を減少させる望ましい特性を有している。 ガーベッジ・コレクション処理中に再配置ガーベッジ・コレクタは参照を変更 するため、参照を認識し、かつガーベッジ・コレクションの目的で変更すること のできない非参照情報、例えばデータと区別することが重要である。結果的に完 全再配置ガーベッジ・コレクタは「厳密(exact)」ガーベッジ・コレクタとして 知られているガーベッジ・コレクション法のサブクラスに属し、メモリ内の任意 の情報部分が参照か又はプリミティブ値かの知識を必要とする。本明細書の目的 のためには、「プリミティブ値」又は「プリミティブ・データ」は参照として機 能しないデータ、例えば整数又は浮動小数点数などと定義する。 厳密ガーベッジ・コレクションの使用を容易にするために、ある種の計算機シ ステムでは全てのメモリ・ロケーションについて「タグ付き」表現を用いてデー タから参照を明確に区別している。こうしたシステムでは、参照と、例えば整数 や浮動小数点数などのプリミティブ・データがメモリ内において常に参照がプリ ミティブ値とは異なるビットパターンを有するような方法で表現される。これは メモリ・ロケーションを保持するビットに加えてタグビットを各々のメモリ・ロ ケーションに含めることによって一般に行なわれるものである。参照値を保持す るメモリ・ロケーションのタグ・ビットはデータ値を保持するメモリ・ロケーシ ョンのタグビットとは必ず異なっている。ＭＩＴ ＬＩＳＰマシンはガーベッジ ・コレクションを用いた最初のアーキテクチャの１つで、明示的にメモリ値にタ グを付けた単一のスタックを有していた。これの後継機でマサチューセッツ州ケ ンブリッジのシンボリクス社（Symbolics，Inc.，Cambridge， ＭＡ）から市販されているシンボリクス3600（Symbolics 3600）も明示的にタグ の付いたメモリ値を使用している。シンボリクス3600は36ビット・ワードを用い 、そのうちの４ビットをタグ情報に永久に割り当てたことにより、単一スタック 内で32ビット参照又は32ビットプリミティブ・データのどちらかに対応すること ができた。このようにすると、36ビット・ワード内の参照のためのビットパター ンはプリミティブ整数又は浮動小数点値のためのビットパターンとは必ず識別す ることができた。 永久に割り当てられたタグビットは、計算データを記憶するために使用するこ とのできるメモリ空間を消費するという欠点を有している。結果的に、多くのコ ンピュータ・システムではメモリ・ワード全体をデータ値の表現に割くことがで きる「タグ無し」データ表現を使用している。こうしたシステムでは、同じビッ トパターンが参照又はプリミティブ値を表わすことがある。その結果、こうした システムでは、参照とプリミティブ値の間の区別は、外部的な考察又は表現、例 えばデータに対して演算すべき命令、又はオブジェクト内部でのデータ位置など で行なわれることが多い。しかし、この区別を行なうために外部的考察を使用す ることは全てのシステムで可能であるというものではなかった。 例えば、Javaプログラミング言語は本来はタグ無しデータ表現を使用するシス テムで用いるように設計されていた。Javaプログラミング言語は、ジェームス・ ゴスリング(James Gosling)、ビル・ジョイ(Bill Joy)、ガイ・スティール(Guy Steele)共著「Java言語仕様("The Java Language Specification")」（Addison -Wesley出版社、1996年）と題する書籍に詳細に記述されている。Java言語は、 ティム・リンドーム(Tim Lindholm)、フランク・ イエリン（Frank Yellin）共著「Java仮想マシン仕様("The Java Virtual Machi ne Specification")」（Addison-Wesley出版社、1996年）に詳細に記述されてい るJava仮想マシン仕様によって指定される特性を備えた計算機システム上で動作 するように設計された。 Java仮想マシン（ＪＶＭ）仕様によれば、32ビット・メモリワードを使用する 計算機システムにおいてローカル変数又はスタック・スロットが32ビット整数、 32ビット浮動小数点数、又は32ビット参照のいずれかを含む。結果として、タグ 付きデータ表現は全ての場合で使用できるものではなくなる(32ビット・コンピ ュータでタグ付きデータ表現を使用するプログラミング言語は典型的には整数の 大きさを30ビットに制限している)。しかし、Java命令を検証してデータから参 照を区別することは、多くの命令が参照とデータに対して無差別に（indiscrimi nately）演算するため、全ての場合において可能であるというものではない。 結果的に、ガーベッジ・コレクションの目的のために、タグ付きデータ表現が 許されておらず参照とデータを全ての場合で区別できるような命令セットを有し ていないシステムにおいて参照とデータを区別する必要がある。 発明の要約 本願発明の原理によれば、タグ情報をプログラム・スタック上に現われる各デ ータ項目に関連付けることによりデータ値から参照値が区別される。タグ情報は スタックが配置されるメモリ領域とは別のメモリ領域に記憶される。プログラム 動作中に、タグ情報は各スタック項目に関連付けられプリミティブ・データ値か ら参照値を識 別するために使用できる。 １つの実施態様によれば、関連付けは、タグ情報メモリ領域からロードされス タック内に見られるデータ項目の少なくとも幾つかの項目についてのタグ情報を 記憶している小さなハードウェアであるスタック・タグキャッシュ・メモリを用 いて実行される。次にスタック上の参照値はキャッシュメモリからタグ情報を取 り出してスタック項目に関連したタグ情報を検証することによりプリミティブ・ データ値から区別することができる。 本願発明の１つの観点ではプログラム・スタック内の多ビット項目のセットの 各々について追加の（extra）１ビットを記憶するキャッシュメモリを含むスタ ック・タグキャッシュ機構の使用を想定している。プロセッサがスタック上の多 ビット・ワードにアクセスするときは常に、本願発明のスタック・タグキャッシ ュ機構がスタック・ワードのメモリアドレスを検証して２種類の動作の内の１種 類の動作を行う。タグ情報がキャッシュメモリ内に記憶されている項目セット内 にスタック・ワードがあることをメモリアドレスが示す場合、本願発明の機構は スタック項目に関連する追加ビットの現在値を供給し、これによってスタック項 目が参照か又はプリミティブ値かの区別ができる。本願発明の機構ではキャッシ ュメモリをこの時点で更新しても良い。これ以外に、本願発明のキャッシュ機構 はプロセッサに信号を出してスタック項目のメモリアドレスがタグ情報の記憶さ れているセット内にはないことを表わすトラップ条件をプロセッサに生成させる ことができる。これに応じて、プロセッサは主メモリの選択されたメモリ・ロケ ーションからこの関連付けられたタグ情報を取り出し、このタグ情報をスタック ・タグキャッシュ・メモリ内に記憶することができる。 別の観点では、本願発明のスタック・タグキャッシュ機構は更に複数ビット・ ワードを有するタグキャッシュ・メモリの内容をロードし記憶するためのデータ ・パスを提供し、これによってトラップ処理を容易にし、並びに複数制御スレッ ド間でのコンテクスト・スイッチを行う過程でのタグキャッシュ・メモリの内容 の保存及び再生（restore）を促進する。 本願発明の更に別の観点では、データ・エントリのプログラム・スタックを有 するコンピュータ・システムで使用するためのスタック・タグキャッシュは、複 数のタグ項目を記憶するように構成したアドレス可能なメモリを含み、データ・ エントリに関連した各々のタグ項目は関連付けられたデータ・エントリが参照又 はプリミティブ値を含むかどうか識別する値を有する。スタック・タグキャッシ ュは更に、スタック・エントリに関連したタグ項目がアドレス可能なメモリ内に 存在しているかどうかを決定するように構成された比較論理と、アドレス可能な メモリに供給されたアドレスに応答する出力論理であって、アドレスによって選 択されたタグ項目の値を提示するように構成された出力論理も含む。アドレス可 能メモリ内に記憶されていないタグビットの値を書き込むように構成された論理 、及び少なくとも２個のタグ項目値の同時アドレシングと同時提示を可能にする 論理が含まれることもある。 本願発明の更なる観点では、第１のメモリ領域内に記憶されたスタック・エン トリ内に配置されたデータが参照か又はプリミティブ値かを決定するための方法 は、第２のメモリ領域内に複数のタグ項目を保持するステップであって、この各 々のタグ項目がスタック・エントリに関連付けられていることを特徴とするステ ップと、選択したスタック・エントリに対応するタグ項目の１つを取り出すステ ップと、 対応するスタック・エントリ内に含まれるデータが参照又はプリミティブ値かど うかを取り出したタグ項目の値から決定するステップとを含む。 本願発明の更に別の観点では、プロセッサとメモリを有するコンピュータ・シ ステムは更にプロセッサに応答して複数のタグ項目を記憶するように構成された スタック・タグキャッシュを含む。各タグ項目はスタック・エントリ内のデータ に関連付けられスタック・エントリ内に含まれるデータが参照又はプリミティブ 値かどうかを表わす値を有する。スタック・タグキャッシュは更に選択したスタ ック・エントリに対応して取り出されたタグ項目がキャッシュ内に常駐している かどうかを決定するように構成された論理と、メモリアドレスに応答するロジッ クであって、スタック・タグキャッシュに適用されたアドレスによって選択され たタグ項目の値をキャッシュ出力に提示するように構成された論理とを含む。 本願発明の更なる観点では、プロセッサとメモリとを有するコンピュータ・シ ステムで使用するコンピュータ・プログラム製品はコンピュータ・プログラムコ ードが実現されるメモリであって、コンピュータで使用可能なメモリを含み、こ のプログラムコードは複数のタグ項目をメモリ内に保持するためのプログラムコ ードであって、この各タグ項目がスタック・エントリ内のデータに関連付けられ ていることを特徴とするプログラムコードと、選択したスタック・エントリに対 応する複数のタグ項目のうちの１つを取り出すためのプログラムコードと、メモ リアドレスに応答するプログラムコードであって、選択したスタック・エントリ に関連付けられたタグ項目の値を提示するためのプログラムコードとを含む。 図面の簡単な説明 本願発明の上記及びその他の特徴、目的、利点は添付の図面との関連で以下の 説明を参照することによってより良く理解されよう。図面において、 図１Ａは、本願発明で使用するのに適したコンピュータ・アーキテクチャを示 す摸式的ブロック図である。 図１Ｂは、従来のプログラム・データスタックの概念図である。 図１Ｃは、本願発明で使用するのに適した、フレームを含むプログラム・スタ ックの概念図である。 図２は、本願発明の第１の実施態様によるスタック・タグキャッシュの摸式的 ブロック図である。 図３は、本願発明の第２の実施態様によるスタック・タグキャッシュの摸式的 ブロック図である。 図４は、スタック項目読み込み動作中にスタック・タグ情報を取り出すための 方法を実現する例示的ルーチンのフローチャートである。 図５、はスタック項目書き込み動作中にスタック・タグ情報を取り出すための 方法を実現する例示的ルーチンのフローチャートである。 発明を実施するための最良の形態 本願発明は厳密ガーベッジ・コレクション・アルゴリズムの要件に対処する方 法並びに装置を提供する。更に詳しくは、本願発明は参照とプリミティブ値が同 じサイズとなるようにデータ表現の使用を構造が奨励しているコンピュータ・ア ーキテクチャでタグ無しデータ表現が名目上使用されているデータスタック内で 参照を非参照から区別する要件に対処する。 例示の実施態様では、Javaプログラミング言語とJava仮想マシ ン仕様を実装しているコンピュータ・システムを参照して説明しているが、本願 発明は同様の要件を有する他のコンピュータ・システムにも等しく応用可能であ る。更に詳しくは、本願発明はオブジェクト指向プログラミング・システム及び 非オブジェクト指向プログラミング・システムの両方に実装できる。更に、本願 発明は単一スレッドと単一のプログラム・スタックを有するシステム、並びに複 数の同時的プログラム・スタックを有するマルチスレッド・システムでも実装で きる。本願発明を詳細に説明する前に、本願発明を使用するのに適したコンピュ ータ・システム、プログラム・スタック構造、Java仮想マシン環境に準拠したプ ログラミング命令の説明を、読者の利便のために提供する。 コンピュータ・システムとプログラム・スタック・アーキテクチャ 図１Ａは、本願発明を実装できるコンピュータ・システムのシステム・アーキ テクチャを示す。図１に例示したコンピュータ・システムは説明のためだけのも のである。説明では特定のコンピュータ・システム、例えばＩＢＭ ＰＳ／２パ ーソナル・コンピュータなどを説明する際に共通に使用される用語を参照するが 、説明並びに概念はネットワーク・コンピュータ、ワークステーション、及びメ インフレーム・コンピュータなど図１Ａと異なるアーキテクチャを有するその他 のコンピュータ・システムにも等しく適用される。 コンピュータ・システム100は、従来のマイクロプロセッサで実現し得る中央 演算処理ユニット（ＣＰＵ）105、一時的な情報記憶のためのランダム・アクセ ス・メモリ（ＲＡＭ）110、永久的な情報記憶のためのリード・オンリー・メモ リ（ＲＯＭ）115を含む。メモリ・制御装置120はＲＡＭ110を制御するために提 供される。 バス130はコンピュータ・システム100の構成要素を相互接続する。バス・コン トローラ125はバス130を制御するために提供される。割り込みコントローラ135 はシステム構成要素からの各種割り込み信号を受信し処理するために使用される 。 大容量記憶はディスケット142、ＣＤ−ＲＯＭ147又はハードディスクドライブ 装置152により提供される。データ及びソフトウェアはリムーバブル媒体例えば ディスケット142及びＣＤ−ＲＯＭ147経由でコンピュータ・システム100と交換 できる。ディスケット142はディスケット・ドライブ装置141に挿入でき、当該装 置がコントローラ140によりバス130に接続される。同様に、ＣＤ−ＲＯＭ147は ＣＤ−ＲＯＭドライブ装置146に挿入でき、当該装置はコントローラ145によりバ ス130へ接続される。ハードディスク152は固定ディスクドライブ装置1５1の一部 であり、当該装置はコントローラ150によりバス130へ接続される。 コンピュータ・システム100へのユーザ入力は多数の装置により提供される。 例えば、キーボード156とマウス157はコントローラ155によりバス130へ接続され る。オーディオ変換器196はマイクロホン及びスピーカの両方として機能するこ とも可能であり、図示してあるようにオーディオ・コントローラ197によりバス1 30へ接続される。。他の入力装置、例えばペン及び／又はタブロイドなども必要 に応じてバス130と適当なコントローラ及びソフトウェアで接続できることは当 業者には明らかなはずである。ＤＭＡコントローラ160はシステムＲＡＭ110への 直接メモリアクセスを実行するために提供される。視覚的表示はビデオ・コント ローラ165によって生成され、当該コントローラがビデオディスプレイ170を制御 する。コンピュータ・システム100はバス191及びネットワーク195によ って模式的に図示されているローカル・エリア・ネットワーク（ＬＡＮ）又は広 域ネットワーク（ＷＡＮ）へシステムを相互接続できるようにする通信アダプタ 190も含む。 コンピュータ・システム100の動作はシングルスレッド化又はマルチスレッド 化されているオペレーティング・システム・ソフトウェアによって一般に制御さ れ調節されている。オペレーティング・システムはシステム資源の割り当てを制 御したり、特にプロセスのスケジューリング、メモリ管理、ネットワーク及びＩ ／Ｏサービスなどのタスクを実行する。 従来のコンピュータ・システムにおいて、進行中の計算はプロシージャ・コー ルをサポートするためと中間計算量例えば参照やプリミティブ値を保持するため の「スタック」を使用する。スタックは内部メモリの未使用部分を含み、これが 一時的記憶に必要とされるレジスタ数を減らしプログラム内で必要とされるステ ップ数を減少させる一方でプッシュ・ダウン型記憶を容易にする。図１Ｂはシス テム・メモリに常駐する従来のプログラム・スタックの構造を概念的に示してい る。メモリ内の３箇所の重要な位置でスタックを定義する：スタック・ベース、 スタックポインタ即ち現在のスタックの最上部、及びスタック・リミットである 。典型的にはこれらの位置は３個のマシン・レジスタに保持されているメモリア ドレスによって識別される。 データをスタック上にプッシュすべき場合、スタックポインタに最も近い未使 用のメモリ・ロケーションに格納される。スタックポインタはスタック・リミッ トに向かって前進する。スタックポインタがスタック・リミットに近付きすぎた 場合、スタックは「オーバフローした」といわれ、例えばエラー信号を出すか又 はスタックを保持するために更にメモリを割り当てるといった、何らかの特別な 動作を取る必要がある。 データをスタックからポップすべき場合、スタックポインタはスタック・ベー スに向かって後退し、データを保持しているメモリを又未使用メモリと見なせる ようにする。スタックポインタがスタック・ベースに近付きすぎると、スタック は「アンダーフローした」と呼ばれ、例えばエラー信号を出すか又は更にスタッ ク・データを保持しているメモリの別の領域にスイッチするなど何らかの特別な 動作を取る必要がある。実装によっては、スタック・ベースはスタック・リミッ トより高いメモリアドレスに常駐することもある。 Javaプログラミング言語においては、スタック上のデータは図１Ｃに図示した ように「フレーム」にグループ化されている。各フレームはサブルーチン呼び出 し又はメソッド呼び出しの１つのレベルに対応する。どのフレームも３つの領域 に分割される：パラメータ、ローカル変数、評価テンポラリである。パラメータ はスタック・ベースに最も近く評価テンポラリはスタック・ベースから最も遠い 。これら３つの領域の各々はそのフレームに対して実行される特定のサブルーチ ンによっては空になることがある。サブルーチンを実行すると、評価テンポラリ の個数はスタックに項目をプッシュするか又はポップすると変化するが、パラメ ータとローカル変数の個数は変化しないのが典型である。その結果、異なるフレ ームが異なるサイズを有することができる。 パラメータとローカル変数のアドレシングを単純化するには、典型的にはマシ ン・レジスタに保持される「フレームポインタ」である追加アドレスで現在のス タック・フレーム内のパラメータ領域の開始を表示する。命令は現在のフレーム ポインタからのオフセットを指定することにより現在のフレーム内でパラメータ 又はローカル 変数にアクセスできる。 サブルーチン又はメソッドを呼び出すべき場合、評価スタック最上部にある幾 つかの項目は新規フレーム内部のパラメータになる。現在のフレームポインタは プログラム・カウンタと一緒にスタック上に保存される。次にフレームポインタ に新規フレームのアドレスがロードされ、一方でプログラム・カウンタにサブル ーチンのコードのアドレスがロードされる。 ある種の計算機システムは「マルチスレッド化」されており、この場合、多数 進行する計算プロセスが単一のアドレス空間又はオブジェクトの単一プールを共 有している。こうしたプロセスのセットは１つ以上のスタック又は各プロセスに １つのスタックを有するのが代表的である。こうした多数のプロセスは単一の記 憶管理ストラテジによって操作することができる。 Javaプログラミング命令 Javaプログラミング言語をサポートするコンピュータ・システムにおいて、ス タック上で演算する命令の多くはデータを参照データとするかプリミティブ・デ ータとするかを指定する。例えば、「iadd」命令はスタックから２個のオペラン ドをポップし、この場合のオペランドは整数でなければならない。これらの和が 整数としてスタックにプッシュされる。同様に「aaload」命令は２項目をスタッ クからポップし、この場合の項目は参照と整数インデックスとからなる配列への 参照でなければならない。この命令は配列からの参照をインデックス値で示され たように選択し、選択した参照のコピーをスタックにプッシュする。 逆に、Java仮想マシンの幾つかの命令はオペランドが参照又はプ リミティブ・データに演算するかどうかを指定しておらず、無差別にどちらの種 類のデータでも動作することを想定している。例えば、「pop」命令はスタック から１つの項目をポップし、参照又は32ビット・プリミティブ値のどちらかを破 棄するために使用することがある。「dup」命令はスタック最上部にこの項目の コピーをプッシュし、参照又は32ビット・プリミティブ値を複製するために使用 できる。「dup2」命令は１個の64ビット・プリミティブ値、２個の32ビット・プ リミティブ値、２個の参照、又は１個の参照と１個の32ビット・プリミティブ値 をいずれかの順番で複製するために使用できる。 こうした「無差別な」使用を許容しているJava仮想マシン命令の完全なリスト は次の通りである： 全ての命令記述において： ｘ1は命令が実行を開始した時にスタックの一番上にある項目を表わす。 ｘ2は命令が実行を開始した時にスタックの一番上から２番目の項目を表わ す。 ｘ3はスタックの一番上から３番目にある項目を表わす。 x4は命令が実行を開始した時に参照スタックの一番上から４番目にある項目 を表わす。 Pop ｘ1をスタックからポップして破棄する。 Pop２ ｘ1をスタックからポップして破棄し、次にｘ2をスタックからポップして破 棄する。 dup ｘ1のコピーをスタックにプッシュする。 dup２ ｘ2のコピーをスタックにプッシュし、次にｘ1のコピーをスタックにプッシュ する。 dup＿ｘ1 ｘ1をスタックからポップし、 ｘ2をスタックからポップし、 ｘ1のコピーをスタックにプッシュし、 ｘ2のコピーをスタックにプッシュし、 ｘ1のコピーをもう１つスタックにプッシュする。 dup＿ｘ2 ｘ1をスタックからポップし、 ｘ2をスタックからポップし、 ｘ3をスタックからポップし、 ｘ1のコピーをスタックにプッシュし、 ｘ2のコピーをスタックにプッシュし、 ｘ1のコピーをもう１つスタックにプッシュする。 dup２＿ｘ1 ｘ1をスタックからポップし、 ｘ2をスタックからポップし、 ｘ3をスタックからポップし、 ｘ2のコピーをスタックにプッシュし、 ｘ1のコピーをスタックにプッシュし、 ｘ3のコピーをスタックにプッシュし、 ｘ2のコピーをもう１つスタックにプッシュし、 ｘ1のコピーをもう１つスタックにプッシュする。 dup２＿ｘ2 ｘ1をスタックからポップし、 ｘ2をスタックからポップし、 ｘ3をスタックからポップし、 ｘ4をスタックからポップし、 ｘ2のコピーをスタックにプッシュし、 ｘ1のコピーをスタックにプッシュし、 ｘ4のコピーをスタックにプッシュし、 ｘ3のコピーをスタックにプッシュし、 ｘ2のコピーをもう１つスタックにプッシュし、 ｘ1のコピーをもう１つスタックにプッシュする。 swap ｘ1をスタックからポップし、 ｘ2をスタックからポップし、 ｘ1のコピーをスタックにプッシュし、 ｘ2のコピーをスタックにプッシュする。 Java仮想マシンの多くの実装において、命令の実際の実装は作業量を減少する ように最適化できる。例えば、「swap」演算は最上部スタック項目２つを読み込 んで各々の値を別のスタック・スロットに書き込み、実際にスタックポインタの 調整は行なわない。更に、Java仮想マシンの幾つかの実装ではいわゆる「クイッ ク」命令を使用している。クイック命令はインターネット上に送信されるような Javaでコンパイルしたプログラムでは有効でない追加命令コードである。しかし 、ＪＶＭ実装は命令が実行される最初の時にリンクを解決し、更に命令をもっと 高速な「クイック」バリアント（variant）で置 き換えることによって、例えば別のクラスで定義されているフィールドの名前な どシンボリック・リンクの解決を必要とする幾つかの遅い命令を処理することが 時々ある。時にはこうしたクイック・バリアントか参照とプリミティブ・データ の両方を処理するために使用される。こうしたクイック命令には次のようなもの が含まれる： getfield＿quick getfield＿quick＿w getstatic＿quick ldc＿quick ldc＿w＿quick putfield＿quick＿w putstatic＿quick これらのクイック命令は「無差別」であり参照データ又はプリミティブ・デー タに対して使用できる。クイック命令は無差別でない遅い命令に置き換えられる 。残念ながら、その特定の命令が必ず参照又はデータを転送するかどうかを表わ し遅い命令又はそのオペランドに関連していた情報は、遅い命令が無差別であら かじめ解決されているがそれらは等価なクイック命令によって置き換えられる時 に失われる。 Java仮想マシンの実装は「ベリファイア(verifier)」と呼ばれるプロセスを含 み、これの目的の１つは、ロードされた時に全てのメソッドのコードを検証して 命令シーケンスが何らかの制約にしたがうことを保証することである。更に詳し く説明すると、ベリファイアは、静的に、コードが実行される前に、スタック上 の項目が参照であることを命令が想定している場合に、その特定の命令のあらゆ る実行で参照であるように保証し、又スタック上の項目がプリミテ ィブ・データであることを命令が想定している場合に、その特定の命令のあらゆ る実行で項目が参照であるように保証する。 検証処理の一部として、無差別な使用を許容する標準（非クイック）ＪＶＭ命 令の特定の発生時に、即ちpop、pop2、dup、dup2、dup＿ｘ1、dup＿ｘ2、dup2＿ ｘ1、dup2＿x2、又は、swap命令で、ベリファイアはその命令の何らかの特定の スタックオペランドが必ず参照であるか絶対に参照でないかのどちらかを決定で きる。 Java仮想マシンはフレームのベースに対して計算したアドレスを介してアクセ スされアドレスが代表的にはフレーム・ポインタ・レジスタに保持されているロ ーカル変数に対して演算する次のようなバイトコード命令を提供する： iload iload＿0 iload＿1 iload＿2 iload＿3 fload fload＿0 fload＿1 fload＿2 fload＿3 lload lload＿0 lload＿1 lload＿2 lload＿3 dload dload＿0 dload＿1 dload＿2 dload＿3 aload aload＿0 aload＿1 aload＿2 aload＿3 istore istore＿0 istore＿1 istore＿2 istore＿3 fstore fstorｅ＿0 fstore＿1 fstore＿2 fstore＿3 lstore lstore＿0 lstore＿1 lstore＿2 lstore＿3 dstore dstore＿0 dstore＿1 dstore＿2 dstore＿3 astore astore＿0 astore＿1 astore＿2 astore＿3 名前に下線（アンダースコア）と整数Ｋか含まれている上記に示したバイトコ ード命令はフレームのベースからオフセットＫにあるローカル変数にアクセスす る。他のバイトコード命令は１つ又は２つ 以上の追加命令バイトにオフセットを符号化することによってもっと広い範囲の オフセットが許容できる。 名前に「load」が含まれている上記に示したバイトコード命令はスタック上に ローカル変数の内容のコピーをプッシュする。名前に「store」が含まれている バイトコード命令はスタックから値をポップしてポップしたデータをローカル変 数に記憶する。名前が「ａ」で始まるバイトコード命令は参照値と組み合わせて 使用される。それ以外のバイトコード命令はプリミティブ値、即ち整数(integer )、浮動小数点数(float)、ロング(long)、ダブル（double）と組み合わせて使用 される。 スタック・タグキャッシュ 本願発明は、各スタック・ワードについて追加タグビットを含め、通常のメモ リ・ワードの幅を越えて各スタック・ワードの幅を効果的に増加させることによ り、スタック内の参照とプリミティブ値の間の区別の問題に対処する。追加タグ ビットはデータを含むプログラム・スタックと相関する方法でプッシュ、ポップ 、検証、更新し得るような疑似スタック方式で記憶される。この第２又は疑似ス タックはタグキャッシュとしてハードウェア内に実現できる。 本願発明の第１の実施態様によるスタック・タグキャッシュ200が図２に図示 してある。スタック・タグ200はマルチポート・ランダム・アクセス・メモリ（ ＲＡＭ）202とサポート論理204〜224を含む。例示の実施態様において、ＲＡＭ2 02は64×32ビットで、第１と第２の読み出しポート、１つの書き込みポート、及 び「フロースルー」機能を有し、同じワードが同一クロックサイクルで読み出し と書き込み両方行なわれる場合にＲＡＭ202から読み出された値はそのクロ ックサイクルでＲＡＭ202に書き込まれる値と同じであるようにする。 タグスタック・ローリミット・レジスタ204Ａとタグスタック・ハイリミット ・レジスタ204Ｂは各々長さ30ビットで、タグスタックの各々ローリミット及び ハイリミットを記憶するために使用する。中央演算処理ユニットはタグスタック ・リミット・レジスタの内容を当業者には理解される方法で読み出し書き込みす るための適当なコマンドを実行する。 ４個の30ビット・コンパレータ206Ａ〜Ｄは各々が１ビットの結果を発生する 、即ち、第１の入力（図２ては左手の入力）が第２の入力（図２では右手の入力 ）より大きい場合には論理値１、それ以外には論理値０を用いてＲＡＭ202の読 み出しポートに供給されたアドレスと、ハイ・タグスタック・リミット及びロー ・タグスタック・リミットとを比較する。更に詳しく説明すると、タグスタック ・ローリミット・レジスタ204Ａの出力がコンパレータ206Ａと206Ｃの第１の入 力に供給される。タグスタック・ハイリミット・レジスタ204Ｂの出力はコンパ レータ206Ｂと206Ｄの第２の入力に供給される。第１のメモリアドレスr1＿addr はコンパレータ206Ａの第２の入力とコンパレータ206Ｂの第１の入力に供給され る。同様に、第２のメモリアドレスr2＿addrはコンパレータ206Cの第２の入力と コンパレータ206Dの第１の入力に供給される。コンパレータ206Ａと206Bの出力 は２入力ＯＲゲート222Ａに供給され、その出力か論理値１の場合には第１のメ モリアドレスr1＿addrのトラップ・リミットを表わす。同様に、コンパレータ20 6Ｃと206Ｄの出力は２入力ＯＲゲート222Ｂに供給され、その出力が論理値１の 場合には第２のメモリアドレスr2＿addrのトラップ・リミットを表わす。 第２の読み込みアドレスの11ビット部分（r2＿addr 12：２）は 11ビット・ラッチ212へ供給される。ラッチ212の11ビット出力は書き込みアドレ スとしてＲＡＭ202に供給される６ビット部分（ｗ＿ addr 12：７）とデコー ダ224へ供給される５ビット部分（ｗ＿addr ６：２）に分割される。第１の１ ビット32対１マルチプレクサ214Ａは入力として、図示したように、ＲＡＭ202の 第１の読み出しポートの３２ビット出力と、５ビット選択信号として第１の読み 出しアドレスの５ビット部分（r1＿addr ６：２）を受信する。第２の１ビット 32対１マルチプレクサ214Ｂは、図示したように、入力としてＲＡＭ202の第２の 読み出しポートの32ビット出力と、５ビット選択信号として第２のアドレス（r2 ＿addr ６：２）の５ビット部分を受信する。第１と第２の読み出しアドレスの ６ビット部分（r1＿addr 12：７、r2＿addr 12：７）も同様に図示したように ＲＡＭ202へ供給される。マルチプレクサ214Ａの１ビット出力は第１のタグビッ トとして供用し、一方で、第２のマルチプレクサ214Ｂの１ビット出力は第２の タグビットとして供用し、これら両方がＣＰＵ105によって読み取り可能である 。マルチプレクサ214Ａ〜Ｂの１ビット出力は１ビット４対１マルチプレクサ220 にも供給され、図示したようにこのマルチプレクサは入力に論理値０と論理値１ も受信する。マルチプレクサ220は図示してあるようにこれの制御入力に２ビッ ト書き込みビット選択信号（ｗ＿bit＿select １：０）を受信する。 32ビット・ラッチ208Ａは図示してあるように32ビット書き込みデータ信号（ ｗ＿data 31：０）を受信する。ラッチ208Ａの出力は32ビット２対１マルチプ レクサ216の第１の入力に供給される。マルチプレクサ216の32ビット出力は図示 したようにＲＡＭ202の書き込みポートへ供給される。マルチプレクサ216は１ビ ット・ラッチ210Ｂから受信した１ビット制御信号によって制御される。ラッ チ210Ｂへの入力は図示したように１ビット書き込みデータ選択信号（ｗ data select）である。ラッチ210Ａの出力は図示したようにＲＡＭ202へ供給される 。 第２の32ビット・ラッチ208Ｂは入力として、図示したようにRAM202の第２の 読み出しポートの32ビット出力（r＿data ３1：０）を受信する。ラッチ208Ｂ の出力は図示したように１ビット対１マルチプレクサ218Ａ〜ｎの各々の第１の 入力に供給される。各マルチプレクサ218Ａ〜ｎの第２の入力は１ビット・ラッ チ210Ｃから受信し、これの入力は図示したようにマルチプレクサ220の出力から 受信する。各マルチプレクサ218Ａ〜ｎの出力は図示したようにマルチプレクサ2 16の第２の32ビット入力に供給される。各マルチプレクサ218への制御信号は図 示したようにデコーダ224の32本の出力線のうちの１本により供給される。 図示した実施態様において、多ビット信号のビットは「リトルエンディアン（ little-endian）」順序で番号が付けてある。例えば、32ビット信号はビット31 ：０（31から０まで、０を含む）として記述でき、ここで、多ビット信号を２進 数として見なす場合にはビット31が最上位ビット、又ビット０が最下位ビットで ある。 スタック・タグキャッシュ200の動作について以下で説明する。全てのクロッ クサイクルで、ＣＰＵ105は多くとも２つのスタック・ロケーションを読み込み 多くとも１つのスタック・ロケーションに書き込むものと仮定する。更に、ＣＰ Ｕ105が１つのスタック・ロケーションに書き込み２つのスタック・ロケーショ ンも読み込む場合、読み込まれるスタック・ロケーションの一方は書き込まれる スタック・ロケーションと同じでなければならない。 いずれか任意のクロックサイクルで、ＣＰＵ105はスタック・タグ キャッシュ200に２つのスタック・ロケーションのメモリアドレスr1＿addrとr2 ＿addrを提示する。これらのアドレスはバイトアドレスされるものと仮定するが 、ワード整列されるべきである。従って、アドレスのビット31：２だけをスタッ ク・タグキャッシュ200に提示すれば良い。書き込まれる又は読み書きされるス タック・ロケーションのアドレスはr2＿addrとして提示できる。アドレスr1＿ad drは読み込まれはするが書き込まれないスタック・ロケーションのために使用で きる。 ２つのアドレスは各々タグスタック・ローリミット・レジスタ204Ａ及びタグ スタック・ハイリミット・レジスタ204Ｂの内容と比較される。どちらかのアド レスがローリミットより小さいかハイリミットより大きい場合、入力としてその アドレスを有している４個の30ビット・コンパレータ206Ａ〜Ｄのうちの１つが 出力として論理値１を生成し、これに対応する２入力ＯＲゲート222が結果とし て論理値１を発生する、即ちr1＿addrに対してlimit＿trap＿1又r2＿addrに対し てlimit＿trap＿2を発生する。limit＿trap＿1又はlimit＿trap＿2のどちらかが 論理値１の場合、スタック・タグキャッシュ200はこのクロックサイクルで意図 した演算をうまく完了できない。ＣＰＵ105は現在の命令の実行を終了させてト ラップを実行することにより応答し、トラップハンドラ・プロセスが詳細には後 述するトラップ・シナリオにアドレスできるようにする。 ２つのアドレスr1＿addrとr2＿addrはＲＡＭ202から２つのタグビットを抽出 するためにも使用される。各アドレスについて、６ビット（ビット１２：７）が ＲＡＭ202の読み出しポートの一方の読み出しアドレスとして用いられ、１個の3 2ビット・ワードを読み出して３２対１マルチプレクサ214Ａ〜Ｂの一方に供給す る。別の５ビット （ビット６：２）は同じマルチプレクサの制御セレクタとして使用され、これに よって１ビットを選択する。このように選択した２つのビットはr1＿addrによっ て選択されたtag＿bit＿1信号及びr2＿addrによって選択されたtag＿bit＿2信号 としてＣＰＵ105で利用できるようになる。ＣＰＵ105は２つのデータスタック・ ロケーションから読み出した32ビット・ワード２個を受信し、tag＿bit＿1及びt ag＿bit＿２ビットは各々ＣＰＵ105によって32ビット・データワードに付加され ２つの33ビット量を発生する。33番目のビットの値は32ビット・スタック項目が 参照か又はプリミティブ値のどちらであるかを表わす。好適実施態様において、 33番目のビットが論理値１だと参照を表わし、33番目のビットが論理値０だとプ リミティブ値を表わす。 図示した実施態様において、スタック・タグキャッシュ200は全ての32ビット ・スタック項目に１追加ビットを提供する。 r1＿addrビット12：７によって選択されＲＡＭ202から読み出された32ビット ・ワード全体も又r＿data 31：０としてＣＰＵ105で利用できるようになるので 、これによってＲＡＭ202から１つ又は２つ以上のワードを迅速に読み出すため のパスを提供する。 同じクロックサイクルで、ＣＰＵ105はスタック・タグキャッシュ200に情報を 書き込む適当な信号を生成する。実際の書き込み動作は次のクロックサイクルで 行なわれるので、前述したラッチのセットを用いて、現在のクロックサイクルか ら次のクロックサイクルまでデータ及び制御信号を保持する。ｗ＿enable信号は ワードをＲＡＭ202に書き込もうとする場合に論理値１、書き込むべきワードが ない場合に論理値０である。 後述の信号は書き込み動作に関連する。r2＿addrビット12：２が 11ビット・ラッチ212にラッチされると、r2＿addrのビット12：７を用いて、32 ビット・ワードが書き込まれるＲＡＭ202内部のロケーションにアドレスする。r 2＿addrのビット６：２は１対32デコーダ224に供給される。デコーダ224の32個 の出力は32個の１ビット・マルチプレクサ218Ａ〜Ｎを制御するために使用する 。これら32個の制御信号のうち、厳密に１つだけが論理値１で、残りは論理値０ になる。 ＣＰＵ105はｗ＿data信号を含む32ビット・データワードを供給する。 ｗ＿data＿select信号が論理値１の場合、ｗ＿data信号としてＣＰＵ105から 供給された32ビット・ワードはＲＡＭ202に書き込まれる。ｗ＿data＿select信 号が論理値０の場合、ＲＡＭ202へ書き込まれるデータは32個の１ビット・マル チプレクサ218Ａ〜ｎによって発生した32ビット「更新値」である。r2＿ addr ビット1２：７によって指定されたＲＡＭ202ロケーションから読み出されたワー ドはラッチ208Ｂと32個のマルチプレクサ218Ａ〜ｎの第１の入力へ供給され、こ の場合、各マルチプレクサへ１ビットづつ供給される。４対１マルチプレクサ22 0の出力である「更新ビット」は32個の２対１マルチプレクサ218Ａ〜ｎの全部の 第２の入力へ供給される。その結果、「更新値」はr＿dataに等しくなり厳密に その内のビットの１つが「更新ビット」に置き換えられている。このようにする と32ビット・ワードのリード・モディファイ・ライト方式（読み取り・変更・書 き込み方式）で、個々のビットまでアドレスできるかのようにＲＡＭ202を使用 できる。 「更新ビット」の値は２ビットのｗ＿bit＿select信号によって制御される。 ｗ＿bit＿select信号が２進値00を有する場合、更新ビ ットはtag＿bit＿1に等しい。ｗ＿bit＿selectが２進値01を有する場合、更新ビ ットはtag＿bit＿2に等しい。ｗ＿bit＿selectが２進値10を有する場合、更新ビ ットは論理値０に等しい。最後に、ｗ＿bit＿selectが２進値11を有する場合、 更新ビットは論理値１に等しい。 ＣＰＵ105はlimit＿trap＿1信号とlimit＿trap＿2信号を任意のクロックサイ クルで使用して同じクロックサイクルのｗ＿enable信号をゲートできる。このよ うにすると、トラップが発生した場合ＲＡＭ202への書き込みが抑圧される。 例示の実施態様において、ＣＰＵ105がマイクロプロセッサで実現されている 場合、本明細書で説明したスタック・タグキャッシュのハードウェアはマイクロ プロセッサとして同じ集積回路パッケージ内に実装できる。スタック最上部にあ る又はその付近の項目を含むハードウェアとしてのスタック・データキャッシュ との関連でスタック・タグキャッシュ200を使用することができる。こうしたハ ードウェアとしてのスタック・データキャッシュの構成と動作は当業者の範囲内 である。スタック・タグキャッシュのエントリ数はスタック・データキャッシュ のエントリ数と等しいか異なることがある。 別の実施態様において、スタック・データキャッシュ並びにスタック・タグキ ャッシュはシステム・メモリに常駐できる。こうしたソフトウェアとしてのスタ ック・タグキャッシュの実装はスタック・タグキャッシュ200の前述の説明と本 文書の残りの説明に鑑みて当業者の範囲内であろう。 前述の説明から、本願発明がスタック内に記憶された参照とプリミティブ値に タグ付き表現を使用し、一方でヒープのオブジェクト内にある参照及びプリミテ ィブ値にはタグ無し表現を使用する方法 と装置を提供することが読者には理解されよう。スタック・ワードに関連したタ グビットはＣＰＵ105がスタックに項目をプッシュする命令を実行するか、又は スタックのアクティブ領域内にすでにロケーションを更新している際にＣＰＵ10 5により自動更新される。 本願発明において、データスタックは必ずしもメモリの連続した領域を占有し ないものと想定している。その代わり、データスタックには連続メモリの初期量 が割り当てられる。スタックがオーバフローした場合、連続メモリの追加領域を 割り当てる。単一スタックを表わす２つ又は３つ以上のこうした連続領域をリス ト状に連鎖できる。現在のスタックのアンダーフローが発生すると現在のスタッ ク領域が放棄され後にリサイクルされる。スタックポインタとフレームポインタ はリストの直前の領域を参照するように調節される。メモリの新規な連続領域が スタックに割り当てられる時には、領域は少なくともスタック上にプッシュされ ようとするフレームを保持するのに充分な大きさでなければならない。ＣＰＵ10 5が１つのスレッド実行から別のスレッドへコンテクスト・スイッチを行なう場 合、ＣＰＵはスタックポインタ・レジスタ、フレーム・ポインタ・レジスタ、ス タック・データリミット・レジスタ、スタック・データの現在の内容を主メモリ に保存するのが典型的である。次にＣＰＵ105は新しい値をスタックポインタ、 フレームポインタ、及びスタックリミット・レジスタにロードする。本願発明に よれば、ＣＰＵ105はタグスタック・リミット・レジスタ204Ａ〜ＢとＲＡＭ202 の内容も主メモリに保存する。ＣＰＵ105はその後でリミット・レジスタ204Ａ〜 Ｂへ新規の値をロードする。 スタック・タグキャッシュ200の設計はＲＡＭ202の内容を保存し易くする。更 に詳しく説明すると、ＣＰＵ105はr2＿addrとして アドレスを提示し32ビット信号（r＿data 31：０）としてデータを読み取るこ とによりＲＡＭ202から一度に32ビットを読み出すことかできる。ＣＰＵ105はr2 ＿addrとしてアドレス、ｗ＿enable、及びｗ＿data＿selectの値、及び３２ビッ トのデータ（ｗ＿data 31：１）を提示することによってＲＡＭ202へ一度に32 ビット書き込むことができる。一度にＲＡＭへ32ビットを読み書きできる能力で トラップの高速処理が容易になる一方、トラップの頻度を最小限に抑さえ高速な コンテクスト・スイッチングを可能にする。 タグビットを保持するのに必要な主メモリ110の量はトラップ又はコンテクス ト・スイッチの時点で割り当てることができ、スタック・データを保持するため に使用されているメモリの付近に配置できる。Java仮想マシンの典型的な実装に おいて、プログラム・スタックはチャンクとしてまとまった状態（chunk）で割 り当てられている。１つのまとまりには５ワードのブックキーピング情報と2000 ワードの実際のスタック・データを含むことができるが数値2000は任意である。 本願発明の好適実施態様において、スタックは２キロワード（2048ワード）のま とまりに割り当てられる。これらのワードのうちの５個はブックキーピング情報 として使用され、62ワードはスタック・タグビットを保持する（1984タグビット を提供する）ために予約され1981ワードが実際のスタック・データを保持するた めに使用できる。タグビットのうちの３個は使用されないことに注意する。この 実装により、常にスタックフレームのタグビット全部を2048ビットのスタック・ タグキャッシュＲＡＭに適合させることができる。スタックのサイズに割り当て られる実際のメモリのサイズは設計要件によって変化し得ることは当業者には明 らかであろう。例えば、本願発明は32×32ビットのＲＡＭと4096ワードの主メモ リ・スタッ ク・チャンクサイズ又は両方に実装できる。しかし、こうした実施態様において は、必ずスタック・タグキャッシュＲＡＭにスタックフレームのタグビット全部 を適合させることはできない。 選択したスタック・エントリのアドレスが所定のリミットの外にあって希望す るタグ項目がスタック・タグキャッシュ200にないことを表わしていることでト ラップが発生する場合、トラップ処理プロシージャは主メモリからキャッシュメ モリへタグ情報をコピーすることを含む。特定のシステムによってキャッシュ全 体が置き換えられるか、又はキャッシュの一部が置き換えられる。キャッシュ「 ミス」を誘発したスタック・タグキャッシュ200のリストアはスタック・タグキ ャッシュ200の前述の説明と本文書の残りの説明に鑑みて当業者の範囲内である 。いずれの場合にも、希望するタグ・エントリを含む最少量の情報を主メモリか ら取り出してキャッシュメモリに記憶する必要がある。 本願発明の前述の説明から、単一のスタックを一緒に増大縮小する２つの協調 スタックとして表現できることが理解されよう。32ビット項目がデータスタック 上へ論理的にプッシュされる時には、１ビット・タグがスタック・タグキャッシ ュへ論理的にプッシュされる。32ビット項目をデータスタック内から取り出す場 合又はその中で更新する場合には、これに対応する１ビット・タグをスタック・ タグキャッシュ内から取り出すか又はその中で更新する。 スタック・タグキャッシュの代替実装 本願発明の第２の実施態様によるスタック・タグキャッシュ300が図３に図示 してある。スタック・タグキャッシュ300の実装と共通するスタック・タグキャ ッシュ200の全ての構成要素は図３におい て同様の番号が付けてあり、こうした構成要素の説明及び動作は本明細書ですで に述べた通りである。スタック・タグキャッシュ200とスタック・タグキャッシ ュ300の違いは、ＲＡＭ202、リミット・レジスタ204Ａ〜Ｂ、コンパレータ206Ａ 〜Ｄが完全結合キャッシュ302（fully associative cache 302）に置き換え られていることである。本実施態様において、キャッシュ302は４線式マルチポ ート完全結合キャッシュを含み、各々の栓は25ビットのアドレスと32ビットのデ ータ、即ちスタック・エントリのタグ情報で構成される。キャッシュ302は２個 の読み出しポートと１個の書き込みポート、及び「フロースルー」機能を有して おり同じ32ビット・データワード即ち同じ関連アドレスを有するデータワードに ついて同じクロックサイクルで読み込みと書き込みの両方が行なわれる場合、キ ャッシュ302から読み出した値はそのクロックサイクルでキャッシュ302に書き込 まれる値と同じである。読み込みアドレスがキャッシュ302に提示されると、こ れに対応する「ヒット」信号を発生し、キャッシュ線のどれかが現在そのアドレ スを含む場合には論理値１である。 更に、30ビット・ラッチ312をキャッシュ200の11ビット・ラッチ212の変わり にスタック・タグキャッシュ300で使用する。ラッチ312の構造と機能はラッチ21 2を参照して前述したのと同様であるが、図３に図示してあるようにラッチ312は r2＿addr信号（r2＿addr 31：２）の30ビットを記憶しこれらのビットのうち25 ビット（ｗ＿addr31：７）をキャッシュ302へ、又５ビット（ｗ＿addr ６：２ ）をデコーダ224へ提供する点で異なっている。更に、２入力ＮＯＴゲート314Ａ と314Ｂの対を各々cache＿hit＿1及びcache＿hit＿2線へ接続する。キャッシュ3 02がゲート314Ａへ論 理値０の値を提示するとlimit＿trap＿1の値が論理値１にされ、このことはキャ ッシュ・ミスが発生したのでトラップ・ルーチンを実行しなければならないこと を表わす。同様に、キャッシュ302がゲート314Ｂへ論理値０の値を提示すると、 limit＿trap＿2の値が論理値１にされ、キャッシュの「ミス入力」か発生したの でトラップ・ルーチンを実行しなければならないことを表わす。 スタック・タグキャッシュ300の動作と機能はスタック・タグキャッシュ200の それと同様で、主要な相違点はキャッシュ・ミスの管理、キャッシュ302のロー ディング及びアンローディングである。前述のスタック・タグキャッシュ200を 参照して提供した説明に鑑みると、こうした動作上の相違点は当業者の範囲内で ありこれ以上詳細には説明しない。 典型的な命令実行 本願発明の典型的実施態様の動作を更に示すため、Java仮想マシン命令セット に準拠した命令を実装しているマイクロプロセッサ又は中央演算処理ユニットを 想定して以下の例を提供する。最大限効率的な命令タイミングの図示の目的で、 実施態様ではスタック・データは２個の読み出しポートと１個の書き込みポート を有するマルチポート・キャッシュメモリにも保持されるものと仮定するが、他 のデータスタック実装も使用する。 iadd命令 「iadd」命令は２つのオペランドをスタックからポップするが、どちらのオペ ランドも整数でなければならない。次に、これらの和が整数としてスタックにプ ッシュされる。マイクロプロセッサは２個の スタック・オペランドを読み込み、これらを加算してその和をスタックに書き戻 す。スタックポインタもスタックから１項目ポップするように（２回のポップと １回のプッシュで結局１回ポップしたことになる）調整される。スタック・デー タキャッシュのスタック・データにより、命令は１クロックサイクルで全て実行 できる。 同様に、ＣＰＵは２個のスタック項目のメモリアドレスを生成する。スタック 最上部にある項目のアドレスはr1＿addrとしてＲＡＭ202に提示され、一方でス タック最上部より下にある項目のアドレスはr2＿addrとしてＲＡＭ202に提示さ れる。スタック・タグキャッシュ200はリミット比較を行なって２つのスタック ・ロケーションに対応するタグビットが論理的にＲＡＭ202内部にあることを保 証する。r1＿addrで示されたスタック・ロケーションのタグビットがキャッシュ 内に存在しない場合、limit＿trap＿1信号は論理値１の値を有することになる。 r2＿addrで表わされるスタック・ロケーションのタグビットがキャッシュ内に存 在しない場合は、limit＿trap＿2信号が論理値１の値となる。 ＲＡＭ202と２個の32対１マルチプレクサ214Ａ〜Ｂが一緒に２つのスタック・ ロケーションに対応するタグビットを取り出して、タグビットをtag＿bit＿1及 びtag＿bit＿2としてＣＰＵ105に提示する。ＣＰＵ105は冗長エラー検査にタグ ビットを使用する。エラー検査は、適当なタグビットによって示されるスタック ・データの性質とスタック・データに関連する命令との比較を内包する。例えば 、プリミティブ値だけで演算する命令は参照としてタグビットによって示されて いるオペランドで実行することができない。このようにすると、タグビットは厳 密ガーベッジ・コレクション技術を支援するだけでなく、スタック・エントリ内 部のデータの有効性の検証に も役立つ。iadd命令の例に戻ると、どちらかのビットが論理値１の場合、スタッ ク・ロケーションは参照を含みiadd命令の実行は誤りである。よってＣＰＵ105 は命令実行を中断する。ＣＰＵ105はtag＿bit＿1、tag＿bit＿2、limit＿trap＿ 1、limit＿trap＿2のいずれかが論理値１に等しい場合トラップを実行する。Ｃ ＰＵ105はトラップを行なわない場合にｗ＿enable信号に論理値１の値を提示す る。ＣＰＵ105はｗ＿data＿selectに論理値０、ｗ＿bit＿selectに２進値１０を 提示する。結果的に、トラップが発生しない場合、その結果についてスタック項 目に対応するタグビットは論理値０となるように更新され、結果がプリミティブ 値であることを表わす。冗長エラー検査を用いてオペランドかプリミティブ値で ない場合にトラップを強行する場合この動作は冗長である。エラー検査が実行さ れないような実装において、この更新は冗長ではない。 aaload命令 「aaload」命令はスタックから２項目をポップする。一番上が整数インデック スで、その下の項目が参照配列への参照である。この命令は、インデックス値で 表わされる通りに配列からの参照を選択し選択した参照のコピーをスタックにプ ッシュする。スタックポインタもスタックから１項目をポップしたように調節さ れる、即ち２回のポップと１回のプッシュで結局１回ポップしたことになる。こ の命令は主メモリからの読み込みを行なうので、複数クロックサイクルを必要と する。 最初のクロックサイクルの間に、ＣＰＵ105は２つのスタック項目のメモリア ドレスを生成する。スタック最上部にある項目のアドレスはr1＿addrとして提示 され、スタック最上部の下にある項目の アドレスはr2＿addrとして提示される。スタック・タグキャッシュ200はリミッ ト比較を実行して２つのスタック・ロケーションに対応するビットが論理的にキ ャッシュ内に存在することを保証する。r1＿addrで表わされるスタック・ロケー ションのタグビットがキャッシュ内に存在しない場合、limit＿trap＿1信号に論 理値１が生成される。r2＿addrで表わされたスタック・ロケーションのビットが キャッシュ内に存在しない場合、limit＿trap＿2信号に論理値１が生成される。 ＲＡＭ202と２個の32対１マルチプレクサ214Ａ〜Ｂが一緒に２つのスタック・ ロケーションに対応するタグビットを取り出して、タグビットをtag＿bit＿1及 びtag＿bit＿2としてＣＰＵ105に提示する。ＣＰＵ105は関連する命令による冗 長エラー検査にタグビットを使用する。tag＿bit＿1が論理値１の場合、tag＿bi t＿2が論理値０の場合、又はlimit＿trap＿1又はlimit＿trap＿2のどちらかが論 理値１の場合にはトラップを行なうべきである。このクロックサイクルで、ＣＰ Ｕ105はｗ＿enable信号に論理値０を提示する。 選択した配列要素が主メモリから到着した後、ＣＰＵ105は後続のクロックサ イクルでスタック結果のアドレス、即ち当初は最上部から２番目であったスタッ ク項目と同じアドレスをもう一度r2＿addrとして提示する。ＣＰＵ105はｗ＿ena ble信号について論理値１の値、ｗ＿data＿selectについて論理値０の値、ｗ＿b it＿selectについて２進値11を提示する。結果的に、結果のスタック項目に対応 するタグビットは論理値１に更新され、このことが結果が参照値であることを表 わす。冗長エラー検査を用いて第１のオペランド即ち最上部から２番目のスタッ ク・エントリが参照値でない場合にトラップを強行する場合こうした更新は冗長 である。エラー検査が行なわれな い実施態様においてこうした更新は冗長ではない。 iaload命令 「iaload」命令の実行は、配列オペランドが整数値の配列であり、スタックに プッシュされる結果が参照ではなく整数値である点を除けば「aaload」命令と全 ての面で同一である。更に、直前に説明したクロックサイクルにおいて、aaload 命令への参照内で、ＣＰＵ105はｗ＿bit＿select信号に２進値10を提示する。結 果的に、命令結果についてスタック項目に相当するタグビットは論理値０となる ように更新され、このことにより、結果がプリミティブ値であることを表わす。 この更新は論理値１から論理値０へタグビットを変更するので冗長ではない。 dup命令 「dup」命令はスタックの一番上の項目のコピーをスタックにプッシュする。 ＣＰＵ105は一番上のスタック項目を読み出してそのすぐ上のスタック・スロッ トに書き込む。スタック・オーバフローが発生した場合には、スタックポインタ も上向きに調節されトラップが行なわれる。 ＣＰＵ105は２つのスタック・スロットのメモリアドレスを生成する。スタッ クの一番上にある項目のアドレスはr1＿addrとして提示されすぐ上のスロットの アドレス、つまり新しく一番上の項目になる項目のアドレスがr2＿addrとして提 示される。スタック・タグキャッシュ200はリミット比較を実行して２つのスタ ック・ロケーションに対応するタグビットが論理的にＲＡＭ202内部に存在する ことを確認する。r1＿addrで表わされるスタック・ロケーションのタ グビットがキャッシュ内部に存在しない場合、limit＿trap＿1信号に論理値１が 生成される。r2＿addrで示されたスタック・ロケーションのビットがキャッシュ 内部に存在しない場合、limit＿trap＿2信号に論理値１が生成される。limit＿t rap＿1又はlimit＿trap＿２が論理値１の場合トラップが行なわれる。 ＲＡＭ202と32対１マルチプレクサ214Ａ〜Ｂが一緒に２つのスタック・ロケー ションに対応するタグビットを取り出して、タグビットをtag＿bit＿1及びtag＿ bit＿2としてＣＰＵ105に提示する。「dup」命令を処理する場合に、ＣＰＵ105 がtag＿bit＿2信号を使用することはない。 トラップを行わない場合には、ＣＰＵ105はｗ＿enable信号に対して、論理値 １の値を提示する。ＣＰＵ105はｗ＿data＿selectに論理値０の値ｗ＿bit＿sele ctに２進値00を提示する。結果的に、トラップが発生しない場合、命令結果につ いてのスタック項目に対応するタグビットがtag＿bit＿1のコピーとなるように 更新される。従って、新規に複製されたスタック項目がもともと一番上であった スタック項目と同じタグビット値を担う。 swap命令 「sｗap」命令は一番上のスタック項目を一番上から２番目のスタック項目で 交換する。スタックポインタの実質的調節は行なわれない。スタック・データが スタック・データキャッシュに保持されるシステムでは、この命令は２クロック サイクルで実行できる。 最初のクロックサイクルで、CPU105は２つのスタック・スロットのメモリアド レスを生成する。スタックの一番上の項目のアドレスはr1＿addrとしてＲＡＭ20 2に提示されスタックの最上部のすぐ 下のスロットのアドレスがr2＿addrとして提示される。スタック・タグキャッシ ュ200はリミット比較を実行して２つのスタック・ロケーションに対応するタグ ビットが論理的にＲＡＭ202内部に存在することを確認する。r1＿addrで指定さ れたスタック・ロケーションのタグビットがＲＡＭ202内部に存在しない場合、l imit＿trap＿１信号に論理値１が発生する。r2＿addrで指定されたスタック・ロ ケーションのタグビットがＲＡＭ202内部に存在しない場合にはlimit＿trap＿2 信号に論理値１が発生する。limit＿trap＿1又はlimit＿trap＿2のどちらかが論 理値１の場合トラップが行なわれる。ＲＡＭ202と32対１マルチプレクサ214Ａ〜 Ｂが一緒に２つのスタック・ロケーションに対応するタグビットを取り出して、 タグビットをtag＿bit＿1及びtag＿bit＿2としてＣＰＵ105に提示する。ＣＰＵ1 05はトラップが行なわれない場合にはｗ＿enable信号に論理値１を提示する。Ｃ ＰＵ105は又ｗ＿data＿select信号に論理値０の値、ｗ＿bit＿selectに２進値00 を提示する。結果的に、トラップが発生しない場合、最上部から２番目のスタッ ク項目に対応するタグビットはtag＿bit＿１のコピーとなるように更新される。 ＣＰＵ105はtag＿bit＿２として提示された値も保存する。 第２のクロックサイクルで、ＣＰＵ105は一番上のスタック・スロットのメモ リアドレスを生成してr2＿addrとして提示する。ＣＰＵ105はｗ＿enable信号に 論理値1,又ｗ＿data＿select信号に論理値０を提示する。ＣＰＵ105は直前のク ロックサイクルから保存したtag＿bit＿２の値が論理値０の場合にはｗ＿bit＿s elect信号に２進値10を提示する。ＣＰＵ105は保存したtag＿bit＿2の値が論理 値１の場合ｗ＿bit＿selectに２進値11を提示する。このようにすると、一番上 のスタック項目に対応するタグビットは保存してあるtag＿ bit＿２のコピーとなるように更新される。実質的な効果は２つのスタック項目 について２つのタグビットを交換したことである。 dup及びswap命令について、１クロックサイクルでＲＡＭ202内部の１つのビッ ト・ロケーションから別のビット・ロケーションへタグビットの値を直接コピー でき、書き込み動作が実際にはラッチ遅延のため後続のクロックサイクルで完了 することが容易に理解される。これ以外に、１つのクロックサイクルでタグビッ トを読み出して後のクロックサイクルでＲＡＭ202の別のロケーションへの値に 保存するためにＣＰＵ105が保存しても良い。 上記の説明によると、どのようにすれば命令dup2、dup＿ｘ1、dup＿ｘ2、dup ２＿ｘ1、dup２＿ｘ2にも同様に必要とされるタグビット値のコピーを実行でき るかが容易に理解されるであろうから、これらの詳細な説明は本明細書では簡潔 にするため提供しない。 iload命令 「iload」命令はフレームポインタからのオフセットとしてアドレスが計算さ れる整数スタック項目のコピーをスタックにプッシュする。アドレスは整数メソ ッド・パラメータ又はローカル変数の値を取り出すために使用される。 ＣＰＵ105はスタック項目を読み出して一番上のスタック項目のすぐ上のスタ ック・スロットにこの項目を書き込む。スタックポインタも上向きに調節される 。スタック・オーバフローが発生するとトラップが行なわれる。スタック・デー タがスタック・データキャッシュに存在する場合、この命令は１クロックサイク ルで実行できる。iload命令の動作はdup命令のそれとほとんど似ており、主な相 違点はオペランドが整数である必要がある点である。よってtag＿bit ＿1を調べれば論理値０を保証することができ、結果のタグビットは論理値０に なる。従ってｗ＿bit＿select信号は２進数00ではなく２進数10になる。 フレームがＲＡＭ202より大きいメソッドでは、少なくとも２つのオプション が存在する。第１に、スタック・タグキャッシュ200はオペランドが参照ではな いことの冗長エラー検査を先行する。第２に、又これ以外に、トラップを行ない 、ＣＰＵ105に命令をエミュレーションさせておく。 好適実施態様において、ＣＰＵ105は２つのスタック・スロットのメモリアド レスを生成する。フレームポインタからのオフセットとして計算されたアドレス はr1＿addrとして提示され、スタックの現在の最上部より上のスロット、即ち新 しく一番上の項目になろうとする項目のアドレスはr2＿addrとして提示される。 スタック・タグキャッシュ200はリミット比較を実行するが、limit＿trap＿1信 号が論理値１の場合トラップは行なわれない。その代わり、limit＿trap＿1が論 理値０でtag＿bit＿1が論理値１の場合、又はlimit＿trap＿2が論理値１の場合 にトラップを行なう。つまり必要なタグビットがスタック・タグキャッシュ200 に存在するかも知れない場合に冗長エラー検査が実行される。それ以外の場合、 トラップを行なうのではなく、冗長エラー検査を実行しない。 スタックにプッシュしようとするデータは同じサイクル又は後続のサイクルの 間に到着する。どちらのサイクルでも実際にはデータは新しくスタック最上部の 項目になるスタック・スロットに書き込まれることになるので、ＣＰＵ105はト ラップを行なわない場合ｗ＿enable信号に論理値１を提示する。ＣＰＵ105はｗ ＿bit＿select信号に２進値10も提示する。結果的に、命令結果についてのスタ ッ ク項目に対応するタグビットは論理値０になるように更新され、結果がプリミテ ィブ値であることを表わす。 istore命令 「istore」命令はスタックから整数をポップして、フレームポインタからのオ フセットとしてアドレスが計算されるスタック・スロットに格納する、即ちこの 項目を用いて整数メソッド・パラメータ又はローカル変数の値を更新する。ＣＰ Ｕ105は一番上のスタック項目を読み込みアドレスしたスタック・スロットに書 き込む。スタックポインタも下向きに調節される。スタック・アンダーフローが 発生した場合にはトラップが行なわれる。 フレームがＲＡＭ202より大きいメソッドでは、トラップを行なう必要がある が、これは候補スタック記憶スロットに記憶されるタグビットを更新して本願発 明の正しい動作を維持する必要があるためである。ＣＰＵ105は更新したスタッ ク・スロットに関連するタグビットの更新を含め、命令の動作をエミュレートす る必要がある。 ＣＰＵ105は２つのスタック・スロットのメモリアドレスを生成する。フレー ムポインタからのオフセットとして計算されるアドレスがr2＿addrとして提示さ れ、スタックの現在の最上部のアドレス、即ちポップされることになる項目がr1 ＿addrとしてて維持される。スタック・タグキャッシュ200はリミット比較を実 行する。ＲＡＭ202と32対１マルチプレクサ214Ａ〜Ｂが一緒に２つのスタック・ ロケーションに対応するタグビットを取り出して、tag＿bit＿1及びtag＿bit＿2 としてＣＰＵ105に提示する。ＣＰＵ105は冗長エラー検査にこれらのタグを使用 できるようになる。tag＿bit＿1、limit＿trap＿1、又はlimit＿trap＿2のどれ かが論理値１の場合トラップを起 こすべきである。tag＿bit＿2信号はＣＰＵ105によるistore命令の処理では使用 されない。ＣＰＵ105はトラップを行なわない場合にｗ＿enable信号に論理値１ を提示する。ＣＰＵ105はｗ＿bit＿select信号に対して２進値10を提示する。結 果的に、命令結果についてのスタック項目に対応するタグビットは論理値０にな るように更新され、このことにより結果がプリミティブ値であることを表わす。 limit＿trap＿1又はlimit＿trap＿2が論理値１であるためにトラップが発生し た場合、ＣＰＵ105はトラップを誘発した命令、並びにトラップハンドラ・ルー チンによって提供された他の情報を調べて適当な動作を起こさなければならない 。命令がtag＿stack＿low＿limit又はtag＿stack＿high＿limitによって示され る境界より外側にあるスタック・スロットのタグビットにアクセスする必要があ る場合、ＣＰＵ105はＲＡＭ202に必要なタグビットをロードし、これに合わせて tag＿stack＿loｗ＿limit及びtag＿stack＿high＿limitの値を調節することがで きる。ＲＡＭ202からデータを読み取りＲＡＭ110に格納することによって最初に スタック・タグキャッシュに空きを作る必要がある。 クイック命令の考察 オブジェクトのフィールドであるオペランドか参照又はプリミティブ値である かについて無差別な「クイック」命令を使用するJava実装では、本願発明は全て の関連する区別を実行する新規命令の追加を企図している。 シンボリック名の解決後に遅い命令をクイック命令で置き換えたJava機構はJa vaインタプリータ又はJITコンピュータとも呼ばれる「ジャストインタイム」コ ンピュータのどちらか又は両方である。 好適実施態様において、２つの考えられるクイック命令の一方を置換命令として 選択するようにJavaインタプリータ及び／又はJIＴコンパイラを変更する。この 選択は何らかの特定のオブジェクト・フィールド・オペランドが参照かどうかに ついての情報を失わないように行なう。以下の半標準ＪＶＭクイック命令は常に プリミティブ値に対して演算するように解釈される： getfield＿quick getfield＿quick＿ｗ getstatic＿quick idc＿quick idc＿ｗ＿quick putfield＿quick putfield＿quick＿ｗ putstatic＿quick 本願発明の追加クイック命令はこれに対応する前述した既存の半標準ＪＶＭク イック命令と正確に同じだが、参照値に対して演算を行なうのは次の通りである ： agetfield＿quick agetfield＿quick＿ｗ agetstatic＿quick aldc＿quick aputfield＿quick aputfield＿quick＿ｗ aputstatic＿quick 遅い命令であるgetfield、getstatic、ldc、ldc＿ｗ、putfield、putstaticを クイック命令により遅い命令を実行するプロセスの間 に置換しようとするときに、シンボリック名解決プロセスでスタックへ又はスタ ックから転送しようとするデータが参照であると分かった場合、名前が「ａ」で 始まっているクイック命令を選択する。それ以外の場合には通常のクイック命令 を選択する。例えば、agetfield＿quick命令はgetfield＿quickと機能的に同一 であるが、この命令は参照値を転送する点で異なっている。上記で言及した他の ７種類のクイック命令についても同様のことがいえる。 好適実施態様において、Javaバイトコード命令セット・オプコードは次のよう に新規命令に割り当てられる： 232 agetfield＿quick 233 agetfield＿quick＿ｗ 234 agetstatic＿quick 235 aldc＿quick 236 aldc＿ｗ＿quick 231 aputfield＿quick 229 aputfield＿quick＿ｗ 230 aputstatic＿quick agetfield＿quick命令 「agetfield＿quick」命令はオブジェクトへの参照をスタックからポップして 、オブジェクト内のオフセットとしてアドレスを計算した参照値のコピーをスタ ックにプッシュする。参照はオブジェクトの参照値フィールドの値を取り出すた めに使用する。agetfield＿quick命令の動作は「aaload」命令と類似しているが 、配列参照と整数インデックスの代わりに、単一のオペランドであるオブジェク ト参照がスタックからポップされる点で異なっている。 本願発明の精神と範囲を維持しつつも本願発明のスタック・タグキャッシュの 読み込み及び書き込み動作の正確なタイミングに多少の変動が発生することがあ ることは当業者には明らかであろう。例えば、ＲＡＭ202へのタグ情報ワードの 書き込みは次のクロックではなくＲＡＭ202から情報を読み出すのと同じクロッ クで行なえる。 更に別の実施態様において、本願発明はコンピュータ・システムで使用するコ ンピュータ・プログラム製品として実装できる。このような実装において、タグ 情報はスタック項目を記憶するために使用されるのと同じシステムＲＡＭの第２ の領域に記憶される。この実施態様において、タグ情報を取り出してシステムＲ ＡＭに直接記憶でき、これによってハードウェア・キャッシュ・メモリ202の機 能とアドレス・リミット・チェック及びキャッシュ「ミス」を処理するためのト ラップ命令の必要性を排除できる。これ以外に、キャッシュメモリ202の機能を 別のシステムＲＡＭ装置、例えば高速スタティックＲＡＭの一部など、他の目的 でも使用される装置で実現できる。この後者の実施態様において、スタック・タ グキャッシュ200又はスタック・タグキャッシュ300内部のハードウェア構成要素 によって実行される機能の全部その全体をこれに対応するプロセッサ命令に置き 換え、類似の機能を実行して同じ結果を実現するようにできる。この実施態様で は、各スタック・エントリについてのタグビット情報かシステムＲＡＭに記憶で きる。プロセッサで実行可能な特定の命令でＲＡＭ内部のタグビット情報を読み 出し、書き込み、変更する。大半のプロセッサ命令セット、アセンブリ言語やＣ プログラミング言語を含めた多数のプログラミング言語がデータワード内の個別 のビットの操作を行ない本願発明のこのような完全ソフトウェア実施態様の実現 に適した装備を提供している。スタック・タグキャ ッシュ200及び300を含む論理構成要素の前述の説明に鑑みて、類似の機能を実装 するために使用される基本的処理ステップはプログラミング技術の当業者の範囲 内にあり図４及び図５に模式的に図示してある。 図４は本願発明のハードウェア実施態様又はソフトウェア実施態様によって実 行されてプログラム・スタック読み込み中にタグ情報を取り出すためのステップ の例示的フローチャートである。この方法はステップ400で始まり、ステップ402 に進み、ここで実装によっては１つ又は２つの読み込みアドレスを生成し記憶す る。単一のスタックを処理している場合には、単一のアドレスを使用し、ハード ウェア実装に関連して前述したように２つのスタックを同時に処理している場合 は第２のアドレスを使用できる。これらのアドレスはスタック項目ロケーション を指定するもので、前述のように、スタック・キャッシュ又はタグ情報が記憶さ れているシステムＲＡＭの他のロケーションをアドレスするためにも使用される 。 ステップ404において、ステップ402で記憶したアドレスで指定されたロケーシ ョンにあるスタック項目が取り出される。次に、ステップ406において、アドレ スをハイトラップ・リミットに対してチェックし、ステップ408において、アド レスをロートラップ・リミットに対してチェックする。アドレスが各々のトラッ プ・リミットによって定義されたアドレス・インターバルの外にある場合には、 すでに議論したように、トラップ処理を開始する。この処理によって、ステップ 412において、要求されたタグ情報がシステムＲＡＭから取り出されることにな る。ステップ414において、少なくともシステムＲＡＭから取り出したタグ情報 を記憶し、可能なら上記の議論に従ってキャッシュメモリ内に追加タグ情報を記 憶することで、キ ャッシュメモリをリストアする機構が開始される。ステップ416において、取り 出されたタグ情報がステップ404で取り出されたスタック項目に追加され、ルー チンはステップ418で終了する。 プログラム・スタック書き込み動作中にタグ情報を記憶するのにも同様な方法 が用いられる。この方法が図５に図示してありステップ500で始まる。ルーチン はステップ502に進み、ここで書き込みアドレスが記憶され、当該アドレスはス タック項目を書き込もうとするプログラム・スタック・ロケーションに対応する 。記憶されたアドレスをステップ504でハイトラップ・リミットと比較し、ステ ップ506でロートラップ・リミットと比較する。アドレスがトラップ・リミット によって定義されたアドレス・インターバル以内に納まる場合、ルーチンはステ ップ508に進み、ここでタグ情報がプログラム・スタック書き込みアドレスから 求めたロケーションでキャッシュメモリ内に記憶される。 これ以外に、ステップ502で記憶したアドレスがステップ504又は506のどちら かで求めたトラップ・リミットの外にある場合、ステップ510でトラップ処理を 開始する。前述のように、このトラップ処理は従来のキャッシュメモリ「ミス」 処理に従って行なわれる。例えば、当業者には周知の方法で、タグ情報はキャッ シュメモリとシステムＲＡＭメモリ・ロケーションの両方に書き込まれるか、又 は情報がキャッシュメモリに書き込まれてから後でシステムＲＡＭロケーション へ「フラッシュ」される。 ステップ508と510のどちらにおいても、要求されたタグ情報がをキャッシュメ モリへ記憶される。ルーチンはステップ512で終了する。 ソフトウェアによる実装は、有形媒体例えばコンピュータで読み 取り可能な媒体例えば図１Ａのディスケット142、ＣＤ−ＲＯＭ147、ＲＯＭ115 、又は固定ディスク装置152上に固定されるか、又はコンピュータ・システムへ 、モデム又はその他のインタフェース装置例えば媒体191上でネットワーク195に 接続された通信アダプタ190などを経由して送信可能な、一連のコンピュータ命 令を含む。媒体191は光又はアナログ通信線を含みこれに限定されない有形の媒 体とするか、又はマイクロ波、赤外線又はその他の伝送技術を含みこれに制限さ れない無線技術で実現できる。一連のコンピュータ命令は本願発明に関連して本 明細書で前述し多機能の全部又は一部を実現する。このようなコンピュータ命令 は多くのコンピュータ・アーキテクチャ又はオペレーティング・システムで使用 するための多数のプログラム言語で書けることが当業者には理解されよう。更に 、こうした命令は半導体、磁気、光又はその他のメモリ装置を含みこれに限定さ れない現在又は将来のあらゆるメモリ技術を使用して記憶するか、又は光、赤外 線、マイクロ波、又はその他の伝送技術を含みこれに限定されない現在又は将来 のあらゆる通信技術を使用して伝送できる。この様なコンピュータ・プログラム 製品は例えばシュリンクラップ・ソフトウェアなど印刷又は電子文書を添付した リムーバブル媒体として配布する、例えばシステムＲＯＭ又は固定ディスク上で コンピュータ・システムへ導入済みソフトウェアとして、又はインターネット又 はワールドワイドウェブなどネットワーク上のサーバ又は電子掲示板から配布す ることができる。 本願発明の典型的な実施態様を開示したが、本願発明の精神と範囲から逸脱す ることなく本願発明の利点の幾つかを実現する様々な変化及び変更を成し得るこ とは当業者には明らかであろう。例えば、スタック・タグキャッシュ200及び300 はハードウェア論理構成要 素を用いての実施を説明したが、本願発明の方法は適当なプロセッサ命令を使用 した完全ソフトウェア実装として、又はハードウェア論理とソフトウェア論理の 組み合わせを使用して同じ結果を達成するハイブリッド実装としてのどちらかで 実現できる。更に、メモリのサイズ、データ又は信号を表現するために使用され るビット数、データワードのサイズ、命令を実行するのに必要なクロックサイク ル数、及び特定の機能を実現するために用いられる論理及び／又は命令の特定の 構成などの側面並びに本願発明の概念に対するその他の変更は添付の請求の範囲 で包含されることを意図している。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 オコナー、ジェイムス・マイケル アメリカ合衆国、カリフォルニア州 94043、マウンテン・ビュー、ルツ・アヴ ェニュー 345 (72)発明者 スティール、ガイ・エル・ジュニア アメリカ合衆国、マサチューセッツ州 02173、レキシントン、ランターン・レー ン ９ (72)発明者 トレンブレイ、マーク アメリカ合衆国、カリフォルニア州 94301、パロ・アルト、ウェイバーリー・ ストリート 801

Claims (1)

1. 【特許請求の範囲】 １．第１のメモリ領域に複数のスタック項目を有するプログラム・データスタッ クを保持することができ、前記複数のスタック項目の各々は参照又はプリミティ ブ値のどちらかとして定義可能なデータを含むコンピュータ・システムにおいて 、選択したプログラム・スタック項目のデータが参照か又はプリミティブ値かを 決定するための方法であって、 Ａ．第２のメモリ領域に複数のタグ項目を保持するステップであって、前記複 数のタグ項目の各々はスタック項目に関連し、各タグ項目は前記関連するスタッ ク項目が参照か又はプリミティブ値かを表わす値を有することを特徴とするステ ップと、 Ｂ．前記選択したスタック項目に関連する前記複数のタグ項目の１つを取り出 すステップと、 Ｃ．前記関連するスタック項目内部に含まれるデータが参照か又はプリミティ ブ値かを前記取り出したタグ項目の値から決定するステップと、 を含むことを特徴とする方法。 ２．前記ステップＡは、 Ａ.1．前記プログラム・スタックの少なくとも一部分をエミュレーションする 順番に前記複数のタグ項目を構成するステップと、 Ａ.2．前記プログラム・スタックの操作に応じてタグ項目を選択的に操作する ステップと、 を含むことを特徴とする請求の範囲１記載の方法。 ３．前記ステップＡ.2.は更に、 Ａ.2.Ａ．選択したスタック項目の順番の操作に応じて、選択したタグ項目の 順番を操作するステップ を含むことを特徴とする請求の範囲２記載の方法。 ４．前記ステップＡ.2.は更に、 Ａ.2.Ａ．対応するスタック項目のデータの操作に応じて、タグ項目の値を操 作するステップ を含むことを特徴とする請求の範囲２記載の方法。 ５．前記ステップＢは、 Ｂ.1．前記選択したスタック項目に対応するタグ項目が前記第２のメモリ領域 内に存在するかどうかを決定するステップ を含むことを特徴とする請求の範囲１記載の方法。 ６．前記ステップＢ.1.は更に、 Ｂ.２．前記タグ項目が前記第２のメモリ領域内に存在していない場合には第 ３のメモリ領域から前記タグ項目を取り出して前記第２のメモリ領域へ前記タグ 項目を書き込むステップ を含むことを特徴とする請求の範囲５記載の方法。 ７．前記ステップＢは更に、 Ｂ.1．前記関連するタグ項目のロケーションに対応するアドレスを前記第２の メモリ領域に提供するステップ を含むことを特徴とする請求の範囲１記載の方法。 ８．前記ステップＣは更に、 Ｃ.1．前記第２のメモリ領域の出力に前記取り出したタグ項目の値を提示す るステップと、 Ｃ.2．前記タグ項目の提示された値とこれに対応するスタック項目のデータ とを比較するステップと、 を含むことを特徴とする請求の範囲１記載の方法。 ９．前記ステップＢは更に、 Ｂ.1．第２の選択したスタック項目に対応する前記複数のタグ項目の第２の 項目を第１のタグ項目と同時に選択するステップと、 Ｂ.2．前記関連する第２のスタック項目内部に含まれるデータが参照か又は プリミティブ値かを前記第２の選択したタグ項目の値から決定するステップと、 を含むことを特徴とする請求の範囲１記載の方法。 １０．複数のスタック・エントリを含むプログラム・データスタックを有するコ ンピュータ・システムて使用するスタック・タグキャッシュであって、各々のス タック・エントリは、タスクの実行中に前記コンピュータ・システムが使用する データを含み、 Ａ．複数のタグ項目を記憶するように構成されたアドレス可能なメモリであ って、各タグ項目は、スタック・エントリに関連しており、かつ、前記関連する スタック・エントリが参照か又はプリミティブ値かを識別する値を有することを 特徴とするアドレス可能なメモリと、 Ｂ．前記アドレス可能なメモリに接続されており、かつ、、選択したスタッ ク・エントリに関連するタグ項目が前記アドレス可能なメモリ内部に存在するか を決定するように構成された比較論理と、 Ｃ．前記アドレス可能なメモリに供給されたアドレスに応答する出力論理で あって、前記アドレスによって選択され前記選択したスタック・エントリに関連 する前記タグ項目の値を提示するように構成された出力論理と、 を含むことを特徴とするスタック・タグキャッシュ。 １１．更に、 Ｄ．選択したスタック・エントリに関連するタグ項目が前記アドレス可能な メモリ内部に存在しないことを前記比較論理が決定した場合には前記アドレス可 能なメモリの外のメモリからタグ項目を取り出すように構成され、かつ、前記取 り出したタグ項目を前記アドレス可能なメモリへ書き込むように構成された書き 込み論理 を含むことを特徴とする請求の範囲１０記載の装置。 １２．前記書き込み論理は更に前記第１と第２の選択したスタック・エントリに 各々関連する第１と第２のタグ項目が前記アドレス可能なメモリ内部に存在する かどうか決定するように構成されていることを特徴とする請求の範囲１０記載の 装置。 １３．前記出力論理は、第１と第２のアドレスに応答するようになっ ており、かつ、第１と第２の選択したスタック・エントリに各々対応する第１と 第２のタグ項目の値を提示するように構成されていることを特徴とする請求の範 囲10記載の装置。 １４．前記アドレス可能なメモリに記憶されている前記複数のタグ項目は前記複 数のプログラム・スタック・エントリより少ないことを特徴とする請求の範囲10 記載の装置。 １５．プロセッサと、 前記プロセッサに接続されたメモリと、 前記プロセッサ及び前記メモリに動作的に接続され、かつ、複数のスタッ ク・エントリを記憶してプログラム命令実行中に前記スタック・エントリを操作 するように構成されたプログラム・スタック論理であって、各々のスタック・エ ントリはプログラム命令の実行に有用なデータを収容しデータ部分とタグ部分と を含み、前記タグ部分には複数の予め規定されたオペランド形式のどれを前記デ ータが表わすかを示す情報を含むことを特徴とするプログラム・スタック論理と を含ムコンピュータ・システムであって、 各プログラム・スタック・エントリのデータ部分はメモリの第１の領域に 格納され、前記データ部分の構成と値は前記プロセッサによる前記プログラム命 令の実行中に前記プロセッサにより操作され、 前記複数のプログラム・スタック・エントリの各々のタグ部分はメモリの 第２領域に格納され、前記タグ部分の構成と値は前記対応するプログラム・スタ ック・エントリのデータ部分と相 関する方法で操作される ことを特徴とするコンピュータ・システム。 １６．前記プロセッサと前記メモリの第２の部分とに動作的に接続され、かつ、 選択した複数のタグ部分を各スタック・エントリのデータ部分とは独立して記憶 して前記タグ部分の構成と値を操作するように構成されたスタック・タグキャッ シュ を更に含むことを特徴とする請求の範囲15記載のコンピュータ・システム 。 １７．前記スタック・タグキャッシュは更に、 プログラム・スタック・エントリのタグ部分が前記スタック・タグキャッ シュ内部に存在するかどうか決定するように構成された比較論理 を含むことを特徴とする請求の範囲15記載のコンピュータ・システム。 １８．前記スタック・タグキャッシュは更に、 前記スタック・タグキャッシュに供給されるアドレスに応答し、かつ、前 記供給されたアドレスにより選択された値をプログラム・スタック・エントリの タグ部分に対して提示するように構成された出力論理 を含むことを特徴とする請求の範囲15記載のコンピュータ・システム。 １９．前記スタック・タグキャッシュ内部のタグ部分の個数はスタ ック・エントリの個数より少ないことを特徴とする請求の範囲15記載のコンピュ ータ・システム。 ２０．プロセッサと、第１のメモリ領域に複数のスタック・エントリを記憶して プログラム命令実行中に前記スタック・エントリを操作するように構成されたメ モリとプログラム・スタック論理とを有するコンピュータ・システムで使用する ためのコンピュータ・プログラム製品であって、各スタック・エントリは参照値 又はプリミティブ値のいずれかとして定義可能なデータを収容することができる 特徴を有し、コンピュータで使用可能な媒体を含む前記コンピュータ・プログラ ム製品は、参照又はプリミティブ値のいずれかとしてスタック・エントリの区別 を行なえるようにするために前記媒体に実現されたプログラム・コードを有し、 前記プログラム・コードは、 第２のメモリ領域に、複数のタグ項目を保持するためのプログラム・コー ドであって、各タグ項目がスタック・エントリに関連していることを特徴とする プログラム・コードと、 選択したスタック項目に対応する前記複数のタグ項目の１つを取り出すた めのプログラム・コードと、 前記取り出すためのプログラム・コードに応答するプログラム・コードで あって、前記選択したスタック・エントリに関連するタグ項目の値を提示するた めのプログラム・コードと、 を含むことを特徴とするコンピュータ・プログラム製品。 ２１．前記選択するためのプログラム・コードは更に、 前記選択したスタック・エントリに対応するタグ項目が前記 第２のメモリ領域内に存在するかどうかを決定するためのプログラム・コード を含むことを特徴とする請求の範囲20記載のコンピュータ・プログラム製 品。 ２２．前記選択するためのプログラム・コードは更に、 前記第２のメモリ領域内に存在しないタグ項目を取り出すためと前記第２ のメモリ領域に前記タグ項目を書き込むためのプログラム・コード を含むことを特徴とする請求の範囲20記載のコンピュータ・プログラム製 品。 ２３．選択した第２のスタック・エントリに対応する前記複数のタグ項目の第２ の項目を同時に選択するためのプログラム・コード を更に含むことを特徴とする請求の範囲20記載のコンピュータ・プログラ ム製品。 ２４．各タグ項目は前記対応するスタック・エントリ内部に含まれるデータが参 照か又はプリミティブ値かを表わす値を有することを特徴とする請求の範囲20記 載のコンピュータ・プログラム製品。 ２５．メモリを有するコンピュータ・システム上でガーベッジ・コレクションを 実行するための装置であって、 前記メモリ内に複数のスタック・エントリを記憶してプログラム命令実行 中に前記スタック・エントリを操作するように構 成されたプログラム・スタック論理であって、各スタック・エントリはプログラ ム命令の実行に有用なデータを収容しデータ部分とタグ部分とを含み、前記タグ 部分には複数の予め規定されたオペランド形式のどれを前記データが表わすかを 示す情報を含むことを特徴とするプログラム・スタック論理と、 第１のメモリ領域に記憶された各プログラム・スタック・エントリのデー タ部分を記憶するように構成された第１の記憶要素であって、前記データ部分の 構成と値がプログラム命令実行中に操作されることを特徴とする第１の記憶要素 と、 前記第１のメモリ領域とは異なる第２のメモリ領域に前記複数のプログラ ム・スタック・エントリの各々のタグ部分を記憶するように構成された第２の記 憶要素であって、前記タグ部分の構成と値がこれに対応するプログラム・スタッ ク・エントリの前記データ部分と相関する方法で操作されることを特徴とする第 ２の記憶要素と、 未使用メモリ・ロケーションのアドレスを決定するために、前記第２のメ モリ領域を調べて前記未使用メモリ・ロケーションを再請求するように動作可能 なガーベッジ・コレクション機構と、 を含むことを特徴とする装置。 ２６．前記第２のメモリ領域は前記メモリとは別のキャッシュメモリであること を特徴とする請求の範囲25記載の装置。 ２７．前記複数のプログラム・スタック・エントリの各々の前記タグ部分は前記 プログラム・スタック・エントリが参照か又はプリミティブ値かを表わすことを 特徴とする請求の範囲25記載の 装置。 ２８．前記ガーベッジ・コレクション機構は前記プログラム・スタック・エント リが参照であることを関連タグ部分が表わしている第１のメモリ領域に記憶され た各プログラム・スタック・エントリのデータ部分を用いることによって、前記 未使用のメモリ・ロケーションのアドレスを決定することを特徴とする請求の範 囲26記載の装置。